Transcript Infinity and Beyond

What are the sizes of the following
sets?
1. The “Z mod n” group, Z . This is the set of
n
numbers formed by the possible remainders
of the integers divided by a positive integer n.
2. The set of all Natural numbers, N, {1,2,3,4,…}.

Q
3. The set of all positive rational numbers, ,
the ratio of two integers in simplified form.
4. The set of real numbers, R, on [0,1].
Example 1
n
The “Z mod n” group, Z ,is formed by the remainders of
n
the integers divided by a positive integer n. Intuitively, how
many elements would be in the set?
What are the possible remainders upon division by n?
{0,1,2,3,…,n-1}
Counting the number of elements in the set, the size of
this is set is n.
Example 2
What is the size of the set, N, {1,2,3,4,…}?
This may be a bit harder to visualize, our first
question may be, is infinity allowed to represent
the size of a set?
If so, how do we represent this?
Example 3
What is the size of the set of Q , the positive ratio of
two integers in simplified form?
Again, the answer seems to be infinity, however; this set
seems a bit “larger” than the one in example 2.
Why? Because you can think of many positive rational
numbers between the first two natural numbers…
For example the sequence: 1 1 ,1 1 ,1 1 ,...,1 1 



2 3 4

n 
This means there are an infinite number of
numbers between the first two numbers of another
infinite set, the natural numbers.
Example 4
What is the size of the set of the real numbers, R,
on the interval [0,1]?
The answer is infinity, again, however; the
underlying question is, how can we compare
these infinite sets?
Introducing Georg Cantor
A German mathematician born in St. Petersburg,
Russia in 1845.
Cantor introduced different “sizes” of
infinity
 Cantor devised a system from the Hebrew letter
aleph, called aleph numbers.
 These numbers were also called Cardinal
numbers or Cardinals, for short.
 The “smallest” infinite set was described as
Cardinal aleph-naught or aleph-null.
 It was denoted as 0 .
 The set of the natural numbers, N , as mentioned
in Example 2, have Cardinal
.

0
Discerning between sizes of infinity
 Cantor used the idea of a bijection between a set
and the natural numbers, N, to describe all sets
Cardinality  .
0
 A bijection is a one to one, onto mapping between
two sets.
 Sets of this type were sometimes called countably
infinite or countable.
 .
Q
 The positive rational numbers, , in example 3,
are another example Cardinality 0.
0
There is a bijection between N and Q+
The idea of the 1-1, onto correspondence follows in the
diagram below.
Cont.
If any redundant fractions are eliminated and we
follow the arrow, the set Q+ is in one to one and
onto correspondence with N. Therefore Q+ is
countably infinite.
Q+ and N are two good examples of sets of
Cardinality  .
0
It is worth noting that Q+ is dense in the real
numbers.
The Aleph Null Song
To the tune 99 bottles of beer on the wall.
♪ Aleph-null bottles of beer on the wall,
Aleph-null bottles of beer.
Take one down, pass it around,
Aleph-null bottles of beer on the wall. ♫
(And repeat…)
“Larger sizes of infinity.”
 Cantor realized that there were sets larger than aleph-




naught. The next Cardinal number he defined was alephone.
These sets were called the Cardinality of the continuum
represented by the real numbers.
It was denoted as 1 or c, for the continuum.
The set of real numbers, R , or the subset on the interval
[0,1] as mentioned in Example 4, have Cardinality 1.
Sets of this size are referred to as uncountable.
A mapping from [0,1] to R.
Consider a circle
of perimeter 1 consisting
of the interval [0,1].
Cantor’s diagonalization argument
Prove that the set R on [0,1] is uncountable.
Write all such numbers in the set in decimal form 0.d1d2d3…
Let dij be the jth decimal in the ith number. Represent the set as:
0.d11d12d13…
0.d21d22d23…
0.d31d32d33…
. . . .
. . .
.
. . .
.
Assume that the set is totally enumerated above. Consider the number
x =0.c1c2c3… constructed by replacing each red digit dnn by a
different digit cn which is not a 9. Thus, this number is in the set, but
not in the list. So no bijection exists between R and N.
Cont.
 Cantor’s original diagonal argument was done with a
binary representation of the real numbers in
decimal form. Thus, the new decimal representation
was chosen to be the complement of each diagonal
element, forming a new number not in the set.
The Cantor Set
 To create the Cantor set, take the interval [0,1] on
the real number line, call this the initial stage or C0.
 In the first stage, C1, we remove the middle third of
the segment.
 For each additional stage continue to remove the
middle third of each segment, call the nth stage Cn.
 The Cantor set is C where, C  lim C n
n 
Graphical Representation of C
The first few “stages” below, C0, C1, C2:
What is the “length” of C?
To figure this out, consider these questions:
 How many segments are taken away in each stage?
 What is the length of each segment taken away in each
stage?
 How can we represent the sum of all the segments
taken away in each stage?
 What is the limit of this sum as n->∞.
Cont.
 The number of segments taken away at each stage
n 1
can be represented by 2 .
 The length of each segment taken away at each stage
n
can be represented by
. 13

 The total length taken away at each stage can be
represented by the series
  2
n
k 1
1 k
3
k 1

 
n
1
3
k 1
2 k 1
3
 The total length taken away from C is given by:
