Godel - Completeness of axiomatic systems

[Hurkyl]

We can define N as the smallest set that contains 0 and for every n in N, we also find n+1 in N.

And there lies the rub. How do you propose to do that using only first-order logic, 0, 1, +, *, and <?

 

[chronon]

The set of integers sitting inside the reals is not definable using 1st order constructs. However, the reals (including 2nd order axiom) are unique up to isomorphism, so the integers sitting inside are the unique objects which we think of as the 'true' integers. With 1st order integer axioms for the integers, Godel tells us that we can always find a different model.
I would guess that Fermat's last theorem is in fact undecidable using 1st order integer axioms (i.e. there is a counterexample in some non-standard model of the integers), but we accept the proof (which uses real numbers) because it applies to the 'true' integers.

 

[Adam Mclean]

I'm pretty sure that we cannot prove that the reals are consistent.

This was my question that opened this thread. As far as I understand the axiomatic system of the Real numbers are consistent. I am trying to understand how Godel's Incompleteness theorem does not work for the reals.

I am accepting that the Reals have been proved consistent.

 

[Adam Mclean]

The set of integers sitting inside the reals is not definable using 1st order constructs.

Yes. These only appear to our minds as the set of integers. Perhaps the minds of mathematicians on the third planet of Sirius, would not see there to be the connection we find hard to resist, and might use entirely different symbols for these different numbers.


They are not a 'special' type of number recognisable within the axiomatisation of Real numbers. Special properties of the system of the integers - such as the fundamental theorem of arithmetic or that every number has a unique successor - are not defineable over the Reals.

The Real numbers 1, 2, 3...

may appear to be integers but they are not - they are entirely different objects. They appear that way to our minds, but mathematically they are different mathematical objects with different mathematical properties.

I love the insight :

I would guess that Fermat's last theorem is in fact undecidable using 1st order integer axioms (i.e. there is a counterexample in some non-standard model of the integers), but we accept the proof (which uses real numbers) because it applies to the 'true' integers.

I have only read the account of the proof in Simon Singh's book. This has a short section on Godel and undecidability, but he does not delve far into this, indeed he rather unfortunately parallels undecidability (in Godel's sense) with Heisenberg Uncertainty in quantum mechanics. It is because of ideas like this that I am trying to sort out in my mind the nature and scope of Godel's Incompleteness theorem. If it cannot be applied to the Reals, then the statement

undecidability ~ quantum uncertainty

or a variant on this is exposed as merely a kind of philosophical nonsense resulting from a failure to understand the nature of Godel's Incompleteness.

 

[Adam Mclean]

Regarding how one axiomatic theory can inherit undecidability from another, I have just read the following
in Fraenkel and Bar-Hillel 'Foundations of Set Theory' :

"The scope of undecidability proofs was greatly increased when it was proved ... that an essentially undecidable and finitely axiomatizable Theory T induces essential undecidability in every theory T'... which is weakly interpretable in T ..."

The term weakly interpretable is elsewhere defined

" One says that T is weakly interpretable in T' if T is interpretable in some consistent extension of T' with the same vocabulary as T' "

and T being interpretable in T' means - T has a model in T'


Does this throw any light on the question about the reals
inheriting undecidability ?

Can one assume that the Reals (here T' in the Fraenkel/Barr-Hillel statement) is not weakly interpretable in T (the natural numbers) ?

 

[master_coda]

"The scope of undecidability proofs was greatly increased when it was proved ... that an essentially undecidable and finitely axiomatizable Theory T induces essential undecidability in every theory T'... which is weakly interpretable in T ..."

Note that the natural numbers are not finitely axiomatizable. The axiom for induction is an axiom schema with infinitely many axioms. This cannot be reduced to a finite number of axioms using first-order logic.

Also, I'm not quite certain what "essentially undecidable" means. Does it just mean "undecidable" or is it a stronger condition?

 

[Hurkyl]

may appear to be integers but they are not - they are entirely different objects. They appear that way to our minds, but mathematically they are different mathematical objects with different mathematical properties.

That's not entirely true...

Every model of the real numbers contains a model of the integers (which contains a model of the natural numbers).

It just so happens that you cannot prove this statement in the first-order theory of the reals. (Actually, you cannot even say this statement)


When we say "THE" integers or "THE" reals, it's somewhat ambiguous as to our real meaning. It could mean that we've preselected a particular model of the integers and the reals which we will use, or it could mean that we're just referring to the fact that all models of the (second-order) theory of the integers are isomorphic, and also for the reals.

 

[master_coda]

That's not entirely true...

Every model of the real numbers contains a model of the integers (which contains a model of the natural numbers).

It just so happens that you cannot prove this statement in the first-order theory of the reals. (Actually, you cannot even say this statement)

I don't think his way of looking at it was that bad, though. Within the universe of the first-order theory of the reals, the objects that we normally think of as the integers really aren't the integers. They don't have the properties that we normally associate with the integers.

When trying to understand the limits of the scope of a theory, it's sometimes helpful to avoid drawing on conclusions that can be reached by going beyond the theory.

 

[Hurkyl]

I don't think it was bad either, I just didn't want him to go too far down that road and think that, with full rigor, it was not allowed for the integers to be a subset of the reals.

Within the universe of the first-order theory of the reals, the objects that we normally think of as the integers really aren't the integers. They don't have the properties that we normally associate with the integers.

I'm not entirely sure what you mean by this... if you're merely saying that many of the properties are unavailable to us, then I agree, because they can't be expressed in the language available to us.

 

[master_coda]

I'm not entirely sure what you mean by this... if you're merely saying that many of the properties are unavailable to us, then I agree, because they can't be expressed in the language available to us.

Yes, that's what I mean. I was trying to express the idea that the integers are a set of numbers with certain properties, not just a set of numbers. So until those properties can be expressed, the set of numbers isn't the set of integers.

 

[chronon]

I was trying to express the idea that the integers are a set of numbers with certain properties, not just a set of numbers.

I would see things the other way round and say that the integers were the things sitting inside the reals, while the other models of the integer axioms are called something else (such as 'supernatural numbers'). I suppose it's a matter of taste really.

 

[Adam Mclean]

I would see things the other way round and say that the integers were the things sitting inside the reals, while the other models of the integer axioms are called something else (such as 'supernatural numbers'). I suppose it's a matter of taste really.

Surely one can produce many models of the integers within the reals.

The Real numbers 1.000, 2.000, 3.000,...

are only one of many possible models of the integers within the reals.

0.1, 0.2, 0.3,... would be another (though one needs to define successor and division differently).

The Reals are not an extension of the Integers which preserves the properties of the Integers into the Reals. One has to abandon certain axioms of the system of Integers in order to construct the Reals. The obvious example is that of succession. There is no unique successor to any real number. One can attempt to define successor for a subset of the Reals through a process such as adding 1 to any number, but this is merely modelling Integers in the Reals, it says nothing about the Real number system.

It seems that the Reals can only inherit Godel incompleteness from the Integers if the Reals can be modeled in the integers. This cannot be done of course.
Modelling the Integers in the Reals, which can be done of course, does not import Godel incompleteness.

So I don't think we can, in a formal sense, see things the other way round.

 

[Adam Mclean]

I'm not quite certain what "essentially undecidable" means. Does it just mean "undecidable" or is it a stronger condition?

Fraenkel and Bar-Hillel use this term within their description of the Church-Rosser undecidability Theorem which says

Elementary arithmetic is essentially undecidable.

They expand on this "Rosser was able to prove... that every consistent extension of first order arithmetic is undecidable".
So "essentially undecidable" is a stronger condition.

 

[Adam Mclean]

I wonder if I have perhaps been seeing the problem of the Incompleteness of formal mathematical systems the wrong way round.

It seems that Godel Incompleteness can only be expressed and defined in axiomatic systems built on first-order logic.

For axiomatic systems built on second-order logic, Godel Incompleteness cannot be expressed.

Second-order logic requires that the system can express quantification across subsets of the mathematical system, and one can only define the Reals using the concept of least upper bound of a subset, which is a step into a second-order logic.

Is it not better for us to see Godel Incompleteness as arising in a more restricted logic environment, and that it is a result of a poverty of the first-order logic and the axioms for the natural numbers, that such strange recursive propositions can be developed, which lead to Godel Incompleteness ?

What I am perhaps trying to say is that the formal system of Real numbers is a sufficiently rich system so that Godel Incompleteness does not arise, whereas the natural numbers (although appealing to the human mind) is not a sufficiently rich system that its axioms cannot lead to these contradictions and recursive propositions.

So it is not that Godel Incompletness flows through all formal axiomatic systems, but rather that it arises in some which do not have a sufficiently "rich" axiomatic system.

Is this a valid way of looking at the Incompleteness problem ?

 

[chronon]

Surely one can produce many models of the integers within the reals.

The Real numbers 1.000, 2.000, 3.000,...

are only one of many possible models of the integers within the reals.

0.1, 0.2, 0.3,... would be another (though one needs to define successor and division differently).

No, there is only one model of the integers within the reals. For instance you have to have 2+2=2x2 (Presumably for Presburger arithmetic you could take the multiples of any real number). For each integer n within the reals there is the successor n+1.0. What you can't do it define the notion of integer within the reals using 1st order constructs - saying that an integer is any number that can be reached by adding 1.0 to 0.0 a finite number of times is not a 1st order definition.

 

[chronon]

First-order logic is complete - Gödel's completeness theorem
Formal system of arithmetic is incomplete - Gödel's Incompleteness theorem.
Arithmetic is undecidable - Church's Theorem or Thesis (not yet proven)
Theory of real numbers is decidable - Tarski's theorem

Church's theorem is that there is no general procedure that can decide first-order logic.

So Gödel's completeness theorem implies that any statement which is true in all models of the integers has a proof, but Church's theorem says that there is no general procedure for finding this proof.
What about statements which are true in the usual model of the integers but not necessarily in all. (I guess that Fermat's last theorem is in this category). Is there anything that rules out the possibility of a general procedure for finding the proof of such statements? (Which would involve going beyond the 1st order axioms, and would probably need real numbers as Fermat's last theorem did)

 

[Adam Mclean]

There is very clear article by David Pierce on Model theory at

http://www.math.metu.edu.tr/~dpierce/philosophy/Kant/model-theory-gen.pdf

 

[master_coda]

What about statements which are true in the usual model of the integers but not necessarily in all. (I guess that Fermat's last theorem is in this category). Is there anything that rules out the possibility of a general procedure for finding the proof of such statements? (Which would involve going beyond the 1st order axioms, and would probably need real numbers as Fermat's last theorem did)

I'm not quite sure what you're asking here. Are you asking if there could be a general procedure for deciding the standard model of the integers? I'm pretty sure that the fact that arithmetic is incomplete allows you to conclude that is not possible, no matter what order of logic you are using.

 

[Hurkyl]

No, there is only one model of the integers within the reals. For instance you have to have 2+2=2x2

You're thinking of embeddings. A model of the integers is under no obligation to use the exact same arithmetic operators as the reals.

 

[Hurkyl]

Here's an example of why Tarski's theorem is useful.


Suppose I have a system of polynomials in many variables with integer coefficients. Suppose I also know that there is a solution to this system in the reals.

Now, I want to know if this system has a solution in the real algebraic numbers.

The answer is yes, and it's trivial using Tarski's theorem. I haven't yet figured out a way to attack the problem without using decidability.

 

[Adam Mclean]

Apparently in his book 'A decision method for elementary
algebra and geometry', 1948, Tarski showed that the first-order
theory of the real numbers under addition and multiplication is decidable.

This seems at first glimpse in contradiction to Godel's
Incompleteness Theorem, but of course, as we have
analysed in this thread, there is a considerable difference
formally between the Natural numbers and the Reals.

Note this result of Tarski is within a first-order logic
and does not require us to step into a sccond order logic.

I don't have access at the moment to this work of Tarski.
Can anyone confirm this reference is correct?

Adam McLean