This Math Jam is a continuation of an earlier Math Jam. Click here for the transcript of the first Infinity Math Jam.

rrusczyk (18:31:33)
Tonight we have Dan Zaharopol from USAMTS sponsor Canada/USA Mathcamp. He is going to continue his intriguing discussion about how mathematicians think about the sizes of infinite sets.

rrusczyk (18:31:40)
Canada/USA Mathcamp is providing $200 scholarships to the top 30 female and top 30 male scorers in the USAMTS. (These students must pass the Mathcamp admission quiz to qualify.) Mathcamp is a very popular summer program for outstanding math students. Many top USAMTS students are alumni of Mathcamp. More information about Mathcamp can be found at www.mathcamp.org. Dan will be back on March 20 to speak about Mathcamp in more detail. Tonight he's going to talk about math. (But if you have Mathcamp questions at the end of class, you might be able to talk him into responding! Please don't ask him questions during class, though.)

rrusczyk (18:31:58)
Dan Zaharopol graduated from MIT in 2004 and is now in the PhD program at the University of Illinois, studying algebraic topology. He teaches advanced mathematics each summer at Canada/USA Mathcamp, as well as with various programs at MIT; he also occasionally teaches calculus (which he says is much more boring!) at the U of I.

rrusczyk (18:32:04)
And now we'll turn the classroom over to Dan!

DanZ (18:32:13)
Hi everyone!

DanZ (18:32:21)
For those of you who were just taking the AIME yesterday, I hope it went well.

DanZ (18:32:37)
Welcome (back) to Part II of the Infinity Math Jam. If you were here two weeks ago (sorry I missed last week!), or if you looked over the transcript, great: you already know what this is about.

DanZ (18:32:45)
If not, here's what this Math Jam is about. We're going to explore the notion of infinity in a mathematically rigorous way. We're going to understand when you can claim (or when you can't claim) that two infinite sets are the same size, and we're going to look a bit at just how many different sizes of infinity there actually [i]are[/i].

DanZ (18:33:01)
In the last Math Jam, we did things very loosely; we moved dots around, and understood infinity. Today I want to make everything we did more precise, but that means that today will have more notation and be a bit more technical. On the other hand, these details and notation will allow us to do things that we couldn't do before, so our manipulation of infinity will become much more powerful today.

DanZ (18:33:14)
If you weren't here last week: that's okay. However, the beginning might be a bit fast! If you're confused, feel free to take a look afterwards both at the transcript of tonight and of last night.

DanZ (18:33:34)
So: Today, we're going to do three big things.

DanZ (18:33:50)


DanZ (18:34:04)
We basically did that last time, without giving the sets such fancy names. :)

DanZ (18:34:10)


DanZ (18:34:24)


DanZ (18:34:41)
So, I just posted a whole ton of text, and I'll let you catch up reading. Meanwhile, does anyone have any questions from last time before we get going?

