Set Theory | 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: algebra, construction, Math, order theory, set theory

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.

(more…)

1 Comment

Cardinal Arithmetic

December 8, 2010, 03:23
Filed under: Math, Set Theory | Tags: cardinals, Math, ordinals, set theory, trivial

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 $\alpha$ th cardinal and the $\alpha$ th 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.

(more…)

1 Comment

Ordinal Arithmetic

December 7, 2010, 21:03
Filed under: Math, Set Theory | Tags: arithmetic, Math, ordinals, set theory

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?

(more…)

Leave a Comment

Ordinals

November 6, 2010, 08:17
Filed under: Math, Set Theory | Tags: Math, order theory, set theory, topology, weird

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.

(more…)

2 Comments

The Axiom of Choice

November 5, 2010, 06:33
Filed under: Math, Set Theory | Tags: axiomatic, MaBloWriMo, Math, order theory, set theory

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:

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$ .
Every Cartesian product of non-empty sets is non-empty.
Zorn’s Lemma: Every partially ordered set, in which every totally ordered subset has an upper bound, has a maximal element.
Hausdorff Maximum Principle: Every partially ordered set has a maximal totally ordered subset.
Well-Ordering Theorem: Every set can be well-ordered.

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

(more…)

2 Comments

Countability

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

(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.)

(more…)

6 Comments

Cardinality

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

(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.

(more…)

3 Comments

The Zermelo-Fraenkel Axioms for Sets

October 29, 2010, 13:17
Filed under: Math, Set Theory | Tags: axiomatic, Math, set theory

I’m going to change tacks a bit here, leave topology behind for a second, and talk about sets from a less naive, more higher math perspective. An axiom, by the way, is an assumed truth or defining property.
Most people are at least a little bit familiar with Euclid’s axioms for geometry; without actually saying what points or lines or planes are, they define (more or less) the essential relationships between them, and the true statements of geometry are all logical consequences of the axioms.

A statement of geometry?

Points, lines, and planes are supposed to be atomic, not relying on any previous definitions, so that their meanings are entirely given by the axioms, and not our preconceived notions of what they “look like.” In the immortal words of David Hilbert, we must always be able to replace the words “point,” “line,” “plane” by “table,” “chair,” “beer mug” and still have valid proofs.

Well, the Zermelo-Fraenkel axioms (or ZFC; the C stands for “choice,” the last axiom) do essentially the same thing for set theory, with the ideas “set” and “element” taken as atomic. So we can think of “sets” as being a kind of thing and “is an element of” as being a kind of “relation” between two sets, but other than that we shouldn’t be using the standard “collection-of-things” visualization that sets were first introduced with. Rather, the axioms will formally give us the idea that “piles-of-things” model so well. We’re also going to go forward without “things” to pile: all sets will be sets of other sets, and we only know that a set exists if we can build it from the axioms.

Below the jump, I introduce the axioms. They’re usually given as sentences of formal logic, using mathematical symbols, but I’d rather say them in plain English.

(more…)

6 Comments

Relations

October 25, 2010, 13:38
Filed under: Math, Set Theory | Tags: elementary, Math, set theory

A relation from $A$ to $B$ is just a subset of $A\times B$ . For example, $R=\{(a,b)\in\mathbb{R}\times\mathbb{R}:a^2=b^2\}$ is a relation from $\mathbb{R}$ to $\mathbb{R}$ that includes, say, $(0,0),(4,4),(4,-4),(-4,4),(3,-3)$ , and so on. We generally write $aRb$ instead of $(a,b)\in R$. Except in very few circumstances, we actually only care about three kinds of relations.

(more…)

3 Comments

Sets

October 24, 2010, 17:31
Filed under: Math, Set Theory | Tags: elementary, Math, set theory

This will probably be review for a lot of readers, but I just want to make sure we’re all on the same page before we really start. These terms get used a lot a lot in higher math. In the 1900′s, sets were seen by luminaries like Bertrand Russell as being the salvation of math, since you could describe basically any mathematical structure in terms of sets. Nowadays, mathematicians tend to believe that the “guts” of math really aren’t that important, and category theory, which instead describes the relations between structures, has become more foundational. By the way, category theory is just about the coolest possible thing, but its coolness only really becomes apparent once you have a bedrock of examples to work with. I’ll start talking about it much later. For now, let’s talk about sets.

(more…)

4 Comments

Gracious Living

Categories

Archives

Links

Follow “Gracious Living”