Wednesday May 7

Russell's Paradox
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.

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:

KURT GODEL
KURT GODEL achieved fame in 1931 with the publication of his Incompleteness Theorem.


.....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. The input and output are written as integers (or whole numbers) and Oracle performs only the usual operations of addition, subtraction, multiplication and division (when possible). Unlike ordinary computers, there are no concerns regarding efficiency or time. Oracle will carry out properly given instructions no matter how long it takes and it will stop only when they are executed--even if it takes more than a million years.

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 there are properly posed questions involving only the arithmetic of integers that Oracle cannot answer. In other words, there are statements that--although inputted properly--Oracle cannot evaluate to decide if they are true or false. Such assertions are called undecidable, and are very complicated.
 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.
Incompleteness_theorem_simply_explained

Explanation: The Vow of  Completeness (based on an essay in rationalwiki.org linked in the title above- by Tetronian.)
Imagine that Arthur (A) is knight on  the Smullyan Island who has also taken the Vow of Completeness:
If A is given a statement and it is true, A must say it out loud.


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 one can formulate an arithmetically cogent characterization of the set of numbers corresponding to the linguistic strings selected as axioms. Thus, once we have a proper numbering for the elements of the language (we will refer to such a numbering as as a Gödel numbering, or a G-numbering for short), and as long as our axiom system A is manageable in the sense indicated above, the following numerical properties all turn out to be expressible within arithmetic itself:

    x is the G-number of an arithmetical formula.
    x is the G-number of the formula obtained by substituting y for all free variables in the formula with G-number z
    x is the G-number of one of the axioms in A
    x is the G-number of a formula which is provable from A.

The construction of the Gödel sentence for A. In view of the expressibility of the properties and relations listed above, it is possible to construct a formula of arithmetic with two free variables which can be "encapsulated" as

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

The formula for which (B) and (C) are shorthands is a formula of arithmetic containing one free variable, "x". Since it is a formula of arithmetic, it itself has a G-number. If we had taken the trouble to spell out (C) in all its gory arithmetic detail, and to give a precise description of our G-numbering, we could in fact calculate this number (which would, undoubtedly, turn out to be quite large). In lieu of this calculation, let us call this number c. Thus, c is the G-number of the (fully spelled out) formula (C).

Let us substitute c for "x" in (C). This gives us, for A, the formula known as the Gödel sentence:

 
(GSentA)   There is no proof from A for the formula obtained by substituting c
           for all free variables in the formula whose G-number is c.

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.