DanZ (18:35:36)
(Also, if you're not very familiar with them, I will go over the symbols up there quickly during the Math Jam.)

henry.zheng (18:35:32)
with the tree, what difference does it make if one just throws every point on the tree into a bag and re-arrange it into a line, matching it up with a line of points?

DanZ (18:36:13)
I'm not sure I understand the question! What do you mean by throwing all the points into a bag?

DanZ (18:36:29)
(Feel free to ask as we proceed, but I'm going to get us going.)

DanZ (18:36:35)
First off: last week, we came up with a rule for how to tell when two sets are the same size. How did we do that?

henry.zheng (18:36:46)
we match it up

tjhance (18:36:47)
one-to-one correspondance

XBlaraYZion (18:37:00)
pairing

DanZ (18:37:10)
Yes, excellent.

DanZ (18:37:20)


DanZ (18:37:29)


DanZ (18:37:33)
Image at: //s3.amazonaws.com/classroom.artofproblemsolving.com/Community/MJImages/DanZ/AB_pairinglarge.jpg

DanZ (18:37:52)
(For the record: I'm going to be posting images, and I'll also link to higher-resolution versions on AoPS' website.)

DanZ (18:38:17)
(If you want to see the higher resolution image, you should just be able to click the link. If you have a popup blocker enabled, it may help you to hold ctrl while clicking it.)

DanZ (18:38:21)


DanZ (18:38:57)


DanZ (18:39:02)
Image at: //s3.amazonaws.com/classroom.artofproblemsolving.com/Community/MJImages/DanZ/CD.jpg

DanZ (18:39:08)


DanZ (18:39:18)


DanZ (18:39:31)
That was backwads.

DanZ (18:39:33)
err, backwards.

DanZ (18:39:38)
Ahem. Technical difficulties. :)

DanZ (18:40:11)
Argh. Okay, one moment.

DanZ (18:40:22)


DanZ (18:40:26)
Image at: //s3.amazonaws.com/classroom.artofproblemsolving.com/Community/MJImages/DanZ/CmapstoDlarge.jpg

DanZ (18:40:31)
This image is not a pairing, because we *miss* something.

DanZ (18:40:40)
There's a point of D that's not matched to any point of C.

DanZ (18:40:48)
On the other hand, here's an example that's not a pairing for a different reason:

DanZ (18:40:54)


DanZ (18:41:03)
(This was the first one I accidentally posted.)

DanZ (18:41:09)
Why is this one not a pairing?

henry.zheng (18:41:16)
two goes to one

fredsong (18:41:17)
2 on 1

variable (18:41:23)
It is not one-to-one.

DanZ (18:41:29)
Very good.

DanZ (18:41:37)
The problem is that two things in D are getting sent to the same thing in C.

DanZ (18:41:46)
So it's not a pairing; they don't have the same number of elements.

DanZ (18:42:01)
The idea of a ``pairing'' is something we can generalize to infinity, whereas counting is not; that's why we use it to measure sizes of infinity.

DanZ (18:42:10)
Here's another way to think about why we pair things up. Imagine if I asked you to tell me if a huge jar of red M&M's had the same number of candies as another huge jar with blue M&M's. You could count them, but it'd be hard, and you might lose track. The easier thing to do is to pair them up --- take out a red M&M, then a blue one; then another red one, then another blue one, and so on. If you run out of both colors at the same time, you had the same number; otherwise, you had a different number of each.

DanZ (18:42:29)


DanZ (18:42:50)


DanZ (18:43:05)


DanZ (18:43:11)


DanZ (18:43:28)
Let's refresh our memories a bit more. Are these the same size --- a.k.a. [b]cardinality[/b] --- or are they different cardinalities? And why?

fredsong (18:43:41)
i did Question:so it has to be 1-1.

DanZ (18:43:59)
Yes, pairings have to be 1-1.

CBAJALM (18:44:00)
one goes 2 ways, the other doesn't

DanZ (18:44:18)
Right, so at first they look different.

DanZ (18:44:37)


henry.zheng (18:43:53)
they are the same b/c they can be matched (odds w/ neg.; even w/ pos)

rill2503456 (18:44:00)
They are the same because you can pair up every number in set N to one in set Z

DanZ (18:44:53)
In fact, this is correct: we can match them up by going around.

DanZ (18:44:57)
Or, here's another good way to see it:

Xantos C. Guin (18:44:48)
You can rewrite Z as 0, -1, 1, -2, 2, -3, 3 , ....

DanZ (18:45:13)
Let's see this graphically:

DanZ (18:45:19)


DanZ (18:45:23)
Image at: //s3.amazonaws.com/classroom.artofproblemsolving.com/Community/MJImages/DanZ/NZspirallarge.jpg

DanZ (18:45:29)


tjhance (18:45:31)
now it only goes 1 way!

DanZ (18:46:19)


DanZ (18:46:22)
That's what we're doing with the spiral pattern.

fredsong (18:46:03)
So there are diffrent ways to pair it up?

DanZ (18:46:28)
Yes, lots of them.

DanZ (18:46:48)
I could have done it the other way, matching evens with negatives, odds with positives.

meenamathgirl (18:46:45)
An infinite number, right?

DanZ (18:46:56)
Oh yes!

DanZ (18:47:18)
There are very many ways to pair them up.

DanZ (18:47:24)


JAM (18:47:39)
The same

lordhighgoose (18:47:44)
same, just divide or multiply by 2

CBAJALM (18:47:50)
they are the same size

ActuarialDJ (18:47:55)
you can pair

DanZ (18:48:03)


DanZ (18:48:13)


DanZ (18:48:19)
Image at: //s3.amazonaws.com/classroom.artofproblemsolving.com/Community/MJImages/DanZ/Zwith2Zlarge.jpg

Zmastr (18:48:00)
an element in z can just be matched up with its corresponding element in 2z, like 1 to 2 or -1 to -2

XBlaraYZion (18:48:17)
2z is missing something in z

DanZ (18:48:41)
It is missing something, but we can still pair them up!

DanZ (18:48:52)
One weird thing about infinity is sometimes you can take stuff out without changing the actual size.

DanZ (18:49:09)
So, every integer is paired to exactly one even integer, and vice-versa. Make sense?

macgeekgrl (18:49:16)
you can do that for any nz can't you?

DanZ (18:49:33)
Yes, indeed.

DanZ (18:49:48)
By the way, Jason asked an interesting question:

Jayson Lynch (18:47:57)
now the question is: Is the cardinality of the number of ways to pair them the same cardinality as the natural numbers?

DanZ (18:50:11)


DanZ (18:50:21)
The answer to your question is no: there are more ways to pair them up.

DanZ (18:50:31)
I'll let you think about it yourself, or I can give you a way to see it after the Math Jam.

lordhighgoose (18:49:51)
hm so can you [i]define[/i] an infinite set as one which is the same size as a proper subset of it self

DanZ (18:50:45)
You've heard that before, haven't you? :)

DanZ (18:51:00)
You can, but a better way to define infinite is just ""not finite.""

DanZ (18:51:23)


DanZ (18:51:50)
This one's weird, because there are infinitely many fractions between any two integers...

miramanujan (18:51:58)
with b not equal to 0

DanZ (18:52:36)
I am embarassed. Yes. I meant to write $a$ is in $\mathbb{Z}$, $b$ is in $\mathbb{N}$, but I screwed it up. But yes, you're right!

CBAJALM (18:51:46)
much, much less?

meenamathgirl (18:51:49)
The same

henry.zheng (18:51:55)
same - this time, perform the cool diagonal snaking pyramid act

macgeekgrl (18:52:11)
they are both countable though, you can arrange the rationals into diagonals and count them

fredsong (18:52:26)
there the same

DanZ (18:53:03)
So, there's some disagreement, but they are actually the same!

DanZ (18:53:22)


DanZ (18:53:41)


fredsong (18:54:02)
can just say a=x <==> b=(x-x, x-x)

DanZ (18:54:35)
I'm not quite sure what you're saying there --- doesn't that make b always (0, 0)?

fredsong (18:54:29)
sorry, i got it wrong

DanZ (18:54:40)
No problem, we'll see how it goes.

henry.zheng (18:54:07)
yes

Jayson Lynch (18:54:08)
yes

variable (18:54:36)
Yes - since we could then also pair up N with the negative rationals - and we know we can pair up N with N to get N.

Xantos C. Guin (18:54:47)
Yes since we can use the ""spiral"" technique to pair up positive rational numbers with all rational numbers

meenamathgirl (18:54:07)
Yes because we can do the thing with the spiral later

DanZ (18:55:05)
Very good.

DanZ (18:55:18)
:Yes! Because using that pairing, I could then pair up all positive rational numbers with the positive integers, all negative rational numbers with the negative integers, and then $\frac{0}{1}$ would just get paired with $0$. That shows $|\mathbb{Q}| = |\mathbb{Z}|$. But we already know $|\mathbb{Z}| = |\mathbb{N}|$. So that does it. (My pairing of $\mathbb{N}$ with $\mathbb{Q}$ just goes ``through'' $\mathbb{Z}$.)

rill2503456 (18:55:17)
what was the decision about rationals and intergers, are they equal?

DanZ (18:55:34)
We're actually working on that now.

DanZ (18:55:45)
Sorry, let me repost that last message:

DanZ (18:55:51)


DanZ (18:56:17)
Okay. So here's what I'm going to do:

DanZ (18:56:28)
1. I'm going to show you how to pair up positive rational numbers (fractions) with natural numbers.

DanZ (18:56:33)
2. Then the argument above shows that it's good enough.

DanZ (18:56:39)
Here's the grid:

DanZ (18:56:47)


DanZ (18:56:52)
Image at: //s3.amazonaws.com/classroom.artofproblemsolving.com/Community/MJImages/DanZ/NQpairinglarge.jpg

DanZ (18:56:55)
Look familiar?

rill2503456 (18:56:44)
Can't you try to pair up each interger with a decimal with an equal number of 9's...ie,
1 - .9
2 - .99
3 - .99
...
infinity - 1, and then say that there are still more decimals that weren't paired up?

DanZ (18:57:26)
You can, but there's a subtle point. Even if we have a pairing that doesn't work, there might be a different pairing that does work.

Xantos C. Guin (18:57:12)
This was F^2 from last math jam

DanZ (18:57:37)
Yes.

DanZ (18:57:48)


DanZ (18:57:56)


DanZ (18:58:01)
Image at: //s3.amazonaws.com/classroom.artofproblemsolving.com/Community/MJImages/DanZ/NQpairinglarge.jpg

DanZ (18:58:12)
So now do we pair up each natural number with a fraction? Well, we pair up 1 with 1/1.

DanZ (18:58:17)
Then we follow that spiral you see up above.

DanZ (18:58:25)
2 is paired with 1/2, 3 with 2/1, etc.

DanZ (18:58:33)
And we eventually hit *every* possible fraction, because we get every number on top of every other!

DanZ (18:58:36)


variable (18:58:10)
But is that particular correspondence one-to-one - it counts 2 an infinite number of times: 2n/n for all n?

DanZ (18:59:00)
Right, that's why we sometimes have to skip stuff. That's a good thing to see.

rill2503456 (18:58:39)
but is there any way to be sure that you wont eventually get to a situation where you are skipping every number?

DanZ (18:59:32)
You can't end up skipping everything, since there are always new fractions in lowest terms.

henry.zheng (18:59:18)
wait...but skipping stuff doesn't imply that those elements are missing?

DanZ (18:59:51)
Right, but we only skip stuff that's not in lowest terms --- which means we already got it before.

DanZ (19:00:15)
Okay... any other questions about this? It's pretty weird already!

DanZ (19:00:31)


3468Yz (19:00:15)
May I ask a different question on this topic?

DanZ (19:00:52)
You may ask, but if it's on advanced stuff I may postpone it until later.

variable (19:00:29)
You can define a one-to-one correspondence between two sets without defining which number in one set a particular number in the other set is paired with?

DanZ (19:01:12)
We actually did define which number everything is paired with.

DanZ (19:01:23)
If you give me any natural number, I can follow the grid along far enough until I know exactly where it goes.

DanZ (19:01:36)
If you give me any fraction, I can make a really big grid, follow it out, and figure what went to it.

rill2503456 (19:01:25)
cantors diagonalization proof was about the pairing of real numbers to intergers, right? Is there any way to be sure that his pairing is the only one and that there is no way to say that there are any other pairings that DO work?

DanZ (19:02:00)


DanZ (19:02:08)
There is no pairing between the natural numbers and the real numbers.

henry.zheng (19:02:20)
why?

DanZ (19:02:43)
That's a good question! It's what we're about to investigate, actually.

DanZ (19:02:54)


miramanujan (19:02:52)
is it possible to do it with the open interval (0,1) to N

DanZ (19:03:12)
No, and we'll see this too.

3468Yz (19:03:13)
Is it possible to pair the algebraic numbers and the natural numbers?

DanZ (19:03:36)
Yes. That'll be a problem I'll leave for you, however.

DanZ (19:03:52)
(There are actually several much more rigorous definitions of the real numbers, but they'd take us a bit far off course.)

DanZ (19:03:55)


DanZ (19:04:13)
So how do you think $|\mathbb{N}|$ compares to $|\mathbb{R}|$?

DanZ (19:04:19)


DanZ (19:04:32)


ActuarialDJ (19:04:40)
neither match up

meenamathgirl (19:04:43)
Different cardinalities.

DanZ (19:04:56)
Yes, good.

DanZ (19:05:02)
So suppose I was going to do a proof of that. How would that proof have to go?

rill2503456 (19:05:09)
binary tree!

tjhance (19:05:12)
real numbers are represented by the tree in the last jam

DanZ (19:05:31)
That's true. But let's talk in general.

meenamathgirl (19:05:15)
Contradiction.

DanZ (19:05:39)
That's exactly what I'm looking for.

rill2503456 (19:05:44)
except that we'd to binary tree...but not binary...tennary!

DanZ (19:06:00)
Hehe, yes, sort-of.

DanZ (19:06:09)


DanZ (19:06:27)
Actually, lets do something a bit better (but even stronger).

DanZ (19:06:30)


Jayson Lynch (19:06:08)
show that for any given corospondance of N to R there exists another R

DanZ (19:06:56)
Exactly --- we'll try out any correspondence and find that we misesd something.

rill2503456 (19:06:50)
so the (0,1) is an interval, right?

DanZ (19:07:04)
Yes.

DanZ (19:07:12)


DanZ (19:07:28)


DanZ (19:07:44)


DanZ (19:07:55)


DanZ (19:08:13)


DanZ (19:08:29)


DanZ (19:08:43)


rill2503456 (19:08:42)
I was very confused about the diagonal proof last year...how can we be sure it hasn't been created yet?

DanZ (19:09:01)
We're doing it now, so watch and see. :)

XBlaraYZion (19:09:01)
irrational numbers?

ActuarialDJ (19:09:04)
sqrt 2?

DanZ (19:09:31)
How do we know there are enough irrational numbers we have to miss? We need to find a specific number that we must have missed in our pairing.

henry.zheng (19:09:03)
there's always another branch from any point

DanZ (19:09:39)
This is closing in on it...

meenamathgirl (19:09:31)
Make a new number where the first digit is different from the 1st digit of the number paired with 1, the second digit is different from the 2nd digit of the number paired with 2, etc.

Jayson Lynch (19:09:33)
create a new number whose nth digit is different from the nth digit of the nth paring

DanZ (19:09:50)
Right!

DanZ (19:10:06)


DanZ (19:10:11)
We'll do that again now.

DanZ (19:10:19)


DanZ (19:10:30)
Someone give me the first digit after the decimal point of a number that isn't paired up with 1.

rill2503456 (19:10:42)
5

meenamathgirl (19:10:43)
4

JAM (19:10:49)
7

DanZ (19:10:59)
Sure, any of these are fine.

DanZ (19:11:05)


DanZ (19:11:15)
What should the second digit be?

Xantos C. Guin (19:11:19)
6

henry.zheng (19:11:22)
5

JAM (19:11:29)
7 again :)

DanZ (19:11:47)
Sure.

DanZ (19:11:52)


DanZ (19:12:03)


DanZ (19:12:16)
What should the third digit be?

fredsong (19:12:16)
2

Xantos C. Guin (19:12:20)
3

Superfluid (19:12:20)
5

fredsong (19:12:21)
2

DanZ (19:12:34)
So, the third digit of the third number is *already* 7.

DanZ (19:12:39)
We need to make this one *different*.

DanZ (19:12:47)
Oh, no it's not.

DanZ (19:13:02)
Wow, we have another 3.

DanZ (19:13:13)
Bloody heck. My examples are awful today. :)

