Simpson S. G. Mathematical Logic.pdf

(769 KB) Pobierz
Copyright c 1998–2000 by Stephen G. Simpson
Mathematical Logic
Stephen G. Simpson
November 16, 2000
Department of Mathematics
The Pennsylvania State University
University Park, State College PA 16802
http://www.math.psu.edu/simpson/
This is a set of lecture notes for introductory courses in mathematical logic
offered at the Pennsylvania State University.
Contents
Table of Contents
1 Propositional Calculus
1.1 Formulas . . . . . . . . . . .
1.2 Assignments and Satisfiability
1.3 Logical Equivalence . . . . . .
1.4 The Tableau Method . . . . .
1.5 The Completeness Theorem .
1.6 Trees and K¨nig’s Lemma . .
o
1.7 The Compactness Theorem .
1.8 Combinatorial Applications .
2 Predicate Calculus
2.1 Formulas and Sentences . .
2.2 Structures and Satisfiability
2.3 The Tableau Method . . . .
2.4 Logical Equivalence . . . . .
2.5 The Completeness Theorem
2.6 The Compactness Theorem
2.7 Satisfiability in a Domain .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
3
3
5
8
10
13
15
16
17
19
19
21
23
27
30
35
36
38
38
39
42
45
49
3 Proof Systems for Predicate Calculus
3.1 Introduction to Proof Systems . . . . .
3.2 The Companion Theorem . . . . . . .
3.3 A Hilbert-Style Proof System . . . . .
3.4 Gentzen-Style Proof Systems . . . . .
3.5 The Interpolation Theorem . . . . . .
4 Extensions of Predicate Calculus
53
4.1 Predicate Calculus with Identity . . . . . . . . . . . . . . . . . . 53
4.2 Predicate Calculus With Operations . . . . . . . . . . . . . . . . 57
4.3 Many-Sorted Predicate Calculus . . . . . . . . . . . . . . . . . . 62
1
5 Theories, Models, Definability
5.1 Theories and Models . . . . . . . .
5.2 Mathematical Theories . . . . . . .
5.3 Foundational Theories . . . . . . .
5.4 Definability over a Model . . . . .
5.5 Definitional Extensions of Theories
5.6 The Beth Definability Theorem . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
65
65
65
66
66
66
66
67
67
67
67
70
71
72
73
74
75
6 Arithmetization of Predicate Calculus
6.1 Primitive Recursive Arithmetic . . . .
6.2 Interpretability of
PRA
in
Z
1
. . . . .
6.3 G¨del Numbers . . . . . . . . . . . . .
o
6.4 Undefinability of Truth . . . . . . . . .
6.5 The Provability Predicate . . . . . . .
6.6 The Incompleteness Theorems . . . . .
6.7 Proof of Lemma 6.5.3 . . . . . . . . .
Bibliography
Index
2
Chapter 1
Propositional Calculus
1.1
Formulas
Definition 1.1.1.
The
propositional connectives
are
negation
(¬ ),
conjunction
( & ),
disjunction
(
∨
),
implication
(
⇒
),
biimplication
(
⇔
). They are read as
“not”, “and”, “or”, “if-then”, “if and only if” respectively. The connectives & ,
∨
,
⇒
,
⇔
are designated as
binary,
while
¬
is designated as
unary.
Definition 1.1.2.
A
propositional language
L
is a set of
propositional atoms
p, q, r, . . ..
An
atomic
L-formula
is an atom of
L.
Definition 1.1.3.
The set of
L-formulas
is generated inductively according to
the following rules:
1. If
p
is an atomic
L-formula,
then
p
is an
L-formula.
2. If
A
is an
L-formula,
then (¬
A)
is an
L-formula.
3. If
A
and
B
are
L-formulas,
then (A &
B),
(A
∨
B),
(A
⇒
B),
and (A
⇔
B)
are
L-formulas.
Note that rule 3 can be written as follows:
3 . If
A
and
B
are
L-formulas
and
b
is a binary connective, then (AbB) is an
L-formula.
Example 1.1.4.
Assume that
L
contains propositional atoms
p, q, r, s.
Then
(((p
⇒
q)
& (q
∨
r))
⇒
(p
∨
r))
⇒ ¬
(q
∨
s)
is an
L-formula.
Definition 1.1.5.
If
A
is a formula, the
degree
of
A
is the number of occur-
rences of propositional connectives in
A.
This is the same as the number of
times rules 2 and 3 had to be applied in order to generate
A.
3
Example 1.1.6.
The degree of the formula of Example 1.1.4 is 8.
Remark 1.1.7.
As in the above example, we omit parentheses when this can
be done without ambiguity. In particular, outermost parentheses can always be
omitted, so instead of ((¬
A)
⇒
B)
we may write (¬
A)
⇒
B.
But we may not
write
¬
A
⇒
B,
because this would not distinguish the intended formula from
¬
(A
⇒
B).
Definition 1.1.8.
Let
L
be a propositional language. A
formation sequence
is
finite sequence
A
1
, A
2
, . . . , A
n
such that each term of the sequence is obtained
from previous terms by application of one of the rules in Definition 1.1.3. A
formation sequence for
A
is a formation sequence whose last term is
A.
Note
that
A
is an
L-formula
if and only if there exists a formation sequence for
A.
Example 1.1.9.
A formation sequence for the
L-formula
of Example 1.1.4 is
p, q, p
⇒
q, r, q
∨
r,
(p
⇒
q)
& (q
∨
r), p
∨
r,
((p
⇒
q)
& (q
∨
r))
⇒
(p
∨
r),
s, q
∨
s,
¬
(q
∨
s),
(((p
⇒
q)
& (q
∨
r))
⇒
(p
∨
r))
⇒ ¬
(q
∨
s) .
Remark 1.1.10.
In contexts where the language
L
does not need to be speci-
fied, an
L-formula
may be called a
formula.
Definition 1.1.11.
A
formation tree
is a finite rooted dyadic tree where each
node carries a formula and each non-atomic formula branches to its immediate
subformulas (see the example below). If
A
is a formula, the
formation tree for
A
is the unique formation tree which carries
A
at its root.
Example 1.1.12.
The formation tree for the formula of Example 1.1.4 is
(((p
⇒
q)
& (q
∨
r))
⇒
(p
∨
r))
⇒ ¬
(q
∨
s)
/
\
((p
⇒
q)
& (q
∨
r))
⇒
(p
∨
r)
¬
(q
∨
s)
/
\
|
(p
⇒
q)
& (q
∨
r)
p
∨
r
q
∨
s
/
\
/
\
/
\
p
⇒
q
q
∨
r
p
r
q
s
/
\
/
\
p
q q
r
or, in an abbreviated style,
⇒
/
\
&
∨
/
\
/
\
⇒ ∨
p r
/
\
/
\
p q q r
4
⇒
¬
|
∨
/
\
q s

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin