Transcript Ch. 11: Cantor*s Infinity!

Ch. 11: Cantor’s Infinity!
N = {1, 2, 3, 4, 5, 6, …} “the natural numbers”
Z = {…, –3, –2, –1, 0, 1, 2, 3, …} “the integers”
Q = {all quotients “a/b” of integers with b≠0} “the rationals”
R = {all real numbers} “the real numbers”
Which of these sets is the largest? Do they all have the same size?
N = {1, 2, 3, 4, 5, 6, …} “the natural numbers”
Z = {…, –3, –2, –1, 0, 1, 2, 3, …} “the integers”
Q = {all quotients “a/b” of integers with b≠0} “the rationals”
R = {all real numbers} “the real numbers”
Which of these sets is the largest? Do they all have the same size?
OLD-FASHIONED DEFINITION OF “SAME SIZE”: A pair of sets is said
to have the same size if either (1) they are both finite and have the
same number of members, or (2) they are both infinite.
According to this definition, all of the sets above have the same size.
N = {1, 2, 3, 4, 5, 6, …} “the natural numbers”
Z = {…, –3, –2, –1, 0, 1, 2, 3, …} “the integers”
Q = {all quotients “a/b” of integers with b≠0} “the rationals”
R = {all real numbers} “the real numbers”
Which of these sets is the largest? Do they all have the same size?
OLD-FASHIONED DEFINITION OF “SAME SIZE”: A pair of sets is said
to have the same size if either (1) they are both finite and have the
same number of members, or (2) they are both infinite.
According to this definition, all of the sets above have the same size.
What else could “same size” possibly mean? Think about
how you decide whether two sets have the same size…
What else could “same size” possibly mean? Think about
how you decide whether two sets have the same size…
How can a child who can’t yet count to seven decide
whether there are equal numbers of cars and drivers?
What else could “same size” possibly mean? Think about
how you decide whether two sets have the same size…
How can a child who can’t yet count to seven decide
whether there are equal numbers of cars and drivers?
BY MATCHING!
What else could “same size” possibly mean? Think about
how you decide whether two sets have the same size…
How can a child who can’t yet count to seven decide
whether there are equal numbers of cars and drivers?
BY MATCHING!
When comparing two infinite sets,
Your situation is similar to this child’s.
You don’t know how to separately
count each set … so you should try matching!
What else could “same size” possibly mean? Think about
how you decide whether two sets have the same size…
How can a child who can’t yet count to seven decide
whether there are equal numbers of cars and drivers?
BY MATCHING!
When comparing two infinite sets,
Your situation is similar to this child’s.
You don’t know how to separately
count each set … so you should try matching!
We have the
same number
of fingers!
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
We have the same number of fingers.
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
IMPORTANT: From now on, to decide whether two sets have the same size,
your only job will be to determine whether their members can be matched
with a one-to-one correspondence!
We have the same number of fingers.
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
IMPORTANT: From now on, to decide whether two sets have the same size,
your only job will be to determine whether their members can be matched
with a one-to-one correspondence!
Q: Do these sets have the same size:
N = {1, 2, 3, 4, 5, 6, …} “the natural numbers”
E = {2, 4, 6, 8, 10, 12, …} “the even natural numbers”
We have the same number of fingers.
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
IMPORTANT: From now on, to decide whether two sets have the same size,
your only job will be to determine whether their members can be matched
with a one-to-one correspondence!
Q: Do these sets have the same size:
N = {1, 2, 3, 4, 5, 6, …} “the natural numbers”
E = {2, 4, 6, 8, 10, 12, …} “the even natural numbers”
WRONG ANSWERS:
“Yes, because they are both infinite”
“No, because N contains all of E’s members plus more.”
We have the same number of fingers.
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
IMPORTANT: From now on, to decide whether two sets have the same size,
your only job will be to determine whether their members can be matched
with a one-to-one correspondence!
Q: Do these sets have the same size: YES!
Formula:
n
N = {1, 2, 3, 4, 5, 6, …} “the natural numbers”
E = {2, 4, 6, 8, 10, 12, …} “the even natural numbers”
2n
We have the same number of fingers.
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
IMPORTANT: From now on, to decide whether two sets have the same size,
your only job will be to determine whether their members can be matched
with a one-to-one correspondence!
Q: Do these sets have the same size: YES!
Formula:
n
N = {1, 2, 3, 4, 5, 6, …} “the natural numbers”
E = {2, 4, 6, 8, 10, 12, …} “the even natural numbers”
2n
How strange that an infinite set can have the
same size as a subset of itself!
We have the same number of fingers.
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
IMPORTANT: From now on, to decide whether two sets have the same size,
your only job will be to determine whether their members can be matched
with a one-to-one correspondence!
Main Goal: to decide which pairs of these sets have the same size
N = {1, 2, 3, 4, 5, 6, …} “the natural numbers”
Z = {…, –3, –2, –1, 0, 1, 2, 3, …} “the integers”
Q = {all quotients “a/b” of integers with b≠0} “the rationals”
R = {all real numbers} “the real numbers”
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
IMPORTANT: From now on, to decide whether two sets have the same size,
your only job will be to determine whether their members can be matched
with a one-to-one correspondence!
Q: Do these sets have the same size:
N = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, …}
“the natural numbers”
Z={…,-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, …}
“the integers”
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
IMPORTANT: From now on, to decide whether two sets have the same size,
your only job will be to determine whether their members can be matched
with a one-to-one correspondence!
Q: Do these sets have the same size:
N = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, …}
“the natural numbers”
Z={…,-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, …}
WRONG ANSWERS:
“Yes, because they are both infinite”
“No, because Z goes to infinity in two directions.”
“the integers”
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
IMPORTANT: From now on, to decide whether two sets have the same size,
your only job will be to determine whether their members can be matched
with a one-to-one correspondence!
Q: Do these sets have the same size:
N = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, …}
“the natural numbers”
Z={…,-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, …}
“the integers”
WRONG ANSWERS:
“Yes, because they are both infinite”
“No, because Z goes to infinity in two directions.”
“No, because my first attempt “n
n” is not a valid one-to-one correspondence.”
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
IMPORTANT: From now on, to decide whether two sets have the same size,
your only job will be to determine whether their members can be matched
with a one-to-one correspondence!
Q: Do these sets have the same size:
N = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, …}
“the natural numbers”
Z={…,-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, …}
“the integers”
BIG IDEA: Match the evens in N with the positives in Z…
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
IMPORTANT: From now on, to decide whether two sets have the same size,
your only job will be to determine whether their members can be matched
with a one-to-one correspondence!
Q: Do these sets have the same size:
N = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, …}
(even n)
Z={…,-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, …}
BIG IDEA: Match the evens in N with the positives in Z…
n/2
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
IMPORTANT: From now on, to decide whether two sets have the same size,
your only job will be to determine whether their members can be matched
with a one-to-one correspondence!
Q: Do these sets have the same size:
N = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, …}
Z={…,-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, …}
(even n)
n/2
BIG IDEA: Match the evens in N with the positives in Z…
…which leaves the odds in N free to match with the negatives in Z.
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
IMPORTANT: From now on, to decide whether two sets have the same size,
your only job will be to determine whether their members can be matched
with a one-to-one correspondence!
Q: Do these sets have the same size:
N = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, …}
Z={…,-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, …}
(even n)
n/2
BIG IDEA: Match the evens in N with the positives in Z…
…which leaves the odds in N free to match with the negatives in Z.
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
IMPORTANT: From now on, to decide whether two sets have the same size,
your only job will be to determine whether their members can be matched
with a one-to-one correspondence!
Q: Do these sets have the same size:
N = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, …}
Z={…,-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, …}
(even n)
n/2
BIG IDEA: Match the evens in N with the positives in Z…
…which leaves the odds in N free to match with the negatives in Z.
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
IMPORTANT: From now on, to decide whether two sets have the same size,
your only job will be to determine whether their members can be matched
with a one-to-one correspondence!
Q: Do these sets have the same size:
N = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, …}
Z={…,-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, …}
(even n)
n/2
BIG IDEA: Match the evens in N with the positives in Z…
…which leaves the odds in N free to match with the negatives in Z.
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
IMPORTANT: From now on, to decide whether two sets have the same size,
your only job will be to determine whether their members can be matched
with a one-to-one correspondence!
Q: Do these sets have the same size:
N = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, …}
Z={…,-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, …}
(even n)
n/2
BIG IDEA: Match the evens in N with the positives in Z…
…which leaves the odds in N free to match with the negatives in Z.
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
IMPORTANT: From now on, to decide whether two sets have the same size,
your only job will be to determine whether their members can be matched
with a one-to-one correspondence!
Q: Do these sets have the same size:
N = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, …}
Z={…,-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, …}
(even n)
n/2
BIG IDEA: Match the evens in N with the positives in Z…
…which leaves the odds in N free to match with the negatives in Z.
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
IMPORTANT: From now on, to decide whether two sets have the same size,
your only job will be to determine whether their members can be matched
with a one-to-one correspondence!
Q: Do these sets have the same size: YES!
N = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, …}
Z={…,-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, …}
(even n)
(odd n)
n/2
-(n-1)/2
BIG IDEA: Match the evens in N with the positives in Z…
…which leaves the odds in N free to match with the negatives in Z.
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
IMPORTANT: From now on, to decide whether two sets have the same size,
your only job will be to determine whether their members can be matched
with a one-to-one correspondence!
Q: Do these sets have the same size: YES!
N = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, …}
Z={…,-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, …}
(even n)
(odd n)
n/2
-(n-1)/2
BIG IDEA: Match the evens in N with the positives in Z…
…which leaves the odds in N free to match with the negatives in Z.
The matching looks simpler if we re-order the members of Z…
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
IMPORTANT: From now on, to decide whether two sets have the same size,
your only job will be to determine whether their members can be matched
with a one-to-one correspondence!
N = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, …}
Z = {0, 1, -1, 2, -2, 3, -3, 4, -4, 5,…}
(even n)
(odd n)
n/2
-(n-1)/2
BIG IDEA: Match the evens in N with the positives in Z…
…which leaves the odds in N free to match with the negatives in Z.
The matching looks simpler if we re-order the members of Z…
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
DEFINITION: An infinite set is called countable if it has the same
size as N (the set of natural numbers).
(We just proved that Z is countable)
N = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, …}
Z = {0, 1, -1, 2, -2, 3, -3, 4, -4, 5,…}
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
DEFINITION: An infinite set is called countable if it has the same
size as N (the set of natural numbers).
(We just proved that Z is countable)
N = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, …}
Z = {0, 1, -1, 2, -2, 3, -3, 4, -4, 5,…}
1st 2nd 3rd 4th 5th 6th 7th 8th 9th 10th …
To prove that an infinite set is countable, we must find an infinite listing of its members
{1st, 2nd, 3rd, …} which is organized so as to eventually include each member.
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
DEFINITION: An infinite set is called countable if it has the same
size as N (the set of natural numbers).
(We previously proved that E is countable)
N = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, …}
E = {0, 2, 4, 6, 8, 10, 12, 14, 16, 18,…}
1st 2nd 3rd 4th 5th 6th
7th
8th
9th
10th …
To prove that an infinite set is countable, we must find an infinite listing of its members
{1st, 2nd, 3rd, …} which is organized so as to eventually include each member.
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
DEFINITION: An infinite set is called countable if it has the same
size as N (the set of natural numbers).
Question: Is Q countable? (the set of rational numbers)
In other words, do the sets Q and N have the same size?
To prove that an infinite set is countable, we must find an infinite listing of its members
{1st, 2nd, 3rd, …} which is organized so as to eventually include each member.
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
DEFINITION: An infinite set is called countable if it has the same
size as N (the set of natural numbers).
Question: Is Q countable? (the set of rational numbers)
In other words, do the sets Q and N have the same size?
Can we list {1st rational, 2nd rational, 3rd rational, …} is a manner that’s
organized so as to eventually include each rational?
To prove that an infinite set is countable, we must find an infinite listing of its members
{1st, 2nd, 3rd, …} which is organized so as to eventually include each member.
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
DEFINITION: An infinite set is called countable if it has the same
size as N (the set of natural numbers).
Question: Is Q countable? (the set of rational numbers)
In other words, do the sets Q and N have the same size?
Can we list {1st rational, 2nd rational, 3rd rational, …} is a manner that’s
organized so as to eventually include each rational?
FIRST ATTEMPT:
1/1,
1/2,
1/3,
1/4,
1/5,
1/6, …
Does this pattern eventually include every fraction?
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
DEFINITION: An infinite set is called countable if it has the same
size as N (the set of natural numbers).
Question: Is Q countable? (the set of rational numbers)
In other words, do the sets Q and N have the same size?
Can we list {1st rational, 2nd rational, 3rd rational, …} is a manner that’s
organized so as to eventually include each rational?
FIRST ATTEMPT:
1/1,
1/2,
1/3,
1/4,
1/5,
1/6, …
Does this pattern eventually include every fraction?
NO, it only includes the positive fractions with numerator 1.
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
DEFINITION: An infinite set is called countable if it has the same
size as N (the set of natural numbers).
Question: Is Q countable? (the set of rational numbers)
In other words, do the sets Q and N have the same size?
Can we list {1st rational, 2nd rational, 3rd rational, …} is a manner that’s
organized so as to eventually include each rational?
FIRST ATTEMPT:
1/1,
1/2,
1/3,
2/3,
1/4,
1/5,
2/4, 3/4,
1/6, …
2/5, 3/5, 4/5,
Idea: insert the other numerators
2/6, 3/6, 4/6, 5/6,
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
DEFINITION: An infinite set is called countable if it has the same
size as N (the set of natural numbers).
Question: Is Q countable? (the set of rational numbers)
In other words, do the sets Q and N have the same size?
Can we list {1st rational, 2nd rational, 3rd rational, …} is a manner that’s
organized so as to eventually include each rational?
FIRST ATTEMPT:
1/1,
1/2,
1/3,
2/3,
1/4,
1/5,
2/4, 3/4,
1/6, …
2/5, 3/5, 4/5,
2/6, 3/6, 4/6, 5/6,
Idea: insert the other numerators (but skip the ones that aren’t reduced).
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
DEFINITION: An infinite set is called countable if it has the same
size as N (the set of natural numbers).
Question: Is Q countable? (the set of rational numbers)
In other words, do the sets Q and N have the same size?
Can we list {1st rational, 2nd rational, 3rd rational, …} is a manner that’s
organized so as to eventually include each rational?
SECOND ATTEMPT:
1/1, 1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5, 3/5, 4/5, 1/6, 5/6, …
Does this eventually include all of the fractions?
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
DEFINITION: An infinite set is called countable if it has the same
size as N (the set of natural numbers).
Question: Is Q countable? (the set of rational numbers)
In other words, do the sets Q and N have the same size?
Can we list {1st rational, 2nd rational, 3rd rational, …} is a manner that’s
organized so as to eventually include each rational?
SECOND ATTEMPT:
1/1, 1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5, 3/5, 4/5, 1/6, 5/6, …
Does this eventually include all of the fractions? No, it only includes positive
fractions whose numerators are smaller than their denominators.
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
DEFINITION: An infinite set is called countable if it has the same
size as N (the set of natural numbers).
Question: Is Q countable? (the set of rational numbers)
In other words, do the sets Q and N have the same size?
Can we list {1st rational, 2nd rational, 3rd rational, …} is a manner that’s
organized so as to eventually include each rational?
SECOND ATTEMPT:
1/1, 1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5, 3/5, 4/5, 1/6, 5/6, …
2/1,
3/1,
3/2,
4/1,
4/3,
Idea: Insert the reciprocals.
5/1,
5/2,
5/3,
5/4,
6/1,
6/5,
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
DEFINITION: An infinite set is called countable if it has the same
size as N (the set of natural numbers).
Question: Is Q countable? (the set of rational numbers)
In other words, do the sets Q and N have the same size?
Can we list {1st rational, 2nd rational, 3rd rational, …} is a manner that’s
organized so as to eventually include each rational?
THIRD ATTEMPT:
1/1, 1/2, 2/1, 1/3, 3/1, 2/3, 3/2, 1/4, 4/1, 3/4, 4/3, 1/5, 5/1, 2/5, 5/2, 3/5, 5/3, …
Idea: Insert the reciprocals. Does this eventually include all of the fractions?
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
DEFINITION: An infinite set is called countable if it has the same
size as N (the set of natural numbers).
Question: Is Q countable? (the set of rational numbers)
In other words, do the sets Q and N have the same size?
Can we list {1st rational, 2nd rational, 3rd rational, …} is a manner that’s
organized so as to eventually include each rational?
THIRD ATTEMPT:
1/1, 1/2, 2/1, 1/3, 3/1, 2/3, 3/2, 1/4, 4/1, 3/4, 4/3, 1/5, 5/1, 2/5, 5/2, 3/5, 5/3, …
0,
-1/1,
-1/2,
-2/1,
-1/3,
-3/1,
and so on…
Idea: Insert the reciprocals. Does this eventually include all of the fractions?
No, but all that remains is to insert zero and intersperse the negatives!
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
DEFINITION: An infinite set is called countable if it has the same
size as N (the set of natural numbers).
Question: Is Q countable? (the set of rational numbers)
In other words, do the sets Q and N have the same size?
Can we list {1st rational, 2nd rational, 3rd rational, …} is a manner that’s
organized so as to eventually include each rational?
FOURTH ATTEMPT:
0, 1/1, -1/1, 1/2, -1/2, 2/1, -2/1, 1/3, -1/3, 3/1, -3/1, 2/3, -2/3, 3/2, -3/2, …
Does this eventually include all of the fractions?
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
DEFINITION: An infinite set is called countable if it has the same
size as N (the set of natural numbers).
Question: Is Q countable? (the set of rational numbers)
In other words, do the sets Q and N have the same size?
YES!
Can we list {1st rational, 2nd rational, 3rd rational, …} is a manner that’s
organized so as to eventually include each rational?
FOURTH ATTEMPT:
0, 1/1, -1/1, 1/2, -1/2, 2/1, -2/1, 1/3, -1/3, 3/1, -3/1, 2/3, -2/3, 3/2, -3/2, …
1st 2nd
3rd
4th
5th
6th
7th
8th
9th 10th …
Does this eventually include all of the fractions? YES!
THEOREM: The set of rational numbers, Q, is countable.
THEOREM: The set of rational numbers, Q, is countable.
ANOTHER PROOF:
THEOREM: The set of rational numbers, Q, is countable.
ANOTHER PROOF: First arrange all of the positive fractions into an infinite grid:
1
2
3
4
5
:
1
2
3
4
5
…
1/1
1/2
1/3
1/4
1/5
:
2/1
2/2
2/3
2/4
2/5
:
3/1
3/2
3/3
3/4
3/5
:
4/1
4/2
4/3
4/4
4/5
:
5/1
5/2
5/3
5/4
5/5
:
…
…
…
…
…
Like a computer spreadsheet,
this grid extends indefinitely right and down.
THEOREM: The set of rational numbers, Q, is countable.
ANOTHER PROOF: First arrange all of the positive fractions into an infinite grid:
1
2
3
4
5
:
1
2
3
4
5
…
1/1
1/2
1/3
1/4
1/5
:
2/1
2/2
2/3
2/4
2/5
:
3/1
3/2
3/3
3/4
3/5
:
4/1
4/2
4/3
4/4
4/5
:
5/1
5/2
5/3
5/4
5/5
:
…
…
…
…
…
Next, organize the cells of this grid into an infinite list by meandering through it:
The list goes: 1/1, 2/1, 2/2, 1/2, 1/3, 2/3, 3/3, 3/2, 3/1, 4/1, 4/2, 4/3, 4/4, 3/4,…
THEOREM: The set of rational numbers, Q, is countable.
ANOTHER PROOF: First arrange all of the positive fractions into an infinite grid:
1
2
3
4
5
:
1
2
3
4
5
…
1/1
1/2
1/3
1/4
1/5
:
2/1
2/2
2/3
2/4
2/5
:
3/1
3/2
3/3
3/4
3/5
:
4/1
4/2
4/3
4/4
4/5
:
5/1
5/2
5/3
5/4
5/5
:
…
…
…
…
…
Next, organize the cells of this grid into an infinite list by meandering through it:
The list goes: 1/1, 2/1, 2/2, 1/2, 1/3, 2/3, 3/3, 3/2, 3/1, 4/1, 4/2, 4/3, 4/4, 3/4,…
Finally, insert zero and intersperse the negative, as before. That’s it!
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
DEFINITION: An infinite set is called countable if it has the same
size as N (the set of natural numbers).
Summary: The following sets are countable:
E = the even natural numbers
Z = the integers
Q = the rational numbers
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
DEFINITION: An infinite set is called countable if it has the same
size as N (the set of natural numbers).
Summary: The following sets are countable:
E = the even natural numbers
Z = the integers
Q = the rational numbers
Question: Is R countable? (the set of real numbers)
In other words, do the sets R and N have the same size?
Can we list {1st real, 2nd real, 3rd real, …} is a manner that’s organized so as to
eventually include each real?
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
DEFINITION: An infinite set is called countable if it has the same
size as N (the set of natural numbers).
Summary: The following sets are countable:
E = the even natural numbers
Z = the integers
Q = the rational numbers
Question: Is R countable? (the set of real numbers)
In other words, do the sets R and N have the same size?
Can we list {1st real, 2nd real, 3rd real, …} is a manner that’s organized so as to
eventually include each real?
FIRST ATTEMPT: Insert √2 and π at the front of my listing of the rational numbers:
√2, π, 0, 1/1, -1/1, 1/2, -1/2, 2/1, -2/1, 1/3, -1/3, 3/1, -3/1, 2/3, -2/3, 3/2, -3/2, …
1st 2nd 3rd 4th 5th 6th 7th 8th 9th 10th …
Does this pattern eventually include every real number?
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
DEFINITION: An infinite set is called countable if it has the same
size as N (the set of natural numbers).
Summary: The following sets are countable:
E = the even natural numbers
Z = the integers
Q = the rational numbers
Question: Is R countable? (the set of real numbers)
In other words, do the sets R and N have the same size?
Can we list {1st real, 2nd real, 3rd real, …} is a manner that’s organized so as to
eventually include each real?
FIRST ATTEMPT: Insert √2 and π at the front of my listing of the rational numbers:
√2, π, 0, 1/1, -1/1, 1/2, -1/2, 2/1, -2/1, 1/3, -1/3, 3/1, -3/1, 2/3, -2/3, 3/2, -3/2, …
1st 2nd 3rd 4th 5th 6th 7th 8th 9th 10th …
Does this pattern eventually include every real number? NO!
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
DEFINITION: An infinite set is called countable if it has the same
size as N (the set of natural numbers).
Summary: The following sets are countable:
E = the even natural numbers
Z = the integers
Q = the rational numbers
Question: Is R countable? (the set of real numbers)
In other words, do the sets R and N have the same size?
Can we list {1st real, 2nd real, 3rd real, …} is a manner that’s organized so as to
eventually include each real?
FIRST ATTEMPT: Insert √2 and π at the front of my listing of the rational numbers:
√2, π, 0, 1/1, -1/1, 1/2, -1/2, 2/1, -2/1, 1/3, -1/3, 3/1, -3/1, 2/3, -2/3, 3/2, -3/2, …
1st 2nd 3rd 4th 5th 6th 7th 8th 9th 10th …
Does this pattern eventually include every real number? NO!
Since this attempt failed, does that mean that R is NOT countable?
MODERN DEFINITION OF “SAME SIZE”: A pair of sets is said to have the same size if their
members can be matched with a one-to-one correspondence.
DEFINITION: An infinite set is called countable if it has the same
size as N (the set of natural numbers).
Summary: The following sets are countable:
E = the even natural numbers
Z = the integers
Q = the rational numbers
Question: Is R countable? (the set of real numbers)
In other words, do the sets R and N have the same size?
Can we list {1st real, 2nd real, 3rd real, …} is a manner that’s organized so as to
eventually include each real?
FIRST ATTEMPT: Insert √2 and π at the front of my listing of the rational numbers:
√2, π, 0, 1/1, -1/1, 1/2, -1/2, 2/1, -2/1, 1/3, -1/3, 3/1, -3/1, 2/3, -2/3, 3/2, -3/2, …
1st 2nd 3rd 4th 5th 6th 7th 8th 9th 10th …
Does this pattern eventually include every real number? NO!
Since this attempt failed, does that mean that R is NOT countable?
NO, a more clever attempt might still succeed!
CANTOR’S THEOREM: The set of real numbers, R, is NOT countable.
(so we’ll call it “uncountable”)
Georg Cantor
CANTOR’S THEOREM: The set of real numbers, R, is NOT countable.
(so we’ll call it “uncountable”)
Cantor proved that no listing {1st real, 2nd real, 3rd real,…},
no matter how cleverly organized, could ever succeed in listing all of the real
numbers. Every attempted listing is doomed in advance to be incomplete!
Georg Cantor
CANTOR’S THEOREM: The set of real numbers, R, is NOT countable.
STRUCTURE OF PROOF: Cantor described a concrete procedure for identifying a
real number that is missing from any given listing of real numbers.
(kind of like how Euclid described a concrete procedure for identifying a prime
number that is missing from any given finite list of prime numbers)
Georg Cantor
CANTOR’S THEOREM: The set of real numbers, R, is NOT countable.
STRUCTURE OF PROOF: Cantor described a concrete procedure for identifying a
real number that is missing from any given listing of real numbers.
Imagine Aunt Clair’s listing begins like this:
…
…
…
We seek a concrete procedure for looking at this (or any such) infinite
listing of real numbers and identifying a real number that is missing
from it!
Georg Cantor
WARM UP WITH FINITE EXAMPLES
Here is a list of exactly five 5-digit numbers:
18901
69072
12501
78543
30727
Can you find a 5-digit number that’s NOT on this list?
Georg Cantor
WARM UP WITH FINITE EXAMPLES
Here is a list of exactly five 5-digit numbers:
18901
69072
12501
78543
30727
Can you find a 5-digit number that’s NOT on this list?
YES, EASILY
Georg Cantor
WARM UP WITH FINITE EXAMPLES
Here is a list of exactly five 5-digit numbers:
18901
69072
12501
78543
30727
What if only the red “diagonal” digits are visible…
Can you find a 5-digit number that’s NOT on this list?
Georg Cantor
WARM UP WITH FINITE EXAMPLES
Here is a list of exactly five 5-digit numbers:
1****
*9***
**5**
***4*
****7
What if only the red “diagonal” digits are visible…
…and the rest are smudged out?
Can you find a 5-digit number that’s NOT on this list?
Do you still have enough information to find a
number that’s not on the list?
Georg Cantor
WARM UP WITH FINITE EXAMPLES
Here is a list of exactly five 5-digit numbers:
1****
*9***
**5**
***4*
****7
What if only the red “diagonal” digits are visible…
…and the rest are smudged out?
Can you find a 5-digit number that’s NOT on this list?
Do you still have enough information to find a
number that’s not on the list?
YES! Just choose a number whose digits are:
(not 1)(not 9)(not 5)(not 4)(not 7)
Like: 27038
(there are lots of choices that work.)
Georg Cantor
WARM UP WITH FINITE EXAMPLES
Given any list of exactly six 6-digit numbers, with only diagonal digits visible, like this:
4*****
*2****
**0***
***9**
****9*
*****7
Can you always find a 6-digit number that’s NOT on this list?
Georg Cantor
WARM UP WITH FINITE EXAMPLES
Given any list of exactly six 6-digit numbers, with only diagonal digits visible, like this:
4*****
*2****
**0***
***9**
****9*
*****7
Can you always find a 6-digit number that’s NOT on this list?
YES! Here you would choose a number whose digits are:
(not 4)(not 2)(not 0)(not 9)(not 9)(not 7)
Like: 276384
(there are lots of choices that work.)
Georg Cantor
WARM UP WITH FINITE EXAMPLES
Given any list of exactly seven 7-digit numbers, with only diagonal digits visible, like this:
4******
*2*****
**0****
***9***
****9**
*****7*
******0
Can you always find a 7-digit number that’s NOT on this list?
Georg Cantor
WARM UP WITH FINITE EXAMPLES
Given any list of exactly seven 7-digit numbers, with only diagonal digits visible, like this:
4******
*2*****
**0****
***9***
****9**
*****7*
******0
Can you always find a 7-digit number that’s NOT on this list?
YES!
Georg Cantor
WARM UP WITH FINITE EXAMPLES
Given any list of infinitely many decimal expressions (each which has infinitely many
digits), with only diagonal digits visible, like this:
0.4*******…
0.*2******…
0.**0*****…
0.***9****…
0.****9***…
0.*****7**…
0.******5*…
…
Can you always find a decimal expression that’s NOT on this list?
Georg Cantor
WARM UP WITH FINITE EXAMPLES
Given any list of infinitely many decimal expressions (each which has infinitely many
digits), with only diagonal digits visible, like this:
0.4*******…
0.*2******…
0.**0*****…
0.***9****…
0.****9***…
0.*****7**…
0.******5*…
…
Can you always find a decimal expression that’s NOT on this list?
YES! Here you would choose a decimal expression whose digits are:
0.(not 4)(not 2)(not 0)(not 9)(not 9)(not 7)(not 5)…
Like: 0.2763846…
(there are lots of choices that work.)
Georg Cantor
WARM UP WITH FINITE EXAMPLES
Given any list of infinitely many decimal expressions (each which has infinitely many
digits), with only diagonal digits visible, like this:
0.4*******…
0.*2******…
0.**0*****…
0.***9****…
0.****9***…
0.*****7**…
0.******5*…
Careful! these two numbers might
be the same! Do you see how?
…
Can you always find a decimal expression that’s NOT on this list?
YES! Here you would choose a decimal expression whose digits are:
0.(not 4)(not 2)(not 0)(not 9)(not 9)(not 7)(not 5)…
Like: 0.2763846…
(there are lots of choices that work.)
Georg Cantor
WARM UP WITH FINITE EXAMPLES
Given any list of infinitely many decimal expressions (each which has infinitely many
digits), with only diagonal digits visible, like this:
0.4*******…
0.*2******…
0.**0*****…
0.***9****…
0.****9***…
0.*****7**…
0.******59999…
Careful! these two numbers might
be the same! Do you see how?
…
Can you always find a decimal expression that’s NOT on this list?
YES! Here you would choose a decimal expression whose digits are:
0.(not 4)(not 2)(not 0)(not 9)(not 9)(not 7)(not 5)…
Like: 0.276384600000…
(there are lots of choices that work.)
Georg Cantor
WARM UP WITH FINITE EXAMPLES
Given any list of infinitely many decimal expressions (each which has infinitely many
digits), with only diagonal digits visible, like this:
0.4*******…
0.*2******…
0.**0*****…
0.***9****…
0.****9***…
0.*****7**…
0.******59999…
Careful! these two numbers might
be the same! Do you see how?
…
Can you always find a decimal expression that’s NOT on this list?
YES! Here you would choose a decimal expression whose digits are:
0.(not 4)(not 2)(not 0)(not 9)(not 9)(not 7)(not 5)…
Like: 0.276384600000…
Easy to fix: just make your number
NOT end in 000… or 999…
Georg Cantor
WARM UP WITH FINITE EXAMPLES
Given any list of infinitely many decimal expressions (each which has infinitely many
digits), with only diagonal digits visible, like this:
0.4*******…
0.*2******…
0.**0*****…
0.***9****…
0.****9***…
0.*****7**…
0.******5*…
Let’s get back to
Cantor’s proof…
…
Can you always find a decimal expression that’s NOT on this list?
YES! Here you would choose a decimal expression whose digits are:
0.(not 4)(not 2)(not 0)(not 9)(not 9)(not 7)(not 5)…
Like: 0.2763846…
Georg Cantor
CANTOR’S THEOREM: The set of real numbers, R, is NOT countable.
STRUCTURE OF PROOF: Cantor described a concrete procedure for identifying a
real number that is missing from any given listing of real numbers.
Imagine Aunt Clair’s listing begins like this:
…
…
…
Georg Cantor
CANTOR’S THEOREM: The set of real numbers, R, is NOT countable.
STRUCTURE OF PROOF: Cantor described a concrete procedure for identifying a
real number that is missing from any given listing of real numbers.
Imagine Aunt Clair’s listing begins like this:
1st ↔
2nd ↔
3.1415926635…
0.3333333333…
( )
(1/3)
1.41421356237… ( )
↔ 256655643.00000000000… (Aunt Clair’s SSN)
↔
509.73737373737… (Her favorite number)
3rd ↔
4th
5th
5.04749726737… (
…
…
…
6th ↔
)
Georg Cantor
CANTOR’S THEOREM: The set of real numbers, R, is NOT countable.
STRUCTURE OF PROOF: Cantor described a concrete procedure for identifying a
real number that is missing from any given listing of real numbers.
Imagine Aunt Clair’s listing begins like this:
1st ↔
2nd ↔
3.1415926635…
0.3333333333…
( )
(1/3)
1.41421356237… ( )
↔ 256655643.00000000000… (Aunt Clair’s SSN)
↔
509.73737373737… (Her favorite number)
3rd ↔
4th
5th
5.04749726737… (
…
…
…
6th ↔
)
A real number that’s missing from Aunt Clair’s list is built like this:
M = 0.(not 1)(not 3)(not 4)(not 0)(not 7)(not 7) ….
Like: M=0.258163… (there are lots of choices that work.)
Georg Cantor
CANTOR’S THEOREM: The set of real numbers, R, is NOT countable.
STRUCTURE OF PROOF: Cantor described a concrete procedure for identifying a
real number that is missing from any given listing of real numbers.
Imagine Aunt Clair’s listing begins like this:
1st ↔
2nd ↔
3.1415926635…
0.3333333333…
( )
(1/3)
1.41421356237… ( )
↔ 256655643.00000000000… (Aunt Clair’s SSN)
↔
509.73737373737… (Her favorite number)
3rd ↔
4th
5th
5.04749726737… (
…
…
…
6th ↔
)
A real number that’s missing from Aunt Clair’s list is built like this:
M = 0.(not 1)(not 3)(not 4)(not 0)(not 7)(not 7) ….
Like: M=0.258163… (there are lots of choices that work.)
How do you know that M is different from Aunt Clair’s
first number? Her second? Her third?
Georg Cantor
CANTOR’S THEOREM: The set of real numbers, R, is NOT countable.
STRUCTURE OF PROOF: Cantor described a concrete procedure for identifying a
real number that is missing from any given listing of real numbers.
Imagine Aunt Clair’s listing begins like this:
1st ↔
2nd ↔
3.1415926635…
0.3333333333…
( )
(1/3)
1.41421356237… ( )
↔ 256655643.00000000000… (Aunt Clair’s SSN)
↔
509.73737373737… (Her favorite number)
3rd ↔
4th
5th
5.04749726737… (
…
…
…
6th ↔
)
A real number that’s missing from Aunt Clair’s list is built like this:
M = 0.(not 1)(not 3)(not 4)(not 0)(not 7)(not 7) ….
Like: M=0.258163… (there are lots of choices that work.)
To be safe, always choose digits other than 0 and 9, or at least
make sure M doesn’t end with 000… or 999…
so that M is not the same as any other decimal expression.
Georg Cantor
CANTOR’S THEOREM: The set of real numbers, R, is NOT countable.
PROOF: Given any infinite listing of real numbers: 1st, 2nd, 3rd, 4th, …
We can construct a number
M = 0.d1d2d3d4d5…
that’s missing from this list. How?
We simply choose the nth digit (dn) of M to be different from the nth digit (after the
decimal point) of the nth real number on the list
(also choose dn ≠ 0,9).
Thus, no listing of real numbers could every be complete!
Georg Cantor
CANTOR’S THEOREM: The set of real numbers, R, is NOT countable.
PROOF: Given any infinite listing of real numbers: 1st, 2nd, 3rd, 4th, …
We can construct a number
M = 0.d1d2d3d4d5…
that’s missing from this list. How?
I hope you
like my proof.
We simply choose the nth digit (dn) of M to be different from the nth digit (after the
decimal point) of the nth real number on the list
(also choose dn ≠ 0,9).
Thus, no listing of real numbers could every be complete!
Georg Cantor