Fundamentals « The Unapologetic Mathematician

Archimedean Fields

Whether we use Dedekind cuts or Cauchy sequences to construct the ordered field of real numbers $\mathbb{R}$ (and it doesn’t matter which), we are taking the ordered field of rational numbers and enlarging it to be “complete” in some sense or another. But we also aren’t making it too much bigger. The universality property we got from completing the uniform structure already gives evidence of that, but there’s another property which we can show is true of $\mathbb{R}$ , and which shows that the real numbers aren’t too unwieldy.

In The Sand Reckoner, the ancient Greek mathematician Archimedes once set about the problem of should the number of grains of sand in existence to be finite. He does this by determining a (very weak) upper bound: the number of grains of sand it would take to fill up the entire universe, as he understood the latter term. He writes:

There are some … who think that the number of the sand is infinite in multitude; and I mean by the sand not only that which exists about Syracuse and the rest of Sicily but also that which is found in every region whether inhabited or uninhabited. Again there are some who, without regarding it as infinite, yet think that no number has been named which is great enough to exceed its multitude. And it is clear that they who hold this view, if they imagined a mass made up of sand in other respects as large as the mass of the earth filled up to a height equal to that of the highest of the mountains, would be many times further still from recognizing that any number could be expressed which exceeded the multitude of the sand so taken. But I will try to show you by means of geometrical proofs, which you will be able to follow, that, of the numbers named by me … some exceed not only the number of the mass of sand equal in magnitude to the earth filled up in the way described, but also that of a mass equal in magnitude to the universe

The deep fact here is a fundamental realization about numbers: the set of natural numbers has no upper bound in the real number system. That is, no matter how huge a real number we pick there’s always a natural number bigger than it. Equivalently, given any positive real number $x$ — even as small as the volume of a grain of sand — and another positive real number $y$ — even as large as the volume of (the ancient Greek conception of) the universe — there’s some natural number $n$ so that $nx\geq y$ . When this happens in a given ordered field we say that the field is “Archimedean”.

So let’s show that $\mathbb{R}$ is Archimedean. If there were positive real numbers $x$ and $y$ so that $nx\leq y$ for all natural numbers $n$ , then $y$ would be an upper bound for the set of $nx$ . Then Dedekind completeness gives us a least upper bound $\sup\{nx\}$ , and we can just take $y$ to be this least upper bound. Now $nx\leq y$ , and also $(n+1)x\leq y$ , and so $nx\leq y-x$ . That is, $y-x$ is another upper bound for the set of multiples of $x$ . But since $x$ was chosen to be positive we see that $y-x<y$ , contradicting the assumption that $y$ was the least such upper bound. So such a pair of real numbers can’t exist.

In particular, we can take a positive real number $x$ and consider the set of natural numbers $n$ which are larger than it. Since the natural numbers are well-ordered, there is a least such number, and it can’t be ${0}$ because we assume $x>0$ . Subtracting one from this number will then give the largest natural number that is still below $x$ in the real number order, and we denote this number by $\lfloor x\rfloor$ . We can thus write any positive number uniquely as the sum $\lfloor x\rfloor+r$ of a natural number and some remainder with $0\leq r<1$ .

It turns out that the real numbers are actually the largest Archimedean field. That is, if $\mathbb{F}$ is any ordered field satisfying the Archimedean property, there will be an monomorphism of ordered fields $\mathbb{F}\rightarrow\mathbb{R}$ , making (the image of) $\mathbb{F}$ a subfield of $\mathbb{R}$ . I won’t prove this here, but I will note one thing about the meaning of this result: the Archimedean property essentially limits the size of an ordered field. That is, an ordered field can’t get too big without breaking this property. Dually, an ordered field can’t get too small without breaking Dedekind completeness or uniform completeness. Completeness pulls the field one way, while the Archimedean property pulls the other way, and the two reach a sort of equilibrium in the real numbers, living both at the top of one world and the bottom of the other.

December 7, 2007 Posted by John Armstrong | Fundamentals, Numbers | 7 Comments

Cuts and Sequences are Equivalent

Sorry to not get this posted until so late, but the end of the semester has been a bit hectic.

