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.
A well-ordering on a set is a special kind of total order: one in which every non-empty subset contains a least element.
The two best examples of ordered sets we have handy are the natural numbers and the integers . For now, forget all the other algebraic structure we’ve talked about. The natural numbers are well-ordered, but the integers are not.
Seeing that the integers are not well-ordered is pretty easy: just take the subset of negative integers. There’s no negative number that’s less than all the others. Seeing that the natural numbers are well-ordered is a little more difficult. Given a set , either is in or it isn’t. If it is, it’s the least element — nothing could be less than it. If it isn’t, then we move to . As we keep going, either we eventually hit an element of or we don’t. If we do, the first one is the least element of . If not, then by induction the set of natural numbers not in is all of them, and must be empty!
It turns out that in the standard logical framework I’m using, any set can be equipped with a well-order. For instance, we could well-order the integers by saying if either or and . We can list the integers in this order: . The problem is that this doesn’t mesh with the algebraic structure very well.
Now as we’ll see when we get to them, the natural order on the real numbers is even further from being well-ordered, and there doesn’t seem to be any sensible way to well-order them. Still, we’ll see eventually that though the well-ordering principle is “plainly false” — very counterintuitive — it turns out to be logically equivalent to another tool that’s so incredibly useful we really should accept this unexpected fact.
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.
As a bonus today, I want to define a few more kinds of relations.
A preorder is a relation on a set which is reflexive and transitive. We often write a general preorder as and say that precedes or that succeeds . A set equipped with a preorder is called a preordered set. If we also have that for any two elements and there is some element (possibly the same as or ) that succeeds both of them we call the structure a directed set.
A partial order is a preorder which is also antisymmetric: the only way to have both and is for and to be the same element. We call a set with a partial order a partially-ordered set or a “poset”.
Any set gives a partial order on its set of subsets, given by inclusion: if and are subsets of a set , then precedes if is contained in . This has the further nice property that it has a top element, itself, that succeeds every element. It also has a bottom element, the empty subset, that precedes everything. The same sort of construction applies to give the poset of subgroups of any given group. These kinds of partially-ordered sets are very important in logic and set theory, and they’ll come up in more detail later.
Finally, a partial order where for any two elements and we either have or is called a total order. Total orders show up over and over, and they’re nice things to have around. I must admit, though, that as far as I’m concerned they’re pretty boring in and of themselves.
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.
Sooner or later I’ll have to use relations, so I may as well get the basics nailed down now.
A relation between two sets and is just a subset of their Cartesian product . That is, it’s a collection of pairs . Often we’ll write when is in the relation.
A function is a special kind of relation where each element of shows up on the left of exactly one pair in . In this case if is in the relation we write . Remember from our discussion of functions that I was saying every element of has to show up both at least once and at most once (that is, exactly once). A surjection is when every element of shows up on the right side of a pair in at least once, and an injection is when each element in shows up at most once.
Also interesting are the following properties a relation between a set and itself might have:
- A relation is “reflexive” if for every in .
- A relation is “irreflexive” if is never true.
- A relation is “symmetric” if whenever then also .
- A relation is “antisymmetric” if whenever and then and are the same.
- A relation is “asymmetric” if whenever then is not true.
- A relation is “transitive” if whenever and then also .
A very important kind of relation is an “equivalence relation”, which is reflexive, symmetric, and transitive. We’ve already used these a bunch of times, actually. When a group acts on a set , we can define a relation by saying whenever there is a group element so that . Since the identity of sends every element of to itself, this is reflexive. If there is a so that , then , so this is symmetric. Finally, if we have and so that and , then , so the relation is transitive.
When we have an equivalence relation on a set , we can break up into its “equivalence classes”. Any two elements and of are in the same equivalence class if and only if . We write the set of equivalence classes as . For group actions, these are the orbits of .
Show for yourself that in our discussion of cosets that there’s an equivalence relation going on, and that the cosets of in are the equivalence classes of elements of under this relation.
I’m soon going to need to really use the notion of a function, and I want to make sure that I lay the groundwork properly. This is also a good place to mention a few things about sets.
For most of my purposes, a naïve concept of sets will suffice. A set is a collection of objects, called the elements of the set. In formal treatments of set theory, the elements are themselves sets. In fact, everything in sight is “really” a set. This sort of foundationalist approach, though, tends to obscure the real structure of mathematical theories, so I’ll avoid talking about formal set theory unless it’s absolutely necessary. What we’ll need from set theory are a few operations on sets.
- Specification: If we have a set and some statement that can be unambiguously determined true or false for each element of , there is a set containing exactly those elements of so that is true. We write this set as , read “the set of those elements of such that is true of “.
- Intersection: This is actually a special case of specification. For our statement we use “ is an element of the set “. This gives us the set of all elements in both and , and we write this set . In practice, we will allow intersections not just of two sets, but of any number of sets — even infinitely many.
- Union: For any two sets and there is a set containing any element in either or . We write this set as . As for intersection, we will allow unions of any collection of sets.
- Cartesian product: For any two sets and there is the set of ordered pairs , where is an element of and is an element of . We write this set . Again, we allow Cartesian products of any number of sets, though only a finite number at a time here.
- Empty set: While not a “construction”, per se, the empty set is something important to pay attention to. This is, predictably enough, the set containing no elements at all. We write it .
- Subset: If every element of is also an element of we say is a subset of — written . Note that specification gives us a subset of .
- Power set: For any set we have the set of all subsets of. We write this set .
I may have forgotten some, but I will mention those (and add them here) if I realize it later.
Anyhow, a function is basically a rule that assigns to each element of one set an element of another. Formally, we need to specify a “domain” set and a “codomain” set (the codomain is often called the “range”). For every element of the domain, there is a uniquely specified element in the codomain. Often there is some sort of calculational method to determine the value of the function, but a simple lookup table will suffice. We write to specify a function with domain and codomain .
There are a few properties a function may have that are worth mentioning here. Every function assigns a value in its codomain to every element in its domain. If every element in the codomain is the value of the function at some element of the domain we say that the function is “onto” or a “surjection”. Every function assigns only one value to every element in the domain. If no element in the codomain is the value of the function at more than one element of the domain, we say that the function is “one-to-one” or an “injection”. If both of these properties hold, we say the function is a “bijection”.
Let’s consider four sets: , , , . We use these to define a number of examples of functions.
- , with , , and . This function is surjective, but not injective.
- , with , , . This function is injective, but not surjective.
- , with , , . This function is neither injective nor surjective.
- , with , , . This function is bijective.