Russell's Paradox

Arithmetic- Coding - Proof : The limitations of finite structure and proof.

Godel's Theorems.

Premiss: If we write a sentence X
describing the elements (members) of the universe, then a set described
by having its members be those objects in the universe that satisfy the
sentence X exists.

Examples: The universe includes the natural numbers and sets of natural numbers.

Sentence A: n is prime natural number. So, the set P ={n: n is prime natural number} exists.

Sentence B: S is a finite set of natural numbers. So, the set FN={S: S is a finite set of natural numbers} exists.

Consider the statements: 1. {1,2,3} is an element of FN. [This statement is true because the statement: "{1,2,3} is a finite set of natural numbers" is true.]

2. P is an element of FN. [ This statement is false because the statement: "P is a finite set of natural numbers" is false.

Examples: The universe includes the natural numbers and sets of natural numbers.

Sentence A: n is prime natural number. So, the set P ={n: n is prime natural number} exists.

Sentence B: S is a finite set of natural numbers. So, the set FN={S: S is a finite set of natural numbers} exists.

Consider the statements: 1. {1,2,3} is an element of FN. [This statement is true because the statement: "{1,2,3} is a finite set of natural numbers" is true.]

2. P is an element of FN. [ This statement is false because the statement: "P is a finite set of natural numbers" is false.

Russell's Paradox: R = { S: S is not an element of S } is not a set.

Proof:

Suppose R is a set.

Then the statement: “R is an element of R” is a statement.

If R is an element of R, then by definition of R, R is not an element of R .

This is a contradiction, so R is not an element of R.

Now by definition of R, R is an element of R.

In summary, if R is a set there is a mathematical proposition that is a contradiction.

This is absurd. So R is not a set. Q.E.D.

Arithmetic- Coding - Proof : The limitations of finite structure and proof.

Godel's Theorems.

Summary of comments on Godel's Theorems

What is Godel's Theorem?

Jan 25, 1999

Melvin Henriksen--Professor of Mathematics Emeritus at Harvey Mudd College--offers this explanation:

.....I will rephrase and simplify it in the language of computers.

Imagine that we have access to a very powerful computer called Oracle. As do the computers with which we are familiar, Oracle asks that the user "inputs" instructions that follow precise rules and it supplies the "output" or answer in a way that also follows these rules. The same input will always produce the same output.

Let's consider a simple example. Remember that a positive integer (let's call it N) that is bigger than 1 is called a prime number if it is not divisible by any positive integer besides 1 and N. How would you ask Oracle to decide if N is prime? Tell it to divide N by every integer between 1 and N-1 and to stop when the division comes out evenly or it reaches N-1. (Actually, you can stop if it reaches the square root of N. If there have been no even divisions of N at that point, then N is prime.)

What Godel's theorem says is that

The proof begins with Godel defining a simple symbolic system. He has the concept of a variables, the concept of a statement, and the format of a proof as a series of statements, reducing the formula that is being proven back to a postulate by legal manipulations. Godel only need define a system complex enough to do arithmetic for his proof to hold.

Godel then points out that the following statement is a part of the system: a statement P which states "there is no proof of P". If P is true, there is no proof of it. If P is false, there is a proof that P is true, which is a contradiction. Therefore it cannot be determined within the system whether P is true.

As I see it, this is essentially the "Liar's Paradox" generalized for all symbolic systems. For those of you unfamiliar with that phrase, I mean the standard "riddle" of a man walking up to you and saying "I am lying". The same paradox emerges. This is exactly what we should expect, since language itself is a symbolic system.

Godel's proof is designed to emphasize that the statement P is *necessarily* a part of the system, not something arbitrary that someone dreamed up. Godel actually numbers all possible proofs and statements in the system by listing them lexigraphically. After showing the existence of that first "Godel" statement, Godel goes on to prove that there are an infinite number of Godel statements in the system, and that even if these were enumerated very carefully and added to the postulates of the system, more Godel statements would arise. This goes on infinitely, showing that there is no way to get around Godel-format statements: all symbolic systems will contain them.

Explanation: The Vow of Completeness (based on

Imagine that Arthur (A) is knight on the Smullyan Island who has also taken the Vow of Completeness:

It seems logical to assert that A can apply this vow to any possible statement. (Remember this feeling: it's important.) Let's look at a simple example: Assume B is a person who does not live on the island and is neither a Knight or a Knave.

(On a cloudy day)

B: It is cloudy outside.

A: It is cloudy outside.

B: It is sunny.

A: ... (silence)

Simple, right? Now, let's look at a slightly more complex example:

(On a cloudy day)

B: I can say that it is cloudy out.

A: I can say that it is cloudy out.

B: I cannot say "it is sunny out."

A: I cannot say "it is sunny out."

Do you understand why A can say the second sentence? If not, let's look at the first in more detail.

A says "I can say 'it is cloudy out,'" which is the same as saying "'It is cloudy out' is true." Since that sentence as a whole is true, A is allowed (in fact - A has to) say it. In the second sentence, he says "I cannot say 'it is sunny out,'" which is the same as saying "'It is sunny out' is false." Since this sentence as a whole is true, A must say it.

Still, it certainly looks like A's Vow's rule can be applied to any particular case, no matter how convoluted-sounding.

This, however, is where Gödel said no.

There are some statements, he said, that show that it is impossible to be both completely accurate and completely universal (that is, be able to be a knight and apply the completeness vow to all statements).

How did he show this? Let's look at another example conversation, in which B is replaced by the crafty Gödel:

Gödel: Imagine the sentence G, which states " 'I can never say G' is true."

Now A am confronted with a serious problem. If A says Gödel's sentence in the quotations, then it is false, since A did say "'I can never say G' is true." This means that A would have uttered a false statement, which means A is not a knight, but a knave!

But if A remains silent, then "'I can never say G' is true" is a true statement, and then A has violated the Vow because A is supposed to always say a statement that is true when A hears it.

Let's break it down:

If A says G, which is "'I can never say G' is true," then G is false and A is not a knight.

If A does not say G, which is "'I can never say G' is true," then G is true and A have broken the rule.

Thus, said Gödel, it is impossible to be completely accurate and completely universal. In terms of the example of the Vow, this means that no one can really be both a knight and Complete; there are some statements that you can never say even though they are true.

Godels_incompleteness_theorems : Detailed outline of proofs

The common thread of Gödel's Incompleteness Theorems is that arithmetic, understood as a branch of mathematics whose goal is to investigate actual properties of the natural numbers, cannot be fully axiomatized. However carefully we choose our axioms, and however many we select, if the axiom set is manageable - so that we can know by some simple procedure what is and what is not an axiom - there will always be actual properties of the natural numbers that we will not be able to "get at" from these axioms through a purely deductive procedure - i.e. statements which must in actuality hold, but which cannot be proved from the chosen axiom system. Notice that the concept of manageability is crucial. We could say, for instance: "Let's simply take as our axioms all true statements about the natural numbers." Such an axiom system would be complete and consistent: one could, in principle, prove every true statement, and no false ones. In practice, however, faced with a complex arithmetic statement, we would have no way of recognizing whether or not it was an axiom, and the system would therefore be actually useless for proving or disproving anything.

This intuitive notion of "manageability", and its relationship to arithmetic itself - specifically the fact that it can be translated very precisely into purely arithmetic concepts - lies at the very heart of Gödel's proofs. The crux of the argument is that if our linguistic means are to be adequate for arithmetic, they have to be expressive enough to permit us to talk about things like divisibility, decomposition into prime numbers, etc. However, if the system possesses that level of expressiveness (which is the least we would expect of it), it turns out to be powerful enough to also "talk", in a certain sense which we will make clearer below, about anything that is "manageable" - in particular, about any useful axiom system we may construct within it, as well as about the proof procedures that constitute "correct reasoning". And this very potential for self-referentiality on the part of the system makes it possible to construct within the system sentences which, one might say, outstrip the system's own deductive capabilities.

... notions of what constitutes a well-formed formula, a formula with free variables, or a proof from a given set of axioms, can all be expressed as rules for how symbols are stringed together, i.e. as rules of concatenation.

And at the same time, the requirement that our axiom system for arithmetic be "manageable" implies, as it turns out, that

(A) y is the G-number of the formula obtained by substituting x

for all free variables in the formula whose G-number is x.

as well as a formula of arithmetic with one free variable which can be "encapsulated" as

(B) for-every-number z

if z is the G-number of the formula obtained by substituting x

for all free variables in the formula whose G-number is x

then z is not the G-number of a formula provable from A.

[By the term "encapsulation", as we just used it above, we mean a summary rendering, in English, of the salient semantic content of an arithmetical formula.]

Remembering that (B) can be treated as a formula of pure arithmetic, let us, for the sake of clarity, express the same idea more understandably. What (B) says, can be formulated as

(C) There is no proof from A for the formula obtained by substituting x

for all free variables in the formula whose G-number is x.

GSentA is a formula of arithmetic. It states that a certain formula of arithmetic is not provable from A. But which formula is that? The one obtained by substituting c for all free variables in the formula whose G-number is c, i.e. the one obtained by substituting c for x in (C). But the formula obtained by substituting g for x in (C) is GSentA itself. Thus, GSentA basically says "There is no proof from A for the formula GSentA", or "I AM NOT PROVABLE FROM A".

Note that since the Gödel sentence, when fully spelled out as a formula of arithmetic, has to contain a spelled-out expression of the property "x is the G-number of one of the axioms in A", it will be a different sentence for different choices of A. So although the construction of the Gödel sentence always proceeds along the same lines, its exact formal content will depend not only on the selected Gödel numbering, but also on the actual axiom system under consideration. This is why we have subscripted its shorthand name GSent with "A".

Gödels First Incompleteness Theorem - Semantic Version

The 1st Incompleteness Theorem, in its semantic formulation, can be stated as follows:

Assume that A is a manageable (in the sense indicated above) set of arithmetic statements that is also arithmetically sound - i.e. such that if we reason correctly using only A as our starting point, we will never arrive at any conclusion that does not actually hold in the realm of the natural numbers. Then it is possible to construct an arithmetical sentence which is actually true in the realm of natural numbers but cannot be proved from A.

To sketch the proof of the theorem, we note that we can construct for A the Gödel sentence GSentA, as outlined above. GSentA is a formula of arithmetic which, when understood as per the mediation of the chosen G-numbering, states that the formula GSentA is not provable from A.

Is GSentA provable from A? If it is, then what it states is false, and so we have a false formula which can be proved. Since, however, we have assumed that A is arithmetically sound - so that we cannot prove from it any arithmetically false proposition - we are forced to conclude that GSentA is in fact not provable. And since this non-provability is exactly what GSentA asserts, GSentA is true. So we have indeed constructed a sentence which, although arithmetically true, cannot be proved from A.