We’ve used Dedekind cuts to “complete” the order on the rational numbers — to make sure that every nonempty set of numbers with an upper bound has a least upper bound. We’ve also used Cauchy sequences to “complete” the uniform structure on the rational numbers — to make sure that every Cauchy sequence converges. But do we actually get the same thing in each case?

If we take a real number $x$ represented by a Cauchy sequence $x_n$ it’s easy to come up with a cut. Given a rational number $q$ we use the constant sequence $q_n=q$ and compare it to $x_n$ . If $x_n-q_n$ is eventually nonnegative then $q$ is less than x$, and should go into the left set $X_L$ . On the other hand, if it’s eventually nonpositive then $q$ is greater than $x$ and should go into the right set $X_R$ . It’s straightforward to show that this function from $\mathbb{R}$ to the set of cuts preserves the order.

Now let’s start with the cut $(X_L,X_R)$ and write down a Cauchy sequence. Pick some $x_L\in X_L$ and $x_R\in X_R$ , and construct the sequence as follows. First write down $x_0=x_L$ and $x_1=x_R$ . Now set $x_2=\frac{x_L+x_R}{2}$ . This value will either be in $X_L$ or it won’t. If it is, replace $x_L$ by $x_2$ , and otherwise replace $x_R$ by $x_2$ . Then define $x_3$ as the midpoint between our two left and right points, and again replace either the left or the right point. Keep going, and we see that all future numbers in the sequence are closer to each other than the current $x_L$ and $x_R$ are to each other. And these two always keep moving closer and closer to each other, halving their distance at each step. So the sequence has to be Cauchy. If we picked a different $x_L$ and $x_R$ to start with, we’d get an equivalent sequence. I’ll leave this to you to show.

Notice here that the points in the sequence that lie in $X_L$ are moving steadily upwards towards the cut, and those in $X_R$ are moving steadily downwards towards it. Eventually, the sequence will rise above any point in $X_L$ and fall below any point in $X_R$ , and so if we take this sequence and build a cut from it we will get back the exact same cut we started with. Also, if we build a cut from a Cauchy sequence, and then a sequence from it, we get back an equivalent sequence. Thus we have set up a bijection between the set of cuts and the set of equivalence classes of Cauchy sequences, and we’ve already seen that it preserves the order structure.

Now let’s look at the map from sequences to cuts and verify that it preserves addition and multiplication of positive numbers. This will make the map into an isomorphism of ordered fields, and so both constructions are describing essentially the same thing. So if we have Cauchy sequences $x_n$ and $y_n$ , which give right sets $X_R$ and $Y_R$ of rational numbers, then what’s the right set of the sequence $x_n+y_n$ ? It’s the set of rational numbers $q$ so that $x_n+y_n-q$ is eventually nonnegative. But any such $q$ can be broken up as $q=q_x+q_y$ , where $x_n-q_x$ and $y_n-q_y$ are both eventually nonnegative. That is, $(X+Y)_R$ is the set of sums of elements of $X_R$ and $Y_R$ , and so addition is preserved. The proof for multiplication is essentially the same.

So both methods of extending the real numbers give us essentially the same ordered field, which is thus both complete as a uniform space and Dedekind complete.

December 7, 2007 Posted by John Armstrong | Fundamentals, Numbers | 1 Comment

Dedekind Completion

There’s another sense in which the rational numbers are lacking and the real numbers fix them up. This one is completely about the order structure on $\mathbb{Q}$ , and will lead to another construction of the real numbers.

Okay, so what’s wrong with the rational numbers now? In any partial order we can consider least upper or greatest lower bounds. That is, given a nonempty set of rational numbers $S$ the least upper bound or “supremum” $\sup S$ is a rational number so that $\sup S\geq s$ for all $s\in S$ — it’s an upper bound — and if $b$ is any upper bound then $\sup S\leq b$ . Similarly the “infimum” $\inf S$ is the greatest lower bound — a lower bound that’s greater than all the other lower bounds.

There’s just one problem: there might not be a supremum of a given set. Even if the set is bounded above, there may be no least upper bound. For instance, the set of all rational numbers $r$ so that $r^2\leq 2$ is bounded above, since $2$ is an example of an upper bound, and $\frac{3}{2}$ is another. But no matter what upper bound we have in hand, we can always find a lower number which is still an upper bound for this set. In fact, the upper bound should be $\sqrt{2}$ , but this isn’t a rational number!

Now we define an ordered field to be “Dedekind complete” if every nonempty set $S$ with an upper bound has a least upper bound $\sup S$ . Considering the set consisting of the negatives of elements of $S$ , every nonempty set with a lower bound will have a least lower bound. The flaw in the rational numbers is that they are not Dedekind complete.

So, in order to complete them, we will use the method of “Dedekind cuts”. Given a nonempty set $S$ with any upper bounds at all, the collection of all the upper bounds forms another set $S'$ , and any element of $S$ gives a lower bound for $S'$ . We then have the collection of all lower bounds of $S'$ , which we call $S''$ . Every rational number will be in either $S'$ or $S''$ . Given a rational number $r$ if there is an $s\in S$ with $s\geq r$ then $r$ is a lower bound for $S'$ , and is thus in $S''$ . If not, then $r$ is an upper bound for $S$ and is thus in $S'$ . However, one number may be in both $S'$ and $S''$ . If $S$ has a rational supremum then it is in both $S'$ and $S''$ . There can be no more overlap.

So we’ve come up with a way of cutting the rational numbers into a pair of sets $(X_L,X_R)$ — the “left set” and “right set” of the “cut” $X$ — with $x_L\geq x_R$ for every $x_L\in X_L$ and $x_R\in x_R$ . We define a new total order on the set of cuts by $(X_L,X_R)\leq(Y_L,Y_R)$ if $X_L\subseteq Y_L$ . Every rational number corresponds to one of the cuts which contains a one-point overlap at that rational number, and clearly this inclusion preserves the order on the rational numbers.

Now if I take any nonempty collection of cuts $(X^\alpha_L,X^\alpha_R)$ with an upper bound (in the order on the set of cuts) we can take the union of all the $X^\alpha_L$ and the intersection of all the $X^\alpha_R$ to get a new cut. The left set contains all the $X^\alpha_L$ , and it’s contained in any other left set which contains them, so it’s the least upper bound. Thus the collection of cuts is now Dedekind complete.

We can also add field structures to this completion of an ordered field. For this purpose, it will be useful to denote a generic element of $X_L$ by $x_L$ , and assume $x_L$ runs over all elements of $X_L$ wherever it appears. For instance, given cuts $(X_L,X_R)$ and $(Y_L,Y_R)$ , we define their sum to be $(\{x_L+y_L\},\{x_R+y_R\})$ . The negative of a cut $(X_L,X_R)$ will be $(\{-x_R\},\{-x_L\})$ . The product of two positive cuts $(X_L,X_R)$ and $(Y_L,Y_R)$ will have as its right set the collection of all products $\{x_Ry_R\}$ , and its left set defined to make this a cut. Finally, the reciprocal of a positive cut $(X_L,X_R)$ will have the set $\{\frac{1}{x_R}\}$ as its right set, and its left set defined to make this a cut.

This suffices to define all the field operations on the set of cuts, and if we start with $\mathbb{Q}$ we get another model of $\mathbb{R}$ . I’ll leave verification of the field axioms as an exercise, and come back to prove that the method of cuts and the method of Cauchy sequences are equivalent. Once you play with cuts for a while, you may understand why I came at the real numbers with Cauchy sequences first. The cut approach seems to have a certain simplicity, and it’s less ontologically demanding since we’re only ever talking about pairs of subsets of the rational numbers rather than gigantic equivalence classes of sequences. But in the end I always find cuts to be extremely difficult to work with. Luckily, once we’ve shown them to be equivalent to Cauchy sequences it will establish that the real numbers we’ve been talking about are Dedekind complete, and we can put the messiness of this definition behind us.

December 5, 2007 Posted by John Armstrong | Fundamentals, Numbers, Orders | 11 Comments

The Order on the Real Numbers

