Gödel según Dale Myers

7/30/2019 Gdel segn Dale Myers

1/10

Godel's

Incompleteness Theorem

By Dale Myers

Cantor's Uncountability Theorem Richard's Paradox

The Halting Problem Tarski's Self-Reference Lemma

Cantor's Power-set Theorem Tarski's Undefinability of Truth Theorem

Russell's Contradiction Godel's First Incompleteness Theorem

The Liar Paradox Godel's Second Incompleteness Theorem

Diagonalization arguments are clever but simple. Particular instances though

have profound consequences. We'll start with Cantor's uncountability theorem

and end with Godel's incompleteness theorems on truth and provability.

In the following, a sequence is an infinite sequence of 0's and 1's. Such a

sequence is a function f: N -> {0,1} where N = {0,1,2,3, ...}.Thus 10101010... is the function f with f(0) = 1, f(1) = 0, f(2) = 1, ... .

A sequencefis the characteristic function of the set {i :f(i) = 1}.

Thus 101010101... is the characteristic function of the set {0,2,4,6, ...}.

IfXhas characteristic functionf(i), its complement has characteristic function 1 -

f(i).

Cantor's Uncountability Theorem. There are uncountably many infinite

sequences of 0's and 1's.

Proof. Suppose not.

Let f0, f1, f2, ... be a list of all sequences.

Let f be the complement of the diagonal sequence fi(i).

Thus f(i) = 1-fi(i).

For each i, f differs from fi at i.

Thus fis not in {f0, f1, f2, ...}.

This contradicts the assumption that the list contained all sequences.
http://www.math.hawaii.edu/~dale/board/myerss.jpghttp://www.math.hawaii.edu/~dale/godel/godel.html#CantorUncountability%23CantorUncountabilityhttp://www.math.hawaii.edu/~dale/godel/godel.html#RichardParadox%23RichardParadoxhttp://www.math.hawaii.edu/~dale/godel/godel.html#HaltingProblem%23HaltingProblemhttp://www.math.hawaii.edu/~dale/godel/godel.html#SelfReference%23SelfReferencehttp://www.math.hawaii.edu/~dale/godel/godel.html#PowerTheorem%23PowerTheoremhttp://www.math.hawaii.edu/~dale/godel/godel.html#TarskiUndefinability%23TarskiUndefinabilityhttp://www.math.hawaii.edu/~dale/godel/godel.html#RussellContradiction%23RussellContradictionhttp://www.math.hawaii.edu/~dale/godel/godel.html#FirstIncompleteness%23FirstIncompletenesshttp://www.math.hawaii.edu/~dale/godel/godel.html#LiarParadox%23LiarParadoxhttp://www.math.hawaii.edu/~dale/godel/godel.html#SecondIncompleteness%23SecondIncompletenesshttp://www.math.hawaii.edu/~dale/board/myerss.jpghttp://www.math.hawaii.edu/~dale/godel/godel.html#CantorUncountability%23CantorUncountabilityhttp://www.math.hawaii.edu/~dale/godel/godel.html#RichardParadox%23RichardParadoxhttp://www.math.hawaii.edu/~dale/godel/godel.html#HaltingProblem%23HaltingProblemhttp://www.math.hawaii.edu/~dale/godel/godel.html#SelfReference%23SelfReferencehttp://www.math.hawaii.edu/~dale/godel/godel.html#PowerTheorem%23PowerTheoremhttp://www.math.hawaii.edu/~dale/godel/godel.html#TarskiUndefinability%23TarskiUndefinabilityhttp://www.math.hawaii.edu/~dale/godel/godel.html#RussellContradiction%23RussellContradictionhttp://www.math.hawaii.edu/~dale/godel/godel.html#FirstIncompleteness%23FirstIncompletenesshttp://www.math.hawaii.edu/~dale/godel/godel.html#LiarParadox%23LiarParadoxhttp://www.math.hawaii.edu/~dale/godel/godel.html#SecondIncompleteness%23SecondIncompleteness


2/10

Corollary. There are uncountably many subsets of N. There are

uncountably many reals.

Proof. The set of subsets of N is isomorphic to the set of 0-1 sequences

via the bijection between subsets and characteristic functions.

There are uncountably many reals since the map which sends a 0-1

sequence 10101010... to the decimal .1010101... is 1-1.

