[17:01] <^LoNeR^> Tonight we have Evandar talking on The Cumulative Hierarchy of Sets
[17:02] <^LoNeR^> let's give him a big hand!
[17:02] * [-K-] applauds
[17:02] * trentrez claps
[17:02] * KimJ claps
[17:02] * vitriol wolf whistles
[17:02] <Evandar> Thanks everyone
[17:02] * ^LoNeR^ stomps his feet
[17:02] * toolro yawns :)
[17:02] * psilocin w00000ts
[17:02] * [sic] blows up a latex glove
[17:03] <Evandar> This talk comes primarily from a set of lectures given by Prof Wilkie at Oxford.  I'm assuming knowledge of a standard undergrad set theory course, including the ordinals, the Zermelo-Frankel axioms (ZF) and transfinite induction and recursion
[17:03] <Evandar> I'll start with some ideas from logic
[17:04] <Evandar> If S is any set of logical formulas, then a model of S is a concrete structure in which every formula in S is true.
[17:04] <Evandar> For example, a model of the axioms of a group is simply a group
[17:04] <Evandar> The set theory that we know and love is a model of the ZF axioms
[17:05] <Evandar> And so on
[17:05] <Evandar> A set of logical formulas is said (for this talk) to be consistent if it has a model
[17:05] <Evandar> So for example, the group axioms are consistent, since any group is a model of these
[17:06] <Evandar> Now, as a consequence of Godel's famous incompleteness theorem, we can never know whether ZF actually has a model
[17:06] <Evandar> But we assume it has one, in the same way as we assume that, say, the real numbers exist
[17:06] <Evandar> I will actually be working with the axioms of ZF without the axiom of foundation, which I will denote ZF-
[17:07] <Evandar> And I will be assuming that this has a model, which I will call V*
[17:07] <Evandar> So V* is the universe of all sets, and it contains all the usual sets - the natural numbers, the cardinals, the ordinals, and so on
[17:07] <Evandar> But it might also contain other sets, such as some set a where a={a}
[17:09] <Evandar> I also want to introduce the idea of a class.  A class is a collection of sets defined by a formula.  If phi(v) is some formula, then the class determined by phi is written {x : phi(x)}
[17:09] <Evandar> So for example, V* is a class: V* = {x : x=x}
[17:09] <Evandar> And any set is a class, for if a is a set then a = {x : x is in a}
[17:10] <Evandar> But not every set is a class; V* is not a set by Russell's paradox.
[17:10] <Evandar> A set that is not a class is called a proper class.
[17:10] <Evandar> Other proper classes are the class On of all ordinals, and the class Card of all cardinals, by the Burali Forti paradox.
[17:11] <Evandar> Questions so far?
[17:12] <vitriol> im curious why the name proper class is used
[17:12] <Evandar> I don't really know.
[17:13] <^LoNeR^> !
[17:13] <Evandar> Presumably someone at some time thought it sounded good
[17:13] <Evandar> Yes Loner?
[17:13] <^LoNeR^> The set of all sets being a set is actually called Cantor's Paradox
[17:14] <Evandar> Hmm.  I've actually never heard it being called that.  But I'll take your word for it.
[17:14] <Evandar> I'm assuming everyone here is familiar with the argument
[17:14] <[-K-]> !
[17:14] <Evandar> K?
[17:14] <[-K-]> I haven't heard of the Burali Forti paradox.
[17:14] <^LoNeR^> Russell's Paradox is that the class of all sets that do not have themselves as an element cosnttutes a set
[17:14] <trentrez> is that the same as russell's antimony?
[17:15] <^LoNeR^> yes
[17:15] <Evandar> [-K-]:  It says that the class of all ordinals is not a set.
[17:15] <[-K-]> I guessed that; I was wondering whether the proof is elementary.
[17:16] <Evandar> If the class of ordinals were a set, it would be a well-ordered set, and therefore would be order-isomorphic to some ordinal.  This means that it would be order-isomorphic to some initial segment of iteslf, which is impossible.
[17:16] <Evandar> itself
[17:17] <[-K-]> thx
[17:17] <Evandar> Some proper initial segment, perhaps I should say
[17:17] <Evandar> Ok, onwards.
[17:17] <Evandar> A class term is a fomula which behaves like a function.  That is, a formula F(u,v) is a class term iff for every set x there is a unique set y such that F(x,y) holds.
[17:18] <Evandar> And in this case we write "F(x) = y", rather than "F(x,y) holds"
[17:19] <Evandar> So with these definitions, we could restate the axiom of replacement as:  whenever F is a class term and a is a set, then the class {y : y=F(x) for some x in a} is a set.
[17:20] <Evandar> Now, I will need the recursion theorem for ordinals (transfinite recursion), and I'm going to give a restatement of it in terms of class terms.
[17:21] <Evandar> Theorem (Transfinite recursion).  Let F be a class term, and let a be a set.  Then there is a unique class term G:On -> V* such that G(0) = a, G(alpha+1) = F(G(alpha)) for all ordinals alpha, and G(delta) = Union_(alpha<delta) G(alpha) whenever delta is a limit ordinal.
[17:22] <Evandar> Proof is by transfinite induction and is omitted
[17:24] <Evandar> Now, for any set x let P(x) denote the power set of x.  Then F(x) = P(x) is a class term, and so we have a class term V:On -> V* such that V(0) = 0, V(alpha + 1) = P(V_alpha), and V(delta) = Union_(alpha<delta) V_alpha whenever delta is a limit ordinal.
[17:24] <Evandar> We write V_alpha for V(alpha)
[17:25] <Evandar> The 'union' of the V_alpha as alpha ranges over the ordinals will also (in a clear abuse of notation) be denoted V.  So x is in V if there is some ordinal alpha such that x is in V_alpha
[17:25] <Evandar> Questions?
[17:26] <Evandar> Either I'm doing a good job or I've lost everyone.  Ok.
[17:27] <[sic]> good so far
[17:27] <Evandar> Theorem:  For all ordinals alpha, the following hold:  (1) V_alpha is transitive.  (2) V_alpha is a subset of V_(alpha+1).  (3) alpha is in V_(alpha+1)
[17:28] <Evandar> Proof is by transfinite induction
[17:28] <Evandar> It's reasonably clear that all statements hold for alpha=0.
[17:29] <Evandar> I should perhaps remind you all what transitive means.  A set a is transitive iff whenever x is in a and y is in x, then y is in a.  Equivalently, whenever x is in a then x is a subset of a.
[17:30] <Evandar> Back to the proof.  Suppose statements 1-3 hold for alpha, and consider alpha+1.
[17:31] <Evandar> (1) I want to show V_(alpha+1) is transitive.  Suppose x is in V_(alpha+1) and y is in x.  Then x is a subset of V_alpha, since V_(alpha+1) = P(V_alpha), so y is a member of V_alpha.
[17:32] <Evandar> By inductive hypothesis 2, V_alpha is a subset of V_(alpha+1).  So y is in V_(alpha+1) as required.
[17:34] <Evandar> (2)  I want to show V_(alpha+1) is a subset of V_(alpha+2).  So suppose x is in V_(alpha+1).  Then x is a subset of V_alpha.  But then V_alpha is a subset of V_(alpha+1), by inductive hypothesis 2, so x is a subset of V_(alpha+1), and then x is a member of P(V_(alpha+1)) = V_(alpha+2)
[17:35] <Evandar> (3) By the inductive hypothesis, alpha is a member of V_(alpha+1).  But V_(alpha+1) is transitive by (1) above, so alpha is a subset of V_(alpha+1).
[17:36] <Evandar> Now alpha is a member of V_(alpha+1) and alpha is also a subset of V_(alpha+1), and this means (alpha union {alpha}) is a subset of V_(alpha + 1).
[17:37] <Evandar> Then (alpha union {alpha}) is a member of V_(alpha+2).  Also, (alpha union {alpha}) is alpha+1, so alpha+1 is in V_(alpha+2) as required.
[17:38] <Evandar> Since this is transfinite induction, it remains to check the case for limit ordinals, but this is considerably easier, and I'm not going to do it unless anyone wants me to.
[17:38] <Evandar> Questions?  Is anyone still following?
[17:39] <[sic]> yep following
[17:39] <^LoNeR^> ok here
[17:39] <Evandar> Ok, the people who knew all this already are following, which is something at least.
[17:40] <trentrez> I'm lost ;)
[17:40] <Evandar> Corollory: (1) V is transitive and contains all the ordinals.  (2) if alpha<beta then V_alpha is a subset of V_beta.
[17:40] <Evandar> Proof:  Immediate from the theorem above.
[17:42] <Fordibolo> what is zfc for? zaramelo-frenkel?
[17:43] <Evandar> The collection (V_alpha) is called the cumulative hierarchy of sets.  Or a cumulative hierarchy of sets, depending on whom you ask.
[17:43] <Evandar> Theorem:  V is a model of ZF.  That is, all of the ZF axioms hold in V.
[17:44] <Evandar> Proof is by checking all the axioms individually.
[17:44] <Evandar> I will do a couple of them.
[17:44] <Evandar> Lemma:  The axiom of pairing holds in V.
[17:46] <Evandar> Proof:  Let x,y be in V.  Then there are ordinals alpha and beta such that x is in V_alpha and y is in V_beta.  Let gamma = max(alpha,beta).  Then x,y are both in V_gamma (by the corollory above), so {x,y} is a subset of V_gamma, so {x,y} is a member of P(V_gamma) = V_(gamma+1)
[17:47] <Evandar> Now there is a subtle logical issue here.  Logical formulae do not necessarily mean the same things in V as they do in V*.  Therefore, in order to do this rigourously, I should write out the axiom of pairing as a logical formula, and check that it does in fact behave the way one would expect.
[17:48] <Evandar> But in fact, it does, and V is a sufficiently nice class for the potential logical problems not to trouble us.
[17:48] <^LoNeR^> !
[17:48] <Evandar> Yes loner?
[17:48] <^LoNeR^> I think you have two uses of V
[17:48] <Evandar> Where?
[17:49] <^LoNeR^> V as the class of all sets equal to themeselves and V as the union of the V_alpha
[17:49] <Evandar> I think I called that V* above
[17:49] <^LoNeR^> that those are equivalent is essentially regularity
[17:49] <^LoNeR^> ok
[17:49] <Evandar> > So for example, V* is a class: V* = {x : x=x}
[17:49] <^LoNeR^> my slip
[17:49] <^LoNeR^> sorry
[17:50] <Evandar> V* is our model of ZF-, ZF without foundation.
[17:50] <Evandar> Lemma:  The axiom of foundation holds in V
[17:51] <Evandar> Proof:  Let x be a nonempty member of V.  Given y in x, I know that y is in V, since V is transitive.
[17:51] <Evandar> I want to find y in x such that (y intersect x) = {}
[17:53] <Evandar> Now, given y in x, I can find some alpha such that y is in V_alpha.  Let beta = Min(alpha : alpha is an ordinal and there is some y in x such that y is in V_alpha)
[17:53] <Evandar> So beta is the minimum ordinal such that x intersects V_beta.
[17:54] <Evandar> I claim beta is a successor ordinal.  For clearly beta != 0.  And if beta is a limit ordinal, and y is in x and V_beta, then y must be in V_alpha for some alpha<beta, contradicting minimality of beta.
[17:55] <Evandar> So beta is a limit.
[17:55] <Evandar> Oopsy.  beta is a successor.
[17:56] <Evandar> So beta = gamma + 1 for some ordinal gamma.  Now V_beta meets x by assumption; let y be in V_beta intersect x.
[17:56] <Evandar> I claim y intersect x = {}, which is what we want.
[17:57] <Evandar> For y is in V_beta, and that means y is a subset of V_gamma.  If some set c were in the intersection of y and x, then c would be in V_gamma and c would be in x.
[17:57] <Evandar> But that would contradict the minimality of beta.
[17:57] <Evandar> So the axiom of foundation holds in V.
[17:57] <Evandar> Questions?
[17:59] <Evandar> Anyone mind if I run on 10 minutes?
[17:59] <^LoNeR^> fine by me :)
[17:59] <[sic]> nope this is great
[17:59] <Evandar> I mean, I don't have to.  I was gonna do the axiom of replacement as well.
[17:59] <Evandar> Ok
[18:00] <Evandar> Lemma:  The axiom of foundation holds in V.
[18:00] <Evandar> Proof:  Let a be a set and let F be a class term.
[18:00] <Evandar> Actually, let's call that set x, to be a bit more consistent.  Let x be a set and let F be a class term.
[18:01] <Evandar> I need F to be a class term on V, so that whenever y is in V then F(y) is in V.
[18:02] <Evandar> Now, by the axiom of replacement in V*, which holds by assumption, the class {z : z = F(y) for some y in x} is actually a set.  I want to show it's in V.
[18:02] <Evandar> Let y be in x.  Then F(y) is in V, so there is some ordinal alpha such that F(y) is in V_alpha.
[18:03] <Evandar> Let G be the class term defined on x such that G(y) is the least ordinal alpha such that F(y) is in V_alpha.
[18:04] <Evandar> Again by replacement in V*, the image of x under G is a set, and moreover it's a set of ordinals.  Let gamma be its union; so gamma is an ordinal.
[18:04] <Evandar> And F(y) is in V_gamma for all y in x.
[18:05] <Evandar> So {z : z = F(y) for some y in x} is a subset of V_gamma, and hence is a member of V_(gamma+1) as required.
[18:05] <Evandar> So the axiom of replacement holds in V.
[18:05] <Evandar> Lemma:  All the other ZF axioms hold in V.
[18:06] <Evandar> Proof:  Omitted.  The only really sticky one is the axiom of separation, which involves a bit of logic I don't want to go into.
[18:06] <Evandar> Hence, V is a model of ZF.
[18:07] <Evandar> Now, I assumed that ZF- was consistent, and took an arbitrary model of ZF-.  I then found within it a class which is in fact a model of ZF; this means, by definition that ZF is consistent.
[18:07] <Evandar> And hence:
[18:07] <Evandar> Theorem:  If ZF- is consistent, then ZF is consistent.
[18:07] <Evandar> And that's all folks.  Questions?
[18:08] * KimJ claps
[18:08] <[sic]> do you know the rank function?
[18:09] <Evandar> It's the function that maps x to the least ordinal alpha such that x is in V_alpha.  Or maybe it maps it to alpha+1.  I don't remember.,
[18:09] <[sic]> yeh, a lot of the argumentation comes down to rank
[18:10] <[sic]> this was really cool, btw
[18:10] <Evandar> I know, but it's not in the notes I'm working from, and I didn't really want to go through and rephrase everything.
[18:10] <^LoNeR^> Yep really nice intro, Evandar, I enjoyed it very much
[18:10] <Evandar> Thanks [sic], Loner
[18:10] <trentrez> good job Evandar
[18:10] <[sic]> rank(x) = least x s.t. x in V_alpha+1
[18:11] <[sic]> least alpha sorry
[18:11] <Evandar> Thanks trentrez