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.