Godel - Completeness of axiomatic systems

[Adam Mclean]

Actually, I've been somewhat misleading: the theory of the real numbers is complete, not because of Tarski's theorem, but because of Godel's completeness theorem: first-order logic is complete.

Tarski's theorem is that the theory of real numbers is decidable.

Does not the decidability of a formal axiomatic system imply the completeness of the axioms ?

 

[master_coda]

Can I ask how one can construct a model for the real numbers from the integers ?

A standard way of constructing a model of the reals using the integers is to first construct a model of the rationals using the integers, and then to construct a model of the reals using the rationals.


Of course, many people intepret this the wrong way. There seems to be this idea that if you can construct a theory of the reals from a theory of integers, then the theory of the reals must be the theory of integers with something added - therefore the theory of integers is contained in the theory of reals.

Except that interpretation is completely backwards. Constructing the reals using the integers proves that the theory of the reals is contained in the theory of the integers. Not the other way around.

It seems to me that it is this idea of a number having a unique successor that is at the root of the incompleteness of a formal system

What about the Presburger arithmetic? Presburger arithmetic is a theory of the natural numbers without multiplication - and it's complete and consistent. Despite the fact that it contains the concept of having a successor.

 

[Adam Mclean]

A standard way of constructing a model of the reals using the integers is to first construct a model of the rationals using the integers, and then to construct a model of the reals using the rationals.

Constructing the reals using the integers proves that the theory of the reals is contained in the theory of the integers. Not the other way around.
QUOTE]

I cannot quite understand this. The positive rationals can be modeled in the integers using Cantor's diagonalization which can establish a one-to-one correspondence. Thus each rational can be mapped uniquely onto an integer through the ordered pair (n,m) ~ n/m. The special property of rationals, that division can be defined for each rational number, could be described as a property of two ordered pairs (n,m) and (p,q) that is

n/m divided by p/q = (n*p)/(m*q) or the ordered pair of integers (n*p,m*q)

Thus division which is well defined for rationals can be modeled in integers even though it is not well defined for integers themselves.

Such a process is surely not possible for the special properties of the reals which go well beyond division. Can one model the limits of cauchy sequences (the main way to describe real numbers) in the integers ?

One can only model the reals using the rationals by abandoning first order logic, as the concept of limit as far as I understand cannot be understood without second-order logic.

Am I correct in this?

 

[master_coda]

Such a process is surely not possible for the special properties of the reals which go well beyond division. Can one model the limits of cauchy sequences (the main way to describe real numbers) in the integers ?

One can only model the reals using the rationals by abandoning first order logic, as the concept of limit as far as I understand cannot be understood without second-order logic.

Am I correct in this?

Well, obviously if you want to take advantage of the properties of the real numbers that can only be expressed using second-order logic then you have to start using second-order logic.

I should have been more accurate and stated that the first-order theory of the reals is contained in the first-order theory of the integers. If you want to reason using second order statements then you have to move beyond first order logic, but that's true for any first-order theory, not just theories of the reals.

 

[Adam Mclean]

What about the Presburger arithmetic? Presburger arithmetic is a theory of the natural numbers without multiplication - and it's complete and consistent. Despite the fact that it contains the concept of having a successor.

You are right. By this counter-example, the defining of unique successor does not lead to incompleteness. Although not a sufficient condition it could still be a necessary condition for incompleteness.

We can also see that Presburger arithmetic as it does not define multiplication has no fundamental theorem of arithmetic which is another of the key elements needed for Godel's proof.

 

[Hurkyl]

When referring to a theory, completeness and decidablility are the same thing. When referring to a logic, completeness means something different. The completeness of a theory does not follow from the fact that it is expressed using a logic that is complete, because those are two different concepts of completeness.

Aha! Now I understand why this always confuses me!

 

[Adam Mclean]

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

Have I got that right ?

 

[master_coda]

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

Have I got that right ?

The fact that arithmetic is undecidable is a consequence of the fact that it is incomplete - when referring to a formal system, completeness and decidablity are equivalent.

Church's theorem is that there is no general procedure that can decide first-order logic. Note that when referring to a logic and not a formal system, completeness and decidability are not the same thing. Also note that just because first-order logic is undecidable in general, it does not mean that we cannot come up with a way for deciding individual formal systems expressed using first-order logic.


Church's thesis is that anything that can be computed can be computed using the lambda calculus. Or Turing's version, that anything that can be computed can be computed using a Turing machine. This is not proven, and probably never will be (although it could be proven wrong).

 

[Adam Mclean]

Note that when referring to a logic and not a formal system, completeness and decidability are not the same thing.

Could I please intrude further on your generosity by asking you to explain this a little further, or perhaps point to a book or web page that might help me understand this point.

 

[master_coda]

When referring to a formal system such as arithmetic, you basically have three things:

1) the rules and symbols of the logic you are using
2) additional symbols used by your system (arithmetic uses 0,1,+,* and =)
3) a set of axioms (statements within the system that are asserted to be true)

