Gracious Living

The Construction of the Reals: Metric Completion and Dedekind Cuts
March 6, 2011, 21:31
Filed under: Algebra, Math, Set Theory, Topology | Tags: , , , ,

It looks like I’m getting views now, which is surprising.  I’ve been pretty busy with schoolwork, but I really want to get this blog up to speed, particularly because I’d like to start discussing things as I’m learning about them.  I’d also like to make more non-mathematical posts, but maybe these are best left to a separate blog?  Thoughts?

Our first example of a field was the field of rationals, \mathbb{Q}.  Recall that this was the field of fractions of the integers, which were in turn the free abelian group on one generator with their natural multiplication.  But now it appears that we’re stuck.  While we intuitively know what \mathbb{R} should be — it’s a line, for crying out loud — there seems to be no algebraic way of “deriving” it from \mathbb{Q}.  A first guess might be to add in solutions of polynomials, like \sqrt{2} as the solution of f(x)=x^2-2, but not only does this include some complex numbers, it also misses some real numbers like e and \pi.  (We call such numbers — those that aren’t solutions of polynomials with rational coefficients — transcendental.  It’s actually quite difficult to prove that transcendental numbers even exist.)

Instead, we turn to topology.  Below, I give two ways of canonically defining \mathbb{R}, one using the metric properties of \mathbb{Q}, one using its order properties.  I found this really interesting when I first saw it, but I can’t see it interesting everyone, so be warned if you’re not a fan of set theory or canonical constructions.  One of the topological techniques we’ll see will be useful later, but at that point it’ll be treated in its own right.

Continue reading

Cardinal Arithmetic
December 8, 2010, 03:23
Filed under: Math, Set Theory | Tags: , , , ,

Let’s get tricky!  Unlike ordinal arithmetic, the arithmetic of cardinals isn’t really an extension of Peano arithmetic.  Rather, it’s a consequence of the set model of ordinals, with the sum of two ordinals being the order type of their disjoint union, and their product being the order type of their Cartesian product.

Part of the reason for this is that cardinals have a vastly different notion of “successor.”  See, the ordinals are well-ordered, so any subset has a least element, and thus we can identify each cardinal with the least ordinal of its cardinality.  So we’ll say \aleph_0=\omega,\aleph_1=\omega_1,\dotsc.  (Exercise: these are all limit ordinals.)  Then the cardinals, as a subset of the ordinals, are also well-ordered, and thus we can define the successor of a cardinal as the least cardinal greater than it, and the limit of a set of cardinals as their least upper bound.

Since the cardinals, as aleph numbers, are also indexed by the ordinals, we have \aleph_{S\alpha}=S\aleph_\alpha,\aleph_{\lim\alpha}=\lim\aleph_\alpha.  We can treat the map \alpha\mapsto\aleph_\alpha as a function \aleph:\mathbf{On}\rightarrow\mathbf{On}; then this function is normal.  So in particular it has a fixed point (indeed, an unbounded class of them): this is an ordinal \alpha such that \omega_\alpha=\alpha.  Even though the cardinals increase a lot “faster” than the ordinals, this number is simultaneously the \alphath cardinal and the \alphath ordinal!  The first such ordinal is \omega_{\omega_{\omega_{\dotsc}}}.

This fills me with the greatest glee.

We won’t be assuming the generalized continuum hypothesis for the first part of this, so we won’t mention the beth numbers (which are \beth_0=\aleph_0,\beth_{S\alpha}=2^{\beth_\alpha},\beth_{\lim\alpha}=\lim\beth_\alpha).  If you do assume it, the beth numbers are the aleph numbers; if you don’t, it’s difficult to say anything about them arithmetic-wise.

Like Devlin, I’ll use \kappa,\lambda,\mu for cardinals, \alpha,\beta,\gamma for ordinals.

Continue reading

Ordinal Arithmetic
December 7, 2010, 21:03
Filed under: Math, Set Theory | Tags: , , ,

Freeing yourself of the bounds of Peano arithmetic, you come upon a number of different routes to take.  You want the addition and multiplication operations you defined to make sense in a larger scope, but what this scope is varies depending on your needs.  The standard thing to do is to start “closing” the ordered semiring \mathbb{N} in a number of different ways: group closure by adding negatives and reciprocals, metric closure by adding limits, or algebraic closure by adding solutions to polynomials.  But instead, we could just model the elements of \mathbb{N} as the finite ordinals and use transfinite recursion to extend the operations to operations on ordinals.  Transfinite recursion is like induction on cagefighting elephant steroids.

Once you’ve done this, you lose some of your semiring properties, but you retain the order and you win the exciting new property of it being closed under limits.  This is ordinal arithmetic.  Building it will let us understand the structure of the ordinals more rigorously than we had before: there was an ordinal we called \omega^2+1, but what does this actually mean?

Continue reading

November 6, 2010, 08:17
Filed under: Math, Set Theory | Tags: , , , ,

