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.

0 thoughts on “From Sets to Numbers: Climbing Up to the Rationals

  1. Charles Tye

    Nice post. How about a follow-up defining an ordering and proving the existence of a rational line (i.e. countable, totally ordered with every open interval non-empty)?
    Also, minor typo: “And that is true: N/M is always a natural number.” I think you meant rational.

    Reply
  2. vhurtig

    Very nice. There seem to be some typos in your definition of multiplication though. You should have E=BxD and G =(AxD+BxC) I believe.

    Reply
  3. John Armstrong

    The mathematician’s more considered answer is, “we can show that the structure is uniquely specified (up to isomorphism) by the axioms we’ve chosen, and so it doesn’t matter how we build them once we know that they can be built.”
    I said this when I presented the natural numbers with the Peano axioms, and again when I characterized the integers as the unique ordered integral domain with unit whose positive cone is well-ordered. I left it tacit when I moved up to rational numbers as the field of fractions of the integers, and I’m about to say it again as I finally move on into the real numbers as the uniform completion of the rationals.
    What’s sitting behind all of these constructions is the following verbiage: we can axiomatically characterize each of these structures so that any two models are isomorphic. Then once we have a model — any model — of the structure, we can use it without reference to how the model was built and speak solely in terms of the structural features specified in the axioms. The only point of these constructions is to say, “If we have a model of set theory, we get a model of the natural numbers”; “If we have a model for the natural numbers, we get a model of the integers”; “If we have a model for the integers, we get a model for the rational numbers”; and so on.
    The point is, you’ve got a very silly mathematician on your hands, who’s going along with you in confounding things like the order relation that the axioms of the rational numbers specifies and its instantiation in a given model of the rational numbers. Of course the instantiation in a given model of the rational number order is different from the instantiation in a model of the integer order. Not only aren’t they the same model, but they’re models of different things! It’s like saying the crossbeams in a matchstick version of the Taj Mahal look different than the crossbeams in an architectural mock-up of a planned nursing home.
    And even when modelling the same things, nobody cares which model you use. The order relation on the von Neumann numerals is set-containment, but that doesn’t mean that the order relation on the natural numbers is set-containment. It just means that it can be modeled by set containment, when we restrict to particular sets which we agree to interpret in a particular way. The order relation on the Church numerals looks nothing at all like set-containment, and the order relation on the lambda-calculus model of the natural numbers looks even more different. Still, they all model the same thing.
    To confuse the abstraction with the model is simply, well, irrational.

    Reply
  4. Antendren

    I’ll point out that there’s actually a little more to do to define the operations. What you’ve done is define operations on pairs (A,B). To get from this to operations on the equivalence classes, you need to check that they remain well defined: If (A,B) is equivalent to (A’,B’) and (C,D) is equivalent to (C’,D’), then (A,B) + (C,D) is equivalent to (A’,B’) + (C’,D’), and similarly for the other operations. It’s not hard to check, but it’s an important detail.

    Reply
  5. Paul Carpenter

    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”.

    I don’t like this, obviously it’s best to have the reprentative as the fraction in least-terms, but I think that can be defined without having to come up with a definition of common factors. At least, I think it can…

    Reply
  6. Buddha Buck

    I may have mentioned this before, but John Conway (in ONAG, I believe), recommends a different path from naturals to reals. He mentions that the conventional path is from N->Z->Q->R, which is the path you seem to be following. His complaint about this method is the extreme amount of special casing needed to deal with negative numbers and zero, especially in relation to multiplication and division.
    He suggests, instead, the path Z+->Q+->R+->R. This path excludes negative numbers until the final step, which simplifies a number of proofs. It also alleviates the need (which I think you glossed over) to have Q be defined as equivalence classes over Z X Z/0. Q+, on the otherhand can be defined using Z+ X Z+, and all of Q+ will have a multiplicative inverse, rather than just those in Q/0.

    Reply
  7. Paul Carpenter

    Sorry, stupid HTML parser made my last post make no sense.
    a/b is in least terms iff b>0 and for all c/d s.t. a/b=c/d, b=<d

    Reply
  8. Token

    Since everyone here seems to like to nitpick, I may as well join in. When defining the rationals, it should be an ordered pair (A,B) where A and B are integers and B is non-zero (or positive, if you want).

    Reply
  9. Doug Spoonwood

    [Because in our understanding of rational numbers, 1/2, 2/4, 3/6, 4/8, 5/10, … are all the same rational number.]
    [So in terms of set theory, each rational number is actually an equivalence class containing an infinite number of members!]
    Well, suppose we had a finite set call it
    z={a1/b1, a2/b2 … an/bn} for rational numbers, ordered such that a1

    Reply
  10. Andy

    Just a typo alert:
    “And that is true: N/M is always a natural number. But: that’s not a good definition”
    s/natural/rational
    (and if you feel like being pedantic, then you could prevent division by zero there too šŸ™‚

    Reply
  11. Slawekk

    It is worth mentioning that there is a nice construction of real numbers that avoids the intermediate step of building rational numbers and defines real numbers directly from the group of integers. This is described on the Wikipedia page on the construction of real numbers.

    Reply
  12. Doug

    Hi Mark,
    Terence Tao [2006 Fields Medal for “for his contributions to partial differential equations, combinatorics, harmonic analysis and additive number theory”] has a very interesting math blog.
    His most recent post ‘The Hahn-Banach theorem, Menger’s theorem, and Helly’s theorem’ relates to optimization and the duality theorem in linear programming.
    http://terrytao.wordpress.com/

    Reply

Leave a Reply to Paul Carpenter Cancel reply