Hacker News Reader

Comment by martincmartin | Hacker News Reader

It says "any system which includes the Peano axioms is either inconsistent or incomplete." So having a wider class doesn't help, if it contains the Peano axioms.

View on HN

Proof was made within specific framework, with very specific quantors and type of inference, I still don't understand how it prevents existence of more powerful frameworks with different quantors and inference where incompleteness theorems wouldn't work.

You can construct a new Incompleteness Theorem for any more powerful formal system. To really get syntactic completeness, you would need an infinite tower of Goedel Statements as axioms, where the truth of each one is a completely independent mathematical fact not reducible to any other axiom ever.

Effectively, syntactic completeness in logic is equivalent to the Halting Problem in computing, via bijective proofs.

Let me give you example. At first you have predicate calculus, and Godel completeness Theorem.

Now you add new tool: existence predicate, and you got first order logic, which allows you to prove Godel's incompleteness Theorem.

What is the guarantee exactly that more advanced systems can't exist? Say system with new 'quantum hack' operator. You can't prove formula from Godel's proof? 'Quantum hack' under some conditions covers missing gap in proof path by building continuum truth table and give you tool to check if formula from Godel's proof actually provable, or it is false.

Goedel's Completeness Theorem is for semantic completeness, and still applies to first-order logic. It says, "every theorem which is semantically true for its theory (true in all models of that theory) is syntactically provable." Goedel's Incompleteness Theorem applies to syntactic completeness. Syntactic completeness would mean, "Every syntactically-valid formula is either provable or refutable." Instead, what Goedel's Incompleteness Theorem tells us is: "Some syntactically-valid formulas are neither provable nor refutable, because they're true in some models (standard models) but not in others (nonstandard models)."

Again, this applies to any given formal system. Goedel's Incompleteness Theorem is parametric over formal systems, with first-order Peano Arithmetic being one of the weakest, most standardized systems in which it applies. The real condition for the Theorem is, "Any formal system sufficient to describe Turing machines."

>Say system with new 'quantum hack' operator.

That operator is called a Turing Oracle, and it's physically impossible. Possessing a Turing Oracle is equivalent to reversing the Second Law of Thermodynamics and refuting Heisenberg's Uncertainty Principle. It's physically wrong.

> Goedel's Incompleteness Theorem is parametric over formal systems, with first-order Peano Arithmetic being one of the weakest, most standardized systems in which it applies.

It is parametric over formal systems described in Principia Mathematics. That's it. It doesn't take into account other possible types of formal systems. At least I didn't notice this when reading actual proof.

> That operator is called a Turing Oracle

I think it may be very different thing. I just gave you a quick example. That operator can be something very different. You can set measure on space of proofs, and derive concept of asymptotic proof, and say if proof is asymptotic, then it is proof. There can be many variations around possible formal systems.

> and it's physically impossible

This is very strange argument. Turing machine contains infinite amount of memory, and likely is physically impossible.

Reply on news.ycombinator.com