The diagonal fi(i) is constructed from the list fj(i) by substituting i forj. Thus

fcan be constructed from the given list using just complementation and

substitution.

In general, diagonalization shows that a set of objects (sequences, programs,provable theorems, true facts) either can't be listed, computed or defined in a nice

way or else a simple-to-construct diagonal or self-referential object is not one of

the set's objects.

Roughly either the objects can't be listed or they aren't closed under the

substitution and complementation operations used to construct a diagonal.

Let's replace "sequences" by "sequences I can comprehend". Then either I can't

comprehend the list of all such sequences, or I can't comprehend the diagonal. I

figure that if I could comprehend the whole list in any way, I should also be ableto comprehend the diagonal. Hence I must accept the first alternative: I can't

comprehend the list of comprehensible sequences. The same applies to

"sequences which God can comprehend". Thus omniscience has some limits.

Now replace "sequences" with "computable sequences".

Definition. A sequence f(i) is computableif there is a program which

given input icomputes f(i).

Are the computable sequences countable? Sure, a program is a finite sequence

of symbols, say, ASCII symbols. There are only countably many finite

sequences of symbols and so there are only countably many programs and hence

only countably many computable sequences. But on the other hand --

Theorem. The set of computable sequences cannot be listed in a

computable way.


3/10

Proof. Suppose f0, f1, f2, ... , is a computable list of all computable

sequences. By this we mean that there is a program P which given

inputsjand icomputes fj(i).

Let fbe the complement of the diagonal: f(i) = 1-fi(i).

As before, fis not in the list f0, f1, f2, ... .

But we can compute fas follows:

Read input i.

Apply Pto the two inputs iand i.

Output 1 if Poutputs 0 and output 0 if not.

Again we have a contradiction.

Pick your favorite programming language (if its COBOL, take a break and comeback after your nap). Each program is a string of symbols.

Definition. A 0-1 sequence programis a string of symbols which

(1) is grammatically correct for the chosen programming language,

(2) has a single input variable iwith domain N,

(3) has output statements only of the form "return 0" or "return 1",

(4) for every input i, produces an output ("halts") in a finite number of

steps.

Any program which computes a sequence of 0's and 1's can easily be rewritten so

as to satisfy (1)-(4).

Corollary. The set of 0-1 sequence programs cannot be listed in a

computable way.

Proof. Suppose P0, P1, P2, ... is a computable list of such programs.

Let f0, f1, f2, ... be the list of sequences they compute. This list containsall computable sequences and it can be computed as follows:

Read inputsjand i.

Get program Pj from the given list.

Run program Pj on input i.

Output whatever Pj outputs.

This contradicts the theorem above.

We can computably list all strings.


4/10

We can also computably check conditions (1), (2), and (3) of the definition

above.

Hence it is condition (4) which can't be checked in a computable way.

Thus --

Lemma. There is no program which each input p, determines if p is a

program which halts on all of its inputs.

What about the simpler problem of checking that a program halts a particular

input?

Halting Problem Theorem. There is no program R(p,i) which for eachprogram p and each input i, can determine "yes" or "no" if p halts on

i.

Proof. Suppose there is such a program R(p,i).

Let hbe the program which on input pcomputes

R(p,0), R(p,1), R(p,2), ... until it finds an isuch that R(p,i) is "no".

On finding such an i, it outputs iand halts.

If there is no such i, it searches forever and doesn't halt.

Now for any program p, we can decide whether or not phalts on all of its

inputs:

pdoesn't halt on all its inputs iff

hdoes halt on input piff

R(h,p) is "yes".

Contradiction: by the lemma above, this is undecidable.

To see why halting problems are hard, consider the program which

on input n, looks for the first pair of twin primes greater than n.

Thus on input 8, we get 11,13.

Does this program halt on all inputs?

The extra-strength version of Cantor's theorem says that a set cannot

count its own subsets.


5/10

Theorem (Cantor). The set P(X) of all subsets of a set Xhas a larger

cardinality (number of elements) than the original set X.

Proof. Suppose they have the same number of elements.

Let f: X-> P(X) be a bijection between Xand P(X).

(1) Let D= {xin X: xis not in f(x)}.

Since Dis a subset of Xand fis onto,

(2) D= f(d) for some d.