l im13  
n
n 
k 1

2 k 1
3

1
3
1
2
3
1
Preliminary Conclusions
 Since the Cantor set is constructed by a set of length
one and the sum of the segments taken away is one,
the Cantor set has a length of zero.
 Length of sets are referred to as measure.
 Thus, the Cantor set has measure 0.
What is the Cardinality of the Cantor
set?
To discover this, ask some other questions.
 What are some elements remaining in the Cantor
set?
 Is there a convenient representation for the entire
Cantor set?
 Is there a bijection between the Cantor set and the
natural numbers, N?
What are some elements remaining in
the Cantor set?
 All the endpoints of the remaining intervals.
 For example: 0, 1/3, 2/3, 1, 1/9, 2/9, 7/9, 8/9, and so
on…
Is there a convenient representation for
the entire Cantor set?
Notice that all elements in the Cantor set are powers of
1/3. A unique way to represent all elements is to use
base 3 or the ternary representation.
Examples:
0=03, 1/3=0.13, 2/3=0.23, 1=0.222…3,
1/9=0.013, 2/9=0.023,7/9=0.213,8/9=0.223,
and so on…
Is there a bijection between the Cantor
set and the natural numbers, N?
 The answer to this question is no, in light of the
ternary representation of the Cantor set, C, and using
Cantor’s Diagonalization Argument.
 What about the real numbers?
 Consider the subset of the real numbers on the interval
[0,1].
 Try to find a mapping, f , from C to the real numbers
on [0,1].
 To this end, represent the real numbers on [0,1] in base
2 or binary just as Cantor did in his original argument.
Finding a function f :C->[0,1]
We can express every number in C in its ternary
representation only consisting of 0’s and 2’s (repeating).
For example, the endpoints of the first few stages are:
0=03, 1=0.222…3, 1/3=0.13=0.0222…3, 2/3=0.23
1/9=0.013=0.00222…3, 2/9=0.023,
7/9=0.213=0.20222…3, 8/9=0.223
and so on…
Notice other numbers besides endpoints are included:
1/4=0.02020202…3
Cont.
Similarly, we can express all real numbers on the
interval [0,1] in their binary representation, from
0=02, to 1=0.111…2.
Thus, replacing all 2’s in the numbers in C by 1’s,
creates a mapping from C to the real numbers in
[0,1].
Define f as follows:
 b
 a
a
j
j
j
f  x    j where b j  and x   j  C
2
j 1 2
j 1 3
The Cantor Function
The mathematical conclusion
Note from the graph, f is not a one to one function, but a
many to one function from C to the real numbers on
[0,1].


For example: f 0.2023  0.1012  0.112 and f 0.223   0.112
however, 0.2023  0.223 so Card[0,1]  CardC .
Also, CardC   Card[0,1] , since C was constructed
from the interval [0,1].
Hence, Card C   Card [0,1].
And as a result C has Cardinality of c or Aleph-1!
Summary of the Cantor Set
 The Cantor set has measure 0.
 The Cantor set is uncountably infinite, with
Cardinality of c or Aleph-1.
 The Cantor set is an example of a set which you
can take an uncountably infinite number of
elements away from an uncountable set and still
have an uncountably infinite set.
 The Cantor set has the added property unlike the
real numbers and irrational numbers of being
closed and bounded so it is nowhere dense.
The Aleph One Song
To the tune 99 bottles of beer on the wall.
♪Aleph-one bottles of beer on the wall,
Aleph-one bottles of beer.
Take infinity down, pass infinity around,
Aleph-one bottles of beer on the wall. ♫
(And repeat…)
The Continuum Hypothesis
Statement: There is no set S such that 0  S  1 .
 In 1940, Godel showed CH could not be disproved
using standard set theory axioms.
 Later in 1963, Cohen showed CH could not be proved
using the same axioms either.
 Thus CH is independent of the natural set theory
axioms, however; is widely believed to be false,
although no concrete justification backs this claim.
Enter Waclaw Sierpinski
A Polish mathematician born in Warsaw, Poland in 1882.
Sierpinski’s Carpet
The process:
 To build Sierpinski's Carpet, S, start with a square
with side length 1 unit, completely shaded.
(Iteration 0, or the initiator)
 Divide each square into nine equal squares and cut
out the middle one. (the generator)
 Repeat this process on all shaded squares.
Graphical representation of S
The Menger Sponge
The process:
 To build the Menger Sponge, M, start with a cube edge 1
unit. (the initiator)
 Divide the cube into twenty-seven equal cubes and cut
out the middle one. (the generator)
 Repeat this process on all remaining cubes.
Graphical representation of M
Extensions to higher dimensions
The procedure then for creating an N dimensional pyramid
can be summarized by the following rules.
 Start with an N-1 dimensional cube centered at the origin.
 Pull the midpoint of the cube (origin) into the Nth
dimension.
 Make edges from the midpoint to each vertex of the N-1
cube.
 Make faces using the midpoint and each edge of the N-1
cube.
 Using these rules the 4D pyramid (hyper-pyramid) is
constructed by taking a 3D cube and pulling its midpoint
into the 4th dimension.
A “4-D” Hyper-Gasket
The process can be continued by
forming another pyramid with the
hyper-cube, and so on…