<<

. 10
( 11 .)



>>

size k.
If all the sets being dealt with are all subsets of some ¬xed set Z,
¯
the complement of Y , Y , is usually taken to mean the complement
of Y relative to Z. It may sometimes be necessary to take unions,
intersections, and cross products of more than two sets.
Definition A.2. Suppose A is a set and X = { Xa | a ∈ A } is a
family of sets indexed by A. Then
1. The union of X is the set X = { z | ∃a ∈ A : z ∈ Xa }.
2. The intersection of X is the set X = { z | ∀a ∈ A : z ∈ Xa }.
3. The cross product of X is the set of sequences (indexed by A)
X = a∈A Xa = { ( za | a ∈ A ) | ∀a ∈ A : za ∈ Xa }.
We will denote the cross product of a set X with itself taken n times
(i.e. the set of all sequences of length n of elements of X) by X n .
Definition A.3. If X is any set, a k-place relation on X is a subset
R ⊆ X k.
For example, the set E = { 0, 2, 3, . . . } of even natural numbers is
a 1-place relation on N, D = { (x, y) ∈ N2 | x divides y } is a 2-place
79
80 A. A LITTLE SET THEORY

relation on N, and S = { (a, b, c) ∈ N3 | a + b = c } is a 3-place relation
on N. 2-place relations are usually called binary relations.
Definition A.4. A set X is ¬nite if there is some n ∈ N such that
X has n elements, and is in¬nite otherwise. X is countable if it is
in¬nite and there is a 1-1 onto function f : N ’ X, and uncountable if
it is in¬nite but not countable.
Various in¬nite sets occur frequently in mathematics, such as N (the
natural numbers), Q (the rational numbers), and R (the real numbers).
Many of these are uncountable, such as R. The basic facts about
countable sets needed to do the problems are the following.
1. If X is a countable set and Y ⊆ X, then
Proposition A.1.
Y is either ¬nite or a countable.
2. Suppose X = { Xn | n ∈ N } is a ¬nite or countable family of
sets such that each Xn is either ¬nite or countable. Then X
is also ¬nite or countable.
3. If X is a non-empty ¬nite or countable set, then X n is ¬nite or
countable for each n ≥ 1.
4. If X is a non-empty ¬nite or countable set, then the set of all
¬nite sequences of elements of X, X <ω = n∈N X n is countable.
The properly sceptical reader will note that setting up propositional
or ¬rst-order logic formally requires that we have some set theory in
hand, but formalizing set theory itself requires one to have ¬rst-order
logic.1




1
Which came ¬rst, the chicken or the egg? Since, biblically speaking, “In the
beginning was the Word”, maybe we ought to plump for alphabetical order. Which
begs the question: In which alphabet?
APPENDIX B


The Greek Alphabet

A ± alpha
B β beta
“ γ gamma
∆ δ delta
E µ epsilon
Z ζ zeta
H · eta
˜ θ ‘ theta
I ι iota
K κ kappa
Λ » lambda
M µ mu
N ν nu
O o omicron
Ξ ξ xi
Π π pi
P ρ rho
Σ σ ‚ sigma
T „ tau
Υ … upsilon
¦ φ • phi
X χ chi
Ψ ψ psi
„¦ ω omega




81
82 B. THE GREEK ALPHABET
APPENDIX C


Logic Limericks


Deduction Theorem

A Theorem ¬ne is Deduction,
For it allows work-reduction:
To show “A implies B”,
Assume A and prove B;
Quite often a simpler production.

Generalization Theorem

When in premiss the variable™s bound,
To get a “for all” without wound,
Generalization.
Not globalization;
Stay away from that management sound!

Soundness Theorem

It™s a critical logical creed:
Always check that it™s safe to proceed.
To tell us deductions
Are truthful productions,
It™s the Soundness of logic we need.

Completeness Theorem

The Completeness of logics is G¨del™s.
o
™Tis advice for looking for m¨dels:
o
They™re always existent
For statements consistent,
Most helpful for logical lab¨rs.
o


