The growth of algebra from the sixteenth to the nineteenth century made the idea of number more and more general, apparently demanding ever greater acts of faith in the existence and meaningfulness of irrational, negative and complex quantities. Then in 1833 William Rowan Hamilton showed how complex numbers (C) could be defined as pairs of real numbers, and the arithmetic operations by formulae involving these pairs. Ten years later he discovered a similar system of rules with four real components, the quaternions.
The rationals (Q) may also be represented in the familiar way as pairs of integers (Z), although now there are many pairs representing each rational (Example 1.2.1), and the positive and negative integers may be obtained from the natural numbers (N) in a similar way. This leaves the construction of the reals (R) from the rationals.
The real numbers The course of the foundations of mathematics in the twentieth century was set on 24 November 1858, when Richard Dedekind first had to teach the elements of the differential calculus, and felt more keenly than before the lack of a really scientific foundation for analysis. In discussing the approach of a variable magnitude to a fixed limiting value, he had to resort to geometric evidences. Observing how a point divides a line into two parts, he was led to what he saw as the essence of continuity:
REMARK 2.1.1 If all points of the straight line fall into two classes such that every point of the first class lies to the left of every point of the second class, then there exists one and only one point which produces this severing of the straight line into two portions.
In [Ded72] he used these Dedekind cuts of the set of rational numbers to define real numbers, and went on to develop their arithmetic and analysis. By way of an example, he proved ``for the first time'' that Ö2xÖ3 = Ö6. There is one slight difficulty, in that each rational number gives rise to two cuts, depending on whether it is itself assigned to the lower or upper part - we shall say neither.
A real number is then a pair of subsets of Q, and, from the universe of all pairs of subsets (L,U Ì Q), the collection \realnoD of (Dedekind) reals is the subset consisting of those satisfying a certain property, namely
"x.\lnot (x Î LÙx Î U) Ù "x, y.y Î LÙx < yÞ x Î L Ù"x, y.y Î UÙx > yÞ x Î U Ù"x.x Î UÞ $y.y Î U Ùy < x Ù"x.x Î LÞ $y.y Î LÙy > x Ù" e > 0.$x, y. x Î LÙy Î UÙy-x < e .
To do this we have used the cartesian product (collecting all pairs), the powerset (collecting all subsets), and comprehension (forming a subset by selecting those elements which satisfy a particular property, for example the circle S1 Ì R2 considered as the set of solutions of x2+y2 = 1).
Georg Cantor (1872) gave another construction of R based on the idea of the convergence of sequences, such as the decimal expansion of p. First we must explain how a sequence may be abstractly convergent without having a limit point which is known in advance.
DEFINITION 2.1.2 A sequence in a set X is a function \arga(-):N® X. This is called a Cauchy sequence (in X = Q or R) if
|
The Dedekind and Cantor constructions, which are equivalent in classical logic, are developed and related in Exercises 2.2- 2.11.
EXAMPLES 2.1.3 Other familiar systems represented by subsets.
|
Functions and equivalence classes The Cantor construction of the reals adds two further operations, but these may themselves be defined in terms of the product, powerset and comprehension. The idea in both cases is to internalise the definitions of equivalence relation and function from Sections 1.2 and 1.3 respectively. The connection between the exponential and the set of functions, defined using input-output pairs, was also first made by Cantor (but for cardinal arithmetic, in 1895).
EXAMPLE 2.1.4 For sets X and Y, the function-type is constructed as YX = {f:P(Xx Y)|y[f]}, where y[f] is ( cf Definition 1.3.1)
"x."y1, y2.x,y1 Î fÙx,y2 Î fÞ y1 = y2 Ù"x.$y.x,y Î f.
Any actual function p:X® Y is represented by {x,p(x)|x Î X}. Conversely, given f Î YX and a:X, from y[f] we have
|
EXAMPLE 2.1.5 Let ~ be an equivalence relation (Definition 1.2.3) on a set X. Then the quotient is the set X/ ~ = {U Ì X|q[U]} of equivalence classes, where q[U] is
"x, y.x Î UÙx ~ yÞ y Î U Ù"x, y.x Î UÙy Î UÞ x ~ y Ù$x.x Î U.
For x Î X, we write [x] = {y|x ~ y} Î X/ ~ . The union of these subsets is X, they are inhabited, and if any two them overlap at all then they coincide (classically, we would say that they are non-empty, and either disjoint or equal); such a family of subsets is called a partition.
Let f:X® Q be a function such that
|
|
omitted diagram environment
thereby defining a function p:X/ ~ ® Q. []
Unions and intersections Having shown that the more powerful operations can be reduced to the product, powerset and comprehension, we complete the picture by treating the simpler ones in the same way. (See also Proposition 2.8.6 for the logical connectives.)
EXAMPLE 2.1.6 Let a be an element of a set X, and U,V Ì X be the subsets characterised by predicates f[x] and y[x] respectively. Then
|
The operations we have just described form subsets of an ambient set X. The disjoint union, like the product, function-type and quotient, forms a new set. It can also be constructed using products, powersets and comprehension, though the following construction may be unfamiliar as it is not the same as that used in set theory. (The common set-theoretic construction is not valid in the axiomatisation of the next section.)
EXAMPLE 2.1.7 If X and Y are sets then their sum or disjoint union is X+Y = {U,V:P(X)xP(Y)| f[U,V]}, where f[U,V] says that U and V have exactly one element altogether, ie
[($x.x Î U)Ú($y.y Î V)] Ù"x1,x2. x1 Î UÙx2 Î UÞ x1 = x2 Ù"y1,y2. y1 Î VÙy2 Î V Þ y1 = y2 Ù"x,y. \lnot (x Î UÙy Î V).
For a Î X or b Î Y we write n0(a) = {a},Æ and n1(b) = Æ,{b}.
Conversely, Exercise 2.13 shows that every element of X+Y is of one or other of these forms, but not both - yet another description. (Exercise 1.11 was based on a similar idea.) Case analysis may be used on such a value: for any two functions f:X® Q and g:Y® Q, there is a unique function p:X+Y® Q such that
|
Singletons and the empty set As with the union and disjoint union, there is a conceptual difference between the singleton as a free-standing set (which we call 1) and the singleton subset consisting of a particular element of a given set. Up to interchangeability (unique isomorphism) there is only one singleton set, and only one empty set. The two notions of singleton are related by the correspondence between elements of any set X (and so its singleton subsets) and functions 1® X.
The symbol Æ appears to be a 1950s variant of zero, having nothing to do with Latin O, Greek f or Danish/Norwegian Ø .
The roles of Æ and 1 are summed up by
PROPOSITION 2.1.9 Let X be any set. Then
omitted array environment
|
There is one further major construction of this kind which we shall do, namely that of the free algebra for a free theory (Proposition 6.1.11), but now we turn to the axiomatisation of these operations.