1.4: The Size of Sets
- Page ID
- 121603
\( \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}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
- 1.4.1: Introduction
- If \(a\), \(b\) and \(c\) are all distinct, then the set \(\{a, b, c\}\) is intuitively larger than \(\{a, b\}\). But what about infinite sets? Are they all as large as each other?
- 1.4.2: Enumerations and Countable Sets
- We’ve already given examples of sets by listing their elements. Let’s discuss in more general terms how and when we can list the elements of a set, even if that set is infinite.
- 1.4.3: Cantor’s Zig-Zag Method
- Cantor’s zig-zag method shows that the sets of pairs of elements of countably infinite sets is also countable.
- 1.4.4: Pairing Functions and Codes
- We can use pairing functions to represent each pair of elements using a single number. Using the inverse of the pairing function, we can decode the number, i.e., find out which pair it represents.
- 1.4.5: An Alternative Pairing Function
- There are other enumerations of \(\mathbb{N}^2\) that make it easier to figure out what their inverses are. Here is one.
- 1.4.6: Uncountable Sets
- One way of showing that a set is uncountable is to give a diagonal argument. We assume that the set \(A\) in question is countable, and use a hypothetical enumeration to define an element of \(A\) which, by the very way we define it, is guaranteed to be different from every element in the enumeration. So the enumeration can’t be an enumeration of all of \(A\) after all, and we’ve shown that no enumeration of \(A\) can exist.
- 1.4.7: Reduction
- A reduction shows that \(A\) is uncountable by associating every element of \(A\) with an element of some known uncountable set \(B\) in a surjective way. If this is possible, then a hypothetical enumeration of \(A\) would yield an enumeration of \(B\). Since \(B\) is uncountable, no enumeration of \(A\) can exist.
- 1.4.8: Equinumerosity
- In general, infinite sets can be compared sizewise: \(A\) and \(B\) are the same size, or equinumerous, if there is a bijection between them.
- 1.4.9: Sets of Different Sizes, and Cantor’s Theorem
- We can define that \(A\) is no larger than \(B\) (\({A}\preceq{B}\)) if there is an injective function from \(A\) to \(B\).
- 1.4.10: The Notion of Size, and Schröder-Bernstein
- Here is an intuitive thought: if \(A\) is no larger than \(B\) and \(B\) is no larger than \(A\), then \(A\) and \(B\) are equinumerous. This is justified by the Schröder-Bernstein Theorem.