We’ve defined the topological space we call the real number line as the completion of the rational numbers as a uniform space. But we want to be able to do things like arithmetic on it. That is, we want to put the structure of a field on this set. And because we’ve also got the structure of a topological space, we want the field operations to be continuous maps. Then we’ll have a topological field, or a “field object” (analogous to a group object) in the category of topological spaces.
Not only do we want the field operations to be continuous, we want them to agree with those on the rational numbers. And since is dense in (and similarly is dense in ), we will get unique continuous maps to extend our field operations. In fact the uniqueness is the easy part, due to the following general property of dense subsets.
Consider a topological space with a dense subset . Then every point has a sequence with . Now if and are two continuous functions which agree for every point in , then they agree for all points in . Indeed, picking a sequence in converging to we have
So if we can show the existence of a continuous extension of, say, addition of rational numbers to all real numbers, then the extension is unique. In fact, the continuity will be enough to tell us what the extension should look like. Let’s take real numbers and , and sequences of rational numbers and converging to and , respectively. We should have
but how do we know that the limit on the right exists? Well if we can show that the sequence is a Cauchy sequence of rational numbers, then it must converge because is complete.
Given a rational number we must show that there exists a natural number so that for all . But we know that there’s a number so that for , and a number so that for . Then we can choose to be the larger of and and find
So the sequence of sums is Cauchy, and thus converges.
What if we chose different sequences and converging to and ? Then we get another Cauchy sequence of rational numbers. To show that addition of real numbers is well-defined, we need to show that it’s equivalent to the sequence . So given a rational number does there exist an so that for all ? This is almost exactly the same as the above argument that each sequence is Cauchy! As such, I’ll leave it to you.
So we’ve got a continuous function taking two real numbers and giving back another one, and which agrees with addition of rational numbers. Does it define an Abelian group? The uniqueness property for functions defined on dense subspaces will come to our rescue! We can write down two functions from to defined by and . Since agrees with addition on rational numbers, and since triples of rational numbers are dense in the set of triples of real numbers, these two functions agree on a dense subset of their domains, and so must be equal. If we take the from as the additive identity we can also verify that it acts as an identity real number addition. We can also find the negative of a real number by negating each term of a Cauchy sequence converging to , and verify that this behaves as an additive inverse, and we can show this addition to be commutative, all using the same techniques as above. From here we’ll just write for the sum of real numbers and .
What about the multiplication? Again, we’ll want to choose rational sequences and converging to and , and define our function by
so it will be continuous and agree with rational number multiplication. Now we must show that for every rational number there is an so that for all . This will be a bit clearer if we start by noting that for each rational there is an so that for all . In particular, for sufficiently large we have , so the sequence is bounded above by some . Similarly, given we can pick so that for and get an upper bound for all . Then choosing to be the larger of and we will have
for . Now given a rational we can (with a little work) find and so that the expression on the right will be less than , and so the sequence is Cauchy, as desired.
Then, as for addition, it turns out that a similar proof will show that this definition doesn’t depend on the choice of sequences converging to and , so we get a multiplication. Again, we can use the density of the rational numbers to show that it’s associative and commutative, that serves as its unit, and that multiplication distributes over addition. We’ll just write for the product of real numbers and from here on.
To show that is a field we need a multiplicative inverse for each nonzero real number. That is, for each Cauchy sequence of rational numbers that doesn’t converge to , we would like to consider the sequence , but some of the might equal zero and thus throw us off. However, there can only be a finite number of zeroes in the sequence or else would be an accumulation point of the sequence and it would either converge to or fail to be Cauchy. So we can just change each of those to some nonzero rational number without breaking the Cauchy property or changing the real number it converges to. Then another argument similar to that for multiplication shows that this defines a function from the nonzero reals to themselves which acts as a multiplicative inverse.
We use cardinal numbers to count how many elements are in a set. Another thing we think of numbers for is listing elements. That is, we put things in order: first, second, third, and so on.
We identified a cardinal number as an isomorphism class of sets. Ordinal numbers work much the same way, but we use sets equipped with well-orders. Now we don’t allow all the functions between two sets. We just consider the order-preserving functions. If and are two well-ordered sets, a function preserves the order if whenever then . We consider two well-ordered sets to be equivalent if there is an order-preserving bijection between them, and define an ordinal number to be an equivalence class of well-ordered sets under this relation.
If two well-ordered sets are equivalent, they must have the same cardinality. Indeed, we can just forget the order structure and we have a bijection between the two sets. This means that two sets representing the same ordinal number also represent the same cardinal number.
Now let’s just look at finite sets for a moment. If two finite well-ordered sets have the same number of elements, then it turns out they are order-equivalent too. It can be a little tricky to do this straight through, so let’s sort of come at it from the side. We’ll use finite ordinal numbers to give a model of the natural numbers. Since the finite cardinals also give such a model there must be an isomorphism (as models of between finite ordinals and finite cardinals. We’ll see that the isomorphism required by the universal property sends each ordinal to its cardinality. If two ordinals had the same cardinality, then this couldn’t be an isomorphism, so distinct finite ordinals have distinct cardinalities. We’ll also blur the distinction between a well-ordered set and the ordinal number it represents.
So here’s the construction. We start with the empty set, which has exactly one order. It can seem a little weird, but if you just follow the definitions it makes sense: any relation from to itself is a subset of , and there’s only one of them. Reading the definitions carefully, it uses a lot of “for every”, but no “there exists”. Each time we say “for every” it’s trivially true, since there’s nothing that can make it false. Since we never require the existence of an element having a certain property, that’s not a problem. Anyhow, we call the empty set with this (trivial) well-ordering the ordinal . Notice that it has (cardinal number) zero elements.
Now given an ordinal number we define . That is, each new number has the set of all the ordinals that came before it as elements. We need to put a well-ordering on this set, which is just the order in which the ordinals showed up. In fact, we can say this a bit more concisely: if . More explicitly, each ordinal number is an element of every one that comes after it. Also notice that each time we make a new ordinal out of the ones that came before it, we add one new element. The successor function here adds one to the cardinality, meaning it corresponds to the successor in the cardinal number model of . This gives a function from the finite ordinals onto the finite cardinals.
What’s left to check is the universal property. Here we can leverage the cardinal number model and this surjection of finite ordinals onto finite cardinals. I’ll leave the details to you, but if you draw out the natural numbers diagram it should be pretty clear how to how that the universal property is satisfied.
The upshot of all of this is that finite ordinals, like finite cardinals, give another model of the natural numbers, which is why natural numbers seem to show up when we list things.
I’ve said a bunch about natural numbers, but I seem to have ignored what we’re most used to doing with them: counting things! The reason is that we actually don’t use natural numbers to count, we use something called cardinal numbers.
So let’s go back and think about sets and functions. In fact, for the moment let’s just think about finite sets. It seems pretty straightforward to say there are three elements in the set , and that there are also three elements in the set . Step back for a moment, though, and consider why there are the same number of elements in these two sets. Try to do it without counting the numbers first. I’ll wait.
The essential thing that says there’s something the same about these two sets is that there is a bijection between them. For example, I could define a function by , , and . Every element of is hit by exactly one element of , so this is a bijection. Of course, it’s not the only one, but we’ll leave that alone for now.
So now let’s move back to all (possibly infinte) sets and define a relation. Say that sets and are “in bijection” — and write — if there is some bijection . This is an equivalence relation! Any set is in bijection with itself, using the identity function. If is in bijection with then we can use the inverse function to see that . Finally, if and are bijections, then is a bijection.
Any time we have an equivalence relation we can split things up into equivalence classes. Now I define a cardinal number to be an bijection class of sets — every set in the class is in bijection with every other, and with none outside the class.
So what does this have to do with natural numbers? Well, let’s focus in on finite sets again. There’s only one empty set , so let’s call its cardinal number . Now given any finite set with cardinal number — bijection class — , there’s something not in . Pick any such something, call it , and look at the set . If I took any other set in bijection with and anything not in then there is a bijection between and . Just apply the bijection from to on those elements from , and send to . This shows that the bijection class — the cardinal number — doesn’t depend on what choices we made along the way. Since it’s well-defined we can call it the successor .
We look at the set of all bijection classes of finite sets. We’ve got an identified element , and a successor function. In fact, this satisfies the universal property for natural numbers. The set of cardinal numbers of finite sets is (isomorphic to) the set of natural numbers!
And that’s how we count things.
It’s actually not too difficult to see that the integers are the only ordered integral domain with unit whose non-negative elements are well-ordered. So let’s go ahead and do it.
In fact, let’s try to build from the ground up. We can start with the additive identity and the unit . Since we’ve got an ordered ring we have to have , otherwise the multiplication can’t preserve the order.
Now we can also tell that is the smallest element larger than . Let’s say there were some element in between: . Then , and , and so on. The collection of all powers of has no lowest element, so the positive elements can’t be well-ordered in this case.
We can add up an arbitrary number of copies of to get , and we know there’s nothing between and , or else there would have to be something between and . We also get all the negative numbers since we have to have them. Multiplication also comes for free since it has to be defined by the distributive property, and every element around is the sum of a bunch of copies of .
Finally, the fact that we’re looking for an integral domain means we can’t introduce any relations saying two different elements like these are really the same in our ring without making a zero-divisor or collapsing the whole structure. I’ll let you play with that one.
Let’s assume we have two integers (still using the definition by pairs of natural numbers) whose product is zero: . Since each of , , , and is a natural number, the order structure of says that for we must have either or be zero and either or as well. Similarly, either or and either or must be zero. If is not zero then this means both and , making . If is not zero again both and are zero. If both and are zero, then . That is, if the product of two integers is zero, one or the other must be zero.
So the integers are an ordered integral domain with unit whose non-negative elements are well-ordered. It turns out that is the only such ring. Any two rings satisfying all these conditions are isomorphic, justifying our use of “the” integers. In fact, now we can turn around and define the integers to be any of the isomorphic rings satisfying these properties. What we’ve really been showing in all these posts is that if we have any model of the axioms of the natural numbers, we can use it to build a model of the axioms of the integers. Once we know (or assume) that some model of the natural numbers exists we know that a model of the integers exists.
Of course, just like we don’t care which model of the natural numbers we use, we don’t really care which model of the integers we use. All we care about is the axioms: those of an ordered integral domain with unit whose non-negative elements are well-ordered. Everything else we say about the integers will follow from those axioms and not from the incidentals of the pairs-of-natural-numbers construction, just like everything we say about the natural numbers follows from the Peano axioms and not from incidental properties of the Von Neumann or Zermelo or Church numeral models.
As I mentioned before, the primal example of a ring is the integers . So far we’ve got an ordered abelian group structure on the set of (equivalence classes of) pairs of natural numbers. Now we need to add a multiplication that distributes over the addition.
First we’ll figure out how to multiply natural numbers. This is pretty much as we expect. Remember that a natural number is either or for some number . We define
where we’ve already defined addition of natural numbers.
Firstly, this is commutative. This takes a few inductions. First show by induction that commutes with everything, then show by another induction that if commutes with everything then so does . Then by induction, every number commutes with every other. I’ll leave the details to you.
Similarly, we can use a number of inductions to show that this multiplication is associative — — and distributes over addition of natural numbers — . This is extremely tedious and would vastly increase the length of this post without really adding anything to the exposition, so I’ll again leave you the details. I’m reminded of something Jeff Adams said (honest, I’m not trying to throw these references in gratuitously) in his class on the classical groups. He told us to verify that the commutator in an associative algebra satisfies the Jacobi identity because, “It’s long and tedious and doesn’t add much, but I had to do it when I was a grad student, so now you’re grad students and it’s your turn.”
So now these operations — addition and multiplication — of natural numbers make into what some call a “semiring”. I prefer (following John Baez) to call it a “rig”, though: a “ring without negatives”. We use this to build up the ring structure on the integers.
Recall that the integers are (for us) pairs of natural numbers considered as “differences”. We thus define the product
Our life now is vastly easier than it was above: since we know addition and multiplication of natural numbers is commutative, the above expression is manifestly commutative. No work needs to be done! Associativity is also easy: just set up both triple products and expand out, checking that each term is the same by the rig structure of the natural numbers. Similarly, we can check distributivity, that acts as an identity, and that the product of two integers is independent of the representing pair of natural numbers.
Lastly, multiplication by a positive integer preserves order. If and then . Together all these properties make the integers as we’ve defined them into a commutative ordered ring with unit. The proofs of all these things have been incredibly dull (I actually did them all today just to be sure how they worked), but it’s going to get a lot easier soon.
I’m back from Ohio at the College Perk again. The place looks a lot different in daylight. Anyhow, since the last few days have been a little short on the exposition, I thought I’d cover integers.
Okay, we’ve covered that the natural numbers are a commutative ordered monoid. We can add numbers, but we’re used to subtracting numbers too. The problem is that we can’t subtract with just the natural numbers — they aren’t a group. What could we do with ?
Well, let’s just throw it in. In fact, let’s just throw in a new element for every possible subtraction of natural numbers. And since we can get back any natural number by subtracting zero from it, let’s just throw out all the original numbers and just work with these differences. We’re looking at the set of all pairs of natural numbers.
Oops, now we’ve overdone it. Clearly some of these differences should be the same. In particular, should be the same as . If we repeat this relation we can see that should be the same as where we’re using the definition of addition of natural numbers from last time. We can clean this up and write all of these in one fell swoop by defining the equivalence relation: . After checking that this is indeed an equivalence relation, we can pass to the set of equivalence classes and call these the integers .
Now we have to add structure to this set. We define an order on the integers by . The caveat here is that we have to check that if we replace a pair with an equivalent pair we get the same answer. Let’s say , , and . Then
so . The first equality uses the equivalences we assumed and the second uses the inequality. Throughout we’re using the associativity and commutativity. That the first inequality implies the second follows because addition of natural numbers preserves order.
We get an addition as well. We define . It’s important to note here that the addition on the left is how we’re defining the sum of two pairs, and those on the right are additions of natural numbers we already know how to do. Now if and we see
so . Addition of integers doesn’t depend on which representative pairs we use. It’s easy now to check that this addition is associative and commutative, that is an additive identity, that (giving additive inverses), and that addition preserves the order structure. All this together makes into an ordered abelian group.
Now we can relate the integers back to the natural numbers. Since the integers are a group, they’re also a monoid. We can give a monoid homomorphism embedding . Send the natural number to the integer represented by . We call the nonzero integers of this form “positive”, and their inverses of the form “negative”. We can verify that and . Check that every integer has a unique representative pair with on one side or the other, so each is either positive, negative, or zero. From now on we’ll just write for the integer represented by and for the one represented by , as we’re used to.
Now we know what the natural numbers are, but there seems to be a lot less to them than we’re used to. We don’t just take successors of natural numbers — we add them and we put them in order. Today I’ll show that if you have a model of the natural numbers it immediately has the structure of a commutative ordered monoid.
The major tool for working with the natural numbers is “induction”. This uses the property that every natural number is either or the successor of some other natural number, as can be verified from the universal property. Think of it like a ladder: proving a statement to be true for lets you get on the bottom of the ladder. Proving that the truth of a statement is preserved when we take a successor lets you climb up a rung. If you can get on the ladder and you can always climb up a rung, you can climb as far as you want.
First let’s define the order. We say the natural number is less than or equal to the natural number (and write ) if either and are the same number, or if is the successor of some number and . This seems circular, but it’s really not. As we step down from to (maybe many times), eventually either will be equal to and we stop, or becomes and we can’t step down any more. A more colloquial way of putting this relation is that we can build a chain of successors from to .
The relation is reflexive right away. It’s also transitive, since if we have three numbers , , and with and then we have a chain of successors from to and one from to , and we can put them together to get one from to . Finally, the relation is antisymmetric, since if we have two different numbers and with both and , then we can build a chain of successors from back to itself. That would make the successor function fail to be injective which can’t happen. This makes into a partial order. I’ll leave it to you to show that it’s total.
The monoid structure of the natual numbers is a bit easier. Remember that a number is either or for some number . We define the sum of and using this fact: is , and is .
That behaves as an additive identity is clear. We need to show that the sum is associative: given three numbers , , and , we have . If , then . If , then and . So if we have associativity when the third number is we’ll get it for , and we have it for . By induction it’s true no matter what the third number is.
There are two more properties here that you should be able to verify using these same techniques. Addition is commutative — — and addition preserves order — if then .
Notice in particular that I’m not using any properties of how we model the natural numbers. The von Neumann numerals preferred by Bourbaki have the nice property that if as sets. But the Church numerals don’t. The specifics of the order structure really come from the Peano axioms. They shouldn’t depend at all on such accidents as what sort of model you pick, any more than they should depend on whether or not is Julius Cæsar. No matter what model you start with that satisfies the Peano axioms you get the commutative ordered monoid structure for free.
UPDATE: added paragraph explaining the meaning of the commutative diagram more thoroughly.
I think I’ll start in on some more fundamentals. Today: natural numbers.
The natural numbers are such a common thing that everyone has an intuitive idea what they are. Still, we need to write down specific rules in order to work with them. Back at the end of the 19th century Giuseppe Peano did just that. For our purposes I’ll streamline them a bit.
- There is a natural number .
- There is a function from the natural numbers to themselves, called the “successor”.
- If and are natural numbers, then implies .
- If is a natural number, then .
- For every set , if is in and the successor of each natural number in is also in , then every natural number is in .
This is the most common list to be found in most texts. It gives a list of basic properties for manipulating logical statements about the natural numbers. However, I find that this list tends to obscure the real meaning and structure of the natural number system. Here’s what the axioms really mean.
The natural numbers form a set . The first axiom picks out a special element of , called . Now, think of a set containing exactly one element: . A function from this set to any other set picks out an element of that set: the image of . So the first axiom really says that there is a function .
The second axiom plainly states that there is a function . The third axiom says that this function is injective: any two distinct natural numbers have distinct successors. The fourth says that the image of the successor function doesn’t contain the image of the zero function.
The fifth axiom is where things get really interesting. So far we have a diagram . What the fifth axiom is really saying is that this is the universal such diagram of sets! That is, we have the following diagram:
with the property that if is any set and and are any functions as in the diagram, then there exists a unique function making the whole diagram commute. In fact, at this point the third and fourth Peano axioms are extraneous, since they follow from the universal property!
Remember, all a commutative diagram means is that if you have any two paths between vertices of the diagram, they give the same function. The triangle on the left here says that . That is, since has a special element, has to send to that element. The square on the right says that . If I know where sends one natural number and I know the function , then I know where sends the successor of . The universal property means just that has nothing in it but what we need: and all its successors, and is not the successor of any of them.
Of course, by the exact same sort of argument I gave when discussing direct products of groups, once we have a universal property any two things satisfying that property are isomorphic. This is what justifies talking about “the” natural number system, since any two models of the system are essentially the same.
This is a point that bears stressing: there is no one correct version of the natural numbers. Anything satisfying the axioms will do, and they all behave the same way.
The Bourbaki school like to say that the natural numbers are the following system: The empty set is zero, and the successor function is . But this just provides one model of the system. We could just as well replace the successor function by , and get another perfectly valid model of the natural numbers.
In the video of Serre that I linked to, he asks at one point “What is the cardinality of 3?” This betrays his membership in Bourbaki, since he clearly is thinking of 3 as some particular set or another, when it’s really just a slot in the system of natural numbers. The Peano axioms don’t talk about “cardinality”, and we can’t build a definition of such a purely set-theoretical concept out of what properties it does discuss. The answer to the question is “無!” (“mu”). The Bourbaki definition doesn’t define the natural numbers, but merely shows that within the confines of set theory one can construct a model satisfying the given abstract axioms.
This is how mathematics works at its core. We define a system, including basic pieces and relations between them. We can use those pieces to build more complicated relations, but we can only make sense of those properties inside the system itself. We can build models of systems inside of other systems, but we should never confuse the model with the structure — the map is not the territory.
This point of view seems to fetishize abstraction at first, but it’s really very freeing. I don’t need to know — or even care — what particular set and functions define a given model of the natural numbers. Anything I can say about one model works for any other model. As long as I use the properties as I’ve defined them everything will work out fine, and whether I use Bourbaki’s model or not.