WIXLIB

:c IN T R o n u c T I o N Ibe enurrter ted merely by omitting all other phrases in the given standardenumeration. Call the nth real number in this enumeration the nth Richard number. Consider the phrase: 'the real number whose nth decimalplace is 1 if the nth decimal place of the nth Richard number is not L, andwhose nth decimal place is 2 if the nth decimal place of the nth Richardnumber is 1.' This phrase defines a Richard number - say, the kth Richard number; but, by its definition, it differs from the kth Richardnumber in the kth decimal place.6. Berry's paradox (1906). There are only a finite number of symbols (letters,punctuation signs, etc.) in the English language. Hence, there are only afinite number of English expressions that contain fewer than 200 occurrences of symbols (allowing repetitions). There are, therefore, only a finitenumber of positive integers that are denoted by an English expressioncontaining fewer than 200 occurrences of symbols. Let k be the leastpositive integer that is not denoted by an English expression containingfewer than 200 occurrences of symbols. The italicized English phrasecontains fewer than 200 occurrences of symbols and denotes the integer k.7. Grelling's paradox (1908). An adjective called auto logical if the propertydenoted by the adjective holds for the adjective itself. An adjective iscalled heterological if the property denoted by the adjective does notapply to the adjective itself. For example, 'polysyllabic' and 'English' areautological, whereas 'monosyllabic' and .'French' are heterological.Consider the adjective 'heterological'. If 'heterological' is heterological,then it is not heterological. If 'heterological' is not heterological, then it isheterological. In either case, 'heterological' is both heterological and notheterological.8. Lob's paradox (1955). LetA be any sentence. Let B be the sentence: 'If thissentence is true, then A'. So, B asserts: 'IfB is true, then A'. Now considerthe following argument: Assume B is true; then, by B, since B is true, Aholds. This argument shows that, if B is true, then A. But this is exactlywhat B asserts. Hence, B is true. Therefore, by B, since B is true, A is true.Thus, every sentence is true.isAll of these paradoxes are genuine in the sense that they contain noobvious logical flaws. The logical paradoxes (1-3) involve only notions fromthe theory of sets, whereas the semantic paradoxes (4-8) also make use ofconcepts like 'denote', 'true' and 'adjective', which need not occur withinour standard mathematical language. For this reason, the logical paradoxesare a much greater threat to a mathematician's peace of mind than thesemantic paradoxes.Analysis of the paradoxes has led to various proposals for avoiding them.All of these proposals are restrictive in one way or another of the 'naive'concepts that enter into the derivation of the paradoxes. Russell noted theself-reference present in all the paradoxes and suggested that every object

,r IN T R O DU C T IO N must have a definite non-negative integer as its 'type'. Then an expression 'xis ·a member of the set y' is to be considered meaningful if and only if thetype of y is one greater than the type of x.This approach, lmown as the theory of types and systematized and developed in Principia Mathematica Whitehead and Russell (1910-13), issuccessful in eliminating the known paradoxes,t but it is clumsy in practiceand has certain other drawbacks as well. A different criticism of the logicalparadoxes is aimed at their assumption that, for every property P(x), thereexists a corresponding set of all objects x that satisfy P(x). If we reject thisassumption, then the logical paradoxes are no longer derivable. t It is necessary, however, to provide new postulates that will enable us to prove theexistence of those sets that are needed by the practising mathematician. Thefirst such axiomatic set theory was invented by Zermelo (1908). In Chapter 4we shall present an axiomatic theory of sets that is a descendant of Zermelo's system (with some new twists given to it by von Neumann, R. Robinson, Bernays, and Godel). There are also various hybrid theoriescombining some aspects of type theory and axiomatic set theory- for example, Quine's system NF.A more radical interpretation of the paradoxes has been advocated byBrouwer and his intuitionist school (see Heyting, 1956). They refuse toaccept the universality of certain basic logical laws, such as the law ofexcluded middle: P or not-P. Such a law, they claim, is true for finite sets,but it is invalid to extend it on a wholesale basis to all sets. Likewise, theysay it is invalid to conclude that 'There exists an object x such that not-P(x)'follows from the negation of 'For all x, P(x)'; we are justified in asserting theexistence of an object having a certain property only if we know an effectivemethod for constructing (or finding) such an object. The paradoxes are notderivable (or even meaningful) if we obey the intuitionist ·.strictures, but soare many important theorems of everyday mathematics, and, for this reason, intuitionism has found few converts among mathematicians.Whatever approach one takes to the paradoxes, it is necessary first toexamine the language of logic and mathematics to see what symbols may beused, to determine the ways in which these symbols are put together to formterms, formulas, sentences and proofs, and to find out what can and cannotbe proved if certain axioms and rules of inference are assumed. This is one ofthe tasks of mathematical logic, and, until it is done, there is no basis fortRussells's paradox, for example, depends on the existence of the set A of all setsthat are not members of themselves. Because, according to the theory of types, it ismeaningless to say that a set belongs to itself, there is no such set A. Russell's paradox then proves that there is no set A of all sets that do notbelong to themselves. The paradoxes of Cantor and Burali-Forti show that there isno universal set and no set that contains all ordinal numbers. The semantic paradoxes cannot even be formulated, since they involve notions not expressible withinthe system.