We’ve defined the real numbers $\mathbb{R}$ as a topological field by completing the rational numbers $\mathbb{Q}$ as a uniform space, and then extending the field operations to the new points by continuity. Now we extend the order on the rational numbers to make $\mathbb{R}$ into an ordered field.

First off, we can simplify our work greatly by recognizing that we just need to determine the subset $\mathbb{R}^+$ of positive real numbers — those $x\in\mathbb{R}$ with $x\geq0$ . Then we can say $x\geq y$ if $x-y\geq0$ . Now, each real number is represented by a Cauchy sequence of rational numbers, and so we say $x\geq0$ if $x$ has a representative sequence $x_n$ with each point $x_n\geq 0$ .

What we need to check is that the positive numbers are closed under both addition and multiplication. But clearly if we pick $x_n$ and $y_n$ to be nonnegative Cauchy sequences representing $x$ and $y$ , respectively, then $x+y$ is represented by $x_n+y_n$ and $xy$ is represented by $x_ny_n$ , and these will be nonnegative since $\mathbb{Q}$ is an ordered field.

Now for each $x$ , $x-x=0\geq0$ , so $x\geq x$ . Also, if $x\geq y$ and $y\geq z$ , then $x-y\geq0$ and $y-z\geq0$ , so $x-z=(x-y)+(y-z)\geq0$ , and so $x\geq z$ . These show that $\geq$ defines a preorder on $\mathbb{R}$ , since it is reflexive and transitive. Further, if $x\geq y$ and $y\geq x$ then $x-y\geq0$ and $y-x\geq0$ , so $x-y=0$ and thus $x=y$ . This shows that $\geq$ is a partial order. Clearly this order is total because any real number either has a nonnegative representative or it doesn’t.

One thing is a little hazy here. We asserted that if a number and its negative are both greater than or equal to zero, then it must be zero itself. Why is this? Well if $x_n$ is a nonnegative Cauchy sequence representing $x$ then $-x_n$ represents $-x$ . Now can we find a nonnegative Cauchy sequence $y_n$ equivalent to $-x_n$ ? The lowest rational number that $y_n$ can be is, of course, zero, and so $\left|y_n-(-x_n)\right|\geq x_n$ . But for $-x_n$ and $y_n$ to be equivalent we must have for each positive rational $r$ an $N$ so that $r\geq\left|y_n-(-x_n)\right|\geq x_n$ for $n\geq N$ . But this just says that $x_n$ converges to ${0}$ !

So $\mathbb{R}$ is an ordered field, so what does this tell us? First off, we get an absolute value $\left|x\right|$ just like we did for the rationals. Secondly, we’ll get a uniform structure as we do for any ordered group. This uniform topology has a subbase consisting of all the half-infinite intervals $(x,\infty)$ and $(-\infty,x)$ for all real $x$ . But this is also a subbase for the metric we got from completing the rationals, and so the two topologies coincide!

One more very important thing holds for all ordered fields. As a field $\mathbb{F}$ is a kind of a ring with unit, and like any ring with unit there is a unique ring homomorphism $\mathbb{Z}\rightarrow\mathbb{F}$ . Now since $1gt;0$ in any ordered field, we have $2=1+1>0$ , and $3=2+1>0$ , and so on, to show that no nonzero integer can become zero under this map. Since we have an injective homomorphism of rings, the universal property of the field of fractions gives us a unique field homomorphism $\mathbb{Q}\rightarrow\mathbb{F}$ extending the ring homomorphism from the integers.

Now if $\mathbb{F}$ is complete in the uniform structure defined by its order, this homomorphism will be uniformly complete. Therefore by the universal property of uniform completions, we will find a unique extension $\mathbb{R}\rightarrow\mathbb{F}$ . That is, given any (uniformly) complete ordered field there is a unique uniformly continuous homomorphism of fields from the real numbers to the field in question. Thus $\mathbb{R}$ is the universal such field, which characterizes it uniquely up to isomorphism!

So we can unambiguously speak of “the” real numbers, even if we use a different method of constructing them, or even no method at all. We can work out the rest of the theory of real numbers from these properties (though for the first few we might fall back on our construction) just as we could work out the theory of natural numbers from the Peano axioms.

