Seminar on Ordinals

This seminar was held in #mathematics on EFnet on 15th of March 2005 at 15:00 EDT by Kit.

It covered set theory: Proofs and constructions by finite and transfinite recursion: e.g the Cantor-Bendixson theorem, cardinality of sigma algebras and strange subsets of R^n.

A set of notes ( was also published by Kit.

Seminar log

20:08 <@Kit> I'm going to be providing an informal introduction to ordinals, one of the basic tools of modern set theory, and show how they can be used in mathematics in general.
20:09 <@Kit> I'll start by providing an informal definition and justification of the ordinals. I'm not going to prove they exist, because this would take too long and you'd probably find it uninformative.
20:09 <@Kit> The ordinals can be thought of as a generalisation of the natural numbers, so I'll start with a brief discussion of them.
20:09 -!- crot [] has joined #mathematics
20:10 <@Kit> Recall the peano axioms:
20:10 <@Kit> There is a natural number 0 and a function succesor, with the succesor of n denoted by n'
20:10 -!- _Hubris [pokey@Administrator.Org.Uk] has joined #mathematics
20:10 <@Kit> The axioms say that for all n, 0 != n'
20:10 <@Kit> If n' = m' then n = m
20:10 -!- x4nti [xantinderi@] has joined #mathematics
20:11 <@Kit> And if we have some subset A of the natural numbers which contains 0 and is closed under taking succesors then it is in fact the whole of N
20:11 <@Kit> This allows us to define various things on the natural numbers, including an order <
20:11 <@Kit> You can (and we shall) think of the succesor of n as the least natural number greater than n in this order
20:12 -!- mode/#mathematics [+l 74] by Evariste
20:12 <@Kit> The natural numbers prove to be the `right' setting on which to define the usual recursion theory.
20:12 <@Kit> We have the principle of recursive definition, which is as follows:
20:12 -!- R^^n [] has joined #mathematics
20:12 <@Kit> Suppose we've got a set X, a point x \in X and a function h : X -> X
20:12 -!- dV [] has joined #mathematics
20:13 -!- robcool [] has joined #mathematics
20:13 <@Kit> There is a unique function f : N -> N with f(0) = x and f(n') = h(f(n))
20:13 < dV> not started yet?
20:13 <@Kit> i.e. we have defined the function f recursively - we know what the base case is, and we have know how to reduce a case to the previous case
20:14 <@Kit> dV: Started about 5 minutes ago.
20:14 <@Galois> you mean f: N -> X
20:14 <@Kit> Yes, I do. Thanks.
20:15 -!- mode/#mathematics [+l 77] by Evariste
20:15 <@Kit> Anyway, this idea of recursive definition is a useful one because it lets us produce a lot of `algorithmic' processes which let us produce objects we want.
20:15 -!- fall__ [] has joined #mathematics
20:15 <@Kit> Euclid's algorithm is one example from number theory. I'll quickly give two more from algebra.
20:15 < azta> !
20:15 <@Kit> azta: Yes?
20:16 < azta> Kit: can I just tell the 7 or so people that joined late that I will paste whats happened so far to #math2 if they want to join
20:16 -!- poiko [] has joined #mathematics
20:16 <@Kit> Sure
20:16 < azta> :)
20:16 < panini> !
20:16 <@Kit> panini: Go on
20:16 < panini> so there is no guarantee that h is computable right?
20:16 <@Kit> Right
20:17 <@Kit> If f is computable then so is h
20:17 <@Kit> But this works for any f.
20:17 < panini> okey doke
20:17 <@Kit> Any more questions?
20:17 < Sex-Tazi> yes
20:17 <@Kit> ok
20:17 <@Kit> Go on
20:17 < Sex-Tazi> could u repeat the definitions of h and f
20:17 < Sex-Tazi> i got confused with the correction
20:18 -!- mode/#mathematics [+l 79] by Evariste
20:18 <@Kit> ok. X is some set. x \in X. h : X -> X
20:18 -!- haklaf [] has joined #mathematics
20:18 <@Kit> There is a unique function f : N -> X with f(0) = x and f(n') = h(f(n))
20:18 -!- mode/#mathematics [+o landen] by Evariste
20:18 <@Kit> Make sense now?
20:19 < Sex-Tazi> yes.. thanks
20:19 <@Kit> ok
20:19 <@Kit> So, first example from algebra.
20:19 <@Kit> Let V be a finite dimensional vector space
20:19 <@Kit> We want to find a basis of V
20:20 <@Kit> We define a process as follows:
20:20 <@Kit> Let B_0 = \emptyset
20:21 -!- landen changed the topic of #mathematics to: Late Arrivals: what you missed is at #math2. Ask about seminar rules in #math
20:21 <@Kit> Having picked B_n, if B_n spans V then we stop. If not then let B_{n+1} = B_n u x_{n+1} where x_{n+1} is some point not in B_n
20:21 <@Kit> This doesn't strictly speaking follow the definition of recursion I've set up above, but it's the same sort of idea
20:21 <@Kit> If we were being pedantic and formal we could convert it into that form
20:21 <@Kit> But I'd rather not. :)
20:21 <@Galois> x_{n+1} is some point not in span(B_n)
20:21 <@Kit> Yes.
20:22 <@Kit> Sorry. Still a wee bit out of it. Thanks for the catches - hopefully the error rate will go down as I progress.
20:22 <@Kit> Anyway, because V is finite dimensional this process eventually terminates
20:22 <@Kit> And we end up with a linearly independent spanning set. i.e. a basis.
20:23 <@Kit> Second example. Suppose we have a noetherian ring R
20:23 <@Kit> We will show that R has a maximal ideal
20:23 <@Kit> (This is all rather trivial I know, it's just to illustrate some ideas)
20:24 -!- tacojoe [] has joined #mathematics
20:24 <@Kit> Proof: Suppose not. We can construct a sequence of ideals I_n with I_n < I_{n+1}
20:24 -!- peano [] has joined #mathematics
20:24 <@Kit> Because each I_n is not maximal
20:24 <@Kit> Contradicting the noetherian condition
20:25 <@Kit> Now, lets look at some features of the above examples.
20:25 -!- SftBoots [] has joined #mathematics
20:25 <@Kit> In the first two cases we knew that the processes must terminate.
20:25 <@Kit> In the first example this was due to the underlying structure of N
20:25 -!- unsocial [unsocial@] has joined #mathematics
20:25 <@Kit> In the second it was due to a finiteness condition on the vector space.
20:26 <@Kit> What do we do when the natural construction turns out to not terminate?
20:26 <@Kit> For example suppose we had an infinite dimensional vector space V
20:26 <@Kit> Then our construction of the B_n would produce an infinite increasing sequence of linearly independent sets B_n
20:26 <@zeno> well, if it's countable-dimensional you might just get lucky
20:26 <@Kit> zeno: Yes. I'm about to come to that. :)
20:27 -!- mode/#mathematics [+l 84] by Evariste
20:27 -!- wtbw [] has joined #mathematics
20:27 <@Kit> So the natural thing to do is to take the union of the B_n
20:27 <@Kit> As zeno says, we mike get lucky if V is finite dimensional. Suppose e_1, ... , e_n, ... was a basis for our vector space.
20:27 <@Kit> Then we might well pick B_n = { e_1, ... , e_n }
20:27 <@Kit> In which case happily the union of the B_ns is a basis
20:28 <@Kit> But we could equally well pick B_n = { e_2, ... , e_{n+1} }
20:28 <@Kit> In which case it wouldn't be
20:28 <@ramanujan> !
20:28 <@Kit> ramanujan: Yes?
20:28 <@Kit> (Oh good. You did make it in the end)
20:28 <@ramanujan> how are you defining a countable dimensional vector space without fixing a basis?
20:29 <@Kit> ramanujan: I'm fixing a basis. :)
20:29 <@ramanujan> so we are fixing a basis and then showing a basis exists?
20:29 <@Kit> No
20:29 <@Kit> I'm showing that if we had an infinite dimensional vector space the naive way of picking it might not work
20:30 <@Kit> This is just with a particular infinite dimensional vector space - it's not supposed to draw a general conclusion yet
20:30 <@ramanujan> okay, sorry, I misread. go o
20:30 <@Kit> (I'll prove that bases exist once I've actually defined the ordinals0
20:30 < fiesh> (is this going to be over constructing the Borel sets via union over all countable ordinals, thus seeing have the same cardinality as R, in contrast to the Lebesgue sets?)
20:30 -!- jrt [] has quit [Read error: Connection reset by peer]
20:30 <@Kit> fiesh: You're getting way ahead of me now. :)
20:30 <@Kit> Shh. You'll spoil the surprise for everyone else
20:30 < fiesh> Kit: I just wonder since I won't have time to listen to all of it probably, so I'm curious ;)
20:30 <@Kit> fiesh: ok. Yes then.
20:30 <@Kit> Now shh.
20:30 < fiesh> okok, thanks
20:31 < fiesh> aye!
20:31 <@Kit> Now where was I...
20:31 <@Kit> Oh yes
20:31 -!- jrt [] has joined #mathematics
20:31 <@Kit> Anyway, we've taken the union of the B_n and got the span of e_n for n >= 2
20:31 <@Kit> So we can repeat our process and just add in e_1
20:31 <@Kit> And yay a basis
20:32 <@Kit> But equally we could have picked only the even e_n, and so needed to take a union again.
20:32 <@Kit> A little imagination will convince you that we might need to take infinitely many unions
20:32 -!- SftBoots [] has left #mathematics []
20:32 <@Kit> So we obviously need some clever trick if this is going to work for even the simplest infinite dimensional spaces!
20:32 <@Kit> Similarly with our ring example
20:33 <@Kit> We have the noetherian condition which says that a certain type of nested collection of ideals can't exist
20:33 <@Kit> But what if we don't have that condition?
20:33 <@Kit> We can again take the union and keep going.
20:33 <@Kit> But we don't know how far we can keep going, or indeed if we can even keep going with this forever (whatever that's supposed to mean if it doesn't just mean infinitely many times!)
20:34 <@Kit> One more example and then I'll go on to actually define the ordinals. :)
20:34 <@Kit> Suppose we've got some big infinite group G
20:34 <@Kit> And some finite or countable subset X
20:34 <@Kit> We want to look at the group generated by X and show that it's countable (e.g. if we want to show that X does not generate the group and G is uncountable)
20:35 <@Kit> So we define X_0 = X u {e}
20:35 <@Kit> This is still countable
20:35 <@Kit> And X_{n+1} = X_n u { x^{-1} : x \in X_n } u {xy : x, y \in X_n}
20:35 <@Kit> By induction X_n is countable
20:35 <@Kit> So the union X_n is countable
20:35 <@Kit> And it is clear tha the union X_n is in fact the group generated by X_n
20:36 <@Kit> err. generated by X
20:36 <@Kit> and union of X_n
20:36 <@Kit> Sorry
20:36 <@Kit> This is because if x \in U X_n then it's in X_n for some n and so x^{-1} is in X_{n+1}
20:36 -!- toad__ [] has joined #mathematics
20:37 <@Kit> And if x, y are in the union then they're in X_m and X_n respectively, so both in X_{max(m, n)} and so xy \in X_{max(m, n) + 1}
20:37 <@Kit> But what would we do if we had a countable operation?
20:37 <@Kit> err. Rather one that takes countably many arguments
20:37 <@Kit> e.g. suppose we had a sigma algebra being generated
20:37 -!- isleepina [~adfs@] has joined #mathematics
20:37 <@Kit> Or a subset of a ring of formal power series (note that we don't require the operation to be defined for all arguments, as in this example)
20:38 <@Kit> How could we get a similar cardinality estimate for the generated group?
20:38 <@Kit> All the answers to these questions shall be revealed shortly... :)
20:39 -!- mode/#mathematics [+l 86] by Evariste
20:39 <@Kit> I shall describe the ordinals with a set of axioms similar to the peano axioms.
20:39 <@Kit> Rather than in terms of a succesor I will describe them in terms of the order relation <
20:40 <@Kit> First there is a least ordinal 0
20:40 <@Kit> The ordinals have the order relation < which is a strict total order
20:40 -!- tol [] has quit [Ping timeout: 182 seconds]
20:40 <@Kit> For any ordinal x there is an ordinal x' which is the least ordinal greater than x
20:41 <@Kit> And for any *set* of ordinals A there is an ordinal which is a least upper bound for A
20:41 <@Kit> This last axiom is what lets us formalise things like in the above where we were taking unions when our process didn't terminate
20:41 <@Kit> And finally we have the induction axiom:
20:42 <@Kit> Suppose there's a collection of ordinals, containing 0, closed under taking succesors and containing the supremum of every one of its subsets.
20:42 <@Kit> Then this collection contains every ordinal
20:42 -!- isleepin^ [~adfs@] has joined #mathematics
20:42 <@Kit> You may notice I slightly dodged around some terminology there
20:42 < panini> !
20:42 <@zeno> ( the fact that x' happens to simply be the set x u {x} is elegant but of no consequence in Prof. Kit's discussion)
20:42 <@Kit> panini: Yes?
20:42 < panini> any *finite* set, right?
20:42 <@Kit> No
20:42 <@Kit> Very much not so
20:43 -!- tol [] has joined #mathematics
20:43 <@Kit> If it were merely any finite set then it would just be the natural numbers
20:43 <@Kit> So we wouldn't have anything new
20:43 < panini> i meant for the least upper bound axiom
20:43 <@Kit> Yes. So did I.
20:43 <@Kit> This is the whole point. In the above vector space example what I wanted to do was you iterate by taking succesor to start with, and you don't reach the end. Then you take the least upper bound of all the ones you've done so far and take the union of the sets you've produced.
20:44 -!- isleepina [~adfs@] has quit [Ping timeout: 360 seconds]
20:44 <@Kit> The least upper bound axiom for arbitrary sets is what means we can `go on for ever' in a way that produces all the results we need.
20:44 < panini> ok thanks
20:44 <@Kit> No problem.
20:45 <@Kit> Lets see. tum ti tum. Oh yes, collections and sets.
20:45 <@Kit> There cannot in fact be a set of all ordinals.
20:45 <@Kit> Suppose there were: Let x be its supremum.
20:45 <@Kit> Then x is >= every ordinal
20:45 <@Kit> So x >= x'
20:45 <@Kit> But x' > x
20:45 <@Kit> Contradiction
20:45 < Sex-Tazi> russel's paradox
20:46 <@Kit> Sex-Tazi: Not quite, but similar
20:46 <@Kit> This is important.
20:46 <@Kit> Certain collections are `too big' to be sets
20:46 <@Kit> We call them proper classes
20:46 < ch0ni> sex-tazi: burali-forti paradox
20:46 < Sex-Tazi> kit paradox :)
20:47 < Sex-Tazi> sorry go on
20:47 <@Kit> Look, I don't want to be grumpy, but could people keep it down and reserve speaking to questions indicated by ! or talking in #math?
20:47 <@Kit> It's a bit distracting. :)
20:47 <@Kit> Thanks.
20:48 <@Kit> Anyway, in a proper formal treatment I would go into the difference between sets and classes
20:48 <@Kit> I don't intend to here. That's as much of a definition as you're going to get. :)
20:48 <@Kit> I will also have functions, etc. defined on classes without worrying about this unduly
20:49 <@Kit> Anyway. The above is actually a really important point, because it gives us our main lemma:
20:49 <@Kit> There is no injective function from the ordinals into any set
20:49 <@Kit> Proof: If there were then they would biject with a subset of that set. So they certainly can't be too big to be a set.
20:49 <@Kit> (This is rather handwavy - really what I'm doing is applying something called the axiom of replacement. You don't need to know about this)
20:50 -!- isleepin^ [~adfs@] has quit []
20:50 <@Kit> This, together with the several other lemmas about the ordinals and functions on them, will give us pretty much all we need to work with transfinite processes.
20:51 <@Kit> Oh. I should quickly restate the induction axiom for the ordinals.
20:51 <@Kit> It can equally well be restated as `Let A be a collection of ordinals such that for any x if \forall y < x \in A then x \in A. Then A contains all of the ordinals.'
20:52 -!- docuk2 [] has joined #mathematics
20:52 <@Kit> Proof: Such a set contains 0, because there are no ordinals y with y < 0
20:53 <@Kit> Argh. Sorry. Temporary brain hiccup. This is really obvious. :)
20:53 <@Kit> In fact my original statement of the induction axiom was stupid. Lets just take the above as the definition.
20:53 -!- JoachimsM [] has joined #mathematics
20:53 <@Kit> (Sorry)
20:54 <@Kit> (Feel free to yell at me for that. :)
20:54 <@Kit> Anyway. Having had my embarassing cockup for this seminar I should hopefully not have any more. Honest.
20:54 <@Kit> We now want to prove an analogue of the recursion theorem.
20:55 <@Kit> For this we'll need a few other results first in order to make sense of some things.
20:55 <@Kit> Let x be an ordinal. Then the collection of ordinals less than x is actually a set.
20:56 <@Kit> Proof: Let A be the class of ordinals x such that the collection of ordinals less than x is a set.
20:56 -!- divinity- [] has joined #mathematics
20:56 <@Kit> Then 0 is certainly in A
20:57 -!- mode/#mathematics [+l 88] by Evariste
20:58 <@Kit> and... it all falls to pieces around Kit. Hold on while I stop and think about this for a moment.
20:58 <@Kit> I spent too much time thinking about the later bits and didn't sort out the details of this. :)
20:58 -!- landen changed the topic of #mathematics to: Late Arrivals: There is a growing log by azta at
20:58 -!- cyby`` [] has joined #mathematics
20:58 <@Kit> My apologies to everyone
20:58 -!- mode/#mathematics [+o cyby``] by NullPtr
20:59 <@Kit> Ah ha
20:59 <@Kit> I understand why I've got myself confused. I'm doing this out of order.
20:59 <@Kit> Start with my original definition of the induction axiom after all.
20:59 < JoachimsM> OMG LECTURE SUXX0RS!
20:59 -!- JoachimsM [] has left #mathematics []
20:59 <@Kit> Now I want to prove that the collection of ordinals less than x is a set.
21:00 <@Kit> As above, 0 is a set.
21:00 -!- lsmsrbls [lsmsrbls@D006132.N1.Vanderbilt.Edu] has quit [Ping timeout: 513 seconds]
21:00 <@Kit> Suppose the collection of ordinals < x is a set. Then the collection of ordinals < x' is { y : y < x} u {x}
21:00 <@Kit> Because x' is the least ordinal > x
21:00 <@Kit> So it's the union of two sets and so a set.
21:00 <@Kit> Now suppose we have some set of ordinals A
21:01 <@Kit> Then the collection of ordinals < sup A is union_{x \in A} { y : y < x }
21:01 <@Kit> So it's a union of a set of sets, and so a set.
21:01 -!- divinity- [] has left #mathematics []
21:01 -!- toad__ [] has left #mathematics []
21:02 <@Kit> Thus by the induction axiom this collection is all of the ordinals.
21:02 <@Kit> Now from this we should be able to prove the other form of the induction axiom relatively easily.
21:02 <@Kit> Suppose A is a collection with the property that \forall y < x, y \in A => x \in A
21:03 -!- mode/#mathematics [+l 85] by Evariste
21:03 -!- cyby [] has quit [Read error: Connection reset by peer]
21:03 -!- cyby`` is now known as cyby
21:03 <@Kit> ... No. I'm just being a moron at the moment. This really should be obvious. I blame end of turn burnout and hope this doesn't cause you all to hate the subejct from now unto eternity. :) `s my own bloody fault for using a non-standard approach.
21:04 <@Kit> Excuse me while I cringe in embarassment and then carry on.
21:04 <@Kit> Anyway... Having failed to prove this, I'm going to assume it anyway.
21:04 -!- lsmsrbls [lsmsrbls@D006132.N1.Vanderbilt.Edu] has joined #mathematics
21:05 <@Kit> *now* lets prove an analogue of the recursion theorem
21:05 <@Kit> Which hopefully I can do.
21:05 <@Kit> First a definition:
21:05 <@Kit> Let a be an ordinal
21:05 <@Kit> A sequence in X of length a is a function from { y : y < x } into X
21:06 -!- tacojoe [] has left #mathematics []
21:06 <@Kit> While we're at it a few more definitions and observations I should have included earlier but didn't because I was getting flustered. :)
21:06 <@Kit> Sets of the form { y : y < x } are called initial segments
21:06 <@Kit> Further we can define a function from N into the ordinals as follows.
21:06 <@Kit> Send the 0 of n to the 0 of the ordinals
21:06 <@Kit> of N
21:06 <@Kit> i.e. f(0) = 0
21:07 <@Kit> And also define f(n') = f(n)'
21:07 <@Kit> Where succesor on the left is in the naturals, on the right in the ordinals
21:07 <@Kit> This is an injective map, and it is an order isomorphism onto its image.
21:07 <@Kit> So we can identify N with a subset of the ordinals.
21:07 <@Kit> Further taking the sup of N, which we will call \omega
21:08 <@Kit> Then N = { y : y < \omega }
21:08 <@Kit> So the natural numbers are an initial segment of the ordinals
21:08 <@Kit> (up to isomorphism)
21:08 <@Kit> Initial segments correspond to the notion of `what we've done so far'
21:08 <@Kit> So this helps confirm the notion of ordinals extending the types of processes we can do via N.
21:09 <@Kit> Now. Finally the recursion theorem I've been promising. :)
21:09 < panini> !
21:09 <@Kit> panini: Yes?
21:09 < panini> sorry for being dense, but i'm confused on a couple of things so far:
21:10 <@Kit> No worries. As the above indicates, so am I. ;)
21:10 < panini> 1. is it supposed to be obvious at this point that there exist non-successor ordinals?
21:10 <@Kit> It's moderately obvious, but I should have mentioned that. Thank you.
21:11 <@Kit> \omega is the simplest example of a non succesor ordinal
21:11 <@Kit> Because if x < \omega then x is a natural number.
21:11 <@Kit> So x' is also a natural number and thus < \omega
21:11 <@Kit> So \omega can't be the succesor of anything
21:11 -!- ^LoNeR^ [] has quit [Ping timeout: 513 seconds]
21:11 -!- dedekind [] has quit [Ping timeout: 513 seconds]
21:12 -!- mode/#mathematics [+l 82] by Evariste
21:13 <@Kit> Next question? :)
21:13 <@Kit> Or is the above still not clear?
21:13 < panini> ok. and that's why the "<" is not being defined in terms of successor?
21:13 <@Kit> Yes
21:13 < panini> ok, cool. thanks
21:14 <@Kit> Sorry, should have made that clearer at the beginning. I'm using both ' and <, as we do in N. But in N we've defined < in terms of ' while for the ordinals its the other way around
21:14 <@Kit> Anything else?
21:14 < panini> nope, i'm good for now :)
21:14 <@Kit> ok
21:14 <@Kit> The fact that not everything is a succesor is actually why things are slightly more complicated
21:15 <@Kit> (in the recursion theorem that is)
21:16 <@Kit> We denote X^(a) to be the set of sequences in X of length a, and X^(ord) to denote the collection of all sequences on X
21:16 <@Kit> Suppose we have a function h : X^(ord) -> X
21:16 <@Kit> i.e. given any sequence on X it gives us an element of X
21:17 <@Kit> There is a unique function f : Ord -> X such that for any ordinal a, f(a) = h( f|_{x : x < a} )
21:17 <@Kit> (Because f restricted to {x : x < a} is exactly the sort of thing we mean by a sequence of lenght a, this makes sense)
21:17 <@Kit> Note that this includes having a starting point.
21:17 -!- ^LoNeR^ [] has joined #mathematics
21:18 <@Kit> The starting point is just h( the empty sequence )
21:18 <@Kit> Where the empty sequence is a sequence of length 0
21:18 <@Kit> However normally when defining our h we end up breaking it into three cases: 0, succesor ordinals and non-succesor ordinals.
21:18 < grim^> whoa, im a little lost, can we start all over?
21:18 <@Kit> Non-succesor ordinals are called limits.
21:18 <@Kit> grim^: ... From which point?
21:19 < grim^> oh wait, I see now
21:19 < grim^> nevermind
21:19 <@Kit> ok
21:19 <@Kit> (Thought for a moment you were asking me to start right from the beginning. This would not have amused me. ;) )
21:19 < grim^> heh
21:19 <@Kit> Seriously though, is that relatively clear?
21:19 < grim^> yea
21:20 <@Kit> Essentially the idea is that we've defined f for all y < x and h gives us a way to define f(x) in terms of what we've done so far.
21:20 -!- Hurwitz [] has quit [Connection closed]
21:20 <@Kit> The proof of this is essentially that you consider the collection of ordinals x such that there is a unique function defined on { y : y <= x } satisfying this condition
21:20 <@Kit> You use the induction axiom to show that this collection consists of all the ordinals
21:21 <@Kit> Then you let f_x be the unique function defined on { y : y <= x } with this property
21:21 <@zeno> May I just give a naive picture (for grim or whoever)? The first several ordinals in order are: 0 < 1 < 2 < ... omega < omega+1 < omega_2 < ... 0 is not a successor and not a limit; everything in {1,2,3,...} is a successor; omega is a limit
21:21 <@zeno> (not a successor, not 0).
21:21 <@Kit> And define f(x) = f_x(x)
21:21 -!- Hurwitz [] has joined #mathematics
21:21 -!- mode/#mathematics [+o Hurwitz] by Thwash
21:21 -!- mode/#mathematics [+o Hurwitz] by bananach, Faisceaux, Evariste
21:21 <@Kit> zeno: Sure. Thanks.
21:21 <@Kit> Although you mean omega+2 rather than omega_2
21:22 <@zeno> oops, yeah
21:22 <@zeno> and all those omega+n (n in {1,2,3,...}) are successors
21:22 <@Kit> Side note: there is a notion of ordinal arithmetic in which omega + 2 makes sense, but it's probably best to just think of it as notation at this stage.
21:22 <@Kit> Alright. Having waved my hands and embarassed myself through the irritating preliminaries about ordinals, lets prove some stuff. :)
21:23 <@zeno> sorry, I should have probably written omega' , omega , etc. (/me shuts up now)
21:23 <@Kit> Theorem: Every vector space has a basis.
21:23 <@Kit> Proof: Suppose not. Then no linearly independent set spans.
21:23 < fiesh> (what's the problem with omega+2? just ordinal arithmetic)
21:23 <@Kit> Let V be a vector space without a basis. We define a function f : Ord -> V by recursion
21:23 <@Kit> Beg pardon. f : Ord -> P(V)
21:23 <@Kit> fiesh: I just haven't defined ordinal arithmetic
21:23 < fiesh> ok
21:24 <@Kit> We start with f(0) = 0
21:24 <@Kit> Hmm. In fact in order to make the notation convenient, f : Ord -> \{ Linearly independent subsets of V }
21:24 <@Kit> Now, suppose we've defined f(x)
21:25 <@Kit> Then f(x) is a linearly independent subset of V
21:25 <@Kit> So it doesn't span by hypothesis
21:25 <@Kit> So pick some element x not in span(f(x))
21:25 <@Kit> err
21:25 <@Kit> That was horrible. :)
21:25 <@Kit> So pick some element v not in span(f(x))
21:25 <@Kit> Then f(x') = f(x) u {v}
21:26 <@Kit> By construction f(x') is linearly independent
21:26 <@Kit> And for limits, take unions. i.e. if x is not a succesor then f(x) = Union_{y < x} f(y)
21:26 <@Kit> Now, notice that if x < y then f(x) is strictly contained in f(y)
21:26 <@Kit> So what we've done is constructed an injective function from the ordinals into P(V)!
21:27 <@Kit> This can't happen
21:27 <@Kit> (As we said above)
21:27 <@Kit> So this process must eventually terminate. We must have some point x where f(x) actually spans
21:27 <@Kit> So is a basis.
21:27 <@Kit> Hence every vector space has a basis
21:28 <@Kit> You'll see in a moment this is really just the standard zorn's lemma proof wrapped up in fancy clothing. It's just to get the idea.
21:28 <@Kit> Exactly the same proof will show that every ring has a maximal ideal
21:29 <@Kit> So we've at the very least proved what we set out to do. :)
21:29 <@Kit> Lets look at some other similar things:
21:29 -!- haklaf [] has quit []
21:29 <@Kit> Theorem: Every set bijects with some initial segment of the ordinals.
21:30 <@Kit> Proof: Suppose X does not. Then every injective function from an initial segment of the ordinals into X is not surjective
21:30 <@Kit> We will use this to define an injective function from the ordinals into X
21:31 <@Kit> Suppose we've defined f(y) for y < x and f is injective on { y : y < x }
21:31 <@Kit> Then it's not surjective
21:31 <@Kit> So we define f(x) by picking some elemement of X not in the image of { y : y < x}
21:31 <@Kit> So we've defined f(x) and it's still injective. Hence we have an injective function from the ordinals into X, etc.
21:32 <@Kit> Good lord. I haven't proved the ordinals are well ordered yet, have I?
21:32 <@Kit> Note to self: Prepare some damn notes next time you give a seminar.
21:32 <@Kit> Anyway, the proof is easy enough.
21:33 <@Kit> Suppose A is a set of ordinals with no least element
21:33 -!- koro- [] has quit [Ping timeout: no data for 247 seconds]
21:33 <@Kit> We will show by induction that for all ordinals x, x is not in A
21:33 <@Kit> Suppose for all y < x, y is not in A. Then if x were in A then it would be the least element of A, which doesn't exist by hypothesis.
21:33 <@Kit> So A is empty, and thus the ordinals are well ordered.
21:34 <@Kit> Ahem. Sorry, minor derailment of train of thought.
21:34 <@Kit> ::ahem::
21:34 <@Kit> The point of the previous theorem is twofold: It proves every set can be well ordered, and it proves that there is an initial segment of the ordinals of every cardinality
21:35 <@Kit> In particular there are uncountable initial segments of the ordinals
21:35 <@Kit> This gives us quite a useful ordinal. omega_1 is the least ordinal x such that {y : y < x} is uncountable.
21:35 -!- Elric- [] has quit []
21:35 <@Kit> I'll show in a moment exactly *why* this is a useful ordinal. :)
21:35 <@Kit> Before I do, any questions?
21:36 <@Kit> Guess not.
21:36 -!- LoNeR^ [] has joined #mathematics
21:36 -!- LoNeR^ [] has left #mathematics []
21:37 <@Kit> Alright. First of all, it is clear that omega_1 is not a succesor ordinal
21:37 <@Kit> Because if omega_1 = x' then {y : y < omega_1} = {x} u {y : y < x}
21:37 <@Kit> So {y : y < x} is uncountable
21:38 <@Kit> Ordinals smaller than omega_1 are called the countable ordinals. Note that if x is a countable ordinal then {y : y < x} is countable
21:38 <@Kit> (Because omega_1 was the least ordinal such that those sets are uncountable)
21:39 <@Kit> For now I'm going to define Omega_1 = { y : y < omega_1}. This is an entirely non-standard definition.
21:39 <@zeno> (if I may:) The way that omega_1 is uncountable but every ordinal < omega_1 is countable is analogous to how omega is infinite (countable) but every ordinal x < omega is finite.
21:40 <@Kit> Right
21:40 -!- koro- [] has joined #mathematics
21:40 <@Kit> Suppose A is a countable subset of Omega_1. Then A has an upper bound in Omega_1. Proof: If not, then Omega_1 = Union_{x \in A} {y : y < x }
21:40 <@Kit> So it is a countable union of countable sets, and so countable.
21:40 <@Kit> Contradicting that Omega_1 is uncountable
21:41 <@Kit> Now, lets return to another example from the beginning. That of a sigma algebra.
21:41 -!- tol [] has quit [Ping timeout: 182 seconds]
21:41 <@Kit> In particular lets look at the borel sigma-algebra on R
21:42 <@Kit> Let B_0 = { [a, b] : a <= b, a, b \in R }
21:43 <@Kit> Then the borel sets are the sigma-algebra generated by B_0
21:43 -!- lsm [lsmsrbls@D007143.N1.Vanderbilt.Edu] has joined #mathematics
21:43 <@Kit> We shall define an ordinal sequence of sets B_x
21:43 <@Kit> (In fact we'll only need it for x < omega_1, but the definition will work for all x)
21:43 <@Kit> B_0 is as above
21:44 <@Kit> Having defined B_x, B_{x'} is B_x u { A^c : A \in B_x } u { UA_n : A_1, ... , A_n, \in B_x }
21:44 <@Kit> And take unions and limits
21:45 <@Kit> at
21:45 -!- struct_ [] has joined #mathematics
21:45 <@Kit> This is analogous to what we were doing with the group generated by a set earlier
21:45 <@Kit> Now, I claim that the borel sets are U_{x < omega_1} B_x
21:46 < fiesh> (wouldn't you want to use Q in your definition of B_0?)
21:46 <@Kit> No
21:46 <@Kit> There's going to be uncountability entering into it anyway, so it doesn't matter
21:46 <@Kit> It will just shunt where some of the sets are appearing
21:46 < fiesh> hmm yeah right
21:47 <@Kit> (All of the intervals of the form [a, b] would be appearing in B_1 in your definition)
21:47 <@Kit> First of all the easy part. Suppose A \in U B_x
21:47 <@Kit> Then A \in B_x for some x < omega_1, so A^c \in B_{x'}
21:47 -!- [1]panini [~panini@] has joined #mathematics
21:48 <@Kit> Now, suppose A_1,... , A_n , ... \in U B_x
21:48 <@Kit> Then we can find x_n with A_n \in B_x_n
21:48 <@Kit> By my above remark the set { x_n } has an upper bound in Omega_1
21:48 -!- tol [] has joined #mathematics
21:48 <@Kit> Thus we can find some y < omega_1 with all the A_n \in B_y
21:49 <@Kit> So UA_n \in B_{y'}
21:49 <@Kit> So U B_x is a sigma algerba
21:49 <@Kit> algebra
21:49 <@Kit> It will take little work to convince you that it's the smallest one
21:50 <@Kit> Suppose that S is a sigma algebra containing B_0, then we can prove by induction that for all x, B_x <= S
21:50 <@Kit> Now, this will give us the cardinality of the set of borel sets
21:50 -!- vaidhy [~vaidhy@] has joined #mathematics
21:50 <@Kit> We first show by induction that |B_x| = |R|
21:50 <@Kit> |B_0| = |R|
21:50 -!- panini [~panini@] has quit [Ping timeout: 260 seconds]
21:50 -!- [1]panini is now known as panini
21:51 -!- mode/#mathematics [+l 84] by Evariste
21:51 <@Kit> If |B_x| = |R| then B_{x'} is the union of three sets, each of which have cardinality |R|
21:51 <@Kit> (The only one of these which is in doubt is the countable unions one, and this follows from |R^N| = |R|)
21:52 -!- lsmsrbls [lsmsrbls@D006132.N1.Vanderbilt.Edu] has quit [Read error: Operation timed out]
21:52 <@Kit> So the borel sets are a union of |Omega_1| sets of cardinality |R|
21:52 <@Kit> So have cardinality <= |Omega_1||R|
21:53 <@Kit> But |Omega_1| <= |R|, because Omega_1 is the initial segment of smallest uncountable cardinality
21:53 -!- vaidhy [~vaidhy@] has left #mathematics []
21:53 <@Kit> So we have the cardinality of the borel sets <= |R||R| = |R^2| = |R|
21:53 <@Kit> And clearly it's >= |R|, so the cardinality of the set of borel sets is |R|
21:54 <@Kit> But it's easy to see that there are 2^|R| lebesgue measurable sets. e.g. every subset of the cantor set is lebesgue measurable
21:54 < fiesh> (actually I think there is no sigma algebra which is coutable, at least if I remember correctly)
21:54 <@Kit> So there are sets which are lebesgue measurable but not borel measurable.
21:54 <@zeno> (that's right: it's the very first exercise in Rudin R&C)
21:54 < fiesh> (ok! ;))
21:54 -!- mMhCkB [] has joined #mathematics
21:55 <@Kit> And that's that bit done. :)
21:55 <@Kit> I will now have a brief digression on cardinalities.
21:55 <@Kit> As we've established, every set bijects with some initial segment of the ordinals
21:56 -!- struct_ [] has quit []
21:56 <@Kit> For any set A we can look at { x : |{y : y < x}| = |A| }
21:56 <@Kit> This has a least element
21:56 <@Kit> We call this the cardinal number of A.
21:57 <@Kit> Basically we are picking a canonical representation for the cardinality of the set A
21:58 <@Kit> If t is a cardinal number then it has the nice property that for any s < t, the initial segment { y : y < s } has | { y : y < s} | < |{ y : y < t }|
21:58 <@Kit> Of particular importance is the cardinal number of R, which we will call c
21:59 -!- grim^ [] has quit []
21:59 <@Kit> And now I'm going to take a 5 minute break. :)
21:59 -!- R^^n [] has quit [Read error: Connection reset by peer]
21:59 < azta> I'm gonna go for a wee !
21:59 <@Kit> After the break I will prove the cantor-bendixson theorem, a nice theorem about the topology of subsets of R, and provide two cute constructions of interesting things you can do with subsets of R^n
22:00 -!- mode/#mathematics [+l 80] by Evariste
22:00 <@Galois> no physical seminar would ever go on for two hours straight and then have a "break"
22:00 < wtbw> heh :)
22:01 < ^LoNeR^> anyone loggig this, that has managed to get a complete log?
22:01 < azta> ^LoNeR^: yeah, topic
22:02 < ^LoNeR^> ok, do you mind if I download that later and repost on #math-zfc home page?
22:02 < ^LoNeR^> I have had some trouble logging
22:02 <@zeno> (I'll inject a comment that omega_1 can be constructed quite explicitly, without the arbitrary choices Kit used in his proof that every set is bijectible with some initial segment of Ord.)
22:02 < azta> ^LoNeR^: sure
22:02 < azta> it might be better to wait until it gets cleaned up though
22:03 < Sex-Tazi> loner u should ask kit also for a permission
22:03 < azta> of course
22:03 < crot> zeno: hartog numbers!
22:03 -!- ChiefWigg [] has joined #mathematics
22:03 < ^LoNeR^> I usually put up an undeited log and then if the spaker wants one a finished draft
22:04 < ^LoNeR^> I allready have kit;s permission, just that I have had some disconnects so I have an incomplete log
22:04 < azta> ^LoNeR^: I have a log, others do too I'm sure
22:05 <@Kit> Galois: Indeed. :) But I'm longwinded
22:05 <@Kit> And also obviously don't know what I'm doing which makes it take twice as long. ;)
22:05 -!- fante7 [] has joined #mathematics
22:06 -!- Elric- [] has joined #mathematics
22:06 <@Kit> Alright. Ready to start again.
22:07 <@Kit> Everyone ready?
22:07 < azta> go !
22:07 < azta> :)
22:07 <@Kit> Ok then.
22:07 <@Kit> The Cantor Bendixson Theorem.
22:07 <@Kit> This assumes a little bit of basic topology
22:08 <@Kit> Let X be a subset of R.
22:08 <@Kit> We say that X is perfect if it is closed and every x \in X is a limit point of X
22:08 <@Kit> e.g. [0, 1] is perfect
22:08 <@Kit> But {0, 1} is not.
22:08 <@Kit> Nor is {1/n : n \in N, n > 0} u {0}
22:08 <@Kit> Because for example 1 isn't a limit point of either of them
22:09 -!- mode/#mathematics [+l 83] by Evariste
22:09 -!- ChiefWigg [] has left #mathematics []
22:09 -!- mode/#mathematics [+o fante7] by Evariste
22:09 <@Kit> The Cantor-Bendixson Theorem says the following: Let F be a closed subset of R. We can write F = X u C, where X is perfect and C is countable.
22:10 <@Kit> We're going to do this by constructing a decreasing ordinal sequence of sets F_x
22:10 <@Kit> F_0 = F
22:10 <@Kit> F_{x+} = { limit points of F_x }
22:10 <@Kit> And take intersections at limits
22:11 <@Kit> Note: You might be tempted to think that this terminates fairly quickly. It actually needn't.
22:11 <@Kit> For example if you let F = {0} u {1/n}
22:12 <@Kit> Then F_{1} = {0}, and F_{2} = \emptyset
22:12 <@Kit> Which is quite quick admittedly. :)
22:13 <@Kit> But if you then stick an extra copy of F on each point of F then it takes two steps to terminate.
22:13 <@Kit> err. three steps
22:13 <@Kit> If you do this again then the number keeps increasing, and with a little bit of trickery you can get it to need infinitely many steps
22:13 <@Kit> So there's a genuine need for ordinals here
22:14 <@Kit> Anyway, usual faff about injective functions proves that we must eventually have F_{x+} = F_x
22:14 <@Kit> i.e. F_x is perfect
22:14 -!- robcool_ [] has joined #mathematics
22:14 <@Kit> But what we need to know is how *long* it takes before this happens.
22:14 <@Kit> In particular in order for us to prove cantor-bendixson, we need to know it happens for x some countable ordinal
22:15 -!- robcool [] has quit [Ping timeout: 182 seconds]
22:15 <@Kit> This will require a bit of topology of the real line.
22:15 <@Kit> First of all note that F_{x} \ F(x') is countable, because it is a discrete subset of R
22:16 <@Kit> So having proved it will terminate at a countable ordinal then we're done, because F_0 \ F_x (where it's terminated at x) will be a countable union of countable sets
22:17 <@Kit> So we want to prove the following lemma: There is no strictly decreasing w_1 sequence of closed subsets of R
22:17 <@Kit> Proof:
22:18 <@Kit> By taking complements we can convert this to showing that there is no strictly increasing w_1 sequence of open subsets of R
22:18 <@Kit> Suppose U_x were such a sequence
22:18 <@Kit> Pick r_x \in U_{x+} \ U_x
22:18 <@Kit> (We can do this because it's strictly increasing)
22:19 <@Kit> Now, we can pick B_x a set of the form (a, b) with a, b rational such that r_x \in B_x \subseteq U_{x+}
22:20 <@Kit> I claim that for x != y, B_x != B_y
22:20 -!- lsm is now known as lsmsrbls
22:20 <@Kit> Proof: We may without loss of generality suppose x < y
22:20 <@Kit> Then B_x \subseteq U_{x+}
22:21 <@Kit> And r_y \in B_y
22:21 <@Kit> But r_y \not\in U_{x+} because it's in U_{y+} \ U_y, and U_{x+} \subseteq U_y
22:21 -!- Cowmoo [~Snak@] has joined #mathematics
22:21 <@Kit> So B_y != B_x
22:22 <@Kit> But this is patently nonsense, because the set of intervals with rational endpoints is countable
22:22 -!- SaumZ [] has joined #mathematics
22:22 <@Kit> And we've just exhibited a countable subset
22:22 <@Kit> err
22:22 <@Kit> uncountable
22:22 <@Kit> Contradiction
22:22 <@Kit> Hence the process terminates at a countable ordinal, and the theorem is proved.
22:22 <@Kit> Yay. :)
22:23 <@Kit> It's occurred to me that after the break I should have asked if there were any questions about the first part
22:23 < wtbw> :)
22:23 <@Kit> So let me ask now
22:23 <@Kit> Are there any questions about the first part or about what I've just done?
22:24 < iangt1> well it was a bit over my head ;)
22:24 < iangt1> i didnt take enough pure options to understand :(
22:24 <@Kit> Sorry. :) I'm trying to keep it elementary, but there's a lack of interesting examples if I keep it too elementary.
22:25 <@Kit> No questions? Ok. I'll carry on.
22:25 <@Kit> The next two results belong to the school of set theory known as `constructing weird-ass subsets of R^n' :)
22:26 <@Kit> They're more to demonstrate cool things you can do with transfinite induction rather than proving anything terribly deep or interesting in its own right
22:26 <@Kit> First:
22:26 <@Kit> Let n > 1
22:26 <@Kit> There is a set A <= R^n such that for any straigh line L, |L n A| = 2
22:27 <@Kit> Proof:
22:27 <@Kit> (Oh, I should note that these are proper lines going out to infinity in both directions, not line segments)
22:27 <@Kit> Consider the set of straight lines in R^n.
22:27 <@Kit> It's clear this set has cardinality |R|
22:28 <@Kit> So we can write it as a c-sequence, L_x with x < c
22:28 <@Kit> (recall that c is the least ordinal who's initial segment has cardinality |R|)
22:28 -!- robcool_ [] has quit [Quit: BitchX: sanitized for your protection]
22:29 <@Kit> We will now define A_x inductively on x for x < c
22:29 -!- carl_ [] has joined #mathematics
22:30 <@Kit> Suppose we've defined A_y for y < x, with |A_y n L_s| = 2 for any s < y
22:30 <@Kit> Hmm. I'm sorry, that's not quite how I want to do it.
22:31 <@Kit> I'm actually going to pick S_y a subset of L_y of cardinality 2
22:32 <@Kit> I'll pick it as follows:
22:32 <@Kit> Dammit. I'm having a really off night tonight. I solved this problem in like 30 seconds when I first saw it...
22:33 -!- cyby`` [] has joined #mathematics
22:34 -!- cyby`` [] has left #mathematics []
22:34 <@Kit> Sigh. Give me a few minutes to stop being stupid. It probably won't help, but we'll see. :)
22:35 < lsmsrbls> We still love you, Kit.
22:35 <@Kit> Aww. Thanks. :)
22:35 < azta> :)
22:35 <@Kit> That doesn't make it any less embarassing
22:35 < wtbw> :)
22:36 < azta> it's quite comforting to know other people slip up too ;)
22:36 <@Kit> Alright. The idea behind this should be very easy. It's essentially a cardinal argument.
22:36 -!- cyby_ [] has joined #mathematics
22:36 <@Kit> We pick points for y < x, and because we know that this set has cardinality < |R|, there are `still points left to pick'
22:37 <@Kit> zeno: I'm not proud. Care to lend a hand? :)
22:39 -!- mode/#mathematics [+l 85] by Evariste
22:39 <@Kit> Ah, got it.
22:40 <@Kit> For each x we pick a set A_x such that for all y < x, |A_x n L_y| = 2 and no three points of A_x are colinear
22:40 <@Kit> We do this inductively
22:40 <@Kit> Suppose we've done it for all x < z
22:42 <@Kit> For any x < z we have |A_y n L_z| <= 2, as else we would have three colinear points of A_x
22:42 <@Kit> Now, take their union.
22:43 <@Kit> ...
22:43 <@Kit> No, I'm just in a state of blithering idiocy tonight.
22:44 <@Kit> I think rather than continue to embarass myself I'm going to call an end to the seminar here.
22:44 <@landen> clap clap
22:44 <@Galois> !!!
22:44 < wtbw> well done Kit, thanks :)
22:44 <@Kit> Hopefully I've given some idea of what ordinals are and how they're used.
22:44 <@Kit> And I apologise that my stupidity has made a lot of this incomprehensible and more of it incomplete.
22:44 <@Kit> Galois: Yes, you may ask all three questions. :)
22:44 <@Galois> it's okay, I walked out in the middle because I am at work, so I missed your stupidity
22:45 -!- carl_ [] has left #mathematics []
22:45 <@Kit> What I'll do is I'll write up a proper set of notes which will hopefully convey how the seminar *should* have gone over the next week or so then post a link in the topic.
22:45 -!- [-K-] [] has joined #mathematics
22:46 < azta> thanks Kit, even though lots of it were above me, you opened my eyes to some new things and some new ideas :)
22:46 * azta claps too
22:46 <@Kit> Any questions before I collapse in defeat? :)
22:46 < azta> haha :)
22:47 <@Kit> Anyway, thanks everyone for being so nice about it. :)
22:47 <@Kit> And hopefully the notes will be more readable
22:48 * [-K-] congratules Kit on giving a great seminar.
22:48 < [-K-]> does that help? :)
22:48 <@Kit> [-K-]: You caught the best part of it. :)
22:48 < [-K-]> skill.
22:48 <@landen> there is a keg and mugs at the back of the hall.
22:48 < vitriol> hey K!
22:48 < [-K-]> hi vitriol
22:49 < vitriol> hows things
22:49 * SaumZ goes to get a frothy mug of ale :D
22:50 * dioid claps and then fills a mug from the keg :)
22:50 < azta> :)