c IN T R o n u cr r o N Icompariflt rival foundations of logic and mathematics. The deep and devastating resGlts ofGodel, Tarski, Church, Rosser, Kleene, and many othershave been ample reward for the labour invested and have earned formathematical logic its status as an independent branch of mathematics.For the absolute novice a summary will be given here of some of the basicnotation, ideas, and results used in the text. The reader is urged to skip theseexplanations now and, if necessary, to refer to them later on.A set is a collection of objects.t The objects in the collection are calledelements or members of the set. We shall write 'x E y' for the statement thatx is a member of y. (Synonymous expressions are 'x belongs to y' and 'ycontains x'.) The negation of 'x E y' will be written 'xtj:y'.By 'x c y' we mean that every member of x is also a mem her of y ( synonymously, that xis a subset of y, or that xis included in y). We shall write t s' to mean that t and s denote the same object. As usual, 't / - s' is thenegation of't s'. For sets x andy, we assume that x y if and only if x c yandy c x - that is, if and only if x and y have the same members. A set x iscalled a proper subset of a set y, written 'x c y' if x C y but x f y. (Thenotation x y is often used instead of x c y.)The union xU y of sets x andy is defined to be the set of all objects that aremembers ofx or y or both. Hence, xUx x, xU y y Ux, and (x Uy) Uz xU (yUz). The intersection xny is the set of objects that x andy have incommon. Therefore, xnx x, xny ynx, and (xny)nz xn(ynz).Moreover, xn (yUz) (xny) U (xnz) and xU (ynz) (xUy) n (x Uz).The relative complement x - y is the set of members of x that are notmembers of y. We also postulate the existence of the empty set (or null set)0 - that is, a set that has no members at all. Then x n 0 0, x U 0 x,x- 0 x, 0 - x f/J, and x- x 0. Sets x and y are called disjoint if·xny 0.Given any objects b 1 , . , bk, the set that contains b1 , . , bk as its onlymembers is denoted {b 1 , . , bk}· In particular, {x,y} is a set having x andyas its only members and, if x f y, is called the unordered pair of x andy. Theset {x,x} is identical with {x} and is called the unit set of x. Notice that{x,y} {y,x}. By (bt, . , bk) we mean the ordered k-tuple of b1 , . , bk. Thebasic property of ordered k-tuples is that (b 1, . , bk) (c1, . , ck) if andonly if b1 q, b2 c2, . , bk Ck· Thus, (bt, b2) (b2, bt) if and only ifb1 b2. Ordered 2-tuples are called ordered pairs. The ordered )-tuple (b) istaken to be b itself. If X is a set and k is a positive integer, we denote by Xkthe set of all ordered k-tuples (bt, . , bk) of elements bt, . , bk of X. Intwhich collections of objects form sets will not be specified here. Care wil1 beexercised to avoid using any ideas or procedures that may lead to the paradoxes; allthe results can be formalized in the axiomatic set theory of Chapter 4. The term'class' is sometimes used as a synonym for 'set', but it will be avoided here because ithas a different meaning in Chapter 4. If a property P(x) does determine a set, that setis often denoted {xI P(x)}.

