Orders « The Unapologetic Mathematician

Darboux Integration

Okay, defining the integral as the limit of a net of Riemann sums is all well and good, but it’s a huge net, and it seems impossible to calculate with. We need a better way of getting a handle on these things. What we’ll use is a little trick for evaluating limits of nets that I haven’t mentioned yet: “cofinal sets”.

Given a directed set $(D,\preceq)$ , a directed subset $S$ is cofinal if for every $d\in D$ there is some $s\in S$ with $s\succeq d$ . Now watch what happens when we try to show that the limit of a net $x_d$ is a point $x$ . We need to find for every neighborhood $U$ of $x$ an index $d_0$ so that for every $d\succeq d_0$ we have $x_d\in U$ . But if $d_0$ is such an index, then there is some $s_0\in S$ above it, and every $s\in S$ above that is also above $d_0$ , and so $x_s\in U$ . That is, if the limit over $D$ exists, then the limit over $S$ exists and has the same value.

Let’s give a cofinal set of tagged partitions by giving a rule for picking the tags that go with any partition. Then our net consists just of partitions of the interval $\left[a,b\right]$ , and the tags come for free. If the function $f$ is Riemann-integrable, then the limit over this cofinal set will be the integral. Here’s our rule: in the closed subinterval $\left[x_{i-1},x_i\right]$ pick a point $t_i$ so that $\lim\limits_{x\rightarrow t_i}f(x)$ is the supremum of the values of $f$ in that subinterval. If the function is continuous it will attain a maximum at our tag, and if not it’ll get close or shoot off to infinity (if there is no supremum).

Why is this cofinal? Let’s imagine a tagged partition $x=((x_0,...,x_n),(t_1,...,t_n))$ where $t_i$ is not chosen according to this rule. Then we can refine the partition by splitting up the $i$ th strip in such a way that $t_i$ is the maximum in one of the new strips, and choosing all the new tags according to the rule. Then we’ve found a good partition above the one we started with. Similarly, we can build another cofinal set by always choosing the tags where $f$ approaches an infimum.

When we consider a partition $x$ in the first cofinal set we can set up something closely related to the Riemann sums: the “upper Darboux sums”

$\displaystyle U_x(f)=\sum\limits_{i=1}^n M_i(x_i-x_{i-1})$

where $M_i$ is the supremum of $f(x)$ on the interval $\left[x_{i-1},x_i\right]$ , or infinity if the value of $f$ is unbounded above here. Similarly, we can define the “lower Darboux sum”

$\displaystyle L_x(f)=\sum\limits_{i=1}^n m_i(x_i-x_{i-1})$

where now $m_i$ is the infimum (or negative infinity). If the function is Riemann-integrable, then the limits over these cofinal sets both exist and are both equal to the Riemann integral. So we define a function to be “Darboux-integrable” if the limits of the upper and lower Darboux sums both exist and have the same value. Then the Darboux integral is defined to be this common value. Notice that if the function ever shoots off to positive or negative infinity we’ll get an infinite value for one of the terms, and we can never converge, so such functions are not Darboux-integrable.

We should notice here that given any partition $x$ , the upper Darboux sum must be larger than any Riemann sum with that same partition, since no matter how we choose the tag $t_i$ we’ll find that $f(t_i)\leq M_i$ by definition. Similarly, the lower Darboux sum must be smaller than any Riemann sum on the same partition. Now let’s say that the upper and lower Darboux sums both converge to the same value $s$ . Then given any neighborhood of $s$ we can find a partition $x_U$ so that every upper Darboux sum over a refinement of $x_U$ is in the neighborhood, and a similar partition $x_L$ for the lower Darboux sums. Choosing a common refinement $x_R$ of both (which we can do because partitions form a directed set) both its upper and lower Darboux sums (and those of any of its refinements) will be in our neighborhood. Then we can choose any tags in $x_R$ we want, and the Riemann sum will again be in the neighborhood. Thus a Darboux-integrable function is also Riemann-integrable.

So this new notion of Darboux-integrability is really the same one as Riemann-integrability, but it involves taking two limits over a much less complicated directed set. For now, we’ll just call a function which satisfies either of these two equivalent conditions “integrable” and be done with it, using whichever construction of the integral is most appropriate to our needs at the time.

January 30, 2008 Posted by John Armstrong | Analysis, Calculus, Orders | 3 Comments

Archimedean Groups and the Largest Archimedean Field

Okay, I’d promised to get back to the fact that the real numbers form the “largest” Archimedean field. More precisely, any Archimedean field is order-isomorphic to a subfield of $\mathbb{R}$ .

There’s an interesting side note here. I was thinking about this and couldn’t quite see my way forward. So I started asking around Tulane’s math department and seeing if anyone knew. Someone pointed me towards Mike Mislove, and when I asked him, he suggested we ask Laszlo Fuchs around the corner from him. Dr. Fuchs, it turned out, did know the answer, and it was in a book he’d written himself: Partially Ordered Algebraic Systems. It’s an interesting little volume, which I may come back and mine later for more topics.

Anyhow, we’ll do this a little more generally. First let’s talk about Archimedean ordered groups a bit. In a totally-ordered group $G$ we’ll say two elements $a$ and $b$ are “Archimedean equivalent” ( $A\sim B$ ) if there are natural numbers $m$ and $n$ so that $|a|<|b|^m$ and $|b|<|a|^n$ (here I’m using the absolute value that comes with any totally-ordered group). That is, neither one is infinitesimal with respect to the other. This can be shown to be an equivalence relation, so it chops the elements of $G$ into equivalence classes. There are always at least two in any nontrivial group because the identity element is infinitesimal with respect to everything else. We say a group is Archimedean if there are only two Archimedean equivalence classes. That is, for any $a$ and $b$ other than the identity, there is a natural number $n$ with $|a|<|b|^n$ .

Now we have a theorem of Hölder which says that any Archimedean group is order-isomorphic to a subgroup of the real numbers with addition. In particular, we will see that any Archimedean group is commutative.

Now either $G$ has a least positive element $g$ or it doesn’t. If it does, then $e\leq x<g$ implies that $x=e$ ( $e$ is the identity of the group). By the Archimedean property, any element $a$ has an integer $n$ so that $g^n\leq a<g^{n+1}$ . Then we can multiply by $g^{-n}$ to find that $e\leq g^{-n}a<g$ , so $g^{-n}a=e$ . Every element is thus some power of $g$ , and the group is isomorphic to the integers $\mathbb{Z}\subseteq\mathbb{R}$ .

On the other hand, what if given a positive $x$ we can always find a positive $y$ with $y<x$ ? In this case, $y^2$ may be greater than $x$ , but in this case we can show that $(xy^{-1})^2\leq x$ , and $xy^{-1}$ itself is less than $x$ , so in either case we have an element $z$ with $e<z<x$ and $z^2\leq x$ .

Now if two positive elements $a$ and $b$ fail to commute then without loss of generality we can assume $ba<ab$ . Then we pick $x=aba^{-1}b^{-1}>e$ and choose a $z$ to go with this $x$ . By the Archimedean property we’ll have numbers $m$ and $n$ with $z^m\leq a<z^{m+1}$ and $z^n\leq b<z^{n+1}$ . Thus we find that $x<z^2$ , which contradicts how we picked $z$ . And thus $G$ is commutative.

So we can pick some positive element $a\in G$ and just set $f(a)=1\in\mathbb{R}$ . Now we need to find where to send every other element. To do this, note that for any $b\in G$ and any rational number $\frac{m}{n}\in\mathbb{Q}$ we’ll either have $a^m\leq b^n$ or $a^m\geq b^n$ , and both of these situations must arise by the Archimedean property. This separates the rational numbers into two nonempty collections — a cut! So we define $f(b)$ to be the real number specified by this cut. It’s straightforward now to show that $f(bc)=f(b)+f(c)$ , and thus establish the order isomorphism.

So all Archimedean groups are just subgroups of $\mathbb{R}$ with addition as its operation. In fact, homomorphisms of such groups are just as simple.

Say that we have a nontrivial Archimedean group $A\subseteq\mathbb{R}$ , a (possibly trivial) Archimedean group $B\subseteq\mathbb{R}$ , and a homomorphism $f:A\rightarrow B$ . If $f(a)=0$ for some positive $a\in A$ then this is just the trivial homomorphism sending everything to zero, since for any positive $x$ there is a natural number $n$ so that $x<na$ . In this case the homomorphism is “multiply by ${0}$ “.

On the other hand, take any two positive elements $a_1,a_2\in A$ and consider the quotients (in $\mathbb{R}$ ) $\frac{a_1}{a_2}$ and $\frac{f(a_1)}{f(a_2)}$ . If they’re different (say, $\frac{f(a_1)}{f(a_2)}<\frac{a_1}{a_2}$ ) then we can pick a rational number $\frac{m}{n}$ between them. Then $nf(a_1)<mf(a_2)$ , while $ma_2<na_1$ , which contradicts the order-preserving property of the isomorphism! Thus we find the ratio $\frac{f(a)}{a}$ must be a constant $r>0$ , and the homomorphism is “multiply by $r$ “.