December 4, 2007 Posted by John Armstrong | Fundamentals, Numbers, Point-Set Topology, Topology | 3 Comments

The Topological Field of Real Numbers

We’ve defined the topological space we call the real number line $\mathbb{R}$ as the completion of the rational numbers $\mathbb{Q}$ 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 $\mathbf{Top}$ 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 $\mathbb{Q}$ is dense in $\mathbb{R}$ (and similarly $\mathbb{Q}\times\mathbb{Q}$ is dense in $\mathbb{R}\times\mathbb{R}$ ), 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 $X$ with a dense subset $D\subseteq X$ . Then every point $x\in X$ has a sequence $x_n\in D$ with $\lim x_n=x$ . Now if $f:X\rightarrow Y$ and $g:X\rightarrow Y$ are two continuous functions which agree for every point in $D$ , then they agree for all points in $X$ . Indeed, picking a sequence in $D$ converging to $x$ we have
$f(x)=f(\lim x_n)=\lim f(x_n)=\lim g(x_n)=g(\lim x_n)=g(x)$ .

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 $x$ and $y$ , and sequences of rational numbers $x_n$ and $y_n$ converging to $x$ and $y$ , respectively. We should have
$s(x,y)=s(\lim x_n,\lim y_n)=s(\lim(x_n,y_n))=\lim x_n+y_n$
but how do we know that the limit on the right exists? Well if we can show that the sequence $x_n+y_n$ is a Cauchy sequence of rational numbers, then it must converge because $\mathbb{R}$ is complete.

Given a rational number $r$ we must show that there exists a natural number $N$ so that $\left|(x_m+y_m)-(x_n+y_n)\right|<r$ for all $m,n\geq N$ . But we know that there’s a number $N_x$ so that $\left|x_m-x_n\right|<\frac{r}{2}$ for $m,n\geq N_x$ , and a number $N_y$ so that $\left|y_m-y_n\right|<\frac{r}{2}$ for $m,n\geq N_y$ . Then we can choose $N$ to be the larger of $N_x$ and $N_y$ and find
$\left|(x_m-x_n)+(y_m-y_n)\right|\leq\left|x_m-x_n\right|+\left|y_m-y_n\right|<\frac{r}{2}+\frac{r}{2}=r$
So the sequence of sums is Cauchy, and thus converges.

What if we chose different sequences $x'_n$ and $y'_n$ converging to $x$ and $y$ ? Then we get another Cauchy sequence $x'_n+y'_n$ of rational numbers. To show that addition of real numbers is well-defined, we need to show that it’s equivalent to the sequence $x_n+y_n$ . So given a rational number $r$ does there exist an $N$ so that $\left|(x_n+y_n)-(x'_n+y'_n)\right|<r$ for all $n\geq N$ ? 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 $\mathbb{R}\times\mathbb{R}\times\mathbb{R}$ to $\mathbb{R}$ defined by $s(s(x,y),z)$ and $s(x,s(y,z))$ . Since $s$ 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 ${0}$ from $\mathbb{Q}$ 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 $x$ by negating each term of a Cauchy sequence converging to $x$ , 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 $x+y$ for the sum of real numbers $x$ and $y$ .

What about the multiplication? Again, we’ll want to choose rational sequences $x_n$ and $y_n$ converging to $x$ and $y$ , and define our function by
$m(x,y)=m(\lim x_n,\lim y_n)=m(\lim(x_n,y_n))=\lim x_ny_n$
so it will be continuous and agree with rational number multiplication. Now we must show that for every rational number $r$ there is an $N$ so that $\left|x_my_m-x_ny_n\right|<r$ for all $m,n\geq N$ . This will be a bit clearer if we start by noting that for each rational $r_x$ there is an $N_x$ so that $\left|x_m-x_n\right|<r_x$ for all $m,n\geq N_x$ . In particular, for sufficiently large $n$ we have $\left|x_n\right|<\left|x_N\right|+r_x$ , so the sequence $x_n$ is bounded above by some $b_x$ . Similarly, given $r_y$ we can pick $N_y$ so that $\left|y_m-y_n\right|<r_y$ for $m,n\geq N_y$ and get an upper bound $b_y\geq y_n$ for all $n$ . Then choosing $N$ to be the larger of $N_x$ and $N_y$ we will have
$\left|x_my_m-x_ny_n\right|=\left|(x_m-x_n)y_m+x_n(y_m-y_n)\right|\leq r_xb_y+b_xr_y$
for $m,n\geq N$ . Now given a rational $r$ we can (with a little work) find $r_x$ and $r_y$ so that the expression on the right will be less than $r$ , 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 $x$ and $y$ , so we get a multiplication. Again, we can use the density of the rational numbers to show that it’s associative and commutative, that $1\in\mathbb{Q}$ serves as its unit, and that multiplication distributes over addition. We’ll just write $xy$ for the product of real numbers $x$ and $y$ from here on.