. 6 ,/INTRODUCTION.I-particular, X 1 is X itself. If Y and Z are sets, then by Y x Z we denote the setof all ordered pairs {y, z) such that y E Y and z E Z . Y .x Z is called theCartesian product of Y and Z.Ann-place relation (or a relation with n arguments) on a set X is a subsetof X"- that is, a set of ordered n-tuples of elements of X. For example, the3-place relation of betweenness for points on a line is the set of all 3-tuples(x, y, z) such that the point x lies between the points y and z. A 2-placerelation is called a binary relation; for example, the binary relation of fatherhood on the set of human beings is the set of all ordered pairs (x,y) suchthat x andy are human beings and x is the father of y . A 1-place relation onX is a subset of X and is called a property on X .Given a binary relation R on a set X, the domain of R is defined to be theset of ally such that (y, z) E R for some z; the range of R is the set of all zsuch that (y,z) E R for some y; and the .field of R is the union of the domainand range of R. The inverse relation R- 1 of R is the set of all ordered pairs(y,z) such that (z,y) E R. For example, the domain of the relation on theset m of non-negative integerst is m, its range is m- {0}, and the inverse of is . Notation: Very oftenxRy is written instead of (x,y) E R. Thus, in theexample just given, we usually write x y instead of (x, y) E .A binary relation R is said to be reflexive if xRx for all x in the field of R; Ris symmetric if xRy implies yRx; and R is transitive if xRy and yRz imply xRz.Examples: The relation on the set of integers is reflexive and transitivebut not symmetric. The relation 'having at least one parent in common' onthe set of human beings is reflexive and symmetric, but not transitive.A binary relation that is reflexive, symmetric and transitive is called anequivalence relation. Examples of equivalence relations are: (I) the identityrelation lx on a set X, consisting of all pairs (x,x). where x'·E X; (2) given afixed positive integer n, the relation x y (mod n), which holds when x andyare integers and x - y is divisible by n; (3) the congruence relation on the setof triangles in a plane; (4) the similarity relation on the set of triangles in aplane. Given an equivalence relation R whose field is X, and given anyy E X, define [ y] as the set of all z in X such that yRz. Then [y] is called theR- equivalence class of y. Clearly, [uJ [vJ if and only if uRv. Moreover, if[uJ f:- [v], then [uJ n [vJ 0; that is, different R-equivalence classes have noelements in common. Hence, the set X is completely partitioned into theR-equivalence classes. In example (I) above, the equivalence classes are justthe unit sets {x}, where x EX. In example (2), there are n equivalenceclasses, the kth equivalence class (k 0, 1, . , n - 1) being the set of allintegers that leave the remainder k upon division by n.A function f is a binary relation such that (x,y) E f and (x,z) E f implyy z. Thus, for any element x of the domain of a function f, there is aunique y such that (x,y) E f; this unique y is denoted f(x). If x is in thet co will also be referred to as the set of natural numbers.