DanZ (19:13:18)
Okay, so we had:

DanZ (19:13:28)


DanZ (19:13:46)
I'm now going to fix my mistakes.

DanZ (19:13:59)
We started off with 0.77, because that's different in the first digit from where 1 goes, and it's different in the second digit.

DanZ (19:14:04)
It's different in the second digit from where 2 goes.

DanZ (19:14:17)
Now we need to make our number different in the third digit from where 3 goes.

DanZ (19:14:22)


ActuarialDJ (19:13:41)
The third digit cannot be 4? Is that correct

DanZ (19:14:42)
Yes, you are correct.

DanZ (19:14:50)
(And I was not terribly correct. :))

rill2503456 (19:14:26)
so, we're going diagonally down

rill2503456 (19:14:30)
and making each digit different

DanZ (19:14:58)
Precisely.

DanZ (19:15:03)


DanZ (19:15:31)
So my rule is: 3s change to 7s, everything else changes to a 3.

DanZ (19:15:49)


DanZ (19:15:59)


rill2503456 (19:16:15)
773373

Xantos C. Guin (19:16:20)
0.773373

ActuarialDJ (19:16:24)
773373

3468Yz (19:16:24)
0.773373...

DanZ (19:16:39)
Excellent.

henry.zheng (19:16:34)
that's why throwing all real #'s and rematching it doesn't work.