To show that $\mathbb{R}$ is a field we need a multiplicative inverse for each nonzero real number. That is, for each Cauchy sequence of rational numbers $x_n$ that doesn’t converge to ${0}$ , we would like to consider the sequence $\frac{1}{x_n}$ , but some of the $x_n$ might equal zero and thus throw us off. However, there can only be a finite number of zeroes in the sequence or else ${0}$ would be an accumulation point of the sequence and it would either converge to ${0}$ 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.

December 3, 2007 Posted by John Armstrong | Fundamentals, Numbers, Point-Set Topology, Topology | 13 Comments

Miscellany

Well, yesterday was given over to exam-writing, so today I’ll pick up a few scraps I mentioned in passing on Thursday.

First of all, the rational numbers are countable. To be explicit, in case I haven’t been before, this means that there is an injective function from the set of rational numbers to the set of natural numbers. Really, I’ll just handle the positive rationals, but it’s straightforward how to include the negatives as well. To every positive rational number we can get a pair of natural numbers — the numerator and the denominator. Then we can send the pair $(m,n)$ to the number $\frac{(m+n)(m+n+1)}{2}+n$ , which is a bijection between the set of all pairs of natural numbers and all natural numbers. Clearly they contain the natural numbers, so the set of rational numbers is countably infinite.

Now, equivalence relations. Given any relation $R\subseteq X\times X$ on a set $X$ we can build it up into an equivalence relation. First throw in the diagonal $\{(x,x)|x\in X\}$ to make it reflexive. Then throw in all the points $(y,x)$ for $xRy$ to make it symmetric. For transitivity, we can similarly start throwing elements into the relation until this condition is satisfied.

But that’s all sort of ugly. Here’s a more elegant way of doing it: given any relation $R\subseteq X\times X$ , consider all the relations $S$ on $X$ that contain $R$ — $R\subseteq S\subseteq X\times X$ . Some of these $S$ will be equivalence relations. In particular, the whole product $X\times X$ is an equivalence relation, so there is at least one such. It’s simple to verify that the intersection of any family of equivalence relations on $X$ is again an equivalence relation, so we can take the intersection of all equivalence relations on $X$ containing $R$ to get the smallest such relation. Notice, by the way, how this is similar to generating a topology from a subbase, or to taking the closure of a subset in a topological space.

Finally, absolute values. In any totally ordered group we have the positive “cone” $G^+$ of all elements $g\in G$ with $g\geq1$ . and the negative “cone” $G^-$ of all elements $g\in G$ with $1\geq g$ . In the latter case, we can multiply both sides by the inverse of $g$ to get $g^{-1}\geq1$ in the positive cone. Notice that the identity $1$ is in both cones, but the reflection described leaves it fixed. So for every element in $g\in G$ we get a well-defined element $\left|g\right|\in G^+$ called its absolute value. Of course, we often assume that $G$ is abelian and write this all additively instead of multiplicatively.

This function has a number of nice properties. First of all, $\left|g\right|$ is always in $G^+$ . Secondly, $\left|g\right|$ is the identity in $G$ if and only if $g$ itself is the identity. Thirdly, $\left|g\right|=\left|g^{-1}\right|$ . And finally, if $G$ is abelian we have the “triangle inequality” $\left|a+b\right|\leq\left|a\right|+\left|b\right|$ .

Okay, does that catch us up?

