Gracious Living


The Zermelo-Fraenkel Axioms for Sets
October 29, 2010, 13:17
Filed under: Math, Set Theory | Tags: , ,

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.

Table, Chair, Beer Mug

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.

From easiest to hardest:

  1. Extensionality.  Two sets are equal if they have the same elements. This is pretty much the definition of “set”; in terms of our naive picture, it means that reordering or duplicating the elements of a set doesn’t change it.
  2. Pairs.  Given two sets A,B, there is a set \{A,B\}. The curly-brace notation isn’t part of our atomic definitions, but it is easily expanded: the set \{A,B\} is the set such that A is an element of it and B is an element of it and if any set is an element of it, it is equal to either A or B.  This is unique by the axiom of extensionality.  Pair sets were “elementary” in Zermelo’s original formulation, but the axioms we’re using actually make this one totally useless, as we’ll see below.  Oh, by the way, if we let A=B, then this shows that \{A\} exists.
  3. Union.  Given a set A, there is a set \bigcup A whose elements are those sets B that are elements of some element of A. Of course, this is just our old definition of union of a set (and, remember, we get A\cup B=\bigcup\{A,B\}.
  4. Power sets.  Given a set A, there is a set \mathcal{P}(A) whose elements are those sets C such that every element of C is also an element of A. So C are subsets of A, and \mathcal{P}(A) is the power set we want.
  5. Specification.  Given a property \phi and a set A, there is a set B whose elements are those elements of A that have the property \phi. The term “property” here is kind of atomic, and is really a thing that gets defined in logic.  You should just think of it as something that sets either have or don’t have.  Being an element of a given set is a property, so specification lets us define intersection: given a set A, we define \bigcap A to be the specification of any element of A by the property “is an element of all the elements of A.”  In order to use this, you have to prove that it doesn’t matter which element of A you choose (not hard), and that you can choose elements in the first place (see below — for the record, I’m pretty sure we can avoid using choice here by formulating things in a more complicated way).
  6. Replacement.  Given a set A and a function \psi on sets, there is a set \psi(A) whose elements are the images under \psi of the elements of A. “Function” is, again, semi-atomic: we shouldn’t think of it as a subset of A\times something, but just as a rule that changes sets to other sets.
  7. Foundation.  Every set A contains an element that is disjoint from A (they do not share any elements). This is pretty weird-looking at first; basically it’s here to prevent Russell’s Paradox.  For example, if A\in A, then \{A\} has no element disjoint from it, because its only element, A, contains A.  So sets can’t contain themselves.  Likewise, if there is a chain of sets A_1\ni A_2\ni A_3\ni\dotsb, then \{A_1,A_2,\dotsc\} has no element disjoint from it, because each A_i contains A_{i+1}, which is in the set.  So no infinite descending sequence of sets like this can exist.  (Ascending sequences are easy to construct: just look at A,\{A\},\{\{A\}\},\dotsc.)
  8. Infinity.  The empty set exists.  There is a set N containing it, and with the property that for each A\in N, A\cup \{A\} is also in N. Foundation implies that A\ne A\cup A, so N must have an infinite number of members.  Note that the empty set is the first set we’ve explicitly defined!
  9. Choice.  Given a set A that does not contain \emptyset, there is a “choice function” sending each element of A to one of its elements. This is the “parallel postulate” of set theory.  It sounds confusing and defines a thing which you can’t, in general, construct naively.  As a result, mathematicians debated it for a while and some authors still warn you when they use it.  It’s worth its own post, so I won’t go into it more now; suffice it to say that this ugly statement is equivalent to the “obvious” statement that every infinite Cartesian product of nonempty sets has an element! (semi-hard problem: prove this).

So there you have it.  With these axioms, the whole of set theory is sculpted.  We’ve already defined unions, subsets, and intersections in our discussion.  Another good construction is the ordered pair: we define (a,b)=\{\{a\},\{a,b\}\}.  Try to prove that this is actually ordered: if \{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\}, then a=c and b=d.  Besides giving us all of our naive constructions, the Zermelo-Fraenkel axioms have the following properties:

The Banner of Set Theory

The Banner of Set Theory.

  • They are pure.  In set-theory language, this means everything they deal with is a set.  There are no atomic elements, like numbers, to be considered.  Soon, we’ll build numbers and arithmetic out of ZFC sets.  To turn-of-the century mathematicians, that you could even do this was very inspiring, as it meant that math could (in theory) be unified under a single banner: the banner of set theory.
  • It has no proper classes.  Later axiom-writers like Von Neumann wanted to be able to refer to “very large” general collections, like the collection of sets, that weren’t sets under ZFC.  Classes were invented for this purpose: they mostly work like sets, but it a proper class (a class that is not a set) cannot be an element of anything — it can only have elements.  So the “class of all sets” is actually well-defined, because, being proper, it is no longer an element of itself.  (Btw, why are proper classes “very large”?  Because a set can never map onto a proper class.  By the axiom of replacement, any image of a set is also a set.  Weirdly enough, they’re too large to even have a size.  We’ll talk about this soon.)
  • It is redundant.  Oh, yes.  I’ve actually made it more redundant in the interest of readability: the axioms of union, power sets, and replacement originally only defined a set containing all the required elements (so at least as big as the set you want).  You then use specification to cut down the set you have into the set you want.  Similarly, pairs can be derived by forming \mathcal{P}(A\cup B) and then using specification to get \{A,B\}.  Even specification is redundant: given a property \phi, define a function \psi on A by \psi(B)=B if B has property \phi, and \psi(B)=C for some C that has \phi if B does not have \phi.  Then by replacement, the image of this function, that is, the subset of A with \phi, is a set.  If no C has \phi, then we say C=\emptyset, using the axiom of infinity to assume the empty set.
  • It is irrelevant.  These days, the only people who work with set axioms are logicians and set theorists.  Foundations like these just aren’t important, because past a certain level of complexity, it becomes easiest to just think of an object’s own properties rather than those given by sets.  What Russell and others failed to foresee is that a set that contains itself is just so pathological (math speak for weird) that most math doesn’t even need to bother to avoid it!  So why am I teaching you this?  Because I think some people might enjoy it; it is sometimes comforting to know that there are always sets to depend on; and everybody should see it at least once, just to get a feel for super-formal axioms.

Hope you enjoyed.  I’m starting to do this to procrastinate, which is supah fun but probably not such a good idea.  In any case, next time I’ll either talk about cardinality or switch back to topology.

Advertisements

6 Comments so far
Leave a comment

[…] Gracious Living and the Two Meat Meal Just another WordPress.com site Skip to content HomeAboutTo Do ← The Zermelo-Fraenkel Axioms for Sets […]

Pingback by Cardinality | Gracious Living and the Two Meat Meal

[…] 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 […]

Pingback by Countability | Gracious Living and the Two Meat Meal

[…] 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 […]

Pingback by The Axiom of Choice | Gracious Living and the Two Meat Meal

[…] the set exists by the ZFC axioms […]

Pingback by Ordinals | Gracious Living and the Two Meat Meal

[…] Peano axioms for arithmetic are something like the Zermelo-Fraenkel axioms for sets.  They describe what we intuitively want to be true about the natural numbers.  Using ZFC, we […]

Pingback by Peano Arithmetic « Gracious Living

[…] increasing subsequence (well, that or a strictly decreasing one, which is impossible by the axiom of regularity), and then the limit of this is just its limit as an ordinal, that is to say, its union.  This is […]

Pingback by Limit Point and Sequential Compactness « Gracious Living




Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s



%d bloggers like this: