Explaining Godel's Theorem: Intuitive Explanation w/o Math

[Big Red Dog]

It's a rather easy to prove that you cannot make an incomplete theory complete by removing axioms. If you have a subset of the axioms, then you only have a subset of the theorems.

"Complete" does not mean that you can demonstrate "everything" just that every sentence S either S or NOT S is a theorem.

The completeness of Presburger arithmetic comes from its restricted language. All of the undecidable propositions of number theory involve multiplication. Presburger does not explicitly have a multiplication operator and is incapable of constructing one. It achieves completeness not by removing axioms, but by reducing the number of statements in its language.

Let's see:

The 5 axioms of Presburger:

1. p7: No number has 0 as a successor
2. p8: Successor is injective: Sx=Sy --> x= y
3. x + 0 = X ;;
4. x + Sy = S(x + Y) ;; addition
5. p9: Induction

Apprentely Presburger is a subset of Peano ... Note: p7,p8, p9 refers to the Numbering of Peano axioms in http://en.wikipedia.org/wiki/Peano_arithmetic#The_axioms

Not quite correct; you can add enough axioms to build a complete theory (i.e. all statements are provable). The problem is that you cannot do it in a recursively enumerable way.

You're absolutely right. But since I cannot do it r.e. what would be the point? :)

 

[Hurkyl]

"Complete" does not mean that you can demonstrate "everything" just that every sentence S either S or NOT S is a theorem.

If a given theory contains neither S nor (not S), then the same is true of all of its subtheories.

In terms of generators... if neither S nor (not S) are provable from a given set of axioms, then the same is true for any subset of that set.

Let's see:

The 5 axioms of Presburger:

1. p7: No number has 0 as a successor
2. p8: Successor is injective: Sx=Sy --> x= y
3. x + 0 = X ;;
4. x + Sy = S(x + Y) ;; addition
5. p9: Induction

Apprentely Presburger is a subset of Peano ... Note: p7,p8, p9 refers to the Numbering of Peano axioms in http://en.wikipedia.org/wiki/Peano_arithmetic#The_axioms

You linked to a formalization of second-order Peano arithmetic. Not only does that yield an expanded language (you have propositional variables), but it introduces additional rules of deduction, so it's not even the same logic.

There is an explicit first-order formalization of Peano arithmetic later in that link (here).


IMHO, the situation can be most cleanly stated in terms of computability: for any model N of the natural numbers, the relevant theorems are that Th(N, +) -- the set of statements about + that are true in N -- is turing decidable. However, Th(N, +, *) is not turing decidable.

You're absolutely right. But since I cannot do it r.e. what would be the point? :)

If we're going to make true statements, we cannot neglect the cases we don't like.

Furthermore, recursive enumerability is not always relevant, and things can be more easily presented without imposing that restriction. For example, the simplest way I've ever seen to set up nonstandard analysis is to formulate the first-order theory starts as follows:

Let V be the superstructure built upon R. (V = \bigcup_{i \in \mathbf{N}} \mathcal{P}^i (\mathbf{R}))

Define a language L whose constant symbols include every element of V, and with the single binary relation symbol \in. (There is an obvious way to define an interpretation of L in V)

Define a first-order theory for L whose statements are precisely those that hold in V.

 

[Big Red Dog]

If a given theory contains neither S nor (not S), then the same is true of all of its subtheories.

In terms of generators... if neither S nor (not S) are provable from a given set of axioms, then the same is true for any subset of that set.

Ok, I made a fool of myself, I didn't realize that in Press. Arithm. all the pieces were actually moving (downsized): less theorems, restricted language, different model.

IMHO, the situation can be most cleanly stated in terms of computability: for any model N of the natural numbers, the relevant theorems are that Th(N, +) -- the set of statements about + that are true in N -- is turing decidable. However, Th(N, +, *) is not turing decidable.

Yep, much better/more clear since it refers to the model.

If we're going to make true statements, we cannot neglect the cases we don't like.

Well, it's more important for people to remember that just adding a theorem found undecidable is not going to solve the issue rather than to know about a technicality? (I know, I know ... :) )

Furthermore, recursive enumerability is not always relevant, and things can be more easily presented without imposing that restriction. For example, the simplest way I've ever seen to set up nonstandard analysis is to formulate the first-order theory starts as follows:

Let V be the superstructure built upon R. (V = \bigcup_{i \in \mathbf{N}} \mathcal{P}^i (\mathbf{R}))

Define a language L whose constant symbols include every element of V, and with the single binary relation symbol \in. (There is an obvious way to define an interpretation of L in V)

Define a first-order theory for L whose statements are precisely those that hold in V.

Showing off on both accounts of HTML and mathemathical wizardry, huh? :)

Actually now that you're mentioning it, non-standard analysis is a great way to demonstrate that Gödel's incompleteness theorems might have had a much lesser impact on the world than one could have thought: physicians were heavily using infinitesimal calculus before Robinson, so who cares if something is not properly defined/axiomatized/demonstrable? ;)

 

[gel]

Can someone explain to me why it is not possible to construct a relatively general logical system that does NOT contain self-referring sentences? I would appreciate an intuitive, rather than a rigorous explanation, as I am not a mathematician (but a theorethycal physicist).