December 1, 2007 Posted by John Armstrong | Fundamentals, Orders | Leave a Comment

Topologies as Categories

Okay, so we’ve defined a topology on a set $X$ . But we also love categories, so we want to see this in terms of categories. And, indeed, every topology is a category!

First, remember that the collection of subsets of $X$ , like the collection of subobjects on an object in any category, is partially ordered by inclusion. And since every partially ordered set is a category, so is the collection of subsets of $X$ .

In fact, it’s a lattice, since we can use union and intersection as our join and meet, respectively. When we say that a poset has pairwise least upper bounds it’s the same as saying when we consider it as a category it has finite coproducts, and similarly pairwise greatest lower bounds are the same as finite products. But here we can actually take the union or intersection of any collection of subsets and get a subset, so we have all products and coproducts. In the language of posets, we have a “complete lattice”.

So now we want to talk about topologies. A topology is just a collection of the subsets that’s closed under finite intersections and arbitrary unions. We can use the same order (inclusion of subsets) to make a topology into a partially-ordered set. In the language of posets, the requirements are that we have a sublattice (finite meets and joins, along with the same top and bottom element) with arbitrary meets — the topology contains the least upper bound of any collection of its elements.

And now we translate the partial order language into category theory. A topology is a subcategory of the category of subsets of $X$ with finite products and all coproducts. That is, we have an arrow from the object $U$ to the object $V$ if and only if $U\subseteq V$ as subsets of $X$ . Given any finite collection $\{U_i\}_{i=1}^n$ of objects we have their product $\bigcap\limits_{i=1}^nU_i$ , and given any collection $\{U_\alpha\}_{\alpha\in A}$ of objects we have their coproduct $\bigcup\limits_{\alpha\in A}U_\alpha$ . In particular we have the empty product — the terminal object $X$ — and we have the empty coproduct — the initial object $\varnothing$ . And all the arrows in our category just tell us how various open sets sit inside other open sets. Neat!

November 9, 2007 Posted by John Armstrong | Category theory, Orders, Point-Set Topology, Topology | 8 Comments

Lattices

A poset which has both least upper bounds and greatest lower bounds is called a lattice. In more detail, let’s say we have a poset $(P,\preceq)$ and give it two operations: meet (written $\wedge$ ) and join (written $\vee$ ). These satisfy the requirements that

$x\preceq x\vee y$ and $y\preceq x\vee y$ .
If $x\preceq z$ and $y\preceq z$ then $x\wedge y\preceq z$ .
$x\wedge y\preceq x$ and $x\wedge y\preceq y$ .
If $z\preceq x$ and $z\preceq y$ then $z\preceq x\wedge y$ .

Not every poset has a meet and a join operation, but if these operations do exist they are uniquely specified by these requirements. In fact, we can see this sort of like how we saw that direct products of groups are unique up to isomorphism: if we have two least upper bounds for a pair of elements then they must each be below or equal to the other, so they must be the same.

We can derive the following properties of the operations:

$a\vee(b\vee c)=(a\vee b)\vee c$ and $a\wedge(b\wedge c)=(a\wedge b)\wedge c$ .
$a\vee b=b\vee a$ and $a\wedge b=b\wedge a$ .
$a\vee(a\wedge b)=a$ and $a\wedge(a\vee b)=a$ .

from these we see that there’s a sort of duality between the two operations. In fact, we can see that these provide two commutative semigroup structures that happen to interact in a certain nice way.

Actually, it gets even better. If we have two operations on any set satisfying these properties then we can define a partial order: $x\preceq y$ if and only if $x=x\wedge y$ . So we can define a lattice either by the order property and get the algebraic properties, or we can define it by the algebraic properties and get the order property from them.

In many cases, a lattice also satisfies $x\vee(y\wedge z)=(x\vee y)\wedge(x\vee z)$ , or equivalently $x\wedge(y\vee z)=(x\wedge y)\vee(x\wedge z)$ . In this case we call it “distributive”. A bit weaker is to require that if $x\preceq z$ then $x\vee(y\wedge z)=(x\vee y)\wedge z$ for all $y$ . In this case we call the lattice “modular”.

