Set Theory
goodmath | December 3, 2007 The point of set theory isn't just to sit around and twiddle our thumbs about
the various definitions we can heap together. It's to create a basis on which we
can build and study interesting things. A great example of that is something
called a group. Once we've built up sets enough to be able to understand a set of values and an operator, we're able to build an amazing deep and interesting construction, called a group.
Back when I started this blog, one of the first topics that I
wrote about was group theory. I was just looking back over that
series of posts, and frankly, they sort of…
goodmath | November 29, 2007 When last we left off, I'd used set theory to show how to construct the natural numbers; and then from the natural numbers, I showed how to construct the integers. Now, we can take the next step in building
up the full tower of numbers, showing how if we've got the natural numbers defined in sets, we can define
the rational numbers using sets and our constructed integers.
Before getting in to that, one question that generally strikes people around this level of
construction is that we've got a big stack of constructions here. We've got basic sets, which aren't numbers. We've got special…
goodmath | November 19, 2007 Even though this post seems to be shifting back to axiomatic set theory, don't go thinking that we're
done with type theory yet. Type theory will make its triumphant return before too long. But before
that, I want to take a bit of time to go through some basic constructions using set theory.
We've seen, roughly, how to create natural numbers using nothing but sets - that's basically what
the ordinal and cardinal number stuff is about. Even doing that much is tricky - witness my gaffe about
ordinals and cardinals and countability. (What I was thinking of is the difference between the ε…
goodmath | November 15, 2007 When Cantor's set theory - what we now call naive set theory - was shown to have problems in
the form of Russell's paradox, there were many different attempts to salvage the theory. In
addition to the axiomatic approaches that we've looked at (ZFC and NBG), there were attempts
by changing the basis of set theory - discarding sets in favor of something similar, but
with restrictions that avoid the problems of naive set theory. Today, I'm going to
talk about an example of the latter approach, called type theory. Type theory is a
very different approach from what we've seen before, and…
goodmath | November 11, 2007 I was visiting my mom, and discovered that I didn't leave my set theory book on the train; I left it at her house. So I've been happily reunited with my old text, and I'm going to get back to a few more posts about the beautiful world of set theory.
When you talk about set theory, you're talking about an extremely abstract notion, one which is capable of representing all sorts of structures: topological spaces, categories, geometries, graphs, functions, relations, and more. And yet, almost every description of set theory plunges straight into the cardinal and ordinal numbers. Why? That's a…
goodmath | September 6, 2007 Suppose you've got a huge graph - millions of nodes. And you know that it's not connected - so the graph actually consists of some number of pieces (called the connected components of the graph). And there are constantly new vertices and edges being added to the graph, but nothing is ever removed. Some questions you might want to ask about this graph at a particular point in time are:
How many components are there in the graph?
Which component is vertex X in?
Are vertices X and Y in the same component?
How many components are there?
All of these questions are variants of a classic…
goodmath | June 21, 2007So far, we've been talking mainly about the ZFC axiomatization of set theory, but in fact,
when I've talked about classes, I've really been talking about the von
Newmann-Bernays-Gödel definition of classes. (For example, the proof I showed the other day that the ordinals are a proper class is an NBG proof.) NBG is an alternate formulation of set
theory which has the same proof power as ZFC, but does it with a finite set of axioms. (If
you recall, several of the axioms of ZFC are actually axiom *schemas*, which need to
be distinctly instantiated for all possible predicates.) NBG uses one axiom…
goodmath | June 17, 2007With ordinals, we use exponents to create really big numbers. The idea is that we can define ever-larger families of transfinite
ordinals using exponentiation. Exponentiation is defined in terms of
repeated multiplication, but it allows us to represent numbers that we
can't express in terms of any finite sequence of multiplications.
As usual, the concept of ordinal exponentiation comes from a concept
of set exponentiation where the ordinal
αβ where α=|A| is the set of positions in
the well-ordering of Aβ; and Aβ is the
set of all ordered tuples of length β consisting of members of
A. (It…
goodmath | June 13, 2007I'll continue my explanation of the ordinal numbers, starting with a nifty trick. Yesterday, I said that the collection of all ordinals is *not* a set, but rather a proper class. There's another really neat way to show that.
Remember that we defined the ordinal 0 as the empty set, ∅, and every other ordinal a+1=a∪{a}. One obvious implication of this is that every ordinal b≤a is a member of a+1: in fact, a+1 is exactly the set of all ordinals ≤ a. So it's not just the case that every b≤a∈a+1, but every b≤a *is a subset* of a.
Imagine that it was possible to have a set S which is the set of all…
goodmath | June 12, 2007I've talked about the idea of the size of a set; and I've talked about the well-ordering theorem, that there's a well-ordering (or total ordering) definable for any set, including infinite ones. That leaves a fairly obvious gap: we know how big a set, even an infinite one is; we know that the elements of a set can be put in order, even if it's infinite: how do we talk about *where* an element occurs in a well-ordering of an infinite set?
For doing this, there's a construction similar to the cardinal numbers called the *ordinal numbers*. Just like the cardinals provide a way of talking about…
goodmath | June 11, 2007This is a short post, in which I attempt to cover up for the fact that I forgot to include some important stuff in my last post.
As I said in the last post, the cardinal numbers are an extension of the natural numbers, which are used for measuring the size of sets. The extended part is the transfinite numbers, which form a sequence of ever-larger infinities.
One major problem with adding the transfinite numbers is that natural number arithmetic doesn't work anymore with the cardinals. It still works for the natural number subset of the cardinals, but not for the transfinites.
But we *do* want…
goodmath | June 10, 2007One of the strangest, and yet one of the most important ideas that grew out of set theory is the idea of cardinality, and the cardinal numbers.
Cardinality is a measure of the size of a set. For finite sets, that's a remarkably easy concept: count up the number of elements in the set, and that's its cardinality. But there are interesting questions that we can ask about the relative size of different sets, even when those sets have an infinite number of elements. And that's where things get really fun.
We've already seen an example of how to compare the cardinality of different infinite sets:…
goodmath | June 7, 2007One of the reasons that the axiom of choice is so important, and so necessary, is that there are a lot of important facts from other fields of mathematics that we'd like to define in terms of set theory, but which either require the AC, or are equivalent to the AC.
The most well-known of these is called the well-ordering theorem, which is fully equivalent to the axiom of choice. What it says is that every set has a well-ordering. Which doesn't say much until we define what well-ordering means. The reason that it's so important is that the well-ordering theorem means that a form of inductive…
goodmath | June 6, 2007One of the things that we always say is that we can recreate all of mathematics using set theory as a basis. What does that mean? Basically, it means that given some other branch of math, which works with some class of objects O using some set of axioms A, we can define a set-based construction of the objects of S(O), and them prove the axioms A about S(O) using the axioms of ZFC.
Let's take a look at what that means, by showing how all of the proofs of number theory using natural numbers can be wrapped up in set theory.
First, we need to define the class of objects that we're going to talk…
goodmath | June 4, 2007Today, I'm going to try to show you an example of why the axiom makes so many people so uncomfortable. When you get down to the blood and guts of what it means, it implies some *very* strange things. What I'm going to do today is tell you about one of those: the Banach-Tarski paradox, in which you can create two spheres of size S out of one sphere of size S cutting the single sphere into pieces, and then gluing those pieces back together. Volume from nowhere, and your spheres for free!
As I said in the post on the axiom of choice, it was very controversial at first: controversial enough that…
goodmath | May 27, 2007The 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…
goodmath | May 24, 2007 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…
goodmath | May 23, 2007 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…
goodmath | May 23, 2007 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…
goodmath | May 20, 2007 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.
There's an interesting parallel between the axioms of ZFC and the axioms of Euclidean logic. Euclidean logic consists of a set of universally accepted rules, and one strange one - the parallel axiom…