Godel - Completeness of axiomatic systems

[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