We then say that the system is complete if for every statement within the system, either the statement can be infered from the axioms or its negation can be. In other words, the system is complete if every statement can be proven to be either true or false. This concept is also commonly referred to as decidability.

This is the meaning of completeness that is talked about by Godel's incompleteness theorem. It refers to the fact that any system that is powerful enough to formulate arithmetic is not complete -> there will be statements within that system that cannot be proven or disproven from the axioms of the system.


When referring to a logic, you generally just have:

1) symbols used by the logic
2) a set of rules for making inferences about statements made using the logic

We say that the logic is complete if for every formal system expressed using that logic, when there is a statement that is true in every model of that system, then that statement can be proven true from the axioms of the system.

For example, consider the theory of a field, expressed using first-order logic. We know of several common models that satisfy the axioms of a field - the rationals Q, the reals R and the complex numbers C. The fact that first-order logic is complete tells us that if something is true in every model of a field (every model, not just those three) then it must be provable from the axioms of a field.

Consider $\forall x,x+x=x\Rightarrow x=0$. This statement is true in every model of a field, so we should be able to prove it using the axioms of a field (and we can).

But consider $\exists x,x\cdot x=-1$. This statement is true for C, but false for Q and R. Which is why this statement is undecidable in the theory of fields. So the theory of fields is not complete.

This means that despite the fact that first-order logic is complete, we still can express statements in first order logic that are not decidable. So for a logic, completeness and decidability mean two different things.


Of course, this overloading of the word completeness is very confusing. When you first hear Godel's completeness and incompleteness theorems you generally assume that they are talking about the same concept of completeness, but they aren't. The completeness theorem is referring to the completeness of a logic - it proves that first-order logic is complete. The incompleteness theorem is referring to the completeness of a formal system - it proves that arithmetic is not complete.

 

[Ethereal]

Church's thesis is that anything that can be computed can be computed using the lambda calculus. Or Turing's version, that anything that can be computed can be computed using a Turing machine. This is not proven, and probably never will be (although it could be proven wrong).

Can you give an explanation of what it means for something to be "computable"? Also, it has been proven that whatever can be computed with the lambda calculus can be computed on Turing machines, is it not?

 

[master_coda]

Can you give an explanation of what it means for something to be "computable"? Also, it has been proven that whatever can be computed with the lambda calculus can be computed on Turing machines, is it not?

Well, in a more general sense a problem is computable if we have a mechanical process that can always correctly solve the problem. In other words, a problem is computable if an algorithm exists to solve it.

A mechanical process is generally assumed to be:
1) finite (it has a finite number of instructions and symbols, and always produces a result in a finite number of steps)
2) can be carried out by a human being with only the intelligence required to understand and execute the instructions

The Church-Turing thesis is just that such algorithm that exists can be implemented on a Turing machine (or using the lambda calculus, since they are equivalent).

 

[DrMatrix]

Without being able to articulate in the formal language of an axiomatic system the idea of a unique successor (such as with the real numbers) then surely Godel's Incompleteness theorem cannot be proven nor even adequately expressed.

Godel showed how to translate statements about a formal system into statements about integers. The formal system can be the integers or the reals. The translation does not depend upon the idea of a successor in the system being modeled. Godel's Incompleteness Theorem applies to any formal system large enough to contain arithmetic.

A standard way of constructing a model of the reals using the integers is to first construct a model of the rationals using the integers, and then to construct a model of the reals using the rationals.


Of course, many people intepret this the wrong way. There seems to be this idea that if you can construct a theory of the reals from a theory of integers, then the theory of the reals must be the theory of integers with something added - therefore the theory of integers is contained in the theory of reals.

Except that interpretation is completely backwards. Constructing the reals using the integers proves that the theory of the reals is contained in the theory of the integers. Not the other way around.

I'm not sure what you mean by "contained in". The issue is consistency. Godel showed that we cannot prove an axiomatic system is consistent. (Actually, what he showed is that if we can prove a system is consistent, then it is not consistent. So we hope we cannot prove the integers, for example, are consistent.) By showing we can construct a model for the reals from the integers, we show "If the integers are consistent, then the reals are consistent." The fact that the reals contain a subset that has the properties of the integers shows that "If the reals are consistent, then the integers are consistent." This tells us that the integers are consistent iff the reals are consistent.

 

[master_coda]

The fact that the reals contain a subset that has the properties of the integers shows that "If the reals are consistent, then the integers are consistent." This tells us that the integers are consistent iff the reals are consistent.

This is not true. Given only the axioms of the reals, we cannot find a subset of the reals that satisfies the axioms of the integers. Which is why the fact that the theory of the reals is consistent does not contradict the fact that the theory of the integers cannot be proven to be consistent.

 

[DrMatrix]

Are you sure about that? We have zero and one, the additive and multiplicative identities. Using 1 and addition, we can define a successor function, f(x) = x+1. We can define N as the smallest set that contains 0 and for every n in N, we also find n+1 in N.

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

 

[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.