DanZ (19:16:52)
Right.

DanZ (19:17:00)
We found something this particular pairing missed.

DanZ (19:17:15)
For a different pairing, we might find something [i]else[/i] that it misses.

DanZ (19:17:28)
But what we had *wasn't* a pairing.

RBareuther (19:17:18)
Why 3's and 7's?

DanZ (19:17:41)
Great question! Mostly, it's because I just had to choose *something* --- what it was really didn't matter.

DanZ (19:18:09)
I choose 3 and 7 to make them different from 0 and 9, so I don't run into any problems there. But essentialyl any numbers work.

rill2503456 (19:17:47)
how can you be sure that there isnt a different pairing where it works?

DanZ (19:18:26)
Because for any pairing I can always find something that is missed.

DanZ (19:18:36)
You could ""fix"" this one, but then you'd find a new number that the ""fixed"" pairing missed.

DanZ (19:18:44)
I didn't assume anything about what the pairing does.

DanZ (19:18:51)
Any other questions about this?

DanZ (19:18:56)
I want to understand it before we go on to new stuff.

Jayson Lynch_2 (19:18:48)
because the rule can be applyed to *any* paring

DanZ (19:19:01)
Exactly.

DanZ (19:19:27)
Ok. In that case, let's keep going.

DanZ (19:19:54)
First, I'd like to mention how I would have written this a bit more formally:

DanZ (19:19:57)


DanZ (19:20:02)


DanZ (19:20:10)


DanZ (19:20:27)
You don't have to follow that formal argument, but it might help.

DanZ (19:20:37)
So let me ask you: which one do you think we should think of as ``bigger?''

DanZ (19:20:58)


DanZ (19:21:02)
Which one should be larger?

3468Yz (19:20:54)
(0,1)

tjhance (19:20:56)
real numbers

bubka (19:20:58)
R

CBAJALM (19:20:59)
all real

JAM (19:21:04)
R

DanZ (19:21:17)
Okay, we all agree.

DanZ (19:21:20)
Why?

macgeekgrl (19:21:38)
N is infinite. R is infinite because R is like the cardinality of N to the infinite power

