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

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