Thus dis in f(d) iff (by 2) dis in D iff (by 1) dis not in f(d).

This is a contradiction.

The set theoretic analog of listing a sequence of things, is grouping or"comprehending" a collection of things into a set. Sets are sort of unordered

lists.

Russell's Contradiction. To formalize Cantor's set theory, Frege

proposed the "comprehension" schema:

For every condition p(x) on x,

there is a set {x: p(x)} of elements which satisfy the condition.

Russell discovered that this omnipotent schema runs afoul of the

diagonalization principal: you can't list (comprehend) things or you can'tconstruct the diagonal.

Let D= {x: xnot in x}.

Then Din D iff Dnot in D, a contradiction.

Quine proposed banning self-referential conditions like "x not inx" by requiring

that the variables of the condition be stratifiable into layers with membership "x

in y" allowed only whenx is in a lower layer than y.

Zermelo proposed restricting the comprehension schema to subsets:

For every conditionp(x) onx and every set Y,

there is a subset {x in Y:p(x)}.

Both proposals finesse Russel's contradiction but are there other

inconsistencies in the closet? Once burned, logicians wanted a proof of

consistency. None was found. Then Godel proved such consistency

proofs are impossible. Zermelo's set theory has been universally

accepted, but its consistency will always be a matter of faith. Quine's set

theory would be just an historical footnote except for a long-standing open

problem: Does the consistency of Zermelo's axioms imply the

consistency of Quine's?


6/10

From sets which are members of themselves we now go to sentences

which refer to themselves.

The Liar Paradox. "Truth" for English sentences is not definable in

English.

Proof. Suppose it is. Then so is its complement "False".

Let s be the sentence "This sentence is false" .

Since the phrase "This sentence" refers to s, we have

s iff "This sentence is false" iff "sis false" iff not s.

A contradiction.

Richard's Paradox. Definability, the relation "the number nis defined by

the (English) sentence s" not definable in English.

Proof. Suppose it is. Let nbe the least number not definable by a

sentence of less than 1000 symbols. Exercise: find the contradiction.

When translated into precise formal logic, these curiosities become

Godel's magnum opus.

To make the transition, note that the sentence s which says

"This sentence is false"

is characterized up to logical equivalence as being the solution to the

logical equation:

s iff "sis false".

Tarski's Self-Reference Lemma states that in adequate mathematicaltheories, such equations always have solutions.

A theory is adequateif it is strong enough to encode finite sequences of

numbers and define simple sequence operations such as concatenation.

In an adequate theory, we can encode the syntax of such things as terms,

sentences, programs, and proofs. In particular, for every formula p, there

is an object < p> which encodes this formula.

Even very weak number theories are adequate. So is set theory since
http://www-groups.dcs.st-and.ac.uk/~history/Mathematicians/Godel.htmlhttp://www-groups.dcs.st-and.ac.uk/~history/Mathematicians/Godel.html


7/10

numbers can be defined in set theory. For concreteness, let's pick

number theory with our favorite axioms: +, x, 0, 1 have the associative,

commutative, distributive, identity and cancellation properties.

For any first-order formula p(x),

if p(0) and p(n) -> p(n+1) for all n, then p(n) holds for all n.

Tarski's Self-Reference Lemma. For any formula p(x) in an adequate

theory, there is a sentence (formula without free variables) s such that

s iff p( < s> )

where < s> is the number which encodes s.

Proof. We omit the short but technical 5-line proof.

Suppose p(x) says "xhas at most 1000 symbols".

By Tarski's Self-Reference Lemma, there is a solution s to:

s iff p( < s> ).

Thus s says "This sentence has at most 1000 symbols".

Since sentences of number theory can be coded up as numbers (the

ASCII coding your computer uses does just fine), the set of true

sentences can be identified with the set TRUTH of numbers which

encode true sentences. Is this set definable in number theory?

Tarski's Undefinability of Truth Theorem. TRUTH, the set of numbers

which encode true sentences of number theory, is not definable in

number theory.

Proof. By the definition of TRUTH, for any sentence s,

(1) < s> is in TRUTH iff sis true.

Let s be the sentence "This sentence is false".

This sentence exists by Tarski's Self-Reference Lemma since it is the

solution of


8/10

(2) s iff < s> is not in TRUTH.

Thus