DanZ (19:22:03)
(Hold that thought. It's not quite right, but we'll see a variation that will tell us how it fits in.)

Xantos C. Guin (19:21:19)
|(0,1)|>|N|

variable (19:21:21)
R - since R includes N.

rill2503456 (19:21:48)
Since there are numbers in the set of reals that the intergers cant even touch, there must be more!

CBAJALM (19:21:56)
R always has 1 left over

Xantos C. Guin (19:21:56)
Cause we could find something that was missed in R, after all N were used up

meenamathgirl (19:22:20)
Because when N is compared to R there are terms left out in R?

DanZ (19:22:33)
Okay, lots of good reasons.

DanZ (19:22:38)
Here's my reason:

DanZ (19:22:49)


DanZ (19:23:06)


DanZ (19:23:27)


DanZ (19:23:30)


DanZ (19:23:43)


DanZ (19:23:45)


DanZ (19:24:00)
Does that make sense as a definition for us?

rill2503456 (19:22:27)
I think that you can't say infinite anymore...Infinity is too broad...can we start using aleph-null and aleph-one or whatever it is?

DanZ (19:24:17)
Hold on --- defining those is trickier than you might think!

DanZ (19:24:31)


DanZ (19:24:51)


DanZ (19:25:13)


DanZ (19:25:19)


DanZ (19:25:49)


ActuarialDJ (19:25:57)
so that would make Q < R as well

DanZ (19:26:12)
Yes, good.

bubka (19:26:02)
there is a scroeder bernstein theorem ...

DanZ (19:26:23)
You're right, and I'll mention it later.

DanZ (19:26:38)
Okay. Let's talk about what a ""pairing"" really should be.

DanZ (19:26:41)


DanZ (19:26:48)


DanZ (19:26:53)


DanZ (19:27:03)


Xantos C. Guin (19:27:35)
No, since -2 and 2 corrresponds to 4

Hamster1800 (19:27:40)
No, since some f(x)'s don't have corresponding x's (e.x. f(x)=-1)

DanZ (19:28:01)
Two excellent reasons!

DanZ (19:28:08)


DanZ (19:28:23)


DanZ (19:28:55)


DanZ (19:29:09)


DanZ (19:29:33)


DanZ (19:29:43)
This was not a pairing, because the first two dots of D go to the same thing in C.

DanZ (19:29:48)
Or here's an example in the infinite case:

DanZ (19:29:55)


DanZ (19:30:00)
Image at: //s3.amazonaws.com/classroom.artofproblemsolving.com/Community/MJImages/DanZ/NNsurjectionlarge.jpg

DanZ (19:30:07)
Do you all agree that both of these aren't actually pairings?

Zmastr (19:30:11)
yes

3468Yz (19:30:14)
Yes.

Zmastr (19:30:15)
they aren't one-to-one

Jayson Lynch_2 (19:30:18)
yes

DanZ (19:30:26)
Excellent.

DanZ (19:30:40)


DanZ (19:30:47)
It ""took two things to the same thing.""

DanZ (19:30:56)
In fact, a really awful function could even take everything to just one element!

DanZ (19:31:28)


DanZ (19:31:32)
Image at: //s3.amazonaws.com/classroom.artofproblemsolving.com/Community/MJImages/DanZ/NtoPointlarge.jpg

ActuarialDJ (19:31:16)
f(x) = 1

macgeekgrl (19:31:26)
f(x)=0

DanZ (19:31:49)
Or those, yup.

DanZ (19:31:54)


DanZ (19:32:07)


DanZ (19:32:16)
Here are some other examples of what happens when you miss something:

DanZ (19:32:27)


DanZ (19:32:36)
This function we saw before, from C to D, missed something in D, so it wasn't a pairing.

DanZ (19:32:38)
and the infinite case

DanZ (19:32:50)


DanZ (19:32:54)
Image at: //s3.amazonaws.com/classroom.artofproblemsolving.com/Community/MJImages/DanZ/NNinjectionlarge.jpg

DanZ (19:33:02)
This misses all the even numbers!

henry.zheng (19:32:38)
our f(x) misses negatives!

DanZ (19:33:09)
Yes!

DanZ (19:33:13)
Good call.

DanZ (19:33:28)


DanZ (19:33:35)


DanZ (19:33:45)


DanZ (19:33:58)
Does that all make sense?

DanZ (19:34:05)
Any questions about this?

miramanujan (19:34:04)
yes

bubka (19:34:05)
sure

fredsong (19:34:05)
sure

ActuarialDJ (19:34:15)
makes sense

DanZ (19:34:24)
Great.

DanZ (19:34:57)
This is the beginning of where we can put down definitions we can really test. Instead of just looking at something and saying ""yup, it's a pairing,"" or ""no, it's not,"" we have criteria we can actually apply.

henry.zheng (19:34:23)
so f(x) = 2x is a bijection

DanZ (19:35:01)
Yes!

DanZ (19:35:06)
Very good.

DanZ (19:35:18)


DanZ (19:35:25)


DanZ (19:35:44)
So being ""half"" of a bijection is enough to tell you that one set is smaller than another.

bubka (19:35:53)
f(x) = x cubed is a bijection

DanZ (19:36:07)
Yes, that's really funny, isn't it?

DanZ (19:36:21)


meenamathgirl (19:36:05)
Couldn't a bijection also be that like it's one to one both ways?

DanZ (19:36:37)
Very good! But you can't get the ""other way"" unless it's already a bijection.

rill2503456 (19:37:04)
so f(x)=x^any odd is a bijection?

DanZ (19:37:13)
Yes.

Zmastr (19:37:08)
What about if X < or equal to Y, and if Y < or equal to X then X is Y! What was that trying to say?

DanZ (19:37:27)
I'll get to that in a bit.

DanZ (19:37:34)
Right now, though, I'd like to show you a few other bijections quickly.

