# Practical Foundations of Mathematics

## 2.1  Constructing the Number Systems

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

 "e > 0.\$N."n,m > N.|\argan-\argam| < e.
If "e > 0.\$N."n,m > N.|\argan-\argbm| < e then the sequences (\argan) and (\argbn) are equivalent, and \realnoC consists of the equivalence classes.

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.

(a)
A point in projective n-space is a line through the origin in Rn+1, ie an equivalence class of Rn+1\{0} with respect to the relation that (x0,¼,xn) ~ (y0,¼,yn) if for some k ¹ 0, x0 = k y0, ..., xn = k yn. The (n-1)-plane at infinity consists of those classes for which the co-ordinate x0 is zero: no infinite co-ordinates are needed.

(b)
As 6 = (1+[Ö(-5)] )(1-[Ö(-5)] ) = 3·2, unique factorisation fails in R = Z[[Ö(-5)] ]. To remedy this, Ernst Kummer (1846) introduced ideal numbers, which are subsets I Ì R closed under addition and under multiplication by elements of R. An ordinary number r Î R is represented by its set of multiples, and in general we define
 (\argr1,¼,\argrn) = {\arga1\argr1+·· ·+\argan\argrn|\argai Î R}.
The product IJ is the ideal generated by {i j|i Î I,j Î J} and then the prime factorisation of 6 is (1+[Ö(-5)],2)2(1+ [Ö(-5)],3)(1-[Ö(-5)],3).

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

 \$!y:Y.a,y Î f,        ie  a,y Î f Û y = f(a),
so a,y Î f is a description (Definition  1.2.10) of the result, called f(a). But in order to understand function-types properly, the evaluation operation ev:(f,a)® f(a) must be studied in its own right. []

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

 "x, y.x ~ yÞ f(x) = f(y);
then for any U Ì X that satisfies q[U], the formula
 \$!z.\$x.x Î UÙz = f(x)
provides a description of a value z Î Q, which we call p(U),

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

(a)
the singleton, {a}, is characterised by the predicate x = a in x,

(b)
the union, UÈV, is characterised by f[x] Úy[x],

(c)
in particular {a,b} = {a}È{b} = {x |x = aÚx = b},

(d)
the intersection, UÇV, is characterised by f[x]Ùy[x], and

(e)
the difference, U\V, by f[x]Ù \lnot y[x].

(f)
Given excluded middle, X\V is the complement of V in X:

 (X\V)ÇV = Æ       (X\V)ÈV = X. []

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,x2x1 Î 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

 p(n0(a)) = f(a)        p(n1(b)) = g(b),
and we write [f,g] for p. []

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.

EXAMPLES 2.1.8

(a)
On any set X we have the constantly true and false predicates, T and ^, which characterise X Ì X and the empty set Æ Ì X; any other subset lies between these. In  particular, Æ º {x:1|^}.

(b)
The only subset of Æ is itself, because the true and false predicates coincide (Exercise 2.29). Hence P(Æ) has exactly one element, Æ. We shall write 1 = {*} for the singleton, since it is clearer to make its element anonymous than to insist on 1 = P(Æ) = {Æ} . []

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

(a)
there is a unique relation Æ\leftharpoondown \rightharpoonup X, namely the empty or constantly false one, and this is a function Æ® X;

(b)
any function X® Æ is bijective;

(c)
for any sets X and Y, there is a unique bijection
 {x: X|^} º {y: Y|^},
so we are justified in using Æ for the smallest subset of any set;

(d)
total functions 1 º {*} ® X are of the form *® a, so correspond bijectively to elements  a Î X;

(e)
there is a unique total function X® 1 º {*} , namely x® *. []

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.