The following is the argument that I thought of when first thinking about Godel's incompleteness theorem, and it was enough to convince me that it can't be avoided in any way. It's similar to the proof of the Halting problem.
Suppose I have a computer program that takes a computer program as an input (say, as a plain text file) and returns one of the following
i) "Input program terminates."
ii) "Input program never terminates."
iii) Or, the main program itself never terminates.

Also suppose that the output is always correct. i.e. If (i) is output and you run the program in the text file then it will indeed terminate, and if (ii) is output then the program in the text file will never terminate.

Then, by the standard method of proof of the Halting problem, it is possible to construct a program which never terminates, but when fed as an input into the main program above will lead to situation (iii).

Suppose that we have a system of logic in which it is possible to state whether or not a program terminates, and which is consistent so that it never says that a terminating program doesn't terminate or vice-versa. You could then write a program that takes in the given text file and simply checks all possible proofs that the input program terminates or not. By the argument above you could feed in a program that causes (iii), so that you know it never terminates but which cannot be proven under the logic system.

So, my conclusion is that any system of logic which is rich enough to be able to make the statement "program P terminates/does not terminate", is consistent, and whose proofs could be enumerated & checked by computer must be incomplete and, furthermore, contains statements that you know are true but cannot be proven within the logic system.

I think Godels proof works because statements of this form "program P terminates" can be converted into statements about the natural numbers.

 

[epenguin]

However, you don't need to go that far to avoid Gödel's theorem, you just need to get rid of multiplication. Then you are left with Presburger Arithmetic which is decidable.

That was just what I meant to ask about! I had read in a Scientific American article, almost as an aside, that arithmetic can be proved consistent as long as you don’t have multiplication (and its inverse, division) in it.

BTW That would mean it can prove its own consistency within its own axioms. OK?
That is also true of projective geometry OK?
? Does that mean you could have a finite machine that can prove any theorem within these systems in a finite time or have I confused issues? If not, why doesn’t someone make such a machine?


Anyway the problem I always had about multiplication is I could never see why it is said to be a separate fundamental operation like an axiom.
Multiplying n by m is just adding n to itself m-1 times! As far as I can see you could specify an algorithm involving just the notions that are in the numbers, succession etc., and addition - define multiplication within those axioms etc.. So if you can assume addition by my reasoning you would have the whole of arithmetic.

But if I have missed something about multiplication, why is raising to a power, n^m being just multiplying n by itself m-1 times completely by the same form of definition as multiplication above, not also a fundamental independent operation or axiom?

 

[chronon]

? Does that mean you could have a finite machine that can prove any theorem within these systems in a finite time or have I confused issues?

Yes

If not, why doesn’t someone make such a machine?

They have done so (although the applet mentioned in wikipedia doesn't seem to load properly)

Anyway the problem I always had about multiplication is I could never see why it is said to be a separate fundamental operation like an axiom.
Multiplying n by m is just adding n to itself m-1 times! As far as I can see you could specify an algorithm involving just the notions that are in the numbers, succession etc., and addition - define multiplication within those axioms etc.. So if you can assume addition by my reasoning you would have the whole of arithmetic.

That you can do something m-1 times involves an assumption about the nature of m, so you're really introducing new axioms which are equivalent to those of multiplication

But if I have missed something about multiplication, why is raising to a power, n^m being just multiplying n by itself m-1 times completely by the same form of definition as multiplication above, not also a fundamental independent operation or axiom?

Once you have multiplication you can define functions which need loops to program. For instance you can define exponentiation in terms of addition and multiplication as I mentioned previously

 

[epenguin]

That you can do something m-1 times involves an assumption about the nature of m, so you're really introducing new axioms which are equivalent to those of multiplication



Once you have multiplication you can define functions which need loops to program. For instance you can define exponentiation in terms of addition and multiplication as I mentioned previously

Thank you, surprisingly I begin to see. When I program to add/subtract numbers I can do it without it having any meaning. E.g. Just add or remove strokes on a tape. Whereas when I said ‘do it m times’ I am attaching a meaning to a number.

I try to get round what this is assuming and make it a purely mechanical algorithm on the lines of codec9. The way I would naturally do it involves a cycle. You are saying a cycle is an idea additional to the simple addition-axioms only arithmetic, and that it can be defined as equivalent to multiplication. You are also saying cycle is inevitable if I want to multiply (less evident but I will think about it). So this primitive arithmetic has no cycles. I needed cycles for multiplication because I have a subroutine going that keeps track of the number of additions I have made, knocking 1 off a register and when that becomes 0 I stop my additions.

And there are no cycles in the dumbed-down addition arithmetic? If I try to prove A + B – A = B in general or for a particular case I am not going to have to go back to the first A when I write the second in order to know it’s the same thing?

 

[Hurkyl]

The magic at work here is that you can do string processing via integer arithmetic. We can encode information into the digits of a number, and the four basic (integer) arithmetic operations are sufficient to extract and manipulate that data, and are thus enough to implement any algorithm -- and first-order logic is powerful enough to let us reason about algorithms in Peano arithmetic.



For your particular question, you only need recursion, and we don't have to fully implement a Turing machine to make use of it. I'll give you a hint and let you mull it over for a bit, and you can ask for more. I've colored the hint white, so you'll have to highlight it to see it:

__________________________________
Notice the 6-digit base-67 number

64,32,16,8,4,2​

has some interesting properties...

(I've written the individual digits in base 10, and separated them with commas)
[/color]__________________________________

 

[epenguin]

I will be away for a time, mulling and other things. Back later.