Transcript Cantor - Muskingum University

Georg Cantor
Born: March 3, 1845
Died: January 6, 1918
Georg Cantor lived at the end of the 19th century and early 20th century. This is a time period in
both mathematics and the world that is referred to as "the age of abstraction". Ideas and
philosophies were changing from the concrete to the abstract. This could be seen in many fields
along with mathematics. In economics abstract notions of different types of economies such as
communism were described Marx And Engle and capitalism was described by Adam Smith. The
world of art was changing to a more abstract form. Artists moved from being a "camera" that
could reproduce what the human eye could see to having an abstract eye. For example the
works of Cezanne, Van Gogh and Gauguin differed greatly from the works of Monet.
Mathematicians began to cross the gap of what visual or physical reality would dictate, such as
the innovation of Bolyai and Lobachevski concerning non- Euclidean geometries.[1 p 246]
Georg Cantor was born in Denmark and grew up with a deep appreciation for culture and the
arts which was instilled in him by his mother who had considerable musical talent as a violinist.
In terms of religion Georg's mother and father were a mixed marriage, his father was a
Protestant who had converted from Judaism and his mother Roman Catholic. Georg was raised
as a Protestant. Georg Cantor's father was a successful merchant and stock broker in St.
Petersburg whose wealth enabled him to afford a private tutor for Georg's early education.
The family moved to Germany because his father's health required a warmer climate. When the
family first moved to Germany young Cantor lived at home and studied at the Gymnasium in
Wiesbaden. Later the family moved to Frankfurt where he went away to boarding school at the
Realschule in Darmstadt. In 1860 he graduated with an excellent academic record with
exceptional skills in mathematics, and in particular trigonometry. He attended the Hoheren
Gewerbeschule in Darmstadt for two years to study engineering and then entered the
Polytechnic of Zurich in 1862. In that year, Cantor sought his father's permission to study
mathematics and was overjoyed when his father gave his consent. His studies were cut short by
the death of his father in the next year. [2]
Cantor moved to the University of Berlin where he had instructors such as Weierstrass, Kummer
and Kronecker. Cantor would occasionally travel to Göttingen to study. He would complete his
dissertation at the University of Berlin in the area of number theory in 1867. In Berlin he was
involved with the Mathematical Society and would become its president in 1864-1865.[2]
Cantor accepted a position teaching at girl's school in Berlin. He joined the Schellbach Seminar
for mathematics teachers while completing his habilitation degree in 1869.
Cantor received an appointment at Halle and the focus of his research changed from number
theory to analysis. This is because one of his colleagues challenged him to prove an open
problem concerning the representation of functions as trigonometric functions, in particular sines
and cosines. This was a famous problem that had been attempted by Dirchlet, Lipschitz and
Riemann. Cantor solved the problem in April 1870 and his solution clearly reflected the teaching
of Weierstrass.[2]
In 1872 Cantor was promoted to Extraordinary Professor at Halle. He published a paper that
year in which he characterized irrational numbers as convergent series of rational numbers.
Cantor had started a friendship with Dedekind (they met on holiday in Switzerland) who referred
to Cantor's result in famous characterization of the real numbers consisting as "Dedekind
Cuts".[2]
Cantor's work with series of trigonometric functions and the convergence of series led him to
consider intrinsic differences among various sets of numbers. In particular this meant devising a
means for comparing the size of sets that did not rely on the concept of counting. Cantor used
the idea of "equinumerosity" to characterize if two set contain the same number of elements.
This is a notion where sets are compared by an element by element pairing to see if all
elements in one set could be paired with all elements in a second set. If such a
pairing exists we call the sets equinumerous or in modern terms we say the sets are
in one-to-one correspondence.[1 p. 253]
In Cantor's own words:
Two sets M and N are equivalent...if it is possible to put them , by some law, in such a
relation to one another that to every element of each one of them corresponds one and
only one element of the other.[1 p. 253]
Cantor was moving to a completely new concept of characterizing the infinite. The
mathematicians who preceded Cantor objected to the idea that a process that considered an
infinite set as being able to be "completed" or a process that referenced them as finished was
not sound reasoning. Gauss once commented:
...I protest above all against the use of an infinite quantity as a completed one, which in
mathematics is never allowed. The infinite is only a manner of speaking...[1 p 254]
At this time (1874) Cantor was engaged to Vally Guttmann a friend of his sisters, who introduced
her to Cantor because she feared he was spending to much time on his professional activities.
They married on August 9, 1874 they spent their honeymoon in Interlaken in Switzerland where
Cantor knew Dedekind was on vacation. Cantor spent much of his honeymoon in mathematical
discussions with Dedekind.[2]
Cantor's research led him to a discovery that many different types of infinity exist. In fact there
are an infinite number of different types of infinity. Along the way to this discovery he
was able to find sets of points that were eqinumerous that he did not expect. He was
able to prove that the set of points in the unit interval was equinumerous with the
points in the unit solid in n-dimensional space. This surprised and amazed Cantor so
much he is attributed with a famous quote:
I see it, but I don't believe it! [2]
In 1881 Heine died leaving open a very important position at Halle. Cantor was asked
to recommend a replacement for Heine. Cantor asked his good friend Dedekind to fill
the place and he was turned down. Weber and Mertens, his second and third choices
also turned him down. Cantor realized that his work was not widely accepted and
people (even his best friend) did not want there work associated with him.
Cantor states clearly the opposition to his ideas:
...I realize that in this undertaking I place myself in a certain opposition to views widely
held concerning the mathematical infinite and to opinions frequently defended on the
nature of numbers. [2]
Cantor became very depressed. In 1884 he had his first recorded attack of depression that he
recovered from after a few weeks. His experience made him lose confidence and fear the
treatment he was subject to. The treatment for mental health disorders at this time was
confinement in a sanatoria which was very unpleasant.
Cantor began to work on the Continuum Hypothesis, but was not able to make much progress.
The Continuum Hypothesis was a theory that stated that the cardinality of the real numbers was
next in order after the natural numbers.
The inability to resolve this worsened his mental state. It was improved and his depression kept
in check with his family and personal life. In 1886 he bought a new house and his wife gave birth
to the last of his six children. Cantor published a strange paper in 1894 that showed Golbach's
conjecture was true for all even numbers up to 1000. This had already been done for all
numbers up to 10000 forty years before. This gives more evidence of his state of mind and
wanting to be accepted again by the mathematical community.
Cantor suffered from periods of depression from 1899 on, following the death of his youngest
son. He was in and out of the sanatoria several times between 1902 and 1908. He had to take
leave from his teaching responsibilities during many winter semesters. When Cantor suffered
from periods of depression he turned away from mathematics and toward his family, philosophy
and Shakespeare. He proported a theory that Francis Bacon had wrote Shakespeare's plays.
In 1911 Cantor was invited to the University of St. Andrews as a distinguished foreign scholar.
Cantor had hoped to meet with Bertrand Russell who had just published Principia Mathematica
to discuss his theory on sets, but news his son was ill made him return to Germany. He retired in
1913 and spent his final years ill and starving because of the small amount of food available to
German citizens due to the war. A major celebration of his 70th birthday was planned at Halle
but was canceled due to the war. In 1917 he entered the sanitarium for the last time were he
would continually write his wife asking to go home. He died mentally ill, scared, starving and
penniless of a heart attack.[2]
Hilbert said the following of Cantor's work:
...the finest product of mathematical genius and one of the supreme achievements of
purely intellectual human activity.[2]
[1] Dunham, William. Journey Through Genius The Great Theorems of Mathematics.
New York: John Wiley & Sons 1990.
[2] Web site: MacTutor History. http://turnbull.mcs.st-and.ac.uk/~history (9/2000).
Cantor's work begins with his notion of "equinumerosity". In modern times we would
say that two sets are "equinumerous" if there exists a one-to-one correspondence
between the two sets. A one-to-one correspondence is a function from one set to
another that is both one-to-one and onto. A cardinal number is what is used to
denote the class of all sets that can be put into one-to-one correspondence with
each other.
That is to say a if there is a function f:A→B that is both one-to-one and onto, then we
say the set A is in one-to-one correspondence with the set B.
Sets and One-to-One Correspondences
An important tool the mathematicians use to compare the size of sets is called a
one-to-one correspondence. This concept is a way of saying two sets are the same
size without counting the numbers in them. We call two sets equivalent if they have
the same number of elements. Equivalent sets can be put into one-to-one
correspondence with each other by showing how all the elements of one set exactly
match with all the elements of another set. You can represent different one-to-one
correspondences by drawing arrows between the sets.
January
Larry
January
Larry
June
Curly
June
Curly
July
Moe
July
Moe
Each of the illustrations above shows a one-to-one correspondence between the
sets {January, June , July} and {Larry, Curly, Moe}. These two sets would be
considered equivalent but not equal.
Can the set {January, June, July} be put into one-to-one correspondence with the
set {Red, Green, Blue, Orange}? NO !
Sets that are equal have exactly the same elements in them. Sets that are
equivalent need only have the same number of elements in them.
The sets {January, June, July} and {Red, Green, Blue} are equivalent but not
equal. The sets {January, June, July} and {July, June, January} are both equal and
equivalent.
Often times it is useful to draw or picture the one-to-one correspondence in row
format. For example a one-to-one correspondence between the sets {January,
June, July} and {Red, Green, Blue} can be illustrated as in the figures below:
As a Diagram
In Function form
{January,
June,
July}
↕
↕
↕
{Red,
Green,
Blue}
f(January) = Red
f(June) = Green
f(July) = Blue
Reference Sets
A reference set for a number is any set that has that number of elements in it. For
example all of the sets listed below are reference sets for the number 3.
{red, green, blue}
{,,}
{Larry, Curly, Moe}
Cardinal Numbers
A cardinal number is the collection of all sets
that are equivalent to a particular reference set.
Below is a table of cardinal numbers and a
reference set for each one.
The symbol 0 (pronounced aleph null it is the
first letter of the Hebrew alphabet) is used to
represent the number of elements in a set
equivalent to N the natural numbers. A set with
cardinality 0 is called denumerable or
countably infinite.
If a number has a finite reference set that
number is called a finite cardinal. If a reference
set for a cardinal number is infinite that number is
called a transfinite cardinal.
Cardinal
Number
Reference Set
0

