PHIL
411: Advanced Logic
LARKIN
____________________________
The
Undecidability of FirstOrder Logic and
The
Incompleteness of SecondOrder Logic
I.
Functions
A.
Functions
are just 2place 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. nplace functions, where n
is greater than 1 are still only 2place relations. It is just that the first member of each ordered pair in the
extension of the relation would be a sequence of n1 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
nonnegative 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.
ChurchTuring
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 q_{i} (L, q_{i})
2. Move right one square and go
into state q_{i} (R, q_{i})
3. Print “1” and go into state
q_{i } (P1, q_{i })
4. Erase square and go into q_{i }(E, q_{i })
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 T_{i}
corresponding to every computable function ¦_{i} . (ChurchTuring 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
ChurchTuring Theorem
A.
Theorem:
FirstOrder Logic is Undecidable
B.
Proof
P1:
Firstorder 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 firstorder 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 firstorder logic is undecidable.
V.
The
Incompleteness of SecondOrder Logic
A.
Preliminaries:
The Reduction Theorem:
A first order logic sentence is consistent iff
a certain argument in secondorder logic (i.e., EInf /\ EG(f/D)) is valid.
1.
EInf
= A sentence of secondorder logic that is true in every interpretation with an
enumerably infinite domain.
2.
EG
(f/D) = A sentence of secondorder logic that
is the existential generalization of a firstorder 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 firstorder logic f is consistent, then it is
true in some interpretation with an enumerably infinite domain.
B.
Proof:
P1: If
secondorder 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 firstorder
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 2^{nd}order logic) and so f is not consistent (Reduction Theorem).
P3: If there
is an effective test for the consistency of any sentence of firstorder logic f, then there is an effective test for the
validity of arguments of firstorder logic.
P4: But
there is no effective test for validity of arguments of firstorder
logic—firstorder logic is undecidable.
C: So
secondorder logic is incomplete.