8: Cardinality
- Page ID
- 19415
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)
The very existence of flame-throwers proves that some time, somewhere, someone said to themselves, “You know, I want to set those people over there on fire, but I’m just not close enough to get the job done.”
–George Carlin
- 8.1: Equivalent Sets
- We have seen several interesting examples of equivalence relations already, and in this section we will explore one more: we’ll say two sets are equivalent if they have the same number of elements. Usually, an equivalence relation has the effect that it highlights one characteristic of the objects being studied, while ignoring all the others. Equivalence of sets brings the issue of size (a.k.a. cardinality) into sharp focus while forgetting all about the many other features of sets.
- 8.2: Examples of Set Equivalence
- There is an ancient conundrum about what happens when an irresistible force meets an immovable object. In a similar spirit, there are sometimes heated debates among young children concerning which super-hero will win a fight. To many people the current topic will seem about as sensible as the schoolyard discussions just alluded to. We are concerned with knowing whether one infinite set is bigger than another, or are they the same size.
- 8.3: Cantor’s Theorem
- Many people believe that the result known as Cantor’s theorem says that the real numbers, ℝ, have a greater cardinality than the natural numbers, ℕ. That isn’t quite right. In fact, Cantor’s theorem is a much broader statement, one of whose consequences is that |ℝ|>|ℕ|. Before we go on to discuss Cantor’s theorem in full generality, we’ll first explore it, essentially, in this simplified form.
- 8.4: Dominance
- We’ve said a lot about the equivalence relation determined by Cantor’s definition of set equivalence. We’ve also, occasionally, written things like |A|<|B|, without being particularly clear about what that means. It’s now time to come clean. There is actually a (perhaps) more fundamental notion used for comparing set sizes than equivalence — dominance. Dominance is an ordering relation on the class of all sets.
- 8.5: The Continuum Hypothesis and The Generalized Continuum Hypothesis
- The word “continuum” in the title of this section is used to indicate sets of points that have a certain continuity property. For example, in a real interval it is possible to move from one point to another, in a smooth fashion, without ever leaving the interval. In a range of rational numbers this is not possible, because there are irrational values in between every pair of rationals.