1
{a}
2
{one, won}
3
{,,}
4
{,,,}

0

N = {1,2,3,…}
A set is denumerable if there is a one-to-one correspondence with the natural numbers N.
This implies a set S is denumerable if there is a function f:N→S that is one-to-one and onto.
We call any function f:N→T a sequence. and use the following notation.
x1=f(1)
x2=f(2)
x3=f(3)
x4=f(4)

x5=f(5)

xn=f(n)
or in in the case of a denumerable set:
S={x1,x2,x3,x4,...}
The phrase Cantor used was to say that denumerable set could be "exhausted" by a
sequence. The table below shows how a sequence could exhaust various sets.
Numbers
Sequence
Set
Even Numbers
xn = 2n
{2,4,6,8,10,…}
Powers of 2
xn = 2n
{2,4,8,16,32,…}
Perfect squares
xn = n2
1   1 
{1,4,9,16,25,…}
n
 2 n 1 
Integers
xn 
Primes
No known formula
4
{0,1,-1,2,-2,3,-3,…}
{2,3,5,7,11,13,17,…}
Sets in One-to-One Correspondence with N
We will see there are many different sets that are in one-to-one correspondnece
with the set of natural numbers N. One of the most famous examples is the set of
integers Z. This seems very counter intuitive since there seems like there should
be "twice" as many integers as natural numbers, but this is not the case.
There are just as many integers as natural numbers!
We show the one-to-one correspondence below by "interweaving" the positive and
negative numbers.
34 ,35
N=
Z=
…,
46
…,
{1,
2,
3,
4,
5,
6,
7,
↕
↕
↕
↕
↕
↕
↕
↕
↕
{0
1,
-1,
2,
-2,
3,
-3,
…, -17, …,
23,
x,
17
y,
86
…,
87,
…}
↕
…,
z,
…}
43,-43
For a negative number in Z look just ahead of it, find the positive and multiply by 2.
For a positive number in Z multiply by 2.
For an even number in N divide by 2.
For an odd number in N divide look at the even ahead divide by 2 and the next
one will be negative.
Putting a plus (+) or a minus sign above a set means that you are looking at just
the positive (+) or negative (-) numbers in that set. The number 0 is not considered
to be either positive or negative.
ℤ+ = Positive Integers = {1,2,3,4, ….} (i.e. this is another name for ℕ)
ℤ− = Negative integers = {-1,-2,-3,-4,…}
ℚ+ = Positive Rational Numbers = Positive Fractions
ℚ− = Negative Rational Numbers = Negative Fractions
One of the surprising results we will talk about is that there are just as many
positive Integers as there are positive Rational numbers (i.e. the sets ℕ and ℚ+
are equivalent).
What is difficult here is to show how the sets correspond. For some sets the
function that describes the sequence xn can be very complicated to write down or
does not exist in terms of products, quotients, powers or other combinations of
known functions. It can be described (such as the case with prime numbers) by
shown the order that the numbers would appear in the sequence.
This will enable us to show that the sets ℕ and ℚ are also equivalent by
"interweaving" the positives and negative like we did for ℕ and ℤ.
1
1
1
2
1
3
1
4
1
5
1
6
1
7
2
1
2
2
2
3
2
4
2
5
3
1
3
2
3
3
3
4
3
5
2
6
3
6
2
7
3
7
4
1
4
2
4
3
4
4
4
5
4
6
4
7
5
1
5
2
5
3
5
4
5
5
5
6
5
7
6
1
6
2
6
3
6
4
6
5
6
6
6
7
7
1
7
2
7
3
7
4
7
5
7
6
7
7
ℕ={
1,
↕
ℚ+ = { 1,
ℕ={
ℚ={
1,
↕
0,
2,
↕
1
2,
2,
↕
1,
3,
↕
2,
4,
↕
3,
3,
↕
−1,
4,
↕
1
2,
5,
↕
1
3,
5,
↕
6,
↕
1
4,
6,
↕
−1
2 , 2,
⋯}
⋯}
⋯}
⋯}
We line up the fractions
with the same numerators
going across and the same
denominators going down.
We then serpentine back
and forth skipping over any
unreduced fraction.
Rational Numbers and Decimals
The decimal expansion of any rational number (integer divided by a natural number
will have a decimal that will look one of two ways.
1. The decimal will terminate:
¼ = .25
½ = .5
⅜ = .375
¾ = .75
2. The decimal will repeat:
1
3
 . 333333   .3
4
2
 . 1212121212   .12
33
The reason that fractions must terminate
or repeat is because there are only a
finite number of remainders you can get
when you do long division. If any
remainder is zero the decimal
terminates, if any remainder repeats
itself so will the digits generated by long
division. The decimal for a fraction must
terminate or repeat in no more digits
than what the denominator is.
 . 2857142857 14   .285714
7
.12…
.75
4 3.00
33 4.00
28
33
20
20
70
66
0
4
¾ terminates
after 2 digits < 4
4
33
repeates after
2 digits < 33
We have seen any fraction can be turned into either a terminating or repeating
decimal by long division. It is also the case that a terminating or repeating
decimal can be turned back into a fraction.
Decimals that Terminate
If the decimal terminates look at the place value of the last digit in the
number. That place value becomes your denominator and the digits you see
are your numerator.
.357
. 357 
357
2.9063
1000
1000's place
2 . 9063 
29063
10000
10,000's place
Decimals that Repeat
In order to change a decimal that repeats back into a fraction there are a few
terms associated with a repeating decimal that we refer to.
The repeat block are the digits that are repeated. The repeat block is marked
with a line over the repeated digits. The size of the repeat block are the
number of digits making up the repeat block.
The delay are the digits in the decimal after the decimal point that do not
repeat.
1st Repeat Block
4 .217  4 . 217217217 
The digits 217 make up the repeat
block for this number.
The size of the repeat block is 3.
2nd Repeat Block
There is no delay for this number.
1st Repeat Block
The digits 82 make up the repeat
block for this number.
0 . 346 82  0 . 346828282 
2nd Repeat Block
The size of the repeat block is 2.
The digits 346 are the delay for this
number.
The procedure for changing a repeating decimal back into a fraction makes use of
algebra and the fact that multiplication by powers of 10 "shift" the decimal point.
The idea is to make the repeating parts "line-up" so they cancel out when you
subtract.
1. Set decimal equal to x.
2. Multiply x by the power of 10 to move decimal point to the end of the first repeat block.
3. Multiply x by the power of 10 to move decimal point to the beginning of the first repeat block.
4. Subtract (the repeating parts should cancel) and solve for x.
Change .37 to a fraction.
x = .3737…
Set x =.37 writing out two repeat blocks.
Multiply by 100. (You want to move it 2 decimal places.)
100x = 37.37…
Subtract x. (The decimal point for x is already at the beginning
of the first repeat block in this case.)
Solve for x.
-.3737…
-x =
99x = 37
x
37
99
This means that the fraction for the decimal number .37 is :
37
99
This was a bit of a special case since there was no delay for the number you can
always subtract the original x. When the decimal delays (i.e. has digits before
the repeat block) you will need to multiply by another power of 10 to get the
decimal point to the beginning of the first repeat block.
Change .26194 to a fraction.
Set x =.26194 writing out two repeat blocks.
Multiply by 100000. (Move it 5 decimal places.)
Multiply by 100. (Move to beginning of repeat block.)
Subtract 100000x-100x.
Solve for x.
x = .26194194…
100000x = 26194.194…
26.194…
100x =
99900x = 26168
x
26168
99900
Change .7495 to a fraction.
Set x =.7495 writing out two repeat blocks.
Multiply by 10000. (Move it 4 decimal places.)
x = .74955…
10000x = 7495.5…
749.5…
Multiply by 1000. (Move to beginning of repeat block.)
1000x =
Subtract 10000x-1000x.
9000x = 6746
Solve for x.
x
6746
9000
Irrational Numbers
There are numbers whose decimal does not repeat in a block or terminate. We call
these numbers irrational. Any irrational number can not be converted into a
fraction. Here are some examples of irrational numbers.
 - Pronounced Pie and written Pi is one of the most famous examples.
.47447444744447… - The repeating block keeps growing.
5 - Taking square roots of numbers that are not perfect squares.
A number is called algebraic if it is the root of a non-zero polynomial with integer coefficients.
Any rational number is algebraic since if r is ration then r=m/n and is the root of the linear nonzero polynomial nx-m=0. Almost all numbers you know are algebraic. For example the square
root of a prime p is algebraic because it is the root of the non-zero polynomial x2-p=0. It can be
proven that a root, sum, product, or quotient of algebraic numbers is another algebraic
number. A number that is not algebraic is called transcendental. Very few transcendental
numbers are known for example  and e are transcendental.
The set of algebraic numbers is denumerable
Proof
A polynomial of degree n has at most n roots. For each natural number n we will count the
number of roots a polynomial of degree n could have whose coefficients do not exceed n in
absolute value.
Let A1={a : a is a root of a polynomial of degree 1 whose coefficients have absolute value less than 1}
Each polynomial is of the form c1x+c0=0 where c1,c0 are in {-1,0,1}. There are 3 choices for c1
and 3 choices for c2 giving 9 total polynomials. Since each polynomial has at most 1 root, thus
there are at most 19=9 possible roots (there are actually less since some of the polynomials
have no roots like 1=0 and some have the same root such as x-1=0 and -x+1=0). The number
of elements in A1 is finite.
Let A1={a11,a12,...,a1m1}.
Let A2={a : a is a root of a polynomial of degree 2 whose coefficients have absolut value less
than 2 and a is not in A1}
Each polynomial is of the form c2x2+c1x+c0=0 where c2,c1,c0 are in {-2,-1,0,1,2}. There are 5
choices for c1,c2 and c3 giving 125 total polynomials. Since each polynomial has at most 2
roots, thus there are at most 2125=250 possible roots (there are actually less). The number in
A2 is finite.
Let A2={a21,a22,...,a2m2}.
In general,
Let An={a : a is a root of a polynomial of degree n whose coefficients have absolute value less
than n and a is not in A1 or A2 or...or An-1}
Each polynomial is of the form cnxn+cn-1xn-1+...+c0=0 where cn,cn-1,...,c0 are in {-n,-(n-1),...,1,0,1,...,n-1,n}. There are 2n+1 choices for cn,cn-1,...,c0 giving (2n+1)(n+1) polynomials. Each
polynomial has at most n roots, thus there are at most n(2n+1)(n+1) possible roots (there are
actually less). The number in An is finite.
Let An={an1,an2,...,anmn}
All of the elements in all of the sets An can be exhausted by the following sequence.
a
11

, a12 ,  , a1 m1 , a 21 , a 22 ,  , a 2 m 2 ,  , a n 1 , a n 2 ,  , a nm n  x1 , x 2 , x 3 , x 4 ,  
If a number x is algebraic then x is a root of cnxn+cn-1xn-1+...+c0=0. Let M=Max{n,|cn|,|cn-1|,...,|c0|}
then x is in AM or AM-1 or...or A1. This x = aij = xk for some k. The sequence (xk) exhausts the
algebraic numbers.
QED
A Different Infinity
The closed interval [0,1] (i.e. every number that can be written as a decimal
between 0 and 1) is called the unit interval.
The unit interval [0,1] is not equivalent to N.
In other words the infinity represented by the natural numbers is a different type of
infinity that is represented by the unit interval [0,1]. The reasoning for this is very
ingenious.
Suppose the unit interval [0,1] has a one-to-one correspondence with N. We don't
know what numbers in [0,1] correspond to N so we call them x1, x2, x3,….
N=
{1,
2,
3,
4,
5,
↕
↕
↕
↕
↕
x2,
x3,
x4,
x5,
[0,1] = {x1,
…}
…}
If we knew
the numbers
arrange them
this way.
We can always create a number that is not in this list
by changing the digit in red to a 4 if it is not a 4 and to
a 5 if it is a 4. In this case the new number would be:
0.4544…
N
[0,1]
1
↔ 0.132786…
2
↔ 0.345802…
3
↔ 0.035211…
4
↔ 0.250000…


Closed Intervals
If we start with any closed interval [a,b] we can show it has just as many points
(i.e. can be put into one-to-one correspondence) with the unit interval [0,1]. This
can be visualized as making the endpoints match up from a common point. For
example if we want to show the closed interval [3,7] is equivalent to the closed unit
interval [0,1] we show how the points correspond.
To locate the points that correspond to x and
y on the other interval we first locate point P
P
0
3
y 1
7
x
P
0
3
We then draw a straight line connecting P
and x or y. Where that line hits the other
segment is the corresponding point.
This could also be calculated directly if you
knew one of the numbers by using a
proportion.
y 1
y
6
3
4
7

3
1
4
y
3
4
Equivalent Shapes
Just like two segments of different size represent the same infinity so can different
shapes. For example the are just as many points on the small circle below as
there are on the large triangle.
To find the points that correspond to the
orange, green and blue points draw a line
from the black point. Where it hits the other
shape is the corresponding point.
2
It is also a well know fact that the unit
segment [0,1] is equivalent to the unit
square [0,1]  [0,1]. This is an amazing
fact because these two shapes are of
different dimension. A line segment is 1
dimensional where the unit square is two
dimensional.
1.5
1
0.5
-0.5
0
0.5
1
1.5
2
-0.5
0.5
1
-0.5
These two sets are equivalent!
1.5
2
Equivalence of [0,1] and [0,1]  [0,1]
The points on the unit interval corresponds to the point on the unit square by
"interweaving" their corresponding decimals. That is if the ordered pair (x,y) is on
the unit square with x and y have the following decimal expansions:
x = 0.x1x2x3x4x5… and
y = 0.y1y2y3y4y5…
The corresponding point on the unit segment is given by:
0.x1y1x2y2x3y3x4y4x5y5… ↔ (0.x1x2x3x4x5… , 0.y1y2y3y4y5…)
With this scheme decimals that terminate have the decimal digits after the last
one all zero.
[0,1]  [0,1]
[0,1]
0.24168
0 .52
0 . 4 7631
0 . 8 203
0 . 2 50
↔
↔
↔
↔
↔
(0.218, 0.46)
0 .5 ,0 .2 
0 .4 61 , 0 .73 
0 .8 023 , 0 .230 
0 .2 , 0 .5 
Power Sets
The power set of a set A (sometimes denoted P(A) or S) is the set of all subsets of
the set A. The table below shows some sets with different cardinality along with
their power sets and the number in their power set.
Cardinal
Number
Cardinality
of Power
Set
Reference
Set
Subsets (Power Set)
0


1
1
{Δ}
,{Δ}
2
2
{Δ,}
,{Δ},{},{Δ,}
4
3
{,,}
,{},{},{},{,},{,},{,},{,,}
8
4
{,,,}
,{},{},{},{},{,},{,},{,},{,},
{,},{,},{,,},{,,},{,,},
{,,},{,,,}
16
What you want to notice is that the cardinality of a set is always smaller than the
cardinality of its power set. Taking the power set gets you a bigger cardinal
number than what you started with.
Cantor's Theorem
The set operation of cross product () does not change the cardinality of a set for
sets that are infinite. Here are some examples:
[0,1]  [0,1] has the same cardinality as [0,1]
ℕ × ℕ has the same cardinality as ℕ
ℝ × ℝ has the same cardinality as ℝ
Cantor's Theorem states that the cardinality of the set of subsets of a
set A (Power Set of A) is always greater than A (regardless if A is
infinite or not). (𝑃 𝐴 = the power set of A)
Since the set of subsets of a set is another set we can create all of its subsets, thus
creating a lager number than what we started with. This leads to the following
conclusion:
There are an infinite number of different sizes of infinity!
The way Cantor argued that the cardinality of the
power set is always larger is very ingenious. He
started with the natural numbers and showed why
they could not have the same cardinality as their
power set.
Number Subset
He assumed if there were a one-to-one
correspondence line them up next to each other.
If a number is not in the set it is paired with color
it red. Some of the numbers will be red and some
black.
Take all the numbers that are red and call that set
R. The set R is paired with a number x.
1
{2, 3, 5}
2
E = Even Nos
3
D = Odd Nos
4
{8,9,10,…}
5
{5,10,15,…}


x
R
The question Cantor asked himself is if x is red or black?
If x is red that means that x is not in R, but the elements of R are red numbers
which means that x is in R. This is illogical so x must not be red.
If x is black that means x is in R, but the elements of R are all the red numbers
which means x is not in R. This is illogical so x must not be black.
Since x must be one of the two colors it must be impossible to do this.
Cardinal numbers can be ordered according to the following definition:
A cardinal number c1 is less than a cardinal number c2 if A is a reference set for c1
and B is a reference set for c2, then A can be put in one-to-one correspondence
with a proper subset of B and the set A can not be put into one-to-one
correspondence with the set B. To denote this we write c1<c2.
Here is a more formal argument for why the cardinality of the P(A) is always
greater than the cardinality of the set A.
Proof:
Let A be a non-empty set. (The case of the empty set is trivial.)
Define f:A→P(A) by f(x)={x}.
This function is a one-to-one correspondence with a proper subset of P(A) since
the empty set will not be paired with anything.
To show the cardinality is less we must show that A can not be put into one-to-one
correspondence with P(A). Use contradiction and assume A can be put into one-toone correspondence with P(A).
This implies there exists a function f:A→P(A) that is a one-to-one correspondence.
For each x in A there is a corresponding f(x) which is a subset of A. The element x is
either in f(x) or it is not. Define the following set S.
S = { x in A : x is not in the corresponding set f(x)}
The set S is a subset of A. That implies there is an element y in A that that
corresponds to it (i.e. f(y) = S). The element y is either in S or it is not in S. Consider
each of the following cases.
Case 1: y is in S
By the definition of S these are all elements x such that x is not in f(x). Since y is in S
and f(y)=S then y is in f(y), therefore y is not in S. This implies Case 1 is impossible.
Case 2: y is not in S
Because f(y) = S then y is not in f(y). This means y is one of the members x such that
x is not in f(x). By the definition of the set S this means y is in S. This implies Case 2
is impossible.
Because both cases are impossible this is a contradiction. It must be true no such
function (one-to-one correspondence) exists.
QED
This gives us a way to create an infinite sequence of set with different cardinality.
Let 0 = cardinality of ℕ.
Let 1 = cardinality of 𝑃 ℕ
Let 2 = cardinality of 𝑃 𝑃 ℕ .
Let 3 = cardinality of 𝑃 𝑃 𝑃 ℕ
.
.
.
.
Then 0<1<2<3<4<....
All the above sets are transfinite cardinal numbers and they are all different.