From Sets to Numbers: Climbing Up to the Rationals

When last we left off, I'd used set theory to show how to construct the natural numbers; and then from the natural numbers, I showed how to construct the integers. Now, we can take the next step in building
up the full tower of numbers, showing how if we've got the natural numbers defined in sets, we can define
the rational numbers using sets and our constructed integers.

Before getting in to that, one question that generally strikes people around this level of
construction is that we've got a big stack of constructions here. We've got basic sets, which aren't numbers. We've got special sets, which we're using to represent natural numbers. Then we're using the set-based natural numbers as representations of integers. And now, we're going to start building more things using the integers. So we'll be building a kind of number using a pair of other numbers, which are represented as another kind of number, which is represented with a fairly complicated set construction. So how do we tell all of these things apart?

There are two answers to that: the mathematician's answer, and the computer scientist's answer.

The mathematicians answer is: who cares? At any given point in time, we're talking about one specific construction, and only that construction. So, for example, we're talking about rational numbers,
we can just assume that every value we see is a rational number. The logic by which we discuss things
keeps them separate: we only talk about rational numbers using predicates on rational numbers. We don't use integer predicates when we're working with rationals, etc. We know what we're talking about, and we simply don't break our abstraction by treating a value that is understood to be an integer
as if it were a natural number, even though we may be using a construction where the integer is represented by a rational number.

The computer scientist's answer is that we can define representations to allow us to know what things are. So we can modify representations a bit. Every number, we'll represent as an ordered pair. The first element of that pair is a natural number, which is a type identifier. The second element of that pair is the actual numeric representation that we've discussed before. So we can say that (0,X) means "X" interpreted as a natural number, (1,X) means "X" interpreted as an integer, (2,X) means "X" interpreted as
a rational, and so on. For each new type of number we can construct, we just assign it a new numeric identifier. So every number is a pair of a natural number and something else, which we interpret according to the value of the first element. We can then encode that into the predicates - so natural number addition is only defined for numbers where the first element of the pair is "0"; rational addition is only defined for numbers where the first element is "2". With this, we have a way of guaranteeing the
separation that the mathematicians handwave: we can define things so that it's impossible to use the
integer subtraction operator on natural numbers.

So, back to constructing numbers. We're up to the point of constructing the rational numbers.

How can we define rational numbers? The naive thing is to say:
given any two natural numbers N and M, the pair (N,M) is the rational number N/M. And that is true: N/M is always a natural number. But: that's not a good definition. Because in our understanding of rational numbers, 1/2, 2/4, 3/6, 4/8, 5/10, ... are all the same rational number. But the simple construction of (N,M) will give us an infinite number of rationals, all of which are just different
versions of the same value, 1/2. So that basic set that we can define, the set of (N,M) values that
represent (N/M), we'll call ratios.

What we need to do is group together the equivalent ratios, to give us a single set to represent each
rational number. So we want to create equivalence classes over the set of ratios. So formally, we
can say that we're going to partition the set of ratios into sets where for any set S, two values A/B and
C/D are in S if and only if A/B and C/D are indistinguishable using the operations of rational arithmetic.
Of course, that's sort of circular: we can't define rational arithmetic until we've defined the set of
values it operates on, but we're defining the values in terms of the semantics of the operations. That's
not a problem: we're working in the land of logic. So long as we ensure that the defined operations have
the properties we need to determine when two values are equivalent, we can for now just say that there
is a set of such equivalence classes.

That's not a particularly satisfying solution to some of us. For those of you who, like me, like to see things be just a bit clearer, we can define a set of equivalence classes where for any two values A/B and C/D, they are in the same equivalence class if and only if A×D = B×C using integer arithmetic.

So in terms of set theory, each rational number is actually an equivalence class containing an infinite number of members! To simplify things, we'll describe each rational by a representative: a single canonical member of the rational's equivalence class. The natural choice is the simplest member of the set: that is, the member A/B for whom A and B share no integral divisors except "1".

Then we need to define arithmetic on the rationals. Once again, one of the nice things that we
can do in set theory is define arithmetic operations using logical predicates - we don't need to
describe a procedure.

So, for example, given two rationals Y=A/B and Z=C/D, Y×Z = (A×C)/(B×D). That's pretty close to an operational definition - but it will frequently result in a value which is not the representative of its equivalence class. We won't let that bother us: we know that it is a member of an equivalence class, and we don't need to say how to find the representative, and so there is an equivalence class containing that number, and that equivalence class has a representative. So that's all we need to say about multiplication.

In the case of the rationals, defining addition is actually harder that defining multiplication. But
once again, we have the advantage that we don't need to say precisely how. Given two rationals,
the sum of (A/B)+(C/D) is a rational G/E where E = α×B and E=β×D, and G=(α×A + β×C).

Subtraction and division should be obvious: define the arithmetic and multiplicative inverses; -(A/B) = (-A)/B, and (A/B)^-1=B/A; and then use the definitions of addition and multiplication. You need to do a bit of work to take care of the undefinedness of the multiplicative inverse of 0, but that's not hard.

And there we go. We've got the rationals. Once we have the rationals, we can define the reals two different ways: via Dedekind cuts, and via Cauchy sequences. But that's a topic for another day.