The Axiom of Choice
The axiom of choice is a fascinating bugger. It’s probably the most controversial statement in mathematics in the last century – which is pretty serious, considering the kinds of things that have gone on in math during the last century.

The axiom itself is quite simple, and reading an informal description of it, it’s difficult to understand how it managed to cause so much trouble. For example, wikipedia has a rather nice informal statement of it:

given a collection of bins each containing at least one object, exactly one object from each bin can be picked and gathered in another bin

Continue reading →

The axiom of infinity is a bundle of tricks. As I said originally, it does two things. First, it gives us our first infinite set; and second, it sets the stage for representing arithmetic in terms of sets. With the axiom of infinity, we get the natural numbers; with the natural numbers, we can get the integers; with the integers, we can get the rationals. Once we have the rationals, things get a bit harder – but we can get the reals via Dedekind cuts; and by transfinite induction, we can get the transfinite numbers. But before we can get to any of that, we need a sound representation of the naturals in terms of sets.

Continue reading →

Some of the basic axioms of ZFC set theory can seem a bit uninteresting on their own. But when you take them together, and reason your way around them, you can find some interesting things.

Let’s start by looking at the axiom of extensionality. Pretty simple, right? All it does is define what set equality means. It says that two sets are equal if, and only if, they have the same members: that is, a set is completely determined by its contents.

How much more trivial can a statement about sets get? It really doesn’t seem to say much. But what happens when we start thinking through what that means?

The way we normally think of sets, they’re collections of objects. So, imagine a set like {red, green, blue}, where the three values are atoms: that is, they’re single objects, not collections. What does the axiom of extensionality say about that? It says that red, green, and blue are not atoms?

Why? Well – let’s look at the axiom of extensionality again: (∀A,B: A=B ⇔
(∀C: C∈A ⇔ C∈B)). So – does red = blue? Well, if they’re atoms, then
yes, red=blue, because nothing is in red, and nothing is in blue. Since neither has any members, they’re equal.

In fact, if we follow that reasoning through, there’s only one possible atom: the only set with no members is the empty set. So anything else we want, we’re going to have to represent using some kind of collection.

As a result of that, along with the axiom of specification, we can show that the axiom
of the empty set is actually redundant. After all – the axiom of specification basically
says that if you can describe a collection of values by a predicate, that collection is a class. So take the predicate P(x)=false; that’s a set with no values. Also known as the empty set. So the empty set exists, and it’s the only set with no members – aka the only atom.

The axiom of pairing is an interesting beast. It looks simple, and in fact, it
is simple. But it opens up a range of interesting things that we’d like to be able
to do. For example, without the axiom of pairing, we wouldn’t be able to formulate the
cartesian products of sets – and without cartesian product, huge ranges of interesting and
important areas of mathematics would be inaccessible to us. (Note that I’m saying that
pairing is necessary, not that it’s sufficient. You also need replacement
to get the projection functions that are part of the usual definition of the cartesian
product.)

Continue reading →

Axiomatic set theory builds up set theory from a set of fundamental initial rules. The most common axiomatization, which we’ll be used, is the ZFC system: Zermelo-Fraenkel with choice set theory. The ZFC axiomatization consists of 8 basic rules which are pretty much universally accepted, and two rules that are somewhat controversial – most particularly the last rule, called the axiom of choice.

Continue reading →

Naive set theory is fun, and as we saw with Cantor’s diagonalization, it can produce some incredibly beautiful results. But as we’ve seen before, in the simple world of naive set theory, it’s easy to run into trouble, in the form of Russell’s paradox and a variety of related problems.

For the sake of completeness, I’ll remind you that Russell’s paradox concerns the set R={ s | s ∉ s}. Is R∈R? If R∈R, then by the definition of R∉R. But by definition, if R∉R, then R∈R. So R is clearly not a well-defined set. But there’s nothing about the form of its definition which is prohibited by naive set theory!

Mathematicians, being the annoying buggers that they are, weren’t willing to just give up on set theory over Russell’s paradox. It’s too beautiful, too useful an abstraction, to just give up on it over the self-reference problems. So they went searching for a way of building up set theory axiomatically in a way that would avoid problems by making it impossible to even formulate the problematic statements.

Continue reading →