Now let’s move up to Archimedean rings, whose definition is the same as that for Archimedean fields. In this case, either the product of any two elements is ${0}$ (we have a “zero ring”) and the additive group is order-isomorphic to a subgroup of $\mathbb{R}$ , or the ring is order-isomorphic to a subring of $\mathbb{R}$ . If we have a zero ring, then the only data left is an Archimedean group, which the above discussion handles, so we’ll just assume that we have some nonzero product and show that we have an order-isomorphism with a subring of $\mathbb{R}$ .

So we’ve got some Archimedean ring $R$ and its additive group $R_+$ . By the theorem above, $R_+$ is order-isomorphic to a subgroup of $\mathbb{R}$ . We also know that for any positive $a\in R$ the operation $\lambda_a(x)=a\cdot x$ (the dot will denote the product in $R$ ) is an order-homomorphism from $R_+$ to itself. Thus there is some non-negative real number $r_a$ so that $\lambda_a(x)=r_ax$ . If we define $r_{-a}=-r_a$ then the assignment $a\mapsto r_a$ gives us an order-homomorphism from $R_+$ to some group $S_+\subseteq\mathbb{R}$ .

Again, we must have $r_a=sa$ for some non-negative real number $s$ . If $s=0$ then all multiplications in $R$ would give zero, so $0<s$ , and so the assignment is invertible. Now we see that $a\cdot b=r_ab=sab$ . Similarly, we have $r_{a\cdot b}=s(a\cdot b)=(sa)(sb)=r_ar_b$ , and so the function $a\mapsto r_a$ is an order-isomorphism of rings.

In particular, a field $\mathbb{F}$ can’t be a zero ring, and so there must be an injective order-homomorphism $\mathbb{F}\rightarrow\mathbb{R}$ . In fact, there can be only one, for if there were more than one the images would be related by multiplication by some positive $r\in\mathbb{R}$ : $\phi_1(a)=r\phi_2(a)$ . But then $r\phi_2(a)\phi_2(b)=r\phi_2(a\cdot b)=\phi_1(a\cdot b)=\phi_1(a)\phi_1(b)=r^2\phi_2(a)\phi_2(b)$ , and so $r=1$ .

We can sum this up by saying that the real numbers $\mathbb{R}$ are a terminal object in the category of Archimedean fields.

December 17, 2007 Posted by John Armstrong | Algebra, Fundamentals, Group theory, Numbers, Orders, Ring theory | 3 Comments

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 | 15 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 | 10 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

Well-Ordering

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 $\mathbb{N}$ and the integers $\mathbb{Z}$ . 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 $X$ , either ${}0$ is in $X$ 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 $S(0)$ . As we keep going, either we eventually hit an element of $X$ or we don’t. If we do, the first one is the least element of $X$ . If not, then by induction the set of natural numbers not in $X$ is all of them, and $X$ 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 $x\preceq y$ if either $|x|\leq|y|$ or $|x|=|y|$ and $x\leq y$ . We can list the integers in this order: $0,-1,1,-2,2,...,-n,n,...$ . 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.

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

Orders

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 $x\preceq y$ and say that $x$ precedes $y$ or that $y$ succeeds $x$ . A set equipped with a preorder is called a preordered set. If we also have that for any two elements $x$ and $y$ there is some element $z$ (possibly the same as $x$ or $y$ ) 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 $x\preceq y$ and $y\preceq x$ is for $x$ and $y$ 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 $A$ and $B$ are subsets of a set $X$ , then $A$ precedes $B$ if $A$ is contained in $B$ . This has the further nice property that it has a top element, $X$ 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 $x$ and $y$ we either have $x\preceq y$ or $y\preceq x$ 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.

March 11, 2007 Posted by John Armstrong | Fundamentals, Orders | 11 Comments

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

Subjects
Archives

June 2023

M T W T F S S

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

« Sep
Search for:

The Unapologetic Mathematician

Mathematics for the interested outsider

Darboux Integration

Archimedean Groups and the Largest Archimedean Field

Dedekind Completion

Miscellany

Topologies as Categories

Lattices

Ordinal numbers

Well-Ordering

Orders

About this weblog

Recent Posts

Blogroll

Art

Astronomy

Computer Science

Education

Mathematics

Me

Philosophy

Physics

Politics

Science

RSS Feeds

Feedback

Subjects

Archives

Site info