s iff < s> is not in TRUTH iff sis not true iff not s.

This is a contradiction. We have used the law of the excluded middle

and the consistency of the set of true sentences.

Since undefinable implies uncomputable, there will never be a program which

can decide, for each sentence of number theory, whether the sentence is true or

false.

Let PROVABLE be the set of sentences of number theory which are provable in

our favorite axiom system. Since all our axioms are true, PROVABLE is a

subset of TRUTH. It would be nice if they were the same. In this case our set

of axioms would be complete. No such luck.

Definition. A theory is axiomatizableif it has a computably generated set

of axioms.

Any sentence can be an axiom as long as it is true.

Godel's First Incompleteness Theorem. Any adequate axiomatizable

theory is incomplete. In particular the sentence "This sentence is not

provable" is true but not provable in the theory.

Proof. Given a computably generated set of axioms, let PROVABLE be

the set of numbers which encode sentences which are provable from the

given axioms.

Thus for any sentence s,(1) < s> is in PROVABLE iff sis provable.

Since the set of axioms is computably generable,

so is the set of proofs which use these axioms and

so is the set of provable theorems and hence

so is PROVABLE, the set of encodings of provable theorems.

Since computable implies definable in adequate theories, PROVABLE is

definable.

Let sbe the sentence "This sentence is unprovable".

By Tarski, sexists since it is the solution of:


9/10

(2) s iff < s> is not in PROVABLE.

Thus

(3) s iff < s> is not in PROVABLE iff sis not provable.

Now (excluded middle again) sis either true or false.

If s is false, then by (3), s is provable.

This is impossible since provable sentences are true.

Thus s is true.

Thus by (3), s is not provable.

Hence s is true but unprovable.

Note 1. An analysis of the proof shows that the axioms don't have to be true. It

suffices that (a) the system is consistent and (b) it can prove the basic factsneeded to do arithmetical computations, e.g., prove that 2+2=4. The latter is

needed to encode sequences of numbers and insure that computable sets are

definable.

Note 2. Godel discovered that the sentence "This sentence is unprovable" was

provably equivalent to the sentence CON:

"There is no with both and < nots > in PROVABLE".

CON is the formal statement that the system is consistent.

Since s was not provable, and since s and CON are equivalent,

CON is not provable. Thus --

Godel's Second Incompleteness Theorem. In any consistent

axiomatizable theory (axiomatizable means the axioms can be

computably generated) which can encode sequences of numbers (and

thus the syntactic notions of "formula", "sentence", "proof") the

consistency of the system is not provable in the system.

The theories of real numbers, of complex numbers, and of Euclidean

geometry do have complete axiomatizations. Hence these theories have

no true but unprovable sentences. The reason they escape the

conclusion of the first incompleteness theorem is their inadequacy, they

can't encode and computably deal with finite sequences.

There is a weak theological parallel in the Problem of Evil:


10/10

God doesn't exist since an ultimate ruler must be responsible for

all things but a perfectly just being wouldn't be responsible for

evil acts.

Actually this doesn't prove divine nonexistence: just that certain notions ofbeing "ultimately responsible" and being "perfectly just" are inconsistent.

Being ultimately responsible is a form of strength like being able to

encode sequences of numbers. Being just is like the property of being

self-consistent (inconsistency is the sole mathematical evil). As with

diagonal arguments, you can't have both.

Godel biography Another biography

References about Godel

Godel's other results

Implications of Godel's theorems
http://www-groups.dcs.st-andrews.ac.uk/~history/Mathematicians/Godel.htmlhttp://www.unca.edu/math/club/godel.htmlhttp://www-groups.dcs.st-and.ac.uk/history/References/Godel.htmlhttp://www.mathacademy.com/platonic_realms/encyclop/articles/godel.htmlhttp://www.santafe.edu/~shalizi/notebooks/godels-theorem.htmlhttp://www-groups.dcs.st-andrews.ac.uk/~history/Mathematicians/Godel.htmlhttp://www.unca.edu/math/club/godel.htmlhttp://www-groups.dcs.st-and.ac.uk/history/References/Godel.htmlhttp://www.mathacademy.com/platonic_realms/encyclop/articles/godel.htmlhttp://www.santafe.edu/~shalizi/notebooks/godels-theorem.html

Documents

Gödel según Dale Myers