Are there degrees of infinity?
- Cardinality of a set is the number of elements
- For finite sets, count the elements
- What about infinite sets?
- Is N smaller than Z?
- Is Z smaller than Q?
- Is Q smaller than R?
- First systematically studied by Georg Cantor
- To compare cardinalities of infinite sets, use bijections
- One-to-one and onto function Pairs elements from the sets so that none are left out
Countable sets
- Starting point of infinite sets is N
- Suppose we have a bijection f between N and a set X
- Enumerate X as {f (0), f (1), . . . , }
- X can be “counted” via f
- Such a set is called countable
Z is countable
- Z extends N with negative integers
- Intuitively, Z is twice as large as N
- Can we set up a bijection between N and Z?
· · · , −4, −3, −2, −1, 0, 1, 2, 3, 4, · · ·
2, 0, 1,
4, 2, 0, 1, 3,
· · · , 8, 6, 4, 2, 0, 1, 3, 5, 7, · · ·
- The enumeration is effective
- f (0) = 0
- For i odd, f (i) = (i + 1)/2
- For i even, f (i) = −(i/2)
- Z is countable
Is Q countable?
- Q is dense, Z is discrete
- Are there more rationals than integers?
- There is an obvious bijection between Z × Z and Q
- (p, q) 7→ p /q
- Sufficient to check cardinality of Z × Z
- For simplicity, we restrict to N × N
- Enumerate N × N diagonally
- Other enumeration strategies are also possible
- Can easily extend these to Z × Z
- Hence Q is countable
Is R countable?
- R extends Q by irrational numbers
- Cantor showed that R is not countable
- First, a different set
- Infinite sequences over {0, 1}
0 1 0 1 1 0 · · · - Suppose there is some enumeration
- Flip bi in si
- Read off the diagonal sequence
- Diagonal sequence differs from each si at bi
- New sequence that it not part of the enumeration
- Infinite sequences over {0, 1} cannot be enumerated
- Each sequence can be read as a decimal fraction
0.011101110011 - Injective function from {0, 1} sequences to interval [0, 1) ⊆ R
- Hence [0, 1) ⊆ R cannot be enumerated
- So R is not countable
Summary
- Any set that has a bijection from N is countable
- Z and Q are countable
- R is not countable — diagonalization
- Is there a set whose size is between N and R?
- Continuum Hypothesis — one of the major questions in set theory
- Paul Cohen showed that you can neither prove nor disprove this hypothesis within set theory
Facebook Comments Box