PHIL
411: Advanced Logic
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.