Cardinalities and Infinity Part III
Go back to the Math Jam ArchiveUniversity of Illinois graduate student Daniel Zaharopol will lead a discussion on how mathematicians think about the sizes of infinite sets. (This is not a problem-solving talk, just a discussion about some amazing mathematics.) See the Transcripts page for Parts I and II on February 28 and March 14.
Copyright © 2024 AoPS Incorporated. This page is copyrighted material. You can view and print this page for your own use, but you cannot share the contents of this file with others.
Facilitator: Dan Zaharopol
DanZ (18:29:31)
Hello everyone, and welcome back to the third and final Math Jam in the series I've been running about infinite sets.
DanZ (18:29:33)
Normally, this would be the point where Richard would introduce me, but he's travelling this week. So rather than prolong the whole bit, let me summarize:
DanZ (18:29:40)
I'm Dan. I'm a graduate student in mathematics at the University of Illinois at Urbana-Champaign. During the summers I teach at Canada/USA Mathcamp, which I think is quite possibly the most awesome place on Earth. I really enjoy sharing interesting mathematics with others, and so I look forward to doing that tonight.
DanZ (18:29:50)
Also before I start, I want to thank Richard and Art of Problem Solving for hosting me here tonight. They have a really wonderful setup, and it's a privilege to get to use it (it's also a lot of fun to use!).
DanZ (18:30:05)
This room is moderated, so messages you send to it go to me, and I'll pass them on to the rest of the room.
DanZ (18:30:23)
Also: before I forget, if you're here for intro number theory or counting and probability, you should leave and re-enter,choosing the appropriate room.
DanZ (18:30:53)
I'm going to be assuming tonight that you've followed earlier Math Jams enough to understand what a bijection is. Although some of the intuition from previous times will be useful, we won't be using the material too heavily.
DanZ (18:30:58)
(bijection == pairing)
DanZ (18:31:03)
Truthfully, I chose the topic for tonight mostly for entertainment value. The past two weeks have been lots of fun, but also very useful mathematically: most serious studies of theoretical mathematics build on the material from those two weeks. This week is a bit more out there --- it's important in some fields of mathematics, but it isn't something everyone needs to know. It's just a bit of fun, a chance for us to fool around with some really interesting concepts. Hopefully, it will also build up your intuition for understanding some other fundamental mathematical results as well.
DanZ (18:31:22)
I actually shouldn't speak too soon, since this very stuff came up in my research recently.
DanZ (18:31:37)
What we're going to be talking about are called ""ordinals,"" and ordinal arithmetic. These are one way to generalize our concept of number to something that can measure infinite sets. We'll see that by doing this generalization, we'll be able to get some insight into the structure of infinite objects.
DanZ (18:31:45)
So, today, we are going to:
DanZ (18:31:56)
DanZ (18:32:12)
DanZ (18:32:23)
DanZ (18:32:39)
Actually, strike that one. I probably won't have time to do that, but I'll try if there's a chance.
DanZ (18:32:42)
DanZ (18:32:50)
But I will make sure to do number 4.
DanZ (18:32:58)
So step 1: If we're going to understand infinite numbers, we're going to have to understand the finite numbers we're used to a bit better than we do right now. In particular, if we want to construct some model of infinite numbers, we need a model of finite numbers. We're going to build the finite numbers you know about --- 0, 1, 2, etc. --- out of [i]sets[/i]. Once we can work with finite numbers using just set theory, we'll take our construction and extend it to the infinite level.
DanZ (18:33:14)
roadnottaken (18:33:22)
null set
davidyko (18:33:24)
empty set?
JAM (18:33:27)
the empty set
variable (18:33:29)
The empty set.
Hamster1800 (18:33:32)
{}
DanZ (18:33:46)
variable (18:33:48)
Then 1 is the set {1}, 2 is the set {1,2}, etc.??
DanZ (18:34:04)
Yes, you're ahead. :)
DanZ (18:34:20)
roadnottaken (18:34:19)
Especially since braces are used as code in latex
DanZ (18:34:29)
Heh.
DanZ (18:34:41)
(Actually, variable, there's a minor correction required to what you said.)
roadnottaken (18:34:36)
{1}
DanZ (18:34:59)
Right --- this is like with variable's answer. It doesn't quite work --- how can we say that 1 is itself in braces, if we don't know what it is yet?
Hamster1800 (18:34:39)
{{}}= {0}
DanZ (18:35:14)
This is a better answer, because we already know what zero is.
DanZ (18:35:19)
DanZ (18:35:32)
E^(pi*i)=-1 (18:34:52)
1={{}}, 2={{{}}}, etc.
variable (18:35:33)
Oh, then 2={0,1}?
roadnottaken (18:35:40)
{{{}}}
davidyko (18:35:47)
{{{}}}
JAM (18:35:51)
{0,1}
DanZ (18:36:00)
We have competition!
Hamster1800 (18:36:05)
{{{}},{}} = {0,1}
DanZ (18:36:24)
So, you *could* do something like {{{}}} for 2.
DanZ (18:36:36)
But it turns out that that would get really ugly, and it won't have a nice property we want.
DanZ (18:36:49)
So let's go with the other suggestion and see where it takes us:
DanZ (18:36:51)
DanZ (18:36:57)
DanZ (18:37:09)
roadnottaken (18:37:05)
Imagine that, a ton of braces gets ugly!
DanZ (18:37:30)
It does! But now that we have this new notation, it'll be easier to keep track of how we're defining our numbers.
DanZ (18:38:06)
Does everyone see how the defintion works? 0 is the empty set, then we use the definition of 0 to get 1, which is the set containing 0 {0}, and we use the definitions of both 0 and 1 to get the definition of 2: {0, 1}, etc.?
DanZ (18:38:39)
Ok, positive responses are good. If you have questions, feel free to ask them at any time.
DanZ (18:38:41)
Now we're going to take all the things you're used to doing with numbers and see that we still know how to do them with these sets representing numbers. The first thing I'd like to do is make sure we can still tell which numbers are less than which other numbers.
DanZ (18:38:45)
roadnottaken (18:39:05)
m contains fewer elements
tjhance (18:39:07)
if |m|<|n|
variable (18:39:11)
The cardinality of the smaller number is smaller than the cardinality of the larger.
DanZ (18:39:23)
These are all excellent answers!
DanZ (18:39:27)
(And they're all the same answer.)
DanZ (18:39:41)
However, I want something that's in terms of more basic set theory operations: I don't want to use everything we've done so far.
DanZ (18:39:48)
So I'd actually like to go with:
JAM (18:39:24)
DanZ (18:39:58)
Ah, but what does that symbol mean?
DanZ (18:40:04)
davidyko (18:40:04)
if m is included in n?
DanZ (18:40:14)
Exactly.
DanZ (18:40:22)
roadnottaken (18:40:13)
M is a subset of n.
DanZ (18:40:36)
Also very good!
DanZ (18:41:02)
DanZ (18:41:20)
DanZ (18:41:48)
We're going to note this propertly later; for now, however, it's enough to just say that $m < n$ if $m \in n$, that is, if $m$ is an element inside $n$.
DanZ (18:41:54)
DanZ (18:42:01)
(Sorry, forgot my semicolon...)
DanZ (18:42:08)
davidyko (18:42:31)
Add the element n.
roadnottaken (18:42:31)
add n as an element.
DanZ (18:42:41)
Right!
DanZ (18:42:45)
DanZ (18:43:03)
DanZ (18:43:09)
DanZ (18:43:22)
DanZ (18:43:44)
Any questions? Does that make sense?
DanZ (18:43:58)
This is oddly more formal than previous weeks because we have all this notation, but it'll turn out to be very powerful.
roadnottaken (18:44:30)
This implies that the set representing a number is a triangular formation, right?
DanZ (18:44:45)
What do you mean by triangular formation? I don't think I know that term
DanZ (18:45:57)
roadnottaken (18:46:00)
Um, it's not particularly technical, but I mean that the set representing n includes any number k, n-k times.
DanZ (18:46:13)
Yup, I think that's true.
DanZ (18:46:19)
DanZ (18:46:43)
Hamster1800 (18:46:55)
m+n = s(s(s(...(n)))...) where you take the successor m times
E^(pi*i)=-1 (18:46:59)
m+n=sss...s(n), with m s's
roadnottaken (18:47:01)
s^(m-n)n
DanZ (18:47:10)
Yes! All correct.
DanZ (18:47:20)
Let's break it down into two cases, and do this recursively.
DanZ (18:47:38)
DanZ (18:47:46)
DanZ (18:47:53)
DanZ (18:48:05)
DanZ (18:48:13)
DanZ (18:48:58)
DanZ (18:49:17)
DanZ (18:49:38)
DanZ (18:50:01)
DanZ (18:50:19)
DanZ (18:50:35)
DanZ (18:50:44)
DanZ (18:51:32)
DanZ (18:51:56)
roadnottaken (18:51:51)
This is where exponent notation for applying functions repeatedly becomes useful.
DanZ (18:52:07)
So true.
DanZ (18:52:17)
I did that out several times --- is that OK?
DanZ (18:52:24)
Because this gives us addition.
DanZ (18:52:40)
DanZ (18:53:23)
DanZ (18:53:34)
It's just the distributive law.
roadnottaken (18:53:36)
s^n(m)+m?
DanZ (18:54:04)
I don't think that's quite correct, actually.
DanZ (18:54:14)
Look it over a bit more later. :)
DanZ (18:54:16)
Anyway, you should all be able to unwind that definition if you think about it for just a minute, but I don't want to spend a lot of time explaining it in detail. The point is that, at each step, what you're multiplying by gets smaller --- so at some point you're just multiplying by zero and you know what to do. In fact, this will turn mn into m + m + m + ... + m, n times over, which is just what multiplication is!
DanZ (18:54:37)
Each time you apply rule 2, you're adding m but multiplying by one less.
DanZ (18:54:45)
Similarly, we should be able to do exponentiation.
DanZ (18:54:47)
roadnottaken (18:54:47)
s^n(m)+[i]k[/i]m?
DanZ (18:55:20)
Think about what you're writing: s^n(m) is just m + n.
DanZ (18:55:32)
So look at what happened: we started with sets and this strange thing called the ""successor function,"" and we used that to get all of these arithmetic operations. But we started with something so simple, maybe we can generalize it to the infinite case!
DanZ (18:55:38)
DanZ (18:55:47)
DanZ (18:55:53)
Image at: //s3.amazonaws.com/classroom.artofproblemsolving.com/Community/MJImages/DanZ/5plus3large.jpg
DanZ (18:55:59)
DanZ (18:56:14)
DanZ (18:56:21)
Start with $5$ and $3$:
DanZ (18:56:27)
DanZ (18:56:33)
Then turn it into a grid:
DanZ (18:56:38)
DanZ (18:56:48)
Then flatten it out into a line:
DanZ (18:56:52)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Community/MJImages/DanZ/53gridtoline.jpg
DanZ (18:56:55)
DanZ (18:57:01)
Image at: //s3.amazonaws.com/classroom.artofproblemsolving.com/Community/MJImages/DanZ/53gridtolinelarge.jpg
DanZ (18:57:10)
(Sorry, that image is really small. And I forgot to zero-index again.)
DanZ (18:57:14)
These pictures are useful because they'll still work (in most ways) when we get to the infinite case.
DanZ (18:57:31)
Okay. I realize this might be technical, and I'm not sure where we are. Questions?
DanZ (18:58:07)
(This is the downside with an online classroom --- you can't read the faces of the audience to see if they're doing fine, or they're totally bored, or they're totally confused...)
DanZ (18:58:27)
DanZ (18:58:40)
In other words, if m is an element of n.
DanZ (18:58:42)
roadnottaken (18:58:59)
Aleph_0.
DanZ (18:59:21)
In some sense you're not wrong, but can you give me a set?
E^(pi*i)=-1 (18:59:36)
{N}
DanZ (18:59:54)
What does that mean?
JAM (18:59:14)
{0,1,2,3,...} (the set of all nutural numbers)
variable (18:59:48)
{0,1,2,...}.
tjhance (18:59:51)
{1,2,3,4,...}
DanZ (19:00:09)
Very good! (Well, we do want 0 in there.)
DanZ (19:00:15)
DanZ (19:00:55)
If you think about it, our numbers are {}, {0}, {0, 1}, {0, 1, 2}. {0, 1, 2, 3}, {0, 1, 2, 3, 4}, and so on --- the logical next step is to just have them all!
DanZ (19:01:03)
By our rules of numbers, we've just created something bigger than all the numbers we had before.
DanZ (19:01:09)
DanZ (19:01:22)
...and that totally went off the side of the classroom.
DanZ (19:01:35)
Well, it almost all fit.
DanZ (19:01:38)
But rather than spending lots of time trying to deal with these details, let's just see what other numbers we can create.
DanZ (19:01:41)
roadnottaken (19:02:00)
{0,1,2...omega}
variable (19:02:20)
And then we can make a larger infinity: {0,1,2,....} union with {omega}.
JAM (19:02:23)
DanZ (19:02:43)
JAM, watch out for your LaTeX code, you lose braces. :)
Hamster1800 (19:02:31)
DanZ (19:03:10)
DanZ (19:03:20)
However, you're all correct, essentially.
DanZ (19:03:31)
DanZ (19:03:44)
roadnottaken (19:03:10)
How do you make latex code in the classroom?
DanZ (19:03:59)
If you're familiar with LaTeX, then just start your line with a semicolon.
DanZ (19:04:05)
DanZ (19:04:13)
davidyko (19:04:11)
Is it just me, or did these images just disappear?
DanZ (19:04:33)
I've still got them... which ones are you missing?
davidyko (19:04:45)
Oh, never mind; they just took a long time to load.
DanZ (19:04:54)
Phew!
E^(pi*i)=-1 (19:04:52)
omega+1 union {omega+1}
Hamster1800 (19:04:55)
DanZ (19:05:04)
Yes!
DanZ (19:05:12)
davidyko (19:05:17)
And we can continue on...indefinitely.
DanZ (19:05:25)
Very good!
DanZ (19:05:35)
But just how indefinitely can we go? Can we only go on a countable number of times, or even more?
DanZ (19:06:01)
E^(pi*i)=-1 (19:06:12)
We can only go on a countable number of times, because our set by its nature is a list
DanZ (19:06:49)
Admittedly, you have me there; but we might be able to get to sets that aren't lists. I haven't actually given you the definition of [i]ordinal[/i] yet, but it turns out that they can go higher!
JAM (19:06:27)
{0,1,2,...,w,w+1,w+2,...}
Hamster1800 (19:06:58)
DanZ (19:07:15)
Good observation.
DanZ (19:07:20)
Mmmm... our definition of addition doesn't work here! Remember how we defined it:
DanZ (19:07:23)
DanZ (19:07:31)
DanZ (19:07:51)
DanZ (19:07:54)
DanZ (19:08:14)
DanZ (19:08:19)
(Sorry, fixed version.)
DanZ (19:08:32)
DanZ (19:08:47)
DanZ (19:09:00)
How are we doing? This is pretty wacky --- any questions?
DanZ (19:09:18)
(But it's cool, too... whatever we're doing, we're defining some kind of addition for infinite numbers...)
davidyko (19:09:10)
I agree that it's pretty wacky. :D
DanZ (19:09:40)
Like I said, sometimes you just have to teach something because it's a little bit crazy and also really fun.
DanZ (19:09:56)
There are actually three types of ordinal numbers, and we've now encountered all three.
DanZ (19:10:01)
DanZ (19:10:03)
DanZ (19:10:21)
DanZ (19:10:39)
Of course, I'm cheating here because I haven't actually told you what an ordinal is! But the definition is strange until you've worked with it, so I'm postponing it as much as possible.
DanZ (19:10:49)
Now that we have these ideas of limit ordinals, we can define a more general form of addition that will work for any two ordinals:
DanZ (19:10:51)
DanZ (19:11:19)
Both the second and third cases [i]simplify[/i] the problem. The second case reduces it to adding an ordinal that is one smaller.
DanZ (19:11:24)
DanZ (19:12:02)
This is pretty weird, but we're going to do some examples that will hopefully make it easier to understand.
DanZ (19:12:05)
DanZ (19:12:24)
E^(pi*i)=-1 (19:12:40)
{0,1,2,..,w,w+1,...,w+w,w+w+1}
davidyko (19:12:50)
s(w+w)
Hamster1800 (19:12:50)
DanZ (19:13:12)
Yay indeed!
DanZ (19:13:30)
DanZ (19:13:52)
Hamster1800 (19:13:12)
ah I lost braces <_<
davidyko (19:13:42)
But we get into more trouble at w+w+w, and have to use the third definition?
DanZ (19:14:16)
Yes, exactly.
davidyko (19:14:36)
I get it! :D
DanZ (19:14:51)
Sweet!
DanZ (19:15:01)
DanZ (19:15:04)
davidyko (19:15:30)
(w+w) union (w+w+1) union (w+w+2) etc.?
DanZ (19:15:50)
Yes, exactly.
JAM (19:15:33)
{0,1,...,w,w+1,...,w+w,w+w+1,...}
E^(pi*i)=-1 (19:15:34)
{1,2,...,w,w+1,...,w+w,w+w+1,...}
Hamster1800 (19:15:46)
DanZ (19:16:10)
(Yes, but start at 0.)
DanZ (19:16:13)
These expressions all work.
calc rulz (19:15:46)
DanZ (19:16:32)
Surprisingly enough, that doesn't work --- we'll look at multiplication in a bit!
DanZ (19:16:35)
But it's strange.
DanZ (19:16:40)
calc rulz (19:16:59)
{2+w}
DanZ (19:17:17)
What does that mean?
davidyko (19:17:22)
s(w+2)=s(s(w+1))=s(s(s(w)))?
DanZ (19:18:04)
JAM (19:17:57)
Hamster1800 (19:18:09)
DanZ (19:18:25)
Yeah... hrm.
DanZ (19:18:35)
E^(pi*i)=-1 (19:18:38)
3+w=w
DanZ (19:18:50)
DanZ (19:19:00)
DanZ (19:19:12)
DanZ (19:19:42)
DanZ (19:20:04)
DanZ (19:20:16)
E^(pi*i)=-1 (19:19:03)
Which means addition is no longer commutative . . .
roadnottaken (19:19:27)
Well, there goes the commutative property!
DanZ (19:20:30)
Yes! This is an addition that's not commutative.
DanZ (19:20:35)
It turns out that there's a good reason for this, which we can see if we look at things by pictures again.
DanZ (19:20:50)
DanZ (19:20:57)
DanZ (19:21:01)
Image at: //s3.amazonaws.com/classroom.artofproblemsolving.com/Community/MJImages/DanZ/5plus3large.jpg
DanZ (19:21:06)
DanZ (19:21:16)
DanZ (19:21:23)
Then we should stick them together:
DanZ (19:21:30)
DanZ (19:21:35)
Image at: //s3.amazonaws.com/classroom.artofproblemsolving.com/Community/MJImages/DanZ/omegaplusthreelarge.jpg
DanZ (19:21:55)
DanZ (19:22:09)
DanZ (19:22:21)
Does everyone see how that worked? We just stuck the dots next to each other.
davidyko (19:21:38)
Which is still an infinite amount...
DanZ (19:22:43)
You're right, and it's still countable. But I'm looking at the order, too.
DanZ (19:22:55)
DanZ (19:23:18)
Apparently I have gone faster than the Internet, so I'm going to slow down for a minute. Can you guys tell me when your images load?
DanZ (19:24:25)
(Sorry, this is what happens when you have a script you copy-paste from --- [i]I[/i] know what it says, so I just keeping going happily... thanks for stopping me!)
DanZ (19:24:42)
Okay, I think we have everyone.
DanZ (19:24:47)
DanZ (19:24:56)
DanZ (19:25:06)
Now we stick them together!
DanZ (19:25:11)
DanZ (19:25:15)
Image at: //s3.amazonaws.com/classroom.artofproblemsolving.com/Community/MJImages/DanZ/omegaplusomegalarge.jpg
DanZ (19:25:37)
DanZ (19:25:49)
DanZ (19:26:20)
DanZ (19:26:27)
DanZ (19:26:36)
(Hmmm, that was a big image.)
DanZ (19:26:39)
Now stick them next to each other:
DanZ (19:26:46)
DanZ (19:26:48)
Image at: //s3.amazonaws.com/classroom.artofproblemsolving.com/Community/MJImages/DanZ/fourplusomegalarge.jpg
DanZ (19:26:53)
DanZ (19:27:15)
Does that make sense? Any questions about these shenanigans?
DanZ (19:27:19)
(I'll also wait for images to load up.)
bubka (19:27:24)
now it's beginning to make sense
DanZ (19:27:36)
Excellent!
DanZ (19:27:48)
(Hrm, does that mean it's time to do something totally crazy again? :))
davidyko (19:27:40)
I get it; since we're adding a finite amount of dots to the end of an infinite thingy, it's different from adding an infinite amount to the end of a finite amount!
DanZ (19:27:57)
Bingo.
macgeekgrl (19:27:48)
w is very large
DanZ (19:28:16)
Yes, but if there's one thing we've learned from earlier math jams, it's that there's always a bigger infinity...
Hamster1800 (19:28:14)
crazy stuff is more fun
bubka (19:28:16)
sure where's the harm in being adventurous?
DanZ (19:28:26)
I approve.
DanZ (19:28:33)
In the same way that I defined addition formally for limit ordinals, I could do multiplication and exponentiation the same way, by taking unions of everything smaller. But I don't want to spend time on the formalism; once you understand the way addition works, you essentially understand the way all of them work.
DanZ (19:28:43)
However, I would like to show you ""multiplication by pictures.""
DanZ (19:28:48)
Remember from before when we multiplied 5 times 3. We started with a set of five dots and a set of three dots:
DanZ (19:28:53)
DanZ (19:29:00)
DanZ (19:29:05)
DanZ (19:29:22)
(Yes, these are the old pictures where I forgot to zero-index. Pretend they actually start at zero. :))
DanZ (19:29:51)
Now we saw that there were 15 dots by spreading this out into a line. But before I go to that step, let me point out something about the order.
DanZ (19:29:58)
Implicitly, there's been an order on everything we've done. Things on the left were always smaller than things on the right. That's still true above. But we'll also take the order to make things on the top always smaller than things on the bottom.
DanZ (19:30:08)
DanZ (19:30:20)
DanZ (19:30:25)
Image at: //s3.amazonaws.com/classroom.artofproblemsolving.com/Community/MJImages/DanZ/53gridtolinelarge.jpg
DanZ (19:30:46)
So we need to remember that the stuff towards the top [b]always[/b] comes before stuff towards the bottom.
DanZ (19:31:18)
(Is anyone else having image trouble? I'm getting a report of problems.)
DanZ (19:31:37)
DanZ (19:32:23)
Does someone want to tell me how to do that?
DanZ (19:32:31)
davidyko (19:32:36)
w+w+w+w+w?
tjhance (19:32:40)
w+w+w+w+w
DanZ (19:32:56)
Yes, exactly.
DanZ (19:33:25)
DanZ (19:33:29)
DanZ (19:33:43)
DanZ (19:33:50)
Image at: //s3.amazonaws.com/classroom.artofproblemsolving.com/Community/MJImages/DanZ/omegatimesfivegridlarge.jpg
DanZ (19:34:01)
Now we're supposed to expand that into a line. Well, what do we get? We get a really tiny, hard-to-see graphic, as it turns out:
DanZ (19:34:08)
DanZ (19:34:15)
Image at: //s3.amazonaws.com/classroom.artofproblemsolving.com/Community/MJImages/DanZ/omegatimesfivelinelarge.jpg
DanZ (19:34:20)
DanZ (19:35:08)
JAM (19:35:15)
w
tjhance (19:35:16)
5+5+5+5+5+5+...
bubka (19:35:22)
omega
DanZ (19:35:34)
I see I'm not fooling any of you...
E^(pi*i)=-1 (19:35:27)
5*w=w
DanZ (19:35:43)
DanZ (19:35:52)
DanZ (19:36:05)
Image at: //s3.amazonaws.com/classroom.artofproblemsolving.com/Community/MJImages/DanZ/fivetimesomegagridlarge.jpg
roadnottaken (19:36:04)
Wow, that's a big image!
DanZ (19:36:17)
Yeah, um, sorry about that.
DanZ (19:36:28)
I prepared my images in a rush this week and so I didn't get a chance to size them all just right.
DanZ (19:36:33)
DanZ (19:36:55)
Apparently mutliplication isn't commutative, either!
DanZ (19:37:16)
We can also see this algebraically, the way we were before.
DanZ (19:37:25)
But if you understand the pictures better than the algebra, you can safely ignore this part.
DanZ (19:37:27)
DanZ (19:37:36)
DanZ (19:37:54)
DanZ (19:38:01)
(Sorry, resent fixed version.)
roadnottaken (19:37:24)
DanZ (19:38:09)
Yes, fortunately.
DanZ (19:38:14)
That's why I sometimes leave off parentheses.
DanZ (19:38:21)
Any questions about all that?
DanZ (19:38:48)
(We're almost done here, by the way.)
bubka (19:38:50)
ummm ... no i guess
DanZ (19:39:15)
Yeah, so this is pretty odd. It's the sort of thing where you'd normally see it spread out more, and have more time to think about it.
DanZ (19:39:26)
So I apologize that I sped up for this last day. Hang on, and we're almost through.
DanZ (19:39:33)
So, I'm just about out of time, and I don't want to go on forever. Rather than going into lots of details about stuff, I want to summarize where this material goes and what it lets you do.
DanZ (19:39:37)
davidyko (19:39:58)
There are twice as many elements in w+w...?
DanZ (19:40:15)
Right, but does twice as many mean that they're different?
JAM (19:39:55)
The same
Hamster1800 (19:40:02)
They're both countable, I think
bubka (19:40:04)
equal
bubka (19:40:07)
both countable
DanZ (19:40:29)
Very good.
davidyko (19:40:27)
Nope.
DanZ (19:40:36)
Exactly.
DanZ (19:40:49)
They are the same size. It's the same way you can match up the integers with the natural numbers.
DanZ (19:41:00)
But you can only match them up if you ignore order!
DanZ (19:41:20)
DanZ (19:41:25)
So they are both countable.
DanZ (19:41:31)
DanZ (19:41:58)
DanZ (19:42:05)
Grr, more dots go the wrong way. Sorry about that.
DanZ (19:42:20)
But you can iterate the exponentiation an infinite number of times and it still stays countable!
bubka (19:42:22)
what does omega power omega mean?
DanZ (19:42:34)
Right, I haven't told you that yet.
DanZ (19:42:40)
But you can extend exponentiation in the same way.
DanZ (19:42:45)
(And I want to skip the details.)
roadnottaken (19:42:25)
DanZ (19:43:09)
That's a good question. The question depends on if you're doing cardinal exponentiation or ordinal exponentiation.
DanZ (19:43:14)
Let me go on, and take these questions at the end.
DanZ (19:43:21)
However, there [i]are[/i] much larger ordinals. If you assume the axiom of choice, you can get ordinals of any cardinality at all, in fact.
DanZ (19:43:28)
DanZ (19:43:39)
Hamster1800 (19:43:46)
yes
bubka (19:43:47)
yes!
JAM (19:43:48)
yes
E^(pi*i)=-1 (19:43:48)
yes
davidyko (19:43:57)
Yes.
DanZ (19:44:06)
DanZ (19:44:22)
E^(pi*i)=-1 (19:44:31)
no
bubka (19:44:34)
no
DanZ (19:44:41)
Why not?
bubka (19:44:48)
or is it finite subsets only?
DanZ (19:44:57)
No, infinite subsets too.
DanZ (19:44:59)
You're right, it's not.
E^(pi*i)=-1 (19:45:00)
there is no least element of Z itself!
DanZ (19:45:08)
Exactly!
DanZ (19:45:15)
DanZ (19:45:26)
DanZ (19:45:33)
DanZ (19:45:44)
Okay. Pause for a moment before I finish off the math jam.
DanZ (19:45:50)
I just threw out a whole ton of complicated notions.
DanZ (19:46:13)
Because this is the last math jam in the series, I'm trying to say a lot of things that are worth knowing, to give you a big picture --- even if you won't follow all the details.
DanZ (19:46:17)
So it's totally okay to be really lost right now.
DanZ (19:47:02)
tjhance (19:46:44)
what's the ""axiom of choice""?
DanZ (19:47:17)
That's a good question, I was hoping you'd all ignore that. :)
DanZ (19:47:21)
I'll talk about it in just a minute.
DanZ (19:47:28)
Now, this isn't what we set out to do. What we set out to do was to find ""numbers"" that would correspond to cardinalities, not to order types. But we can use the ordinal numbers to construct what are called the [b]cardinal numbers[/b].
bubka (19:47:26)
i think you'll go to bed a little later than usual today, there's so mcuh to clear up :-)
DanZ (19:47:39)
*laugh*
DanZ (19:47:57)
davidyko (19:47:56)
We'll be grilling you with questions for hours on end.
DanZ (19:48:08)
Oh, dear!
DanZ (19:48:19)
DanZ (19:48:50)
DanZ (19:49:10)
DanZ (19:49:26)
DanZ (19:49:52)
In other words, how do you get the next largest cardinal number? Find the smallest ordinal number of that cardinality.
DanZ (19:50:21)
DanZ (19:50:43)
DanZ (19:50:47)
You can define a notion of arithmetic on cardinals. (Which is [b]different[/b] from arithmetic on ordinals.)
DanZ (19:50:52)
Anyway, there's a huge amount of mathematics to be done here. Sadly I don't have time to cover it in detail, but there are lots of references.
DanZ (19:50:56)
A few endnotes before we call it a night:
DanZ (19:51:02)
First of all, I never gave you a real definition of ordinal. I suppose I should at least say [i]something[/i] about it before the end of the night.
DanZ (19:51:07)
DanZ (19:51:30)
That must seem like a really weird definition.
DanZ (19:51:41)
DanZ (19:52:16)
The definition comes from wanting things to be well-ordered. This definition guarantees that the results are well-ordered.
davidyko (19:51:42)
Is there an explanation with less symbols? XD
DanZ (19:52:31)
Hehe... for this definition, no. But don't worry about them yet.
DanZ (19:52:36)
Second, what's so good about ordinals? Well, besides the fact that they're really cool, they let you do something called [b]transfinite induction[/b]. Essentially, this lets you prove things about all ordinal numbers in the same way that normal induction lets you prove things about all natural numbers. This works because they're well-ordered, just like infinite descent; I can explain more about it after the Math Jam if you're interested.
DanZ (19:52:49)
Finally, I want to mention that a lot of what we've done relied on some set theory that I have completely ""swept under the rug.""
DanZ (19:52:53)
Just like there are ""axioms"" for geometry, there are axioms for set theory. They were put in place when people realized that you could get into contradictions if you weren't careful. (For example, there is no ""set of all sets."" If there was, you could create the ""set of all sets which do not contain themselves,"" and this would only lead to pain --- it's a contradiction.)
bubka (19:52:56)
that's true - they do seem to get well ordered by definition
DanZ (19:53:10)
I'm glad you can see it!
DanZ (19:53:13)
To fix this, axioms for set theory were laid down. The most famous set of axioms are called the Zermelo-Frankel axioms (although there are others). They say some basic things --- such as, the empty set exists. They also say things like power sets exist, and there exist infinite sets. Then there are also a lot of axioms that seem technical when you first see them but are actually quite important.
DanZ (19:53:28)
After a while, there was this big debate in the mathematical community when a mathematician named Zorn gave a proof where he chose an element out of each of infinitely many sets. This led to a debate about the [i]axiom of choice[/i], which turns out to be independent of the Z-F axioms. You can assume the axiom of choice is true, or that it's false, and it won't hurt you. It turns out that most mathematicians assume it's true, because it's really useful!
roadnottaken (19:53:23)
Russel's paradox!
DanZ (19:53:41)
Exactly --- that's what the ""set of all sets"" paradox is called.
DanZ (19:53:45)
Basically: there's a rigorous foundation you can put underneath everything we've been doing, and I've been totally ignoring it.
DanZ (19:54:02)
Okay, I am really out of time. Any quick questions? Longer questions should wait until I formally call it a night. :)
DanZ (19:54:23)
And I know this was hard! If you are in pain, it's OK. If you look up Wikipedia's entry on ordinal numbers, it might make more sense now. :)
DanZ (19:54:34)
So, thank you all for coming. I hope you enjoyed it!
DanZ (19:54:40)
I want to thank Art of Problem Solving again for hosting this. If you have any questions, I'll stick around a bit after everything is over; but otherwise, good night, and thanks again!
davidyko (19:54:49)
Thanks a lot!
macgeekgrl (19:54:52)
thanks!
DanZ (19:55:10)
Thank you! I hope it was manageable. :)
JAM (19:55:08)
thanks!
tjhance (19:55:02)
i'd like to know more about the transfinite induction
DanZ (19:55:35)
Let me address other questions and then get to that.
tjhance (19:55:23)
thanks a ton
E^(pi*i)=-1 (19:55:27)
Thanks, Dan!
DanZ (19:56:01)
(BTW, if you're a Mathcamper, I have no idea who you are in real life. You should tell me at some point. :))
davidyko (19:55:57)
To tell you the truth, it was a bit overwhelming, but now I want/need to study some of it on my own...what would this branch of math be called? Set theory?
DanZ (19:56:25)
Yes, this is set theory. A good book is ""The Joy of Sets"" by Keith Devlin. Also, the Wikipedia entries are pretty good.
DanZ (19:56:44)
The big book that does this all very carefully is called ""Set Theory"" by Thomas Jech, but it's a bit advanced.
bubka (19:56:29)
does halmos have all this?
DanZ (19:57:13)
Halmos' book, ""Naive Set Theory,"" has some of it.
DanZ (19:57:31)
It's a good read, well worth looking at. But it doesn't go as far. It does what we did more carefully, but it doesn't go beyond what we did.
bubka (19:55:28)
so like what's the ordinal corresponding to the reals?
DanZ (19:57:54)
So, remember that I said that every ordinal is well-ordered.
DanZ (19:58:11)
It turns out that it's independent of the normal axioms of set theory if you can well-order the reals, unless you use the axiom of choice.
DanZ (19:58:26)
And even when you do that, it doesn't tell you how to do it. This depends on the continuum hypothesis.
DanZ (19:58:34)
Note that the reals themselves --- the order you know --- isn't well ordered.
roadnottaken (19:57:42)
Isn't naive set theory what led to Russell's paradox?
DanZ (19:59:09)
Well, Halmos is referring to something a bit different.
DanZ (19:59:16)
He's careful to only do things that follow from the axioms.
Hamster1800 (19:56:01)
DanZ (20:00:01)
(My LaTeX isn't rendering for some reason.)
DanZ (20:00:07)
No. For example, $\{ 1, 3, 5 \} \subset 6$, but $\{ 1, 3, 5 \}
ot\in 6$.
DanZ (20:00:12)
There's what I wrote without LaTeX.
DanZ (20:00:17)
(Good thing it lasted until the end of the night!)
DanZ (20:00:50)
(Hrm. That's very strange.)
Hello everyone, and welcome back to the third and final Math Jam in the series I've been running about infinite sets.
DanZ (18:29:33)
Normally, this would be the point where Richard would introduce me, but he's travelling this week. So rather than prolong the whole bit, let me summarize:
DanZ (18:29:40)
I'm Dan. I'm a graduate student in mathematics at the University of Illinois at Urbana-Champaign. During the summers I teach at Canada/USA Mathcamp, which I think is quite possibly the most awesome place on Earth. I really enjoy sharing interesting mathematics with others, and so I look forward to doing that tonight.
DanZ (18:29:50)
Also before I start, I want to thank Richard and Art of Problem Solving for hosting me here tonight. They have a really wonderful setup, and it's a privilege to get to use it (it's also a lot of fun to use!).
DanZ (18:30:05)
This room is moderated, so messages you send to it go to me, and I'll pass them on to the rest of the room.
DanZ (18:30:23)
Also: before I forget, if you're here for intro number theory or counting and probability, you should leave and re-enter,choosing the appropriate room.
DanZ (18:30:53)
I'm going to be assuming tonight that you've followed earlier Math Jams enough to understand what a bijection is. Although some of the intuition from previous times will be useful, we won't be using the material too heavily.
DanZ (18:30:58)
(bijection == pairing)
DanZ (18:31:03)
Truthfully, I chose the topic for tonight mostly for entertainment value. The past two weeks have been lots of fun, but also very useful mathematically: most serious studies of theoretical mathematics build on the material from those two weeks. This week is a bit more out there --- it's important in some fields of mathematics, but it isn't something everyone needs to know. It's just a bit of fun, a chance for us to fool around with some really interesting concepts. Hopefully, it will also build up your intuition for understanding some other fundamental mathematical results as well.
DanZ (18:31:22)
I actually shouldn't speak too soon, since this very stuff came up in my research recently.
DanZ (18:31:37)
What we're going to be talking about are called ""ordinals,"" and ordinal arithmetic. These are one way to generalize our concept of number to something that can measure infinite sets. We'll see that by doing this generalization, we'll be able to get some insight into the structure of infinite objects.
DanZ (18:31:45)
So, today, we are going to:
DanZ (18:31:56)
DanZ (18:32:12)
DanZ (18:32:23)
DanZ (18:32:39)
Actually, strike that one. I probably won't have time to do that, but I'll try if there's a chance.
DanZ (18:32:42)
DanZ (18:32:50)
But I will make sure to do number 4.
DanZ (18:32:58)
So step 1: If we're going to understand infinite numbers, we're going to have to understand the finite numbers we're used to a bit better than we do right now. In particular, if we want to construct some model of infinite numbers, we need a model of finite numbers. We're going to build the finite numbers you know about --- 0, 1, 2, etc. --- out of [i]sets[/i]. Once we can work with finite numbers using just set theory, we'll take our construction and extend it to the infinite level.
DanZ (18:33:14)
roadnottaken (18:33:22)
null set
davidyko (18:33:24)
empty set?
JAM (18:33:27)
the empty set
variable (18:33:29)
The empty set.
Hamster1800 (18:33:32)
{}
DanZ (18:33:46)
variable (18:33:48)
Then 1 is the set {1}, 2 is the set {1,2}, etc.??
DanZ (18:34:04)
Yes, you're ahead. :)
DanZ (18:34:20)
roadnottaken (18:34:19)
Especially since braces are used as code in latex
DanZ (18:34:29)
Heh.
DanZ (18:34:41)
(Actually, variable, there's a minor correction required to what you said.)
roadnottaken (18:34:36)
{1}
DanZ (18:34:59)
Right --- this is like with variable's answer. It doesn't quite work --- how can we say that 1 is itself in braces, if we don't know what it is yet?
Hamster1800 (18:34:39)
{{}}= {0}
DanZ (18:35:14)
This is a better answer, because we already know what zero is.
DanZ (18:35:19)
DanZ (18:35:32)
E^(pi*i)=-1 (18:34:52)
1={{}}, 2={{{}}}, etc.
variable (18:35:33)
Oh, then 2={0,1}?
roadnottaken (18:35:40)
{{{}}}
davidyko (18:35:47)
{{{}}}
JAM (18:35:51)
{0,1}
DanZ (18:36:00)
We have competition!
Hamster1800 (18:36:05)
{{{}},{}} = {0,1}
DanZ (18:36:24)
So, you *could* do something like {{{}}} for 2.
DanZ (18:36:36)
But it turns out that that would get really ugly, and it won't have a nice property we want.
DanZ (18:36:49)
So let's go with the other suggestion and see where it takes us:
DanZ (18:36:51)
DanZ (18:36:57)
DanZ (18:37:09)
roadnottaken (18:37:05)
Imagine that, a ton of braces gets ugly!
DanZ (18:37:30)
It does! But now that we have this new notation, it'll be easier to keep track of how we're defining our numbers.
DanZ (18:38:06)
Does everyone see how the defintion works? 0 is the empty set, then we use the definition of 0 to get 1, which is the set containing 0 {0}, and we use the definitions of both 0 and 1 to get the definition of 2: {0, 1}, etc.?
DanZ (18:38:39)
Ok, positive responses are good. If you have questions, feel free to ask them at any time.
DanZ (18:38:41)
Now we're going to take all the things you're used to doing with numbers and see that we still know how to do them with these sets representing numbers. The first thing I'd like to do is make sure we can still tell which numbers are less than which other numbers.
DanZ (18:38:45)
roadnottaken (18:39:05)
m contains fewer elements
tjhance (18:39:07)
if |m|<|n|
variable (18:39:11)
The cardinality of the smaller number is smaller than the cardinality of the larger.
DanZ (18:39:23)
These are all excellent answers!
DanZ (18:39:27)
(And they're all the same answer.)
DanZ (18:39:41)
However, I want something that's in terms of more basic set theory operations: I don't want to use everything we've done so far.
DanZ (18:39:48)
So I'd actually like to go with:
JAM (18:39:24)
DanZ (18:39:58)
Ah, but what does that symbol mean?
DanZ (18:40:04)
davidyko (18:40:04)
if m is included in n?
DanZ (18:40:14)
Exactly.
DanZ (18:40:22)
roadnottaken (18:40:13)
M is a subset of n.
DanZ (18:40:36)
Also very good!
DanZ (18:41:02)
DanZ (18:41:20)
DanZ (18:41:48)
We're going to note this propertly later; for now, however, it's enough to just say that $m < n$ if $m \in n$, that is, if $m$ is an element inside $n$.
DanZ (18:41:54)
DanZ (18:42:01)
(Sorry, forgot my semicolon...)
DanZ (18:42:08)
davidyko (18:42:31)
Add the element n.
roadnottaken (18:42:31)
add n as an element.
DanZ (18:42:41)
Right!
DanZ (18:42:45)
DanZ (18:43:03)
DanZ (18:43:09)
DanZ (18:43:22)
DanZ (18:43:44)
Any questions? Does that make sense?
DanZ (18:43:58)
This is oddly more formal than previous weeks because we have all this notation, but it'll turn out to be very powerful.
roadnottaken (18:44:30)
This implies that the set representing a number is a triangular formation, right?
DanZ (18:44:45)
What do you mean by triangular formation? I don't think I know that term
DanZ (18:45:57)
roadnottaken (18:46:00)
Um, it's not particularly technical, but I mean that the set representing n includes any number k, n-k times.
DanZ (18:46:13)
Yup, I think that's true.
DanZ (18:46:19)
DanZ (18:46:43)
Hamster1800 (18:46:55)
m+n = s(s(s(...(n)))...) where you take the successor m times
E^(pi*i)=-1 (18:46:59)
m+n=sss...s(n), with m s's
roadnottaken (18:47:01)
s^(m-n)n
DanZ (18:47:10)
Yes! All correct.
DanZ (18:47:20)
Let's break it down into two cases, and do this recursively.
DanZ (18:47:38)
DanZ (18:47:46)
DanZ (18:47:53)
DanZ (18:48:05)
DanZ (18:48:13)
DanZ (18:48:58)
DanZ (18:49:17)
DanZ (18:49:38)
DanZ (18:50:01)
DanZ (18:50:19)
DanZ (18:50:35)
DanZ (18:50:44)
DanZ (18:51:32)
DanZ (18:51:56)
roadnottaken (18:51:51)
This is where exponent notation for applying functions repeatedly becomes useful.
DanZ (18:52:07)
So true.
DanZ (18:52:17)
I did that out several times --- is that OK?
DanZ (18:52:24)
Because this gives us addition.
DanZ (18:52:40)
DanZ (18:53:23)
DanZ (18:53:34)
It's just the distributive law.
roadnottaken (18:53:36)
s^n(m)+m?
DanZ (18:54:04)
I don't think that's quite correct, actually.
DanZ (18:54:14)
Look it over a bit more later. :)
DanZ (18:54:16)
Anyway, you should all be able to unwind that definition if you think about it for just a minute, but I don't want to spend a lot of time explaining it in detail. The point is that, at each step, what you're multiplying by gets smaller --- so at some point you're just multiplying by zero and you know what to do. In fact, this will turn mn into m + m + m + ... + m, n times over, which is just what multiplication is!
DanZ (18:54:37)
Each time you apply rule 2, you're adding m but multiplying by one less.
DanZ (18:54:45)
Similarly, we should be able to do exponentiation.
DanZ (18:54:47)
roadnottaken (18:54:47)
s^n(m)+[i]k[/i]m?
DanZ (18:55:20)
Think about what you're writing: s^n(m) is just m + n.
DanZ (18:55:32)
So look at what happened: we started with sets and this strange thing called the ""successor function,"" and we used that to get all of these arithmetic operations. But we started with something so simple, maybe we can generalize it to the infinite case!
DanZ (18:55:38)
DanZ (18:55:47)
DanZ (18:55:53)
Image at: //s3.amazonaws.com/classroom.artofproblemsolving.com/Community/MJImages/DanZ/5plus3large.jpg
DanZ (18:55:59)
DanZ (18:56:14)
DanZ (18:56:21)
Start with $5$ and $3$:
DanZ (18:56:27)
DanZ (18:56:33)
Then turn it into a grid:
DanZ (18:56:38)
DanZ (18:56:48)
Then flatten it out into a line:
DanZ (18:56:52)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Community/MJImages/DanZ/53gridtoline.jpg
DanZ (18:56:55)
DanZ (18:57:01)
Image at: //s3.amazonaws.com/classroom.artofproblemsolving.com/Community/MJImages/DanZ/53gridtolinelarge.jpg
DanZ (18:57:10)
(Sorry, that image is really small. And I forgot to zero-index again.)
DanZ (18:57:14)
These pictures are useful because they'll still work (in most ways) when we get to the infinite case.
DanZ (18:57:31)
Okay. I realize this might be technical, and I'm not sure where we are. Questions?
DanZ (18:58:07)
(This is the downside with an online classroom --- you can't read the faces of the audience to see if they're doing fine, or they're totally bored, or they're totally confused...)
DanZ (18:58:27)
DanZ (18:58:40)
In other words, if m is an element of n.
DanZ (18:58:42)
roadnottaken (18:58:59)
Aleph_0.
DanZ (18:59:21)
In some sense you're not wrong, but can you give me a set?
E^(pi*i)=-1 (18:59:36)
{N}
DanZ (18:59:54)
What does that mean?
JAM (18:59:14)
{0,1,2,3,...} (the set of all nutural numbers)
variable (18:59:48)
{0,1,2,...}.
tjhance (18:59:51)
{1,2,3,4,...}
DanZ (19:00:09)
Very good! (Well, we do want 0 in there.)
DanZ (19:00:15)
DanZ (19:00:55)
If you think about it, our numbers are {}, {0}, {0, 1}, {0, 1, 2}. {0, 1, 2, 3}, {0, 1, 2, 3, 4}, and so on --- the logical next step is to just have them all!
DanZ (19:01:03)
By our rules of numbers, we've just created something bigger than all the numbers we had before.
DanZ (19:01:09)
DanZ (19:01:22)
...and that totally went off the side of the classroom.
DanZ (19:01:35)
Well, it almost all fit.
DanZ (19:01:38)
But rather than spending lots of time trying to deal with these details, let's just see what other numbers we can create.
DanZ (19:01:41)
roadnottaken (19:02:00)
{0,1,2...omega}
variable (19:02:20)
And then we can make a larger infinity: {0,1,2,....} union with {omega}.
JAM (19:02:23)
DanZ (19:02:43)
JAM, watch out for your LaTeX code, you lose braces. :)
Hamster1800 (19:02:31)
DanZ (19:03:10)
DanZ (19:03:20)
However, you're all correct, essentially.
DanZ (19:03:31)
DanZ (19:03:44)
roadnottaken (19:03:10)
How do you make latex code in the classroom?
DanZ (19:03:59)
If you're familiar with LaTeX, then just start your line with a semicolon.
DanZ (19:04:05)
DanZ (19:04:13)
davidyko (19:04:11)
Is it just me, or did these images just disappear?
DanZ (19:04:33)
I've still got them... which ones are you missing?
davidyko (19:04:45)
Oh, never mind; they just took a long time to load.
DanZ (19:04:54)
Phew!
E^(pi*i)=-1 (19:04:52)
omega+1 union {omega+1}
Hamster1800 (19:04:55)
DanZ (19:05:04)
Yes!
DanZ (19:05:12)
davidyko (19:05:17)
And we can continue on...indefinitely.
DanZ (19:05:25)
Very good!
DanZ (19:05:35)
But just how indefinitely can we go? Can we only go on a countable number of times, or even more?
DanZ (19:06:01)
E^(pi*i)=-1 (19:06:12)
We can only go on a countable number of times, because our set by its nature is a list
DanZ (19:06:49)
Admittedly, you have me there; but we might be able to get to sets that aren't lists. I haven't actually given you the definition of [i]ordinal[/i] yet, but it turns out that they can go higher!
JAM (19:06:27)
{0,1,2,...,w,w+1,w+2,...}
Hamster1800 (19:06:58)
DanZ (19:07:15)
Good observation.
DanZ (19:07:20)
Mmmm... our definition of addition doesn't work here! Remember how we defined it:
DanZ (19:07:23)
DanZ (19:07:31)
DanZ (19:07:51)
DanZ (19:07:54)
DanZ (19:08:14)
DanZ (19:08:19)
(Sorry, fixed version.)
DanZ (19:08:32)
DanZ (19:08:47)
DanZ (19:09:00)
How are we doing? This is pretty wacky --- any questions?
DanZ (19:09:18)
(But it's cool, too... whatever we're doing, we're defining some kind of addition for infinite numbers...)
davidyko (19:09:10)
I agree that it's pretty wacky. :D
DanZ (19:09:40)
Like I said, sometimes you just have to teach something because it's a little bit crazy and also really fun.
DanZ (19:09:56)
There are actually three types of ordinal numbers, and we've now encountered all three.
DanZ (19:10:01)
DanZ (19:10:03)
DanZ (19:10:21)
DanZ (19:10:39)
Of course, I'm cheating here because I haven't actually told you what an ordinal is! But the definition is strange until you've worked with it, so I'm postponing it as much as possible.
DanZ (19:10:49)
Now that we have these ideas of limit ordinals, we can define a more general form of addition that will work for any two ordinals:
DanZ (19:10:51)
DanZ (19:11:19)
Both the second and third cases [i]simplify[/i] the problem. The second case reduces it to adding an ordinal that is one smaller.
DanZ (19:11:24)
DanZ (19:12:02)
This is pretty weird, but we're going to do some examples that will hopefully make it easier to understand.
DanZ (19:12:05)
DanZ (19:12:24)
E^(pi*i)=-1 (19:12:40)
{0,1,2,..,w,w+1,...,w+w,w+w+1}
davidyko (19:12:50)
s(w+w)
Hamster1800 (19:12:50)
DanZ (19:13:12)
Yay indeed!
DanZ (19:13:30)
DanZ (19:13:52)
Hamster1800 (19:13:12)
ah I lost braces <_<
davidyko (19:13:42)
But we get into more trouble at w+w+w, and have to use the third definition?
DanZ (19:14:16)
Yes, exactly.
davidyko (19:14:36)
I get it! :D
DanZ (19:14:51)
Sweet!
DanZ (19:15:01)
DanZ (19:15:04)
davidyko (19:15:30)
(w+w) union (w+w+1) union (w+w+2) etc.?
DanZ (19:15:50)
Yes, exactly.
JAM (19:15:33)
{0,1,...,w,w+1,...,w+w,w+w+1,...}
E^(pi*i)=-1 (19:15:34)
{1,2,...,w,w+1,...,w+w,w+w+1,...}
Hamster1800 (19:15:46)
DanZ (19:16:10)
(Yes, but start at 0.)
DanZ (19:16:13)
These expressions all work.
calc rulz (19:15:46)
DanZ (19:16:32)
Surprisingly enough, that doesn't work --- we'll look at multiplication in a bit!
DanZ (19:16:35)
But it's strange.
DanZ (19:16:40)
calc rulz (19:16:59)
{2+w}
DanZ (19:17:17)
What does that mean?
davidyko (19:17:22)
s(w+2)=s(s(w+1))=s(s(s(w)))?
DanZ (19:18:04)
JAM (19:17:57)
Hamster1800 (19:18:09)
DanZ (19:18:25)
Yeah... hrm.
DanZ (19:18:35)
E^(pi*i)=-1 (19:18:38)
3+w=w
DanZ (19:18:50)
DanZ (19:19:00)
DanZ (19:19:12)
DanZ (19:19:42)
DanZ (19:20:04)
DanZ (19:20:16)
E^(pi*i)=-1 (19:19:03)
Which means addition is no longer commutative . . .
roadnottaken (19:19:27)
Well, there goes the commutative property!
DanZ (19:20:30)
Yes! This is an addition that's not commutative.
DanZ (19:20:35)
It turns out that there's a good reason for this, which we can see if we look at things by pictures again.
DanZ (19:20:50)
DanZ (19:20:57)
DanZ (19:21:01)
Image at: //s3.amazonaws.com/classroom.artofproblemsolving.com/Community/MJImages/DanZ/5plus3large.jpg
DanZ (19:21:06)
DanZ (19:21:16)
DanZ (19:21:23)
Then we should stick them together:
DanZ (19:21:30)
DanZ (19:21:35)
Image at: //s3.amazonaws.com/classroom.artofproblemsolving.com/Community/MJImages/DanZ/omegaplusthreelarge.jpg
DanZ (19:21:55)
DanZ (19:22:09)
DanZ (19:22:21)
Does everyone see how that worked? We just stuck the dots next to each other.
davidyko (19:21:38)
Which is still an infinite amount...
DanZ (19:22:43)
You're right, and it's still countable. But I'm looking at the order, too.
DanZ (19:22:55)
DanZ (19:23:18)
Apparently I have gone faster than the Internet, so I'm going to slow down for a minute. Can you guys tell me when your images load?
DanZ (19:24:25)
(Sorry, this is what happens when you have a script you copy-paste from --- [i]I[/i] know what it says, so I just keeping going happily... thanks for stopping me!)
DanZ (19:24:42)
Okay, I think we have everyone.
DanZ (19:24:47)
DanZ (19:24:56)
DanZ (19:25:06)
Now we stick them together!
DanZ (19:25:11)
DanZ (19:25:15)
Image at: //s3.amazonaws.com/classroom.artofproblemsolving.com/Community/MJImages/DanZ/omegaplusomegalarge.jpg
DanZ (19:25:37)
DanZ (19:25:49)
DanZ (19:26:20)
DanZ (19:26:27)
DanZ (19:26:36)
(Hmmm, that was a big image.)
DanZ (19:26:39)
Now stick them next to each other:
DanZ (19:26:46)
DanZ (19:26:48)
Image at: //s3.amazonaws.com/classroom.artofproblemsolving.com/Community/MJImages/DanZ/fourplusomegalarge.jpg
DanZ (19:26:53)
DanZ (19:27:15)
Does that make sense? Any questions about these shenanigans?
DanZ (19:27:19)
(I'll also wait for images to load up.)
bubka (19:27:24)
now it's beginning to make sense
DanZ (19:27:36)
Excellent!
DanZ (19:27:48)
(Hrm, does that mean it's time to do something totally crazy again? :))
davidyko (19:27:40)
I get it; since we're adding a finite amount of dots to the end of an infinite thingy, it's different from adding an infinite amount to the end of a finite amount!
DanZ (19:27:57)
Bingo.
macgeekgrl (19:27:48)
w is very large
DanZ (19:28:16)
Yes, but if there's one thing we've learned from earlier math jams, it's that there's always a bigger infinity...
Hamster1800 (19:28:14)
crazy stuff is more fun
bubka (19:28:16)
sure where's the harm in being adventurous?
DanZ (19:28:26)
I approve.
DanZ (19:28:33)
In the same way that I defined addition formally for limit ordinals, I could do multiplication and exponentiation the same way, by taking unions of everything smaller. But I don't want to spend time on the formalism; once you understand the way addition works, you essentially understand the way all of them work.
DanZ (19:28:43)
However, I would like to show you ""multiplication by pictures.""
DanZ (19:28:48)
Remember from before when we multiplied 5 times 3. We started with a set of five dots and a set of three dots:
DanZ (19:28:53)
DanZ (19:29:00)
DanZ (19:29:05)
DanZ (19:29:22)
(Yes, these are the old pictures where I forgot to zero-index. Pretend they actually start at zero. :))
DanZ (19:29:51)
Now we saw that there were 15 dots by spreading this out into a line. But before I go to that step, let me point out something about the order.
DanZ (19:29:58)
Implicitly, there's been an order on everything we've done. Things on the left were always smaller than things on the right. That's still true above. But we'll also take the order to make things on the top always smaller than things on the bottom.
DanZ (19:30:08)
DanZ (19:30:20)
DanZ (19:30:25)
Image at: //s3.amazonaws.com/classroom.artofproblemsolving.com/Community/MJImages/DanZ/53gridtolinelarge.jpg
DanZ (19:30:46)
So we need to remember that the stuff towards the top [b]always[/b] comes before stuff towards the bottom.
DanZ (19:31:18)
(Is anyone else having image trouble? I'm getting a report of problems.)
DanZ (19:31:37)
DanZ (19:32:23)
Does someone want to tell me how to do that?
DanZ (19:32:31)
davidyko (19:32:36)
w+w+w+w+w?
tjhance (19:32:40)
w+w+w+w+w
DanZ (19:32:56)
Yes, exactly.
DanZ (19:33:25)
DanZ (19:33:29)
DanZ (19:33:43)
DanZ (19:33:50)
Image at: //s3.amazonaws.com/classroom.artofproblemsolving.com/Community/MJImages/DanZ/omegatimesfivegridlarge.jpg
DanZ (19:34:01)
Now we're supposed to expand that into a line. Well, what do we get? We get a really tiny, hard-to-see graphic, as it turns out:
DanZ (19:34:08)
DanZ (19:34:15)
Image at: //s3.amazonaws.com/classroom.artofproblemsolving.com/Community/MJImages/DanZ/omegatimesfivelinelarge.jpg
DanZ (19:34:20)
DanZ (19:35:08)
JAM (19:35:15)
w
tjhance (19:35:16)
5+5+5+5+5+5+...
bubka (19:35:22)
omega
DanZ (19:35:34)
I see I'm not fooling any of you...
E^(pi*i)=-1 (19:35:27)
5*w=w
DanZ (19:35:43)
DanZ (19:35:52)
DanZ (19:36:05)
Image at: //s3.amazonaws.com/classroom.artofproblemsolving.com/Community/MJImages/DanZ/fivetimesomegagridlarge.jpg
roadnottaken (19:36:04)
Wow, that's a big image!
DanZ (19:36:17)
Yeah, um, sorry about that.
DanZ (19:36:28)
I prepared my images in a rush this week and so I didn't get a chance to size them all just right.
DanZ (19:36:33)
DanZ (19:36:55)
Apparently mutliplication isn't commutative, either!
DanZ (19:37:16)
We can also see this algebraically, the way we were before.
DanZ (19:37:25)
But if you understand the pictures better than the algebra, you can safely ignore this part.
DanZ (19:37:27)
DanZ (19:37:36)
DanZ (19:37:54)
DanZ (19:38:01)
(Sorry, resent fixed version.)
roadnottaken (19:37:24)
DanZ (19:38:09)
Yes, fortunately.
DanZ (19:38:14)
That's why I sometimes leave off parentheses.
DanZ (19:38:21)
Any questions about all that?
DanZ (19:38:48)
(We're almost done here, by the way.)
bubka (19:38:50)
ummm ... no i guess
DanZ (19:39:15)
Yeah, so this is pretty odd. It's the sort of thing where you'd normally see it spread out more, and have more time to think about it.
DanZ (19:39:26)
So I apologize that I sped up for this last day. Hang on, and we're almost through.
DanZ (19:39:33)
So, I'm just about out of time, and I don't want to go on forever. Rather than going into lots of details about stuff, I want to summarize where this material goes and what it lets you do.
DanZ (19:39:37)
davidyko (19:39:58)
There are twice as many elements in w+w...?
DanZ (19:40:15)
Right, but does twice as many mean that they're different?
JAM (19:39:55)
The same
Hamster1800 (19:40:02)
They're both countable, I think
bubka (19:40:04)
equal
bubka (19:40:07)
both countable
DanZ (19:40:29)
Very good.
davidyko (19:40:27)
Nope.
DanZ (19:40:36)
Exactly.
DanZ (19:40:49)
They are the same size. It's the same way you can match up the integers with the natural numbers.
DanZ (19:41:00)
But you can only match them up if you ignore order!
DanZ (19:41:20)
DanZ (19:41:25)
So they are both countable.
DanZ (19:41:31)
DanZ (19:41:58)
DanZ (19:42:05)
Grr, more dots go the wrong way. Sorry about that.
DanZ (19:42:20)
But you can iterate the exponentiation an infinite number of times and it still stays countable!
bubka (19:42:22)
what does omega power omega mean?
DanZ (19:42:34)
Right, I haven't told you that yet.
DanZ (19:42:40)
But you can extend exponentiation in the same way.
DanZ (19:42:45)
(And I want to skip the details.)
roadnottaken (19:42:25)
DanZ (19:43:09)
That's a good question. The question depends on if you're doing cardinal exponentiation or ordinal exponentiation.
DanZ (19:43:14)
Let me go on, and take these questions at the end.
DanZ (19:43:21)
However, there [i]are[/i] much larger ordinals. If you assume the axiom of choice, you can get ordinals of any cardinality at all, in fact.
DanZ (19:43:28)
DanZ (19:43:39)
Hamster1800 (19:43:46)
yes
bubka (19:43:47)
yes!
JAM (19:43:48)
yes
E^(pi*i)=-1 (19:43:48)
yes
davidyko (19:43:57)
Yes.
DanZ (19:44:06)
DanZ (19:44:22)
E^(pi*i)=-1 (19:44:31)
no
bubka (19:44:34)
no
DanZ (19:44:41)
Why not?
bubka (19:44:48)
or is it finite subsets only?
DanZ (19:44:57)
No, infinite subsets too.
DanZ (19:44:59)
You're right, it's not.
E^(pi*i)=-1 (19:45:00)
there is no least element of Z itself!
DanZ (19:45:08)
Exactly!
DanZ (19:45:15)
DanZ (19:45:26)
DanZ (19:45:33)
DanZ (19:45:44)
Okay. Pause for a moment before I finish off the math jam.
DanZ (19:45:50)
I just threw out a whole ton of complicated notions.
DanZ (19:46:13)
Because this is the last math jam in the series, I'm trying to say a lot of things that are worth knowing, to give you a big picture --- even if you won't follow all the details.
DanZ (19:46:17)
So it's totally okay to be really lost right now.
DanZ (19:47:02)
tjhance (19:46:44)
what's the ""axiom of choice""?
DanZ (19:47:17)
That's a good question, I was hoping you'd all ignore that. :)
DanZ (19:47:21)
I'll talk about it in just a minute.
DanZ (19:47:28)
Now, this isn't what we set out to do. What we set out to do was to find ""numbers"" that would correspond to cardinalities, not to order types. But we can use the ordinal numbers to construct what are called the [b]cardinal numbers[/b].
bubka (19:47:26)
i think you'll go to bed a little later than usual today, there's so mcuh to clear up :-)
DanZ (19:47:39)
*laugh*
DanZ (19:47:57)
davidyko (19:47:56)
We'll be grilling you with questions for hours on end.
DanZ (19:48:08)
Oh, dear!
DanZ (19:48:19)
DanZ (19:48:50)
DanZ (19:49:10)
DanZ (19:49:26)
DanZ (19:49:52)
In other words, how do you get the next largest cardinal number? Find the smallest ordinal number of that cardinality.
DanZ (19:50:21)
DanZ (19:50:43)
DanZ (19:50:47)
You can define a notion of arithmetic on cardinals. (Which is [b]different[/b] from arithmetic on ordinals.)
DanZ (19:50:52)
Anyway, there's a huge amount of mathematics to be done here. Sadly I don't have time to cover it in detail, but there are lots of references.
DanZ (19:50:56)
A few endnotes before we call it a night:
DanZ (19:51:02)
First of all, I never gave you a real definition of ordinal. I suppose I should at least say [i]something[/i] about it before the end of the night.
DanZ (19:51:07)
DanZ (19:51:30)
That must seem like a really weird definition.
DanZ (19:51:41)
DanZ (19:52:16)
The definition comes from wanting things to be well-ordered. This definition guarantees that the results are well-ordered.
davidyko (19:51:42)
Is there an explanation with less symbols? XD
DanZ (19:52:31)
Hehe... for this definition, no. But don't worry about them yet.
DanZ (19:52:36)
Second, what's so good about ordinals? Well, besides the fact that they're really cool, they let you do something called [b]transfinite induction[/b]. Essentially, this lets you prove things about all ordinal numbers in the same way that normal induction lets you prove things about all natural numbers. This works because they're well-ordered, just like infinite descent; I can explain more about it after the Math Jam if you're interested.
DanZ (19:52:49)
Finally, I want to mention that a lot of what we've done relied on some set theory that I have completely ""swept under the rug.""
DanZ (19:52:53)
Just like there are ""axioms"" for geometry, there are axioms for set theory. They were put in place when people realized that you could get into contradictions if you weren't careful. (For example, there is no ""set of all sets."" If there was, you could create the ""set of all sets which do not contain themselves,"" and this would only lead to pain --- it's a contradiction.)
bubka (19:52:56)
that's true - they do seem to get well ordered by definition
DanZ (19:53:10)
I'm glad you can see it!
DanZ (19:53:13)
To fix this, axioms for set theory were laid down. The most famous set of axioms are called the Zermelo-Frankel axioms (although there are others). They say some basic things --- such as, the empty set exists. They also say things like power sets exist, and there exist infinite sets. Then there are also a lot of axioms that seem technical when you first see them but are actually quite important.
DanZ (19:53:28)
After a while, there was this big debate in the mathematical community when a mathematician named Zorn gave a proof where he chose an element out of each of infinitely many sets. This led to a debate about the [i]axiom of choice[/i], which turns out to be independent of the Z-F axioms. You can assume the axiom of choice is true, or that it's false, and it won't hurt you. It turns out that most mathematicians assume it's true, because it's really useful!
roadnottaken (19:53:23)
Russel's paradox!
DanZ (19:53:41)
Exactly --- that's what the ""set of all sets"" paradox is called.
DanZ (19:53:45)
Basically: there's a rigorous foundation you can put underneath everything we've been doing, and I've been totally ignoring it.
DanZ (19:54:02)
Okay, I am really out of time. Any quick questions? Longer questions should wait until I formally call it a night. :)
DanZ (19:54:23)
And I know this was hard! If you are in pain, it's OK. If you look up Wikipedia's entry on ordinal numbers, it might make more sense now. :)
DanZ (19:54:34)
So, thank you all for coming. I hope you enjoyed it!
DanZ (19:54:40)
I want to thank Art of Problem Solving again for hosting this. If you have any questions, I'll stick around a bit after everything is over; but otherwise, good night, and thanks again!
davidyko (19:54:49)
Thanks a lot!
macgeekgrl (19:54:52)
thanks!
DanZ (19:55:10)
Thank you! I hope it was manageable. :)
JAM (19:55:08)
thanks!
tjhance (19:55:02)
i'd like to know more about the transfinite induction
DanZ (19:55:35)
Let me address other questions and then get to that.
tjhance (19:55:23)
thanks a ton
E^(pi*i)=-1 (19:55:27)
Thanks, Dan!
DanZ (19:56:01)
(BTW, if you're a Mathcamper, I have no idea who you are in real life. You should tell me at some point. :))
davidyko (19:55:57)
To tell you the truth, it was a bit overwhelming, but now I want/need to study some of it on my own...what would this branch of math be called? Set theory?
DanZ (19:56:25)
Yes, this is set theory. A good book is ""The Joy of Sets"" by Keith Devlin. Also, the Wikipedia entries are pretty good.
DanZ (19:56:44)
The big book that does this all very carefully is called ""Set Theory"" by Thomas Jech, but it's a bit advanced.
bubka (19:56:29)
does halmos have all this?
DanZ (19:57:13)
Halmos' book, ""Naive Set Theory,"" has some of it.
DanZ (19:57:31)
It's a good read, well worth looking at. But it doesn't go as far. It does what we did more carefully, but it doesn't go beyond what we did.
bubka (19:55:28)
so like what's the ordinal corresponding to the reals?
DanZ (19:57:54)
So, remember that I said that every ordinal is well-ordered.
DanZ (19:58:11)
It turns out that it's independent of the normal axioms of set theory if you can well-order the reals, unless you use the axiom of choice.
DanZ (19:58:26)
And even when you do that, it doesn't tell you how to do it. This depends on the continuum hypothesis.
DanZ (19:58:34)
Note that the reals themselves --- the order you know --- isn't well ordered.
roadnottaken (19:57:42)
Isn't naive set theory what led to Russell's paradox?
DanZ (19:59:09)
Well, Halmos is referring to something a bit different.
DanZ (19:59:16)
He's careful to only do things that follow from the axioms.
Hamster1800 (19:56:01)
DanZ (20:00:01)
(My LaTeX isn't rendering for some reason.)
DanZ (20:00:07)
No. For example, $\{ 1, 3, 5 \} \subset 6$, but $\{ 1, 3, 5 \}
ot\in 6$.
DanZ (20:00:12)
There's what I wrote without LaTeX.
DanZ (20:00:17)
(Good thing it lasted until the end of the night!)
DanZ (20:00:50)
(Hrm. That's very strange.)
Copyright © 2024 AoPS Incorporated. This page is copyrighted material. You can view and print this page for your own use, but you cannot share the contents of this file with others.