When we talked about cardinality, we defined “standardized” finite cardinal numbers as the set \mathbb{N}, which we modeled as 0=\emptyset, 1=\{0\},2=\{0,1\}, and so on.  We’ve since noted certain special properties of this model:

  • the set exists by the ZFC axioms
  • because of this, it is “pure” — everything is a set of sets, there are no ur-elements
  • the “successor function” S(n)=n\cup\{n\} is well-defined, injective, and its image is everything but 0
  • because of this, if a statement is true for 0 and its truth for n implies its truth for S(n), it is true for all elements of \mathbb{N} — this is the “inductive property”
  • n\subset m iff n\in m, and these synonymous relations are total orders on \mathbb{N}.

In the discussion of the Axiom of Choice, we defined a “well-order” as a total order in which every subset has a least element, and proved that every set can be well-ordered if we assume the AC.  In fact, the subset/element ordering on \mathbb{N} is already a well-order: given M\subset\mathbb{N}, the set \bigcap M is a least element, and you should prove that this is always an element of M (induction might help).

Cardinalities tell us everything about sets up to bijection.  But when sets also have orders on them, this isn’t enough.  If we care about the orders on X and Y, the only functions we should be caring about are those that are order-preserving: that is, that f(a)\le_Y f(b) when a\le_X b.  Likewise, rather than all bijections, we care about the order isomorphisms: bijections that are order-preserving and have order-preserving inverses.  We’re “pairing off” the sets again, but in the same order.  None of the bijections with \mathbb{N} in the post on countability did this, and it’s pretty clear why: any order isomorphism has to preserve the type of ordering, and \mathbb{N} is well-ordered while \mathbb{Z} and \mathbb{Q} aren’t.

The order isomorphism classes (or order types) of general posets or tosets are many and difficult to talk about.  But the order types of well-ordered sets are easier to study.  Below the fold, let’s take them on.

Continue reading

The Axiom of Choice
November 5, 2010, 06:33
Filed under: Math, Set Theory | Tags: , , , ,

This post is going to be a bit more technical than most, so feel free to skim it if you find it difficult.  You should know the statements of the theorems and the definition of well-ordering, though.

When I stated the ZFC set axioms, I put choice last for a reason.  As I said there, it’s a bit like the parallel postulate in Euclidean geometry (if you don’t know this story, you should read about it — it’s fascinating).  Unlike the other axioms, it’s non-constructive, and it looks complicated enough that you should be able to get it from the other axioms, though it’s in fact independent of them (meaning they can’t prove it or disprove it).  For these reasons, many mathematicians in the early half of the century used choice sparingly, and made it very clear what pieces of their work required it.  But as we’ve seen, we needed it to show that every infinite set contains a sequence, and likewise, many of its consequences are so useful that it’s common nowadays to use it without reservation.  (And yes, Munroe, the Banach-Tarski paradox is a good thing.)

Besides important consequences, there are about four important equivalent statements to the axiom of choice, and that’s what I’ll be talking about today.  Hopefully this will give you an idea of what a choice function is and how powerful it is.  We’ll be showing the following statements are equivalent:

  1. The axiom of choice: every set S has a choice function c:\mathcal{P}(S)\rightarrow S such that c(A)\in A for all A\subset S.
  2. Every Cartesian product of non-empty sets is non-empty.
  3. Zorn’s Lemma: Every partially ordered set, in which every totally ordered subset has an upper bound, has a maximal element.
  4. Hausdorff Maximum Principle: Every partially ordered set has a maximal totally ordered subset.
  5. Well-Ordering Theorem: Every set can be well-ordered.

Below the fold, definitions of these terms and proofs of equivalence.

Continue reading

November 2, 2010, 01:28
Filed under: Math, Set Theory | Tags: ,

(This is a follow-up to my post on cardinality. In it, I constructed a model of the natural numbers, which I also called \mathbb{N}, by 0=\emptyset,1=\{0\},2=\{0,1\}, and so on [I used boldface for these sets last time, but it really isn’t necessary]. This set is “pure” and it exists by the Zermelo-Fraenkel axioms. Assuming the axiom of choice, it’s also the “smallest” infinite set up to bijection.   Below the jump, I talk about larger infinities.)

Continue reading

November 1, 2010, 04:45
Filed under: Math, Set Theory | Tags: , ,

(This was originally a longer post that went through to countability and the continuum hypothesis. I’ve broken it in half, ending at the definition of infinite sets, in the interest of keeping things short, and also possibly of MaBloWriMo. The next half will be up soon!)

What we’re going to do today is measure sets.  I said that sets have no structure back in the first couple of posts, but this isn’t entirely true.  Finite sets, for example, have a definite number of elements.  Today, I show that you can extend this idea of number to infinite sets by considering a special class of function between sets that preserves number.  The strange properties of this will end up making topology and set theory a lot more interesting.

Continue reading