LARKIN

____________________________

The Undecidability of First-Order Logic and

The Incompleteness of Second-Order Logic

I.                     Functions

A.     Functions are just 2-place relations whose extensions are sets of ordered pairs, where no two pairs have the same first member (input/argument) but different second members (output/value).

1.  “The mother of x” is a function.

2.  “The sister of x” is not a function.

3.  n-place functions, where n is greater than 1 are still only 2-place relations.  It is just that the first member of each ordered pair in the extension of the relation would be a sequence of n-1 elements.

B.       Terminology

1.  In ¦(a) = v, ‘a’ is called the argument and ‘v’ is called the value.

2.  The Domain of a function is the set of all arguments for the function.

3.  The Range of a function is the set of all values for the function.

C.      Partial Functions

1.  A function with Domain S is partial on S if the function is undefined for some members of S.

2.  The function ¦(x) = x – 1 is partial on the set of non-negative integers:

x – 1, if x ³ 1

¦(x)

undefined, if x = 0

D.      Machine Analogy: A function can be thought of as an input/output machine.  The domain of the function is the set of possible inputs and the range is the corresponding set of outputs.  When a function is partial, then there are some inputs for which the machine never provides an output.

E.       Computability:  A function ¦ is effectively computable if there is an algorithm (mechanical procedure) that will yield ¦(m) for any argument m at which ¦ is defined and give no result for any argument at which ¦ is undefined.

F.       Church-Turing Thesis (Conjecture)

Any function that is effectively computable is computable by a Turing machine.

II.                   Turing Machines

A.     Parts

1.  Infinite tape sectioned into squares

2.  Scanner/printer: Can tell whether a square is blank or has a “1” on it; and can print a “1” on a square or erase it.

3.  Control: Contains the software/program that tells the scanner/printer what to do when.

B.      Directions

1.  Move left one square and go into state qi  (L, qi)

2.  Move right one square and go into state qi (R, qi)

3.  Print “1” and go into state qi  (P1, qi )

4.  Erase square and go into qi  (E, qi )

5.  Halt  (H)

C.      Example: The Turing Machine Program (represented in the form of a “machine table”) for computing the function ¦(x) = x – 1 would look like this

 Blank 1 Q0 H (E, Q1) Q1 (R, Q1) H

III.                 The Halting Problem

A.     Imagine that we have the following:

1.  An enumeration of all computable functions ¦i  , where ¦m  is the mth element of the enumeration.

2.  There is a Turing Machine Ti corresponding to every computable function ¦i .  (Church-Turing Thesis).

B.      Question:  Can we build a Turing Machine that will tell us whether some Turing Machine Tm, which computes function ¦m, will halt when started with input n?

C.      In other words, is the following function computable?

1, if ¦m (n) is defined

h(m,n) =

0, if ¦m (n) is undefined

D.      The Halting Problem is Unsolvable

P1:  Assume that h(m,n) is computable.

P2:  Then the following would also be computable:

1, if h(x,x) = 0

g(x) =

0, if h(x,x) =1

P3:  If g(x) is computable, then g(x) = ¦e  and g(e) is either defined or not defined.

P5:  g(e) cannot be defined.

5.1:  If g(e) is defined, then ¦e (e) is defined.

5.2:  If ¦e (e) is defined, then h(e,e) = 1.

5.3:  If h(e,e) = 1, then g(e) is undefined.

P6:  g(e) cannot be undefined.

6.1:  If g(e) is undefined, then ¦e (e) is undefined.

6.2:  If ¦e (e) is undefined, then h(e,e) = 0.

6.3:  If h(e,e) = 0, then g(e) = 1 and is defined.

C1:  So g(e) is not computable.

C2:  So h(m,n) is not computable.

IV.                 The Church-Turing Theorem

A.     Theorem: First-Order Logic is Undecidable

B.      Proof

P1:  First-order logic is undecidable if the following function is not computable:

P2:  If v(a) is computable, then h(m,n) is computable.

2.1:  For any Turing Machine Tm, there is an associated argument of first-order logic that is valid iff Tm halts for n.

P3:  But h(m,n) is not computable.  (The halting problem is unsolvable.)

C1:  So v(a) is not computable.

C2:  So first-order logic is undecidable.

V.                   The Incompleteness of Second-Order Logic

A.     Preliminaries:

The Reduction Theorem:

A first order logic sentence is consistent iff a certain argument in second-order logic (i.e., EInf /\ EG(f/D)) is valid.

1.        EInf = A sentence of second-order logic that is true in every interpretation with an enumerably infinite domain.

2.        EG (f/D) = A sentence of second-order logic that is the existential generalization of a first-order logic sentence f relativized to a domain D.  This sentence is constructed in such a way that if it is true in some interpretation with an enumerably infinite domain, then it is true in every interpretation with an enumerably infinite domain.

3.        Lowenheim’s Theorem: If a sentence of first-order logic f is consistent, then it is true in some interpretation with an enumerably infinite domain.

B.      Proof:

P1:  If second-order logic is complete, then EInf /\EG(f/D) is provable if valid.

P2:  If EInf /\ EG(f/D) is provable if valid, then there is an effective test for consistency of any sentence of first-order logic f.

We try to prove EInf /\ EG (f/D) valid.  If we succeed, then the argument is valid and so f is consistent (Reduction Theorem).  If we do not succeed, then the argument is not valid (completeness of 2nd-order logic) and so f is not consistent (Reduction Theorem).

P3:  If there is an effective test for the consistency of any sentence of first-order logic f, then there is an effective test for the validity of arguments of first-order logic.

P4:  But there is no effective test for validity of arguments of first-order logic—first-order logic is undecidable.

C:  So second-order logic is incomplete.