DanZ (19:37:49)
I'm going to have to go through my notes a bit fast, since we've already gone a long time!

DanZ (19:38:00)


DanZ (19:38:05)


DanZ (19:38:07)


DanZ (19:38:14)
How do you think these two compare in size?

Xantos C. Guin (19:38:20)
the same

3468Yz (19:38:23)
Same size.

meenamathgirl (19:38:25)
The same

DanZ (19:38:36)
Why?

JAM (19:38:35)
The same, use f(x) = 2x

DanZ (19:38:43)
Good!

DanZ (19:38:55)


DanZ (19:39:07)


DanZ (19:39:12)


DanZ (19:39:18)


DanZ (19:39:24)
Image at: //s3.amazonaws.com/classroom.artofproblemsolving.com/Community/MJImages/DanZ/0102large.jpg

DanZ (19:39:28)


DanZ (19:39:43)


DanZ (19:40:02)


DanZ (19:40:08)


DanZ (19:40:21)
Is that OK?

Xantos C. Guin (19:40:40)
Would it work with [a,b) and [c,d)?

DanZ (19:40:53)
It could if you reversed one first.

DanZ (19:40:58)
To get those annoying endpoints to line up!

DanZ (19:41:10)
In fact, [a, b) and (a, b) are the same size, but due to time I won't prove that right now.

3468Yz (19:40:48)
What about |R| and (0,1)? Can those be paired?

DanZ (19:41:22)
Good question! What do you all think?

Zmastr (19:41:27)
yes

meenamathgirl (19:41:31)
Yes

Jayson Lynch_2 (19:41:34)
yes

DanZ (19:41:49)
How?

Zmastr (19:41:32)
multiply by r

DanZ (19:41:56)
What does that mean?

Xantos C. Guin (19:41:52)
Yes, use a tangent function

DanZ (19:42:14)
Ah, good call. We'll do that, but it's going to be disguised as a picture.

bubka (19:42:01)
draw a curved line below an infinite line and use the above method

macgeekgrl (19:41:40)
with the circle-line projection thingty

DanZ (19:42:37)
So, what I'm going to do is take the interval $(0, 1)$ and curve it up into a half-circle:

DanZ (19:42:44)


DanZ (19:42:53)


DanZ (19:42:58)
Image at: //s3.amazonaws.com/classroom.artofproblemsolving.com/Community/MJImages/DanZ/01Rlarge.jpg

DanZ (19:43:00)
Now you should see what happens...

DanZ (19:43:10)


DanZ (19:43:21)


DanZ (19:43:26)
Image at: //s3.amazonaws.com/classroom.artofproblemsolving.com/Community/MJImages/DanZ/01Rpairinglarge.jpg

DanZ (19:43:36)


DanZ (19:43:56)
In other words, as the line gets closer to being parallel with the real line, it goes farther and farther out along it, eventually hitting every real number.

macgeekgrl (19:44:13)
does 0 and 1 hit anything though

DanZ (19:44:32)
No! But that's okay.

DanZ (19:44:43)


DanZ (19:45:19)


DanZ (19:45:32)
(For some reason my LaTeX isn't rendering for me.)

DanZ (19:45:45)
Anyway, it's okay, because we're doing (0, 1), where 0 and 1 aren't included.

DanZ (19:46:01)
Now, due to time, I'm going to skip a proof.

DanZ (19:46:06)
But you should think about this, and you can ask me later.

DanZ (19:46:21)


DanZ (19:46:34)
Where $\mathbb{R}^2$ is a plane.

DanZ (19:46:38)


DanZ (19:47:13)


Jayson Lynch_2 (19:47:11)
same, use the diagnal method again.

macgeekgrl (19:47:17)
diagonal thing again

DanZ (19:47:37)
Watch out! You can't just go diagonally like that because it's not discrete.

DanZ (19:47:53)
So, I'm not going to give the proof, but I'll tell you that they [i]are[/i] the same.

DanZ (19:48:08)
And the way to see it is a bit complicated, but very cool. Essentially, you ""interweave"" the digits.

DanZ (19:48:19)
If you want to see this after the Math Jam, I'll be happy to show you.

bubka (19:47:58)
we can write them in binary expansion and take alternate digits of x and y to get the corresponding element in R for (x, y)

DanZ (19:48:29)
That's essentially correct!

DanZ (19:48:55)
Okay. I want to do one more thing tonight, which will let us construct infinitely many sizes of infinity.

DanZ (19:48:57)
Who's heard of power sets before?

DanZ (19:49:25)
Ok, excellent.

DanZ (19:49:34)


DanZ (19:49:40)


miramanujan (19:49:37)
set of all subsets of the set

DanZ (19:49:55)
Exactly.

DanZ (19:49:59)


DanZ (19:50:14)


DanZ (19:51:16)
So, many of you have good answers for the finite case:

Zmastr (19:50:54)
Because n is always less than 2 to the nth power?

macgeekgrl (19:51:03)
n <= 2^n

miramanujan (19:51:03)
n less tha or eual to 2 power n

DanZ (19:51:31)
But here's one that generalizes to the infinite case:

Hamster1800 (19:51:00)
All one element subsets of A are in P(A), and each one can correspond to the element, so there is a bijection between A and a subset of P(A).

DanZ (19:51:49)


DanZ (19:51:53)


DanZ (19:52:13)


DanZ (19:52:19)


DanZ (19:52:33)
Even for infinite sets, now!

miramanujan (19:52:39)
in the case of finite yes

DanZ (19:52:52)
Good, that's progress...

Zmastr (19:53:01)
Yes because P(A) always contains A and other stuff

meenamathgirl (19:53:05)
Bigger, because lots of terms in P(A) aren't in A?

DanZ (19:53:17)
That's good intuition.

DanZ (19:53:20)
It's not a proof.

DanZ (19:53:24)
But we can, in fact, make a proof.

DanZ (19:53:32)
It's going to go almost exactly like our other proofs!

DanZ (19:54:01)


meenamathgirl (19:53:55)
Contradiction?

variable (19:54:01)
Contradiction.

DanZ (19:54:27)
You guys are learning fast. :)