83
84 C. LOGIC LIMERICKS
Bibliography

[1] Jon Barwise (ed.), Handbook of Mathematical Logic, North Holland, Amster-
dam, 1977, ISBN 0-7204-2285-X.
[2] Merrie Bergman, James Moor, and Jack Nelson, The Logic Book, Random
House, NY, 1980, ISBN 0-394-32323-8.
[3] C.C. Chang and H.J. Keisler, Model Theory, third ed., North Holland, Ams-
terdam, 1990.
[4] Herbert B. Enderton, A Mathematical Introduction to Logic, Academic Press,
New York, 1972.
[5] Paul R. Halmos, Naive Set Theory, Undergraduate Texts in Mathematics,
Springer-Verlag, New York, 1974, ISBN 0-387-90092-6.
[6] James M. Henle, An Outline of Set Theory, Problem Books in Mathematics,
Springer-Verlag, New York, 1986, ISBN 0-387-96368-5.
[7] Douglas R. Hofstadter, G¨del, Escher, Bach, Random House, New York, 1979,
o
ISBN 0-394-74502-7.
[8] Jerome Malitz, Introduction to Mathematical Logic, Springer-Verlag, New
York, 1979, ISBN 0-387-90346-1.
[9] Yu.I. Manin, A Course in Mathematical Logic, Graduate Texts in Mathemat-
ics 53, Springer-Verlag, New York, 1977, ISBN 0-387-90243-0.
[10] Roger Penrose, The Emperor™s New Mind, Oxford University Press, Oxford,
1989.




85
86 BIBLIOGRAPHY
Index

R, 80
(, 7, 24
Rn , 53
), 7, 24
S, 10
=, 24, 25
©, 79 T , 11
∪, 79 Th, 39, 45
∃, 30 vn , 24
∀, 24, 25, 30 X n , 79
”, 9, 30 [X]k , 79
¯
∈, 79 Y , 79
§, 9, 30
abbreviations, 9, 30
¬, 7, 24, 25
all, 2
∨, 9, 30
and, 2, 9
|=, 14, 35, 37
assignment, 34, 35
, 14, 36, 37
extended, 35
, 79
truth, 11
, 16, 43
atomic formulas, 7, 27
\, 79
axiom, 15, 28, 39
⊆, 79
logical, 43
—, 79
schema, 15, 42
’, 7, 24, 25
A1, 15, 42
A2, 15, 42
An , 7
A3, 15, 42
F , 11
A4, 42
•x , 42
t
A5, 42
L, 24
A6, 42
L= , 26
A7, 42
L1 , 26
A8, 42
LF , 26
LG, 51 bound variable, 29
LN , 26
LNT , 25 chicken, 80
LO , 26 clique, 52
LP , 7 Compactness Theorem, 20, 50
LS , 26 applications of, 51
M, 33 complement, 79
N, 80 Completeness Theorem, 20, 50, 83
N, 33 connectives, 7, 9, 24
P, 79 consistent, 19, 47
Q, 80 maximally, 19, 48
87
88 INDEX

constant, 24, 25, 31, 33, 35 isomorphism of structures, 53
contradiction, 13, 38
John, 80
convention
common symbols, 25
language, 26, 31
parentheses, 9, 30
extension of, 30
countable, 80
¬rst-order, 23
cross product, 79
formal, 1
natural, 1
deduction, 16, 43
propositional, 7
Deduction Theorem, 17, 44, 83
limericks, 83
logic
edge, 52
¬rst-order, 2, 23
egg, 80
mathematical, 1
element, 79
natural deductive, 1
elementary equivalence, 54
predicate, 7
equality, 24, 25
propositional, 2, 7
equivalence
sentential, 7
elementary, 54
logical axiom, 43
existential quanti¬er, 30
extension of a language, 30
mathematical logic, 1
maximally consistent, 19, 48
¬nite, 80
metalanguage, 31
¬rst-order
metatheorem, 31
languages, 23
model, 37
logic, 2, 23

<<

. 10
( 11 .)



>>