Godel - Completeness of axiomatic systems

[DrMatrix]

The real number 1 and the unsigned integer 1 are constructed differently.

The reals and the integers are not constructed. The real numbers is a set which has certain properties. The set of integers is a set with certain other properties. You can construct a model for the integers using set theory. You can construct a model for the real numbers from the integers. The constructed model for the reals contains a model for the integers.

 

[DrMatrix]

The real numbers form a complete ordered field. This use of complete is not the complete used by Godel. The axioms of the real numbers are not complete in the sense Godel uses the word complete.

 

[Hurkyl]

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.


edit: nevermind

 

[master_coda]

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.

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.

 

[Adam Mclean]

You can construct a model for the integers using set theory. You can construct a model for the real numbers from the integers. The constructed model for the reals contains a model for the integers.

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

For real numbers there is no concept of the successor of a number, whereas this is the key concept for the integers. Indeed the idea of successor is one of the Peano axioms for the integers.

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. Godel's proof of his theorem rests on the idea of the successor of a number, as this allows one to assign a unique Godel number to a formal proposition in the system, and be able to read back from a unique Godel number to the string of symbols of the proposition.

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.

 

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