DanZ (19:54:42)


DanZ (19:54:56)
The trick is to show that it's not actually a bijection, which means we have to find something that it [i]misses[/i].

DanZ (19:55:07)


DanZ (19:55:23)


DanZ (19:55:39)
(My LaTeX isn't working again...)

DanZ (19:55:54)


DanZ (19:56:14)
Okay, I'm going to write this in plain text.

DanZ (19:56:28)
If we think carefully about it: the elements of P(A) are the [i]subsets[/i] of A.

DanZ (19:56:42)


DanZ (19:56:54)
Many of you have the right ideas:

Hamster1800 (19:55:44)
Say we pair A with P(A), we could construct a subset that includes a (in A) iff the element in P(A) that corresponds to a excludes it, would that work?

bubka (19:55:29)
the set of all x such that x does not belong to f(x)

DanZ (19:57:13)
These are all on the right track.

DanZ (19:57:19)


DanZ (19:57:35)
This is tricky!

DanZ (19:57:39)


miramanujan (19:57:46)
will it be non empty?

DanZ (19:58:01)
That's a good question. If it's empty, that's OK.

DanZ (19:58:07)
The empty set is also an element of P(A).

DanZ (19:59:00)
(One sec.)

DanZ (19:59:16)


DanZ (19:59:37)


macgeekgrl (19:59:54)
3,4

JAM (19:59:55)
3 and 4

bubka (19:59:56)
3, 4

DanZ (20:00:08)
Great.

DanZ (20:00:11)


bubka (20:00:25)
sure

Jayson Lynch_2 (20:00:30)
yes

DanZ (20:00:35)


Jayson Lynch_2 (20:00:55)
no

fredsong (20:01:15)
no

Hamster1800 (20:01:25)
No, because if f(a) = B, then we get a contradiction since by the definition of B, B includes a iff B doesn't include a

DanZ (20:01:34)
Very good.

DanZ (20:01:39)
Let me expand out what you just said case-by-case:

DanZ (20:01:51)


DanZ (20:01:59)


JAM (20:02:33)
By defintion, if it is then it isn't, and if it isn't then it is

Zmastr (20:02:40)
maybe

DanZ (20:02:49)
Hehe. Confusing stuff!

miramanujan (20:02:44)
no

DanZ (20:03:06)
Right!

DanZ (20:03:11)


DanZ (20:03:27)
Follow through the definitions: if a is in B, then it's not in B.

DanZ (20:03:28)
This is weird.

DanZ (20:03:33)


macgeekgrl (20:03:47)
yup

Zmastr (20:03:47)
yes

Zmastr (20:03:50)
now it is

meenamathgirl (20:03:52)
yes

DanZ (20:04:05)


DanZ (20:04:16)
Now, let's think about where we are.

DanZ (20:04:23)


DanZ (20:04:30)


DanZ (20:04:35)


DanZ (20:05:03)


DanZ (20:05:18)
But any attempt to pair up these two sets has to fail; you can always build a set B which you must have missed!

Zmastr (20:05:00)
wow

macgeekgrl (20:05:08)
oh no!

DanZ (20:05:39)
Yeah.

DanZ (20:05:43)
It's just like before, but more abstract.

DanZ (20:05:59)


DanZ (20:06:18)
So how many different sizes of infinity are there?

Hamster1800 (20:06:24)
as many as you want

Xantos C. Guin (20:06:29)
an infinite ammount

Jayson Lynch_2 (20:06:29)
infinitly many

meenamathgirl (20:06:32)
Infinite!

Zmastr (20:06:36)
infinity sizes of infinity

3468Yz (20:06:38)
At least two.

DanZ (20:06:51)
Like good mathematicians, you are all correct. :)

bubka (20:06:46)
at least countably many, as of now

DanZ (20:07:10)
Bubka: you're right. All we've shown is that we can keep making more power sets:

DanZ (20:07:17)


DanZ (20:07:34)
(So many it runs off the screen!)

DanZ (20:07:41)
(But there are much, much, [i]much[/i] larger infinities than what I wrote above. As a start, you could take the [i]union[/i] of all the above sets and get something even bigger. But then you could take power sets of that, and then the union of all of those, and so on, iterating the process infinitely many times. Then you could take the union of all of those... and these are still small compared to all the different infinites out there!)

DanZ (20:08:10)
(You may be wondering if your brain is supposed to hurt at this point. The answer is yes. :))

DanZ (20:08:13)
There are two natural questions to ask, aside from ``what demented person ever came up with this?''. Those questions are:

DanZ (20:08:17)


bubka (20:08:25)
will the union be bigger than the largest set?

DanZ (20:08:38)
Watch out --- no largest set!

DanZ (20:08:50)
There can't be a largest set, because you can always take the power set of that set and get a *bigger* one.

DanZ (20:09:12)
I'm going to skip the answer to the second for now, although I can give you a handwavy reason why there actually have to be [i]more[/i] sizes of infinity than any actual size of infinity! The precise reason requires using the axioms of set theory a bit more closely.