[ IN T R O D uc T I O N I.:.Jdomain offrthenf(x) is said to be defined. A function/ with domain X andrange y is said to be a function from X onto Y. Iff is a function from X ontoa subset of Z, then f is said to be a function from X into Z. For example. ifthe domain off is the set of integers and f(x) 2x for every integer x, thenf is a function from the set of integers onto the set of even integers, and f isa function from the set of integers into the set of integers. A function whosedomain consists of n-tuples is said to be a function of n arguments. A wtalfunction of n arguments on a set X is a function f whose domain is X". It iscustomary to writef(xt, . ,xn) instead off((xt, . . . ,x")), and we refer tof(x 1, , x 11 ) as the value off for the arguments x1 , . , X 11 A partial functionofn arguments on-a set X is a function whose domain is a subset of xn. Forexample, ordinary division is a partial, but not total, function of two arguments on the set of integers, since division by 0 is not defined. Iff is afunction with domain X and range Y, then the restriction fz off to a set Z isthe function f n (Z x Y). Then fz(u) v if and only if u E Z and f(u) v.The image of the set Z under the function f is the range of fz. The inverseimage of a set W under the function f is the set of all u in the domain offsuch that f(u) E W. We say that f maps X onto (into) Y if X is a subset ofthe domain off and the image of X under f is (a subset of) Y. By ann-placeoperation (or operation with n arguments) on a set X we mean a functionfrom X" into X. For example, ordinary addition is a binary (i.e., 2-place)operation on the set of natural numbers {0, 1,2, · · ·}. But ordinary subtraction is not a binary operation on the set of natural numbers.The composition fog (sometimes denoted fg) of functions f and g is thefunction such that (! o g)(x) f(g(x)); (! o g)(x) is defined if and only ifg(x) is defined and f(g(x)) is defined. For example, if g(x) x2 andf(x) x 1 for every integer x, then (f o g)(x) 1 and (go f)(x) (x 1) 2 . Also, if h(x) -x for every real number x andf(x) Vi for everynon-negative real number x, then (f o h)(x) is defined only for x O, and, forsuchx, (f o h)(x) .J X. A function/ such thatf(x) f(y) impliesx y iscalled a 1-1 (one-one) function. For example, the identity relation Ix on a setX is a 1-1 function, since lx(Y) y for every y EX; the function g withdomain w, such that g(x) 2x for every x E w, is 1-1; but the function hwhose domain is the set of integers and such that h(x) x2 for every integerxis not 1-1, since h( -1) h(1). Notice that a function/ is 1-1 if and only ifits inverse relation f- 1 is a function. If the domain and range of a 1-1function/ are X andY, then/ is said to be a 1 - 1 (one-one) correspondencebetween X and Y; then 1· 1 is a 1-1 correspondence between Y and X, and(f- 1 of) lx and (f o ly. Iff is a 1-1 correspondence between Xand Y and g is a 1-1 correspondence between Y and Z, then g of is a 1-1correspondence between X and Z. Sets X and Y are said to be equinumerous(written X rv Y) if and only if there is a l-1 correspondence between X andY. Clearly, X rv X, X rv Y implies Y rv X, and X rv Y and Y rv Z impliesX rv Z. It is somewhat harder to show that, if X rv Y1 C Y and Y rv X1 C X,.r- )l 7

-8-- ' IN T R O DU C T IO N then X"' Y (see Bernstein's theorem in Chapter 4). If X"' Y, one says thatX and Y have the same cardinal number, and if X is equinumerous with asubset of Y but Y is not equinumerous with a subset of X, one says that thecardinal number of X is smaller than the cardinal number of Y.tA set X is denumerable if it is equinumerous with the set of positiveintegers. A denumerable set is said to have cardinal number No, and any setequinumerous with the set of all subsets of a denumerable set is said to havethe cardinal number 2No (or to have the power of the continuum). A set X isfinite if it is empty or if it is equinumerous with the set { 1, 2, . . , n} of allpositive integers that are less than or equal to some positive integer n. A setthat is not finite is said to be infinite. A set is countable if it is either finite ordenumerable. Clearly, any subset of a denumerable set is countable. Adenumerable sequence is a function s whose domain is the set of positiveintegers; one usually writes sn instead of s(n ). A finite sequence is a functionwhose domain is the empty set or { 1, 2, . , n} for some positive integer n.Let P(x,y , . ,yk) be some relation on the set of non-negative integers. Inparticular, P may involve only the variable x and thus be a property. IfP(O,y1 , . ,yk) holds, and, if, for every n, P(n,y1 , . ,Yk) impliesP(n 1,y1, . ,yk), thenP(x,y1, . ,Yk) is true for all non-negative integers x(principle of mathematicalinduction). In applying this principle, one usuallyproves that, for every n, P(n,y1, . ,yx) implies P(n 1,y1, . ,yk) by assuming P(n,y1 , ,yk) and then deducing P(n 1,y1, . ,yk); in the courseof this deduction, P(n,y1, . ,yk) is called the inductive hypothesis. If therelation P actually involves variables Yl, . . ,yk other than x, then the proof issaid to proceed by induction on x. A similar induction principle holds for theset of integers greater than so

Published by Chapman & Hall, 2-6 Boundary Row, London SEl 8HN, UK Chapman & Hall, 2-6 Boundary Row. London SEI 8HN, UK Chapman & Hall GmbH, Pappelallee 3, 69469 Weinheim, Germany Chapman & Hall USA, 115 Fifth Avenue, New York, NY 10003, USA Chapman & Hall Japan, ITP-Japan, Kyowa Building, 3F, 2-2-1 Hirakawacho, Chiyoda-ku, Tokyo I 02, Japan Chapman & Hall Australia, I 02 Dodds Street, South .