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