DanZ (20:09:25)
If you want to know this, ask me at the end (we're just about done now).

DanZ (20:09:50)


DanZ (20:09:54)


DanZ (20:09:57)


DanZ (20:10:07)


DanZ (20:10:11)


DanZ (20:10:19)


DanZ (20:10:26)


DanZ (20:10:32)
Image at: //s3.amazonaws.com/classroom.artofproblemsolving.com/Community/MJImages/DanZ/NNadd3large.eps

DanZ (20:10:34)
and

DanZ (20:10:39)


DanZ (20:10:43)
Image at: //s3.amazonaws.com/classroom.artofproblemsolving.com/Community/MJImages/DanZ/NNmultby2large.jpg

DanZ (20:10:52)


DanZ (20:11:23)
It turns out that you can do this.

DanZ (20:11:27)
It's called the Shroeder-Bernstein theorem.

DanZ (20:11:33)
But it's hard to prove. I'll offer you a guided tour later on.

DanZ (20:11:53)
It also lets you do one other interesting thing.

DanZ (20:12:08)


DanZ (20:12:15)
That should be pretty amazing.

DanZ (20:12:32)


DanZ (20:12:47)
Using the Shroeder-Bernstein theorem, you have the tools to prove this yourself.

DanZ (20:12:58)
Ok, so, I have run over.

DanZ (20:13:08)
(I was going to show you that last thing myself, but there really isn't time.)

3468Yz (20:12:57)
Then does |P(P(N))| = |P(R)|?

DanZ (20:13:19)
Yes!

DanZ (20:13:20)
Good.

DanZ (20:13:26)
Before we close up, I'd like to mention a few things. You're not expected to understand any of it, but you might find it interesting anyway!

DanZ (20:13:40)


DanZ (20:13:54)


DanZ (20:14:05)


DanZ (20:14:34)


DanZ (20:14:48)
Okay. So, that's all I have for tonight.

DanZ (20:14:55)
Questions about what I've said?

Jayson Lynch_2 (20:14:08)
Yes... there is a reason he went crazy...

bubka (20:14:33)
paradise lost :)

DanZ (20:15:05)
(Hehe.)

Zmastr (20:15:19)
this material is eye-opening yet spine-shivering

DanZ (20:15:30)
Excellent! There is a lot more out there.

DanZ (20:15:34)
Was this comprehensible? Did you guys have fun, and learn something?

bubka (20:15:45)
wow Zmastr is very poetic

henry.zheng (20:15:42)
oh yes definitely!

JAM (20:15:51)
Yeah

3468Yz (20:15:52)
Yes, yes, and yes.

DanZ (20:16:00)
Excellent!

henry.zheng (20:15:34)
will there be a sequel?

Superfluid (20:16:01)
Yes!!

meenamathgirl (20:15:25)
Thank you!

DanZ (20:16:11)
I would actually like to do a sequel.

DanZ (20:16:29)
I'd like to prove a couple of things I missed today, and tell you a little bit about how you can do arithmetic with ""infinite numbers"" (and explain what those are).

DanZ (20:16:43)
Would you guys be interested, same time next week?

Jayson Lynch_2 (20:16:36)
I'd love to see this continued

meenamathgirl (20:16:50)
Yes!

bubka (20:16:51)
of course

Xantos C. Guin (20:16:53)
yes

henry.zheng (20:16:53)
definitely!

bubka (20:16:54)
without question

Hamster1800 (20:16:58)
sure. Also, do you have a problem set like you did last week?

DanZ (20:17:05)
Sweet!

DanZ (20:17:11)
I actually feel bad, because I didn't prepare this week as well as last time.

DanZ (20:17:15)
Things have been really busy for me!

DanZ (20:17:21)
But next week is my spring break. :)?

DanZ (20:17:29)
Now, I meant to also offer you some new problems for this week, like the ones from last week, but I actually haven't quite finished writing them yet! They're almost done, and when they are I really encourage you to look at them. You'll get to prove the Shroeder-Bernstein theorem, for example. You'll be able to find them at my web page,

DanZ (20:17:38)
They'll definitely be up by tomorrow.

DanZ (20:17:41)
http://www.math.uiuc.edu/~dzaharo2/teaching/mathjam/

DanZ (20:17:57)
That's all for tonight. I'm going to stick around to answer any questions you might have. Thanks for coming!

DanZ (20:18:16)
Good night everyone, and thanks for sticking around for the extra-long time.

bubka (20:18:33)
there is some omega stuff related to ordinal numbers that i have no idea about at all, could you touch them?

DanZ (20:18:46)
I do plan to talk about it next time.

DanZ (20:19:22)
There are two ""kinds"" of infinite numbers that people use commonly, if you will. One counts just sizes; another includes ordering.

DanZ (20:19:28)
Those are ""ordinals,"" and those get you the omegas.

henry.zheng (20:18:40)
thanks alot.

DanZ (20:19:38)
Thank you for coming!

bubka (20:20:00)
see you next week

DanZ (20:20:12)
Yes! See you next week.

3468Yz (20:20:18)
Does |(0,1)| = the number of ordered triples?

DanZ (20:20:45)
What do you mean by ""ordered tripes?""

3468Yz (20:21:52)
I mean sets of three real numbers, but where order matters. For example, (2,1,3) and (1,3,2) are different ordered triples.

DanZ (20:22:18)
Yes, they are the same.

DanZ (20:22:27)
You can do a similar thing with interweaving digits.

3468Yz (20:23:03)
Like (0.023000...,0.024000...,0.025000) --> 0

DanZ (20:23:18)
They won't go to 0.

3468Yz (20:23:17)
.000000000222345000...

DanZ (20:23:25)
Ah, yes.

DanZ (20:23:26)
That's close.

DanZ (20:23:30)
You actually don't quite want to do it that way.

DanZ (20:23:37)
There are some details. :)

3468Yz (20:23:34)
Right. I accidentally pressed enter.

DanZ (20:24:06)
I'll put up a little something on that web page about those details.

DanZ (20:24:09)
But yes, it works.

bubka (20:24:27)
in fact R to the power of anything finite is the same as R

DanZ (20:24:45)
Yes indeed.

DanZ (20:25:38)
Okay, so: I will see you all next week. Expect a very exciting night!

DanZ (20:25:52)
Until then, good night! And hope you get more sleep than I did last night! :)