A lattice may have elements above everything else or below everything else. We call a greatest element of a lattice $1$ and a least element ${0}$ . In this case we can define “complements”: $x$ and $y$ are complements if $x\vee y=1$ and $x\wedge y=0$ . If the lattice is distributive, then the complement of $x$ is unique if it exists. A distributive lattice where every element has a complement is called “Boolean”.

May 14, 2007 Posted by John Armstrong | Algebra, Lattices, Orders | 8 Comments

Ordinal numbers

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 $(X,\leq)$ and $(Y,\preceq)$ are two well-ordered sets, a function $f:X\rightarrow Y$ preserves the order if whenever $x_1\leq x_2$ then $f(x_1)\preceq f(x_2)$ . 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 $\mathbb{N}$ 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 $\{\}\times\{\}=\{\}$ , 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 ${}0$ . Notice that it has (cardinal number) zero elements.

Now given an ordinal number $O$ we define $S(O)=O\cup\{O\}$ . 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: $O_1\leq O_2$ if $O_1\in O_2$ . 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 $\mathbb{N}$ . 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.

April 26, 2007 Posted by John Armstrong | Fundamentals, Numbers, Orders | 2 Comments

Cardinal numbers

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 $\{a,b,c\}$ , and that there are also three elements in the set $\{x,y,z\}$ . 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 $f$ by $f(a)=x$ , $f(b)=z$ , and $f(c)=y$ . Every element of $\{x,y,z\}$ is hit by exactly one element of $\{a,b,c\}$ , 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 $X$ and $Y$ are “in bijection” — and write $X\leftrightarrow Y$ — if there is some bijection $f:X\rightarrow Y$ . This is an equivalence relation! Any set is in bijection with itself, using the identity function. If $X$ is in bijection with $Y$ then we can use the inverse function to see that $Y\leftrightarrow X$ . Finally, if $f:X\rightarrow Y$ and $g:Y\rightarrow Z$ are bijections, then $g\circ f:X\rightarrow Z$ 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 ${}0$ . Now given any finite set $X$ with cardinal number — bijection class — $c$ , there’s something not in $X$ . Pick any such something, call it $x$ , and look at the set $X\cup\{x\}$ . If I took any other set $Y$ in bijection with $X$ and anything $y$ not in $Y$ then there is a bijection between $x\cup\{x\}$ and $Y\cup\{y\}$ . Just apply the bijection from $X$ to $Y$ on those elements from $X$ , and send $x$ to $y$ . 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 $S(c)$ .

We look at the set of all bijection classes of finite sets. We’ve got an identified element ${}0$ , 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.

April 13, 2007 Posted by John Armstrong | Fundamentals, Numbers | 3 Comments

« Previous Entries Next Entries »

About this weblog

This is mainly an expository blath, with occasional high-level excursions, humorous observations, rants, and musings. The main-line exposition should be accessible to the “Generally Interested Lay Audience”, as long as you trace the links back towards the basics. Check the sidebar for specific topics (under “Categories”).

I’m in the process of tweaking some aspects of the site to make it easier to refer back to older topics, so try to make the best of it for now.

RSS Feeds

RSS - Posts
RSS - Comments
Feedback

Got something to say? Anonymous questions, comments, and suggestions at Formspring.me!
Subjects
Archives

May 2013

M T W T F S S

« Sep

1 2 3 4 5

6 7 8 9 10 11 12

13 14 15 16 17 18 19

20 21 22 23 24 25 26

27 28 29 30 31
Search for:

The Unapologetic Mathematician

Mathematics for the interested outsider

Archimedean Fields

Cuts and Sequences are Equivalent

Dedekind Completion

The Order on the Real Numbers

The Topological Field of Real Numbers

Miscellany

Topologies as Categories

Lattices

Ordinal numbers

Cardinal numbers

About this weblog

Recent Posts

Blogroll

Art

Astronomy

Computer Science

Education

Mathematics

Me

Philosophy

Physics

Politics

Science

RSS Feeds

Feedback

Subjects

Archives

Site info

Follow “The Unapologetic Mathematician”

May 2013
M	T	W	T	F	S	S
« Sep
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31