A nice connection between Russel’s paradox and Gödel’s incompleteness theorems

Russel’s paradox states that there must not be a set y:={x|x∉x}, because then y∈y→y∉y and y∉y→y∈y.

In my younger days, when I had less knowledge but more time and fun when increasing it, I had a time when looking for paradoxes inside common theories. I simply didnt want to believe in the consistencies of the theories we have. I was desperately trying to get articles from Eduard Wette and liked hearing about failures mathematicians had made in the past. Well, this time wasnt too long, and soon I realized that searching for paradoxes in common theories is not useful anyway, since if they really arent consistent, either we will never know (and thus dont have to care) or we will notice someday and then adapt our theories. Anyway, on some day at this time, somehow I was thinking about the Russel Paradox and what happened to it if you did formal set theory inside number theory. Thinking deeper about it, I had a strange result which I firstly didnt quite understand.

First, lets not be too formal – such that you can understand my confusion at first sight.

Lets consider , the standard-model of peano arithmetic. As Gödel did, you can encode propositions about natural numbers in natural numbers themselves. Lets denote by [P] the natural number encoding the proposition P. Especially, you can encode every proposition with one free variable as a number, and a proposition with one free variable is something similar to a set of natural numbers. So lets denote by n∈[P] the fact that P(n) holds (and define it to be false if the second given argument doesnt encode a proposition with exactly one free variable). Now, is a binary relation between natural numbers, which can be expressed inside arithmetic, and so is its negation, which we denote by . Then the proposition n ∉ n has exactly one free variable, and can also be encoded as a natural number, say m:=[n ∉ n]. Now assume m m. Then, by definition of m, we have m m. Same vice versa. Sounds like a contradiction.

Ok, well, something obviously went wrong. Lets get a little more formal.

The first flaw is that we may be able to denote every proposition about natural numbers, but not the question whether it is true. Because we have to give a finite relation which tells when a given proposition should be true. Thus, lets redefine our relation by n∈[P] saying „there is a formal proof of P(n)„, or in signs ⊦P(n) – it is known that this is possible. Then again consider our m:=[n ∉ n]. It applies to all [P] such that ⊦P([P]). Again, we may ask whether m m. This time that means ⊦m m. That is, if m m then we can prove that m m which is a contradiction. Hence, m m if any. At this point we had the contradiction above.

But this time, m m means ¬⊦m m. That is, there is no formal proof for m m. At this point, we have shown that m m is not provable in peano arithmetic, but that it is indeed true in . That is, we have a proposition that is true in the standard model, but not provable, like the one Gödel created.

And if you think about it, you will notice that actually we created exactly the same proposition as Gödel did, namely a proposition stating its own unprovability. But essentially we have followed the same idea as done in Russel’s Paradox.

The main difference is that in Russels‘ Paradox, we assume some „omniscient“ decider for the relation, while in we also assume an „omniscient“ decider for the arithmetic relations we have, but we cannot assume an „omniscient“ decider for meta-propositions [P], we must use provability for this.

To emphasize this a bit, lets not talk about sets but about deciding functions f:’abool. Lets say ‚a may contain every of these functions. That is, every function can be passed an arbitrary function as first argument. Lets again define a relation f a g stating g(f)=True. Then we can define the function NSA(f):=True, if f a g and False otherwise. Then as before, we can ask whether NSA∈aNSA. Of course, this will lead to the same contradictions as above. In this case, the answer is again that such a function NSA must not exist. But this time we can clearly see the connections to both situations above: On the one hand, with NSA, we denote a set of objects, like in the Russel paradox. On the other hand, we want NSA to be something which can always „tell“ us the truth of a proposition, and there must not be such a thing, like in Gödel’s incompleteness theorem.

Btw, NSA stands for Non-Self-Accepting, one can identify it with the class of Non-Self-Accepting algorithms, i.e. algorithms which return False when they are passed their own code, and with a little more recursion theory, the above argument is the proof of NSA not being decidable.

Schreibe einen Kommentar

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s

%d Bloggern gefällt das: