The Unapologetic Mathematician

Mathematics for the interested outsider

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 | Fundamentals, Orders | Leave a comment