The Open Logic Text — accessible offline edition

The Size of Sets — Source and provenance

The Size of Sets

Source and provenance

These are all 14 files in the frozen The Size of Sets source boundary, shown line by line and copied byte-for-byte for download. The reading views bind all 1082 formula occurrences to their exact source locations.

Source label and reader link correction

Editorial projection note: the source gives this alternate exercise the same link label as the corresponding exercise in the earlier Reduction section. This edition assigns the alternate copy its own link target; unqualified references lead to the earlier copy. The canonical source is unchanged.

The preserved source below still shows the duplicate at reduction-alt.tex line 106 and the primary definition at reduction.tex line 108. The reading views use the four-character derived-stream correction and keep the earlier exercise as the target of unqualified references.

Open the derived reading stream. Open the exact correction sidecar.

content/sets-functions-relations/size-of-sets/comparing-size.tex

150 lines; SHA-256 cb92c7e6df9529ced700d708ad8c6efda9a0d8c3f8e69d08bcb4d614c6f5041b. Open the preserved source file.

  1. % Part:sets-functions-relations
  2. % Chapter: size-of-sets
  3. % Section: comparing-sizes
  5. \documentclass[../../../include/open-logic-section]{subfiles}
  7. \begin{document}
  9. \olfileid{sfr}{siz}{car}
  11. \olsection{Sets of Different Sizes, and Cantor's Theorem}
  13. \begin{explain}
  14. We have offered a precise statement of the idea that two sets have the
  15. same size. We can also offer a precise statement of the idea that one
  16. set is smaller than another. Our definition of ``is smaller than (or
  17. equinumerous)'' will require, instead of !!a{bijection} between the
  18. sets, !!a{injection} from the first set to the second. If such a
  19. function exists, the size of the first set is less than or equal to
  20. the size of the second. Intuitively, !!a{injection} from one set to
  21. another guarantees that the range of the function has at least as many
  22. !!{element}s as the domain, since no two !!{element}s of the domain
  23. map to the same !!{element} of the range.
  24. \end{explain}
  26. \begin{defn}
  27. $A$ is \emph{no larger than}~$B$, written $\cardle{A}{B}$, iff there
  28. is !!a{injection} $f \colon A \to B$.
  29. \end{defn}
  31. It is clear that this is a reflexive and transitive relation, but that
  32. it is not symmetric (this is left as an exercise). We can also
  33. introduce a notion, which states that one set is (strictly) smaller
  34. than another.
  36. \begin{defn}
  37. $A$ is \emph{smaller than}~$B$, written $\cardless{A}{B}$, iff there
  38. is !!a{injection}~$f\colon A \to B$ but no !!{bijection}~$g\colon A
  39. \to B$, i.e., $\cardle{A}{B}$ and $\cardneq{A}{B}$.
  40. \end{defn}
  42. It is clear that this relation is irreflexive
  43. and transitive. (This is left as an exercise.) Using this notation, we
  44. can say that a set $A$ is !!{enumerable} iff $\cardle{A}{\Nat}$, and
  45. that $A$ is !!{nonenumerable} iff $\cardless{\Nat}{A}$. This allows us
  46. to restate
  47. \oliflabeldef{sfr:siz:nen-alt:thm:nonenum-pownat}{%
  48. \olref[sfr][siz][nen-alt]{thm:nonenum-pownat}
  49. as the observation that
  50. $\cardless{\Nat}{\Pow{\Nat}}$}{%
  51. \olref[sfr][siz][nen]{thm:nonenum-pownat}
  52. as the observation that $\cardless{\PosInt}{\Pow{\PosInt}}$}. In fact,
  53. \citet{Cantor1892} proved that this last point is \emph{perfectly
  54. general}:
  56. \begin{thm}[Cantor]\ollabel{thm:cantor}
  57. $\cardless{A}{\Pow{A}}$, for any set $A$.
  58. \end{thm}
  60. \begin{proof}
  61. The map $f(x) = \{x\}$ is !!a{injection} $f \colon A \to \Pow{A}$,
  62. since if $x \neq y$, then also $\{x\} \neq \{y\}$ by extensionality,
  63. and so $f(x) \neq f(y)$. So we have that $\cardle{A}{\Pow{A}}$.
  65. \begin{editorial}
  66. We present the slow proof if \olref[nen]{sec} is
  67. present, otherwise a faster proof matching \olref[nen-alt]{sec}.
  68. \end{editorial}
  70. \oliflabeldef{sfr:siz:nen:sec}{%
  71. We will now show that there cannot be !!a{surjective} function~$g\colon A \to
  72. \Pow{A}$, let alone !!a{bijective} one, and hence that
  73. $\cardneq{A}{\Pow{A}}$. For suppose that $g\colon A \to \Pow{A}$.
  74. Since $g$ is total, every $x \in A$ is mapped to a subset $g(x)
  75. \subseteq A$. We can show that $g$ cannot be surjective. To do this, we
  76. define a subset~$\overline{A} \subseteq A$ which by definition cannot be in the
  77. range of~$g$. Let
  78. \[
  79. \overline{A} = \Setabs{x \in A}{x \notin g(x)}.
  80. \]
  81. Since $g(x)$ is defined for all $x \in A$, $\overline{A}$ is clearly
  82. a well-defined subset of~$A$. But, it cannot be in the range
  83. of~$g$. Let $x \in A$ be arbitrary, we will show that $\overline{A} \neq
  84. g(x)$. If $x \in g(x)$, then it does not satisfy $x \notin g(x)$,
  85. and so by the definition of~$\overline{A}$, we have $x \notin
  86. \overline{A}$. If $x \in \overline{A}$, it must satisfy the
  87. defining property of~$\overline{A}$, i.e., $x \in A$ and $x \notin
  88. g(x)$. Since $x$ was arbitrary, this shows that for each $x \in
  89. \overline{A}$, $x \in g(x)$ iff $x \notin \overline{A}$, and so
  90. $g(x) \neq \overline{A}$. In other words, $\overline{A}$ cannot be
  91. in the range of~$g$, contradicting the assumption that~$g$ is
  92. surjective.}{It remains to show that $\cardneq{A}{\Pow{A}}$. For
  93. reductio, suppose $\cardeq{A}{\Pow{A}}$, i.e., there is some
  94. !!{bijection} $g \colon A \to \Pow{A}$. Now consider:
  95. \[
  96. D = \Setabs{x \in A}{x \notin g(x)}
  97. \]
  98. Note that $D \subseteq A$, so that $D \in \Pow{A}$. Since $g$ is
  99. !!a{bijection}, there is some $y \in A$ such that $g(y) = D$. But
  100. now we have:
  101. \[
  102. y \in g(y) \text{ iff } y \in D \text{ iff } y \notin g(y).
  103. \]
  104. This is a contradiction; so $\cardneq{A}{\Pow{A}}$.}{}
  105. \end{proof}
  107. \begin{explain}
  108. \oliflabeldef{sfr:siz:nen:thm:nonenum-pownat}{It's instructive to
  109. compare the proof of \olref{thm:cantor} to that of
  110. \olref[nen]{thm:nonenum-pownat}. There we showed that for any list
  111. $Z_1$, $Z_2$, \dots, of subsets of~$\PosInt$ one can construct a
  112. set~$\overline{Z}$ of numbers guaranteed not to be on the list. It
  113. was guaranteed not to be on the list because, for every $n \in
  114. \PosInt$, $n \in Z_n$ iff $n \notin \overline{Z}$. This way, there
  115. is always some number that is !!a{element} of one of $Z_n$ or
  116. $\overline{Z}$ but not the other. We follow the same idea here,
  117. except the indices~$n$ are now !!{element}s of~$A$ instead
  118. of~$\PosInt$. The set $\overline{A}$ is defined so that it is
  119. different from~$g(x)$ for each $x \in A$, because $x \in g(x)$ iff
  120. $x \notin \overline{A}$. Again, there is always !!a{element} of~$A$
  121. which is !!a{element} of one of $g(x)$ and $\overline{A}$ but not
  122. the other. And just as $\overline{Z}$ therefore cannot be on the
  123. list $Z_1$, $Z_2$, \dots, $\overline{A}$ cannot be in the range
  124. of~$g$.}{}
  126. \oliflabeldef{sfr:siz:nen-alt:thm:nonenum-pownat}{It's instructive to
  127. compare the proof of \olref{thm:cantor} to that of
  128. \olref[nen-alt]{thm:nonenum-pownat}. There we showed that for any
  129. list $N_0$, $N_1$, $N_2$, \dots, of subsets of~$\Nat$ we can construct a
  130. set~$D$ of numbers guaranteed not to be on the list. It was
  131. guaranteed not to be on the list because $n \in N_n$ iff $n \notin
  132. D$, for every $n \in \Nat$. We follow the same idea here, except the
  133. indices~$n$ are now !!{element}s of~$A$ rather than of~$\Nat$. The
  134. set $D$ is defined so that it is different from~$g(x)$ for each $x
  135. \in A$, because $x \in g(x)$ iff $x \notin D$.}{}
  137. The proof is also worth comparing with the proof of Russell's Paradox,
  138. \olref[sfr][set][rus]{thm:russells-paradox}. Indeed, Cantor's Theorem was
  139. the inspiration for Russell's own paradox.
  140. \end{explain}
  142. \begin{prob}
  143. Show that there cannot be !!a{injection} $g\colon \Pow{A} \to
  144. A$, for any set~$A$. Hint: Suppose $g\colon \Pow{A} \to A$ is
  145. !!{injective}. Consider $D = \Setabs{g(B)}{B \subseteq A \text{ and
  146. } g(B) \notin B}$. Let $x = g(D)$. Use the fact that $g$ is
  147. !!{injective} to derive a contradiction.
  148. \end{prob}
  150. \end{document}

content/sets-functions-relations/size-of-sets/enumerability-alt.tex

135 lines; SHA-256 8ad8d8941a5ca6d1b4cd2cc351fc16a912d00273783c0358838dd4fa51fb4627. Open the preserved source file.

  1. % Part:sets-functions-relations
  2. % Chapter: size-of-sets
  3. % Section: enumerations-alt
  5. \documentclass[../../../include/open-logic-section]{subfiles}
  7. \begin{document}
  9. \olfileid{sfr}{siz}{enm-alt}
  11. \olsection{Enumerations and \usetoken{S}{enumerable} Sets}
  13. \begin{editorial}
  14. This section defines enumerations as bijections with (initial
  15. segments) of $\Nat$, the way it's done in set theory. So it
  16. conflicts slightly with the definitions in \olref[enm]{sec}, and
  17. repeats all the examples there. It is also a bit more terse than
  18. that section.
  19. \end{editorial}
  21. We can specify finite set is by simply enumerating its
  22. !!{element}s. We do this when we define a set like so:
  23. \[
  24. A = \{a_1, a_2, \ldots, a_n\}.
  25. \]
  26. Assuming that the !!{element}s $a_1$, \dots, $a_n$ are all distinct,
  27. this gives us !!a{bijection} between $A$ and the first $n$ natural
  28. numbers $0$, \dots, $n-1$. Conversely, since every finite set has only
  29. finitely many !!{element}s, every finite set can be put into such a
  30. correspondence. In other words, if $A$ is finite, there is
  31. !!a{bijection} between $A$ and $\{0, \dots, n-1\}$, where $n$ is the
  32. number of !!{element}s of~$A$.
  34. If we allow for certain kinds of infinite sets, then we will also
  35. allow some infinite sets to be enumerated. We can make this precise by
  36. saying that an infinite set is enumerated by !!a{bijection} between it
  37. and all of~$\Nat$.
  39. \begin{defn}[Enumeration, set-theoretic]
  40. An \emph{enumeration} of a set $A$ is !!a{bijection} whose range is
  41. $A$ and whose domain is either an initial set of natural numbers $\{0,
  42. 1, \ldots, n\}$ {or} the entire set of natural numbers~$\Nat$.
  43. \end{defn}
  45. \begin{explain}
  46. There is an intuitive underpinning to this use of the word
  47. \emph{enumeration}. For to say that we have enumerated a set $A$ is to
  48. say that there is !!a{bijection} $f$ which allows us to count out the
  49. elements of the set $A$. The $0$th element is $f(0)$, the 1st is
  50. $f(1)$, \ldots the $n$th is $f(n)$\ldots.\footnote{Yes, we count
  51. from $0$. Of course we could also start with~$1$. This would
  52. make no big difference. We would just have to replace~$\Nat$
  53. by~$\PosInt$.} The rationale for this may be made even clearer by
  54. adding the following:
  55. \end{explain}
  57. \begin{defn}
  58. \ollabel{defn:enumerable}
  59. A set~$A$ is !!{enumerable} iff either $A = \emptyset$ or there is
  60. an enumeration of~$A$. We say that $A$ is !!{nonenumerable} iff $A$
  61. is not !!{enumerable}.
  62. \end{defn}
  64. \begin{explain}
  65. So a set is !!{enumerable} iff it is empty or you can use an
  66. enumeration to count out its !!{element}s.
  67. \end{explain}
  69. \begin{ex}
  70. A function enumerating the natural numbers is simply the identity
  71. function $\Id{\Nat} \colon \Nat \to \Nat$ given by $\Id{\Nat}(n) = n$. A
  72. function enumerating the \emph{positive} natural numbers, $\Nat^+ =
  73. \Nat \setminus \{0\}$, is the function $g(n) = n + 1$, i.e., the
  74. successor function.
  75. \end{ex}
  77. \begin{prob}
  78. Show that a set $A$ is !!{enumerable} iff either $A = \emptyset$ or
  79. there is !!a{surjection} $f\colon \Nat \to A$. Show that $A$ is
  80. !!{enumerable} iff there is !!a{injection} $g\colon A \to \Nat$.
  81. \end{prob}
  83. \begin{ex}
  84. The functions $f\colon \Nat \to \Nat$ and $g \colon \Nat \to \Nat$
  85. given by
  86. \begin{align*}
  87. f(n) & = 2n \text{ and}\\
  88. g(n) & = 2n+1
  89. \end{align*}
  90. respectively enumerate the even natural numbers and the odd natural
  91. numbers. But neither is !!{surjective}, so neither is an enumeration
  92. of $\Nat$.
  93. \end{ex}
  95. \begin{prob}
  96. Define an enumeration of the square numbers $1$, $4$, $9$, $16$, \dots
  97. \end{prob}
  99. \begin{ex}
  100. Let $\lceil x \rceil$ be the \emph{ceiling} function, which rounds $x$
  101. up to the nearest integer. Then the function $f \colon \Nat \to \Int$
  102. given by:
  103. \[
  104. f(n) = (-1)^{n} \left\lceil\tfrac{n}{2}\right\rceil
  105. \]
  106. enumerates the set of
  107. integers~$\Int$ as follows:
  108. \[
  109. \begin{array}{c c c c c c c c}
  110. f(0) & f(1) & f(2) & f(3) & f(4) & f(5) & f(6) & \dots \\ \\
  111. \big\lceil \tfrac{0}{2} \big\rceil & -\big\lceil \tfrac{1}{2}\big\rceil & \big\lceil \tfrac{2}{2} \big\rceil & -\big\lceil \tfrac{3}{2} \big\rceil & \big\lceil \tfrac{4}{2} \big\rceil & -\big\lceil \tfrac{5}{2}\big\rceil & \big\lceil \tfrac{6}{2} \big\rceil & \dots \\ \\
  112. 0 & -1 & 1 & -2 & 2 & -3 & 3& \dots
  113. \end{array}
  114. \]
  115. Notice how $f$ generates the values of $\Int$ by ``hopping'' back and
  116. forth between positive and negative integers. You can also think of
  117. $f$ as defined by cases as follows:
  118. \[
  119. f(n) = \begin{cases}
  120. \frac{n}{2} & \text{if $n$ is even}\\
  121. -\frac{n+1}{2} & \text{if $n$ is odd}
  122. \end{cases}
  123. \]
  124. \end{ex}
  126. \begin{prob}
  127. Show that if $A$ and $B$ are !!{enumerable}, so is $A \cup B$.
  128. \end{prob}
  130. \begin{prob}
  131. Show by induction on $n$ that if $A_1$, $A_2$, \dots, $A_n$ are all
  132. !!{enumerable}, so is $A_1 \cup \dots \cup A_n$.
  133. \end{prob}
  135. \end{document}

content/sets-functions-relations/size-of-sets/enumerability.tex

279 lines; SHA-256 7657db317a07eef9cd5497ad88997483dd43c9f94f27d257abe857084886a2fe. Open the preserved source file.

  1. % Part:sets-functions-relations
  2. % Chapter: size-of-sets
  3. % Section: enumerations
  5. \documentclass[../../../include/open-logic-section]{subfiles}
  7. \begin{document}
  9. \olfileid{sfr}{siz}{enm}
  11. \olsection{Enumerations and \usetoken{S}{enumerable} Sets}
  13. \begin{editorial}
  14. This section discusses enumerations of sets, defining them as
  15. surjections from $\PosInt$. It does things slowly, for readers with
  16. little mathematical background. An alternative, terser
  17. version is given in \olref[enm-alt]{sec}, which defines enumerations
  18. differently: as bijections with $\Nat$ (or an initial segment).
  19. \end{editorial}
  21. \begin{explain}
  22. We've already given examples of sets by listing their !!{element}s.
  23. Let's discuss in more general terms how and when we can list the
  24. !!{element}s of a set, even if that set is infinite.
  25. \end{explain}
  27. \begin{defn}[Enumeration, informally]
  28. Informally, an \emph{enumeration} of a set~$A$ is a list (possibly
  29. infinite) of !!{element}s of~$A$ such that every !!{element} of $A$
  30. appears on the list at some finite position. If $A$ has an
  31. enumeration, then $A$ is said to be \emph{!!{enumerable}}.
  32. \end{defn}
  34. \begin{explain}
  35. A couple of points about enumerations:
  36. \begin{enumerate}
  37. \item We count as enumerations only lists which have a beginning and
  38. in which every !!{element} other than the first has a single
  39. !!{element} immediately preceding it. In other words, there are
  40. only finitely many elements between the first !!{element} of the
  41. list and any other !!{element}. In particular, this means that every
  42. !!{element} of an enumeration has a finite position: the first
  43. !!{element} has position~$1$, the second position~$2$, etc.
  44. \item We can have different enumerations of the same set~$A$ which
  45. differ by the order in which the !!{element}s appear: $4$, $1$,
  46. $25$, $16$,~$9$ enumerates the (set of the) first five square
  47. numbers just as well as $1$, $4$, $9$, $16$,~$25$ does.
  48. \item Redundant enumerations are still enumerations: $1$, $1$, $2$,
  49. $2$, $3$, $3$,~\dots{} enumerates the same set as $1$, $2$,
  50. $3$,~\dots{} does.
  51. \item Order and redundancy \emph{do} matter when we specify an
  52. enumeration: we can enumerate the positive integers beginning with
  53. $1$, $2$, $3$, $1$, \dots{}, but the pattern is easier to see when
  54. enumerated in the standard way as $1$, $2$, $3$, $4$,~\dots
  55. \item Enumerations must have a beginning: \dots, $3$, $2$, $1$ is not
  56. an enumeration of the positive integers because it has no first
  57. !!{element}. To see how this follows from the informal definition,
  58. ask yourself, ``at what position in the list does the number 76
  59. appear?''
  60. \item The following is not an enumeration of the positive integers:
  61. $1$, $3$, $5$, \dots, $2$, $4$, $6$, \dots\@ The problem is that the
  62. even numbers occur at places $\infty + 1$, $\infty + 2$, $\infty +
  63. 3$, rather than at finite positions.
  64. \item The empty set is enumerable: it is enumerated by the empty list!{}
  65. \end{enumerate}
  66. \end{explain}
  68. \begin{prop}
  69. If $A$ has an enumeration, it has an enumeration without
  70. repetitions.
  71. \end{prop}
  73. \begin{proof}
  74. Suppose $A$ has an enumeration $x_1$, $x_2$, \dots{} in which each
  75. $x_i$ is an !!{element} of~$A$. We can remove repetitions from an
  76. enumeration by removing repeated !!{element}s. For instance, we can
  77. turn the enumeration into a new one in which we list $x_i$ if
  78. it is !!a{element} of~$A$ that is not among $x_1$, \dots,
  79. $x_{i-1}$ or remove $x_i$ from the list if it already appears among
  80. $x_1$, \dots,~$x_{i-1}$.
  81. \end{proof}
  83. The last argument shows that in order to get a good handle on
  84. enumerations and !!{enumerable} sets and to prove things about them,
  85. we need a more precise definition. The following provides it.
  87. \begin{defn}[Enumeration, formally]
  88. An \emph{enumeration} of a set $A \neq \emptyset$ is any
  89. !!{surjective} function $f \colon \PosInt \to A$.
  90. \end{defn}
  92. \begin{explain}
  93. Let's convince ourselves that the formal definition and the informal
  94. definition using a possibly infinite list are equivalent. First, any
  95. !!{surjective} function from $\PosInt$ to a set~$A$ enumerates~$A$.
  96. Such a function determines an enumeration as defined informally above:
  97. the list $f(1)$, $f(2)$, $f(3)$, \dots. Since $f$ is !!{surjective},
  98. every !!{element} of~$A$ is guaranteed to be the value of~$f(n)$ for
  99. some~$n \in \PosInt$. Hence, every !!{element} of $A$ appears at some
  100. finite position in the list. Since the function may not be
  101. !!{injective}, the list may be redundant, but that is acceptable (as
  102. noted above).
  104. On the other hand, given a list that enumerates all !!{element}s
  105. of~$A$, we can define !!a{surjective} function $f\colon \PosInt \to A$
  106. by letting $f(n)$ be the $n$th !!{element} of the list, or the final
  107. !!{element} of the list if there is no $n$th !!{element}. The only
  108. case where this does not produce !!a{surjective} function is when $A$ is
  109. empty, and hence the list is empty. So, every non-empty list
  110. determines !!a{surjective} function $f\colon \PosInt \to A$.
  111. \end{explain}
  113. \begin{defn}
  114. \ollabel{defn:enumerable}
  115. A set~$A$ is !!{enumerable} iff it is empty or has an enumeration.
  116. \end{defn}
  118. \begin{ex}
  119. A function enumerating the positive integers ($\PosInt$) is simply the
  120. identity function given by $f(n) = n$. A function enumerating the
  121. natural numbers $\Nat$ is the function $g(n) = n - 1$.
  122. \end{ex}
  124. \begin{ex}
  125. The functions $f\colon \PosInt \to \PosInt$ and $g \colon \PosInt \to
  126. \PosInt$ given by
  127. \begin{align*}
  128. f(n) & = 2n \text{ and}\\
  129. g(n) & = 2n - 1
  130. \end{align*}
  131. enumerate the even positive integers and the odd positive integers,
  132. respectively. However, neither function is an enumeration of
  133. $\PosInt$, since neither is !!{surjective}.
  134. \end{ex}
  136. \begin{prob}
  137. Define an enumeration of the positive squares $1$, $4$, $9$, $16$, \dots
  138. \end{prob}
  140. \begin{ex}
  141. The function $f(n) = (-1)^{n} \lceil \frac{(n-1)}{2}\rceil$ (where
  142. $\lceil x \rceil$ denotes the \emph{ceiling} function, which rounds
  143. $x$ up to the nearest integer) enumerates the set of
  144. integers~$\Int$. Notice how $f$ generates the values of $\Int$ by
  145. ``hopping'' back and forth between positive and negative integers:
  146. \[
  147. \begin{array}{c c c c c c c c}
  148. f(1) & f(2) & f(3) & f(4) & f(5) & f(6) & f(7) & \dots \\ \\
  149. - \lceil \tfrac{0}{2} \rceil & \lceil \tfrac{1}{2}\rceil & - \lceil \tfrac{2}{2} \rceil & \lceil \tfrac{3}{2} \rceil & - \lceil \tfrac{4}{2} \rceil & \lceil \tfrac{5}{2}
  150. \rceil & - \lceil \tfrac{6}{2} \rceil & \dots \\ \\
  151. 0 & 1 & -1 & 2 & -2 & 3 & \dots
  152. \end{array}
  153. \]
  154. You can also think of $f$ as defined by cases as follows:
  155. \[
  156. f(n) = \begin{cases}
  157. 0 & \text{if $n = 1$}\\
  158. n/2 & \text{if $n$ is even}\\
  159. -(n-1)/2 & \text{if $n$ is odd and $>1$}
  160. \end{cases}
  161. \]
  162. \end{ex}
  164. \begin{prob}
  165. Show that if $A$ and $B$ are !!{enumerable}, so is $A \cup B$. To do
  166. this, suppose there are !!{surjective} functions $f\colon \PosInt \to
  167. A$ and $g\colon \PosInt \to B$, and define !!a{surjective}
  168. function~$h\colon \PosInt \to A \cup B$ and prove that it is
  169. !!{surjective}. Also consider the cases where $A$ or~$B = \emptyset$.
  170. \end{prob}
  172. \begin{prob}
  173. Show that if $B \subseteq A$ and $A$ is !!{enumerable}, so is~$B$. To
  174. do this, suppose there is !!a{surjective} function $f\colon \PosInt \to
  175. A$. Define !!a{surjective} function~$g\colon \PosInt \to B$ and prove
  176. that it is !!{surjective}. What happens if $B = \emptyset$?
  177. \end{prob}
  179. \begin{prob}
  180. Show by induction on $n$ that if $A_1$, $A_2$, \dots, $A_n$ are all
  181. !!{enumerable}, so is $A_1 \cup \dots \cup A_n$. You may assume the
  182. fact that if two sets $A$ and~$B$ are !!{enumerable}, so is~$A \cup
  183. B$.
  184. \end{prob}
  186. Although it is perhaps more natural when listing the !!{element}s of a
  187. set to start counting from the $1$st !!{element}, mathematicians like
  188. to use the natural numbers~$\Nat$ for counting things. They
  189. talk about the $0$th, $1$st, $2$nd, and so on, !!{element}s of a list.
  190. Correspondingly, we can define an enumeration as !!a{surjective}
  191. function from $\Nat$ to~$A$. Of course, the two definitions are
  192. equivalent.
  194. \begin{prop}\ollabel{prop:enum-shift}
  195. There is !!a{surjection} $f\colon \PosInt \to A$ iff there is
  196. !!a{surjection} $g\colon \Nat \to A$.
  197. \end{prop}
  199. \begin{proof}
  200. Given !!a{surjection} $f\colon \PosInt \to A$, we can define $g(n) =
  201. f(n+1)$ for all $n \in \Nat$. It is easy to see that $g\colon \Nat
  202. \to A$ is !!{surjective}. Conversely, given !!a{surjection} $g\colon
  203. \Nat \to A$, define $f(n) = g(n-1)$.
  204. \end{proof}
  206. This gives us the following result:
  208. \begin{cor}\ollabel{cor:enum-nat}
  209. A set $A$ is !!{enumerable} iff it is empty or there is
  210. !!a{surjective} function $f\colon \Nat \to A$.
  211. \end{cor}
  213. We discussed above that a list of !!{element}s of a set~$A$ can be
  214. turned into a list without repetitions. This is also true for
  215. enumerations, but a bit harder to formulate and prove rigorously. Any
  216. function $f\colon \PosInt \to A$ must be defined for all $n \in
  217. \PosInt$. If there are only finitely many !!{element}s in~$A$ then we
  218. clearly cannot have a function defined on the infinitely many
  219. !!{element}s of~$\PosInt$ that takes as values all the !!{element}s
  220. of~$A$ but never takes the same value twice. In that case, i.e., in
  221. the case where the list without repetitions is finite, we must choose
  222. a different domain for~$f$, one with only finitely many !!{element}s.
  223. Not having repetitions means that $f$ must be !!{injective}. Since it
  224. is also !!{surjective}, we are looking for !!a{bijection} between some
  225. finite set $\{1, \dots, n\}$ or $\PosInt$ and~$A$.
  227. \begin{prop}\ollabel{prop:enum-bij}
  228. If $f\colon \PosInt \to A$ is !!{surjective} (i.e., an enumeration
  229. of~$A$), there is !!a{bijection} $g\colon Z \to A$ where $Z$ is
  230. either~$\PosInt$ or $\{1, \dots, n\}$ for some~$n \in \PosInt$.
  231. \end{prop}
  233. \begin{proof}
  234. We define the function $g$ recursively: Let $g(1) = f(1)$. If $g(i)$
  235. has already been defined, let $g(i+1)$ be the first value of $f(1)$,
  236. $f(2)$, \dots{} not already among $g(1)$, \dots, $g(i)$, if there is
  237. one. If $A$ has just $n$ !!{element}s, then $g(1)$, \dots, $g(n)$ are all
  238. defined, and so we have defined a function $g\colon \{1, \dots, n\}
  239. \to A$. If $A$ has infinitely many !!{element}s, then for any $i$
  240. there must be !!a{element} of~$A$ in the enumeration $f(1)$, $f(2)$,
  241. \dots, which is not already among $g(1)$, \dots, $g(i)$. In this
  242. case we have defined a function $g\colon \PosInt \to A$.
  244. The function $g$ is !!{surjective}, since any element of~$A$ is
  245. among $f(1)$, $f(2)$, \dots{} (since $f$ is !!{surjective}) and so
  246. will eventually be a value of~$g(i)$ for some~$i$. It is also
  247. !!{injective}, since if there were $j < i$ such that $g(j) = g(i)$,
  248. then $g(i)$ would already be among $g(1)$, \dots, $g(i-1)$, contrary
  249. to how we defined~$g$.
  250. \end{proof}
  252. \begin{cor}\ollabel{cor:enum-nat-bij}
  253. A set $A$ is !!{enumerable} iff it is empty or there is !!a{bijection}
  254. $f\colon N \to A$ where either $N = \Nat$ or $N = \{0, \dots, n\}$ for
  255. some $n \in \Nat$.
  256. \end{cor}
  258. \begin{proof}
  259. $A$ is !!{enumerable} iff $A$ is empty or there is !!a{surjective}
  260. $f\colon \PosInt \to A$. By \olref{prop:enum-bij}, the latter holds
  261. iff there is !!a{bijective} function~$f\colon Z \to A$ where $Z =
  262. \PosInt$ or $Z = \{1, \dots, n\}$ for some $n \in \PosInt$. By the
  263. same argument as in the proof of \olref{prop:enum-shift}, that in turn
  264. is the case iff there is !!a{bijection} $g\colon N \to A$ where either
  265. $N = \Nat$ or $N = \{0, \dots, n-1\}$.
  266. \end{proof}
  268. \begin{prob}
  269. According to \olref[sfr][siz][enm]{defn:enumerable}, a set $A$ is
  270. enumerable iff $A = \emptyset$ or there is !!a{surjective} $f\colon
  271. \PosInt \to A$. It is also possible to define ``!!{enumerable} set''
  272. precisely by: a set is enumerable iff there is !!a{injective}
  273. function $g\colon A \to \PosInt$. Show that the definitions are
  274. equivalent, i.e., show that there is !!a{injective} function
  275. $g\colon A \to \PosInt$ iff either $A = \emptyset$ or there is
  276. !!a{surjective} $f\colon \PosInt \to A$.
  277. \end{prob}
  279. \end{document}

content/sets-functions-relations/size-of-sets/equinumerous-sets.tex

111 lines; SHA-256 7b0444e3293b300b72b7a6d49638913a778f5131fd94650dd64a5f11040c91f2. Open the preserved source file.

  1. % Part:sets-functions-relations
  2. % Chapter: size-of-sets
  3. % Section: equinumerous-sets
  5. \documentclass[../../../include/open-logic-section]{subfiles}
  7. \begin{document}
  9. \olfileid{sfr}{siz}{equ}
  11. \olsection{Equinumerosity}
  13. We have an intuitive notion of ``size'' of sets, which works fine for
  14. finite sets. But what about infinite sets? If we want to come up with
  15. a formal way of comparing the sizes of two sets of \emph{any} size, it
  16. is a good idea to start by defining when sets are the same size. Here
  17. is Frege:
  18. \begin{quote}
  19. If a waiter wants to be sure that he has laid exactly as many knives
  20. as plates on the table, he does not need to count either of them, if
  21. he simply lays a knife to the right of each plate, so that every
  22. knife on the table lies to the right of some plate. The plates and
  23. knives are thus uniquely correlated to each other, and indeed
  24. through that same spatial relationship. \citep[\S70]{Frege1884}
  25. \end{quote}
  26. The insight of this passage can be brought out through a formal
  27. definition:
  29. \begin{defn}\ollabel{comparisondef}
  30. $A$ is \emph{equinumerous} with $B$, written $\cardeq{A}{B}$, iff
  31. there is !!a{bijection} $f \colon A \to B$.
  32. \end{defn}
  34. \begin{prop}\ollabel{equinumerosityisequi}
  35. Equinumerosity is an equivalence relation.
  36. \end{prop}
  38. \begin{proof}
  39. We must show that equinumerosity is reflexive, symmetric, and
  40. transitive. Let $A, B$, and $C$ be sets.
  42. \emph{Reflexivity.} The identity map $\Id{A} \colon A \to A$, where
  43. $\Id{A} (x) = x$ for all $x \in A$, is !!a{bijection}. So
  44. $\cardeq{A}{A}$.
  46. \emph{Symmetry.} Suppose $\cardeq{A}{B}$, i.e., there is
  47. !!a{bijection} $f\colon A \to B$. Since $f$ is !!{bijective}, its
  48. inverse $f^{-1}$ exists and is also !!{bijective}. Hence,
  49. $f^{-1}\colon B \to A$ is !!a{bijection}, so $\cardeq{B}{A}$.
  51. \emph{Transitivity.} Suppose that $\cardeq{A}{B}$ and $\cardeq{B}{C}$,
  52. i.e., there are !!{bijection}s $f\colon A \to B$ and $g\colon B \to
  53. C$. Then the composition $\comp{f}{g}\colon A \to C$ is !!{bijective},
  54. so that $\cardeq{A}{C}$.
  55. \end{proof}
  57. \begin{prop}
  58. If $\cardeq{A}{B}$, then $A$ is !!{enumerable} if
  59. and only if $B$ is.
  60. \end{prop}
  62. \begin{editorial}
  63. The following proof uses \olref[enm]{defn:enumerable} if
  64. \olref[enm]{sec} is included and \olref[enm-alt]{defn:enumerable}
  65. otherwise.
  66. \end{editorial}
  68. \begin{proof}
  69. Suppose $\cardeq{A}{B}$, so there is some !!{bijection} $f \colon A
  70. \to B$, and suppose that $A$ is !!{enumerable}.
  71. \oliflabeldef{sfr:siz:enm:defn:enumerable}{
  72. Then either $A = \emptyset$ or there is !!a{surjective} function
  73. $g\colon \PosInt \to A$. If $A = \emptyset$, then $B = \emptyset$
  74. also (otherwise there would be !!a{element}~$y \in B$ but no $x \in
  75. A$ with $g(x) = y$). If, on the other hand, $g\colon \PosInt \to A$
  76. is !!{surjective}, then $\comp{g}{f} \colon \PosInt \to B$ is
  77. !!{surjective}. To see this, let $y \in B$. Since $f$ is
  78. !!{surjective}, there is an $x \in A$ such that $f(x) = y$. Since
  79. $g$ is !!{surjective}, there is an $n \in \PosInt$ such that $g(n) =
  80. x$. Hence,
  81. \[
  82. (\comp{g}{f})(n) = f(g(n)) = f(x) = y
  83. \]
  84. and thus $\comp{g}{f}$ is !!{surjective}. We have that $\comp{g}{f}$
  85. is an enumeration of~$B$, and so $B$~is !!{enumerable}.}
  86. {
  87. Then either $A = \emptyset$ or there is !!a{bijection}~$g$ whose
  88. range is $A$ and whose domain is either $\Nat$ or an initial
  89. sequence of natural numbers. If $A = \emptyset$, then $B =
  90. \emptyset$ also (otherwise there would be some~$y \in B$ with no $x
  91. \in A$ such that $g(x) = y$). So suppose we have our
  92. !!{bijection}~$g$. Then $\comp{g}{f}$ is !!a{bijection} with
  93. range~$B$ and domain the same as that of~$g$ (i.e., either $\Nat$ or
  94. an initial segment of it), so that $B$ is !!{enumerable}.}
  96. If $B$ is !!{enumerable}, we obtain that $A$ is !!{enumerable} by
  97. repeating the argument with the !!{bijection} $f^{-1}\colon B \to A$
  98. instead of~$f$.
  99. \end{proof}
  101. \begin{prob}
  102. Show that if $\cardeq{A}{C}$ and $\cardeq{B}{D}$, and $A \cap B =
  103. C \cap D = \emptyset$, then $\cardeq{A \cup B}{C \cup D}$.
  104. \end{prob}
  106. \begin{prob}
  107. Show that if $A$ is infinite and !!{enumerable}, then
  108. $\cardeq{A}{\Nat}$.
  109. \end{prob}
  111. \end{document}

content/sets-functions-relations/size-of-sets/introduction.tex

28 lines; SHA-256 e771bd78d2b9819350b17f333524e22ce44a26647916f5b864cb934e380c1fb9. Open the preserved source file.

  1. % Part:sets-functions-relations
  2. % Chapter: size-of-sets
  3. % Section: introduction
  5. \documentclass[../../../include/open-logic-section]{subfiles}
  7. \begin{document}
  9. \olfileid{sfr}{siz}{int}
  11. \olsection{Introduction}
  13. When Georg Cantor developed set theory in the 1870s, one of his aims
  14. was to make palatable the idea of an infinite collection---an actual
  15. infinity, as the medievals would say. A key part of this was his
  16. treatment of the \emph{size} of different sets. If $a$, $b$ and $c$ are
  17. all distinct, then the set $\{a, b, c\}$ is intuitively \emph{larger}
  18. than $\{a, b\}$. But what about infinite sets? Are they all as large
  19. as each other? It turns out that they are not.
  21. The first important idea here is that of an enumeration. We can
  22. list every finite set by listing all its !!{element}s. For some
  23. infinite sets, we can also list all their !!{element}s if we allow the
  24. list itself to be infinite. Such sets are called !!{enumerable}.
  25. Cantor's surprising result, which we will fully understand by the end
  26. of this chapter, was that some infinite sets are not !!{enumerable}.
  28. \end{document}

content/sets-functions-relations/size-of-sets/non-enumerability-alt.tex

162 lines; SHA-256 0c20a2c420fbf4dbd801bb97e37799b3c602ae33ef2b1dc85ff94e24208ca2bb. Open the preserved source file.

  1. % Part:sets-functions-relations
  2. % Chapter: size-of-sets
  3. % Section: non-enumerability-alt
  5. \documentclass[../../../include/open-logic-section]{subfiles}
  7. \begin{document}
  9. \olfileid{sfr}{siz}{nen-alt}
  11. \olsection{\printtoken{S}{nonenumerable} Sets}
  13. \begin{editorial}
  14. This section proves the non-enumerability of $\Bin^\omega$ and
  15. $\Pow{\Nat}$ using the definitions in \olref[enm-alt]{sec}, i.e.,
  16. requiring a bijection with~$\Nat$ instead of a surjection from
  17. $\PosInt$.
  18. \end{editorial}
  20. \begin{explain}
  21. The set $\Nat$ of natural numbers is infinite. It is also trivially
  22. !!{enumerable}. But the remarkable fact is that there are
  23. \emph{!!{nonenumerable}} sets, i.e., sets which are not !!{enumerable}
  24. (see \olref[sfr][siz][enm-alt]{defn:enumerable}).
  26. This might be surprising. After all, to say that $A$ is
  27. !!{nonenumerable} is to say that there is \emph{no} !!{bijection} $f
  28. \colon \Nat \to A$; that is, no function mapping the infinitely many
  29. !!{element}s of~$\Nat$ to~$A$ exhausts all of~$A$. So if $A$ is
  30. !!{nonenumerable}, there are ``more'' !!{element}s of~$A$ than there
  31. are natural numbers.
  33. To prove that a set is !!{nonenumerable}, you have to show that no
  34. appropriate !!{bijection} can exist. The best way to do this is to
  35. show that every attempt to enumerate !!{element}s of~$A$ must leave at
  36. least one !!{element} out; this shows that no function $f\colon \Nat
  37. \to A$ is !!{surjective}. And a general strategy for establishing this
  38. is to use Cantor's \emph{diagonal method}. Given a list of
  39. !!{element}s of $A$, say, $x_1$, $x_2$, \dots, we construct another
  40. !!{element} of~$A$ which, by its construction, cannot possibly be on
  41. that list.
  43. But all of this is best understood by example. So, our first example
  44. is the set~$\Bin^\omega$ of all infinite strings of $0$'s and $1$'s.
  45. (The `$\Bin$' stands for binary, and we can just think of it as the
  46. two-element set
  47. $\{0,1\}$.)\oliflabeldef{sfr:card-arithmetic:card-opps:sec}{\footnote{More
  48. accurately, we should stipulate that $\Bin^\omega$ is the set of all
  49. $\omega$-sequences of $0$'s and $1$s, i.e., the set
  50. $\funfromto{\omega}{\{0,1\}}$. But the meaning of this will only
  51. become clear in \olref[sfr][card-arithmetic][card-opps]{sec}.}{} This
  52. slightly loose formulation should not cause any confusions
  53. for now, however.}
  54. \end{explain}
  56. \begin{thm}
  57. \ollabel{thm:nonenum-bin-omega}
  58. $\Bin^\omega$~is !!{nonenumerable}.
  59. \end{thm}
  61. \begin{proof}
  62. Consider any enumeration of a subset of $\Bin^\omega$. So we have some
  63. list $s_{0}$, $s_{1}$, $s_{2}$, \dots{} where every $s_n$ is an
  64. infinite string of $0$'s and~$1$'s. Let $s_n(m)$ be the $n$th digit of
  65. the $m$th string in this list. So we can now think of our list as an
  66. array, where $s_n(m)$ is placed at the $n$th row and $m$th column:
  67. \[
  68. \begin{array}{c|c|c|c|c|c}
  69. & 0 & 1 & 2 & 3 & \dots \\\hline
  70. 0 & \mathbf{s_{0}(0)} & s_{0}(1) & s_{0}(2) & s_0(3) & \dots \\\hline
  71. 1 & s_{1}(0)& \mathbf{s_{1}(1)} & s_1(2) & s_1(3) & \dots \\\hline
  72. 2 & s_{2}(0)& s_{2}(1) & \mathbf{s_2(2)} & s_2(3) & \dots \\\hline
  73. 3 & s_{3}(0)& s_{3}(1) & s_3(2) & \mathbf{s_3(3)} & \dots \\\hline
  74. \vdots & \vdots & \vdots & \vdots & \vdots & \mathbf{\ddots}
  75. \end{array}
  76. \]
  77. We will now construct an infinite string, $d$, of $0$'s and $1$'s
  78. which is not on this list. We will do this by specifying each of its
  79. entries, i.e., we specify $d(n)$ for all $n \in \Nat$. Intuitively,
  80. we do this by reading down the diagonal of the array above (hence the
  81. name ``diagonal method'') and then changing every $1$ to a $0$ and
  82. every $1$ to a~$0$. More abstractly, we define $d(n)$ to be $0$ or $1$
  83. according to whether the $n$-th !!{element} of the diagonal, $s_n(n)$,
  84. is $1$ or $0$, that is:
  85. \[
  86. d(n) =
  87. \begin{cases}
  88. 1 & \text{if $s_{n}(n) = 0$}\\
  89. 0 & \text{if $s_{n}(n) = 1$}
  90. \end{cases}
  91. \]
  92. Clearly $d \in \Bin^\omega$, since it is an infinite string of $0$'s
  93. and $1$'s. But we have constructed $d$ so that $d(n) \neq s_n(n)$ for
  94. any $n \in \Nat$. That is, $d$ differs from $s_n$ in its $n$th entry.
  95. So $d \neq s_n$ for any $n\in \Nat$. So $d$ cannot be on the list
  96. $s_0$, $s_1$, $s_2$,
  97. \dots
  99. We have shown, given an arbitrary enumeration of some subset of
  100. $\Bin^\omega$, that it will omit some !!{element} of $\Bin^\omega$. So
  101. there is no enumeration of the set $\Bin^\omega$, i.e., $\Bin^\omega$
  102. is !!{nonenumerable}.
  103. \end{proof}
  105. \begin{explain}
  106. This proof method is called ``diagonalization'' because it uses the
  107. diagonal of the array to define~$d$. However, diagonalization need
  108. not involve the presence of an array. Indeed, we can show that some set is
  109. !!{nonenumerable} by using a similar idea, even when no array and no
  110. actual diagonal is involved. The following result illustrates how.
  111. \end{explain}
  113. \begin{thm}
  114. \ollabel{thm:nonenum-pownat}
  115. $\Pow{\Nat}$ is not !!{enumerable}.
  116. \end{thm}
  118. \begin{proof}
  119. We proceed in the same way, by showing that every list of subsets
  120. of~$\Nat$ omits some subset of $\Nat$. So, suppose that we have some
  121. list $N_0, N_1, N_2, \ldots$ of subsets of $\Nat$. We define a set $D$
  122. as follows: $n \in D$ iff $n \notin N_{n}$:
  123. \[
  124. D = \Setabs{n \in \Nat}{n \notin N_n}
  125. \]
  126. Clearly $D\subseteq \Nat$. But $D$ cannot be on the list. After all,
  127. by construction $n \in D$ iff $n\notin N_n$, so that $D \neq N_n$ for
  128. any $n \in \Nat$.
  129. \end{proof}
  131. \begin{explain}
  132. The preceding proof did not mention a diagonal. Still, you can think
  133. of it as involving a diagonal if you picture it this way: Imagine the
  134. sets $N_0$, $N_1$, \dots, written in an array, where we write $N_n$ on
  135. the $n$th row by writing $m$ in the $m$th column iff if $m \in N_n$.
  136. For example, say the first four sets on that list are
  137. $\{0,1,2,\dots\}$, $\{1, 3, 5, \dots\}$, $\{0,1,4\}$, and
  138. $\{2,3,4,\dots\}$; then our array would begin with
  139. \[
  140. \begin{array}{r@{}rrrrrrr}
  141. N_0 = \{ & \mathbf{0}, & 1, & 2, & & & & \dots\}\\
  142. N_1 = \{ & & \mathbf{1}, & & 3, & & 5, & \dots\}\\
  143. N_2 = \{ & 0, & 1, & & & 4\phantom{,} & & \}\\
  144. N_3 = \{ & & & 2, & \mathbf{3}, & 4, & & \dots\}\\
  145. &\vdots & & & & & & \ddots\phantom{\}}
  146. \end{array}
  147. \]
  148. Then $D$ is the set obtained by going down the diagonal, placing $n
  149. \in D$ iff $n$ is \emph{not} on the diagonal. So in the above case, we
  150. would leave out $0$ and $1$, we would include~$2$, we would leave
  151. out~$3$, etc.
  152. \end{explain}
  154. \begin{prob}
  155. Show that the set of all functions $f \colon \Nat \to \Nat$ is
  156. !!{nonenumerable} by an explicit diagonal argument. That is, show that
  157. if $f_1$, $f_2$, \dots, is a list of functions and each $f_i\colon
  158. \Nat \to \Nat$, then there is some $g \colon \Nat \to
  159. \Nat$ not on this list.
  160. \end{prob}
  162. \end{document}

content/sets-functions-relations/size-of-sets/non-enumerability.tex

214 lines; SHA-256 a272a841f8c50bda6589aac40278b9bff7f8a1f5284730c7195423b09ac3ba2e. Open the preserved source file.

  1. % Part:sets-functions-relations
  2. % Chapter: size-of-sets
  3. % Section: non-enumerability
  5. \documentclass[../../../include/open-logic-section]{subfiles}
  7. \begin{document}
  9. \olfileid{sfr}{siz}{nen}
  11. \olsection{\printtoken{S}{nonenumerable} Sets}
  13. \begin{editorial}
  14. This section proves the non-enumerability of $\Bin^\omega$ and
  15. $\Pow{\PosInt}$ using the definition in \olref[enm]{sec}. It is
  16. designed to be a little more elementary and a little more detailed
  17. than the version in \olref[enm-alt]{sec}
  18. \end{editorial}
  20. Some sets, such as the set $\PosInt$ of positive integers, are
  21. infinite. So far we've seen examples of infinite sets which were all
  22. !!{enumerable}. However, there are also infinite sets which do not
  23. have this property. Such sets are called \emph{!!{nonenumerable}}.
  25. First of all, it is perhaps already surprising that there are
  26. !!{nonenumerable} sets. For any !!{enumerable} set~$A$ there is
  27. !!a{surjective} function $f \colon \PosInt \to A$. If a set is
  28. !!{nonenumerable} there is no such function. That is, no function
  29. mapping the infinitely many !!{element}s of~$\PosInt$ to~$A$ can
  30. exhaust all of~$A$. So there are ``more'' !!{element}s of~$A$ than
  31. the infinitely many positive integers.
  33. How would one prove that a set is !!{nonenumerable}? You have to show
  34. that no such surjective function can exist. Equivalently, you have to
  35. show that the elements of~$A$ cannot be enumerated in a one way
  36. infinite list. The best way to do this is to show that every list of
  37. !!{element}s of~$A$ must leave at least one element out; or that no
  38. function $f\colon \PosInt \to A$ can be !!{surjective}. We can do this
  39. using Cantor's \emph{diagonal method}. Given a list of !!{element}s
  40. of~$A$, say, $x_1$, $x_2$, \dots, we construct another element of~$A$
  41. which, by its construction, cannot possibly be on that list.
  43. Our first example is the set~$\Bin^\omega$ of all infinite, non-gappy
  44. sequences of $0$'s and $1$'s.
  46. \begin{thm}
  47. \ollabel{thm:nonenum-bin-omega}
  48. $\Bin^\omega$~is !!{nonenumerable}.
  49. \end{thm}
  51. \begin{proof}
  52. Suppose, by way of contradiction, that $\Bin^\omega$ is
  53. !!{enumerable}, i.e., suppose that there is a list $s_{1}$, $s_{2}$,
  54. $s_{3}$, $s_{4}$, \dots{} of all !!{element}s of~$\Bin^\omega$. Each
  55. of these $s_i$ is itself an infinite sequence of $0$'s and~$1$'s.
  56. Let's call the $j$-th element of the $i$-th sequence in this list
  57. $s_i(j)$. Then the $i$-th sequence~$s_i$ is
  58. \[
  59. s_i(1), s_i(2), s_i(3), \dots
  60. \]
  62. We may arrange this list, and the elements of each sequence $s_i$ in
  63. it, in an array:
  64. \[
  65. \begin{array}{c|c|c|c|c|c}
  66. & 1 & 2 & 3 & 4 & \dots \\\hline
  67. 1 & \mathbf{s_{1}(1)} & s_{1}(2) & s_{1}(3) & s_1(4) & \dots \\\hline
  68. 2 & s_{2}(1)& \mathbf{s_{2}(2)} & s_2(3) & s_2(4) & \dots \\\hline
  69. 3 & s_{3}(1)& s_{3}(2) & \mathbf{s_3(3)} & s_3(4) & \dots \\\hline
  70. 4 & s_{4}(1)& s_{4}(2) & s_4(3) & \mathbf{s_4(4)} & \dots \\\hline
  71. \vdots & \vdots & \vdots & \vdots & \vdots & \mathbf{\ddots}
  72. \end{array}
  73. \]
  74. The labels down the side give the number of the sequence in the list
  75. $s_1$, $s_2$, \dots; the numbers across the top label the !!{element}s
  76. of the individual sequences. For instance, $s_{1}(1)$ is a name for
  77. whatever number, a $0$ or a~$1$, is the first !!{element} in the
  78. sequence $s_{1}$, and so on.
  80. Now we construct an infinite sequence, $\overline{s}$, of $0$'s and
  81. $1$'s which cannot possibly be on this list. The definition of
  82. $\overline{s}$ will depend on the list $s_1$, $s_2$, \dots. Any
  83. infinite list of infinite sequences of $0$'s and $1$'s gives rise to
  84. an infinite sequence~$\overline{s}$ which is guaranteed to not appear
  85. on the list.
  87. To define $\overline{s}$, we specify what all its !!{element}s are,
  88. i.e., we specify $\overline{s}(n)$ for all $n \in \PosInt$. We do this
  89. by reading down the diagonal of the array above (hence the name
  90. ``diagonal method'') and then changing every $1$ to a $0$ and every
  91. $0$ to a~$1$. More abstractly, we define $\overline{s}(n)$ to be $0$
  92. or $1$ according to whether the $n$-th !!{element} of the diagonal,
  93. $s_n(n)$, is $1$ or $0$.
  94. \[
  95. \overline{s}(n) =
  96. \begin{cases}
  97. 1 & \text{if $s_{n}(n) = 0$}\\
  98. 0 & \text{if $s_{n}(n) = 1$}.
  99. \end{cases}
  100. \]
  101. If you like formulas better than definitions by cases, you could also
  102. define $\overline{s}(n) = 1 - s_n(n)$.
  104. Clearly $\overline{s}$ is an infinite sequence of $0$'s and
  105. $1$'s, since it is just the mirror sequence to the sequence of $0$'s
  106. and $1$'s that appear on the diagonal of our array. So $\overline{s}$
  107. is !!a{element} of~$\Bin^\omega$. But it cannot be on the list $s_1$,
  108. $s_2$, \dots{} Why not?
  110. It can't be the first sequence in the list, $s_1$, because it differs from
  111. $s_1$ in the first !!{element}. Whatever $s_1(1)$ is, we defined
  112. $\overline{s}(1)$ to be the opposite. It can't be the second
  113. sequence in the list, because $\overline{s}$ differs from $s_2$ in the second
  114. element: if $s_2(2)$ is $0$, $\overline{s}(2)$ is $1$, and vice
  115. versa. And so on.
  117. More precisely: if $\overline{s}$ were on the list, there would be
  118. some $k$ so that $\overline{s} = s_{k}$. Two sequences are identical
  119. iff they agree at every place, i.e., for any~$n$, $\overline{s}(n) =
  120. s_{k}(n)$. So in particular, taking $n = k$ as a special case,
  121. $\overline{s}(k) = s_{k}(k)$ would have to hold. $s_k(k)$ is either
  122. $0$ or~$1$. If it is $0$ then $\overline{s}(k)$ must be~$1$---that's
  123. how we defined $\overline{s}$. But if $s_k(k) = 1$ then, again because
  124. of the way we defined $\overline{s}$, $\overline{s}(k) = 0$. In either
  125. case $\overline{s}(k) \neq s_{k}(k)$.
  127. We started by assuming that there is a list of !!{element}s of
  128. $\Bin^\omega$, $s_1$, $s_2$, \dots{} From this list we constructed a
  129. sequence~$\overline{s}$ which we proved cannot be on the list. But it
  130. definitely is a sequence of $0$'s and $1$'s if all the $s_i$ are
  131. sequences of $0$'s and $1$'s, i.e., $\overline{s} \in
  132. \Bin^\omega$. This shows in particular that there can be no list of
  133. \emph{all} !!{element}s of~$\Bin^\omega$, since for any such list we
  134. could also construct a sequence~$\overline{s}$ guaranteed to not be on
  135. the list, so the assumption that there is a list of all sequences
  136. in~$\Bin^\omega$ leads to a contradiction.
  137. \end{proof}
  139. \begin{explain}
  140. This proof method is called ``diagonalization'' because it uses the
  141. diagonal of the array to define~$\overline{s}$. Diagonalization need
  142. not involve the presence of an array: we can show that sets are not
  143. !!{enumerable} by using a similar idea even when no array and no
  144. actual diagonal is involved.
  145. \end{explain}
  147. \begin{thm}
  148. \ollabel{thm:nonenum-pownat}
  149. $\Pow{\PosInt}$ is not !!{enumerable}.
  150. \end{thm}
  152. \begin{proof}
  153. We proceed in the same way, by showing that for every list of subsets
  154. of~$\PosInt$ there is a subset of $\PosInt$ which cannot be on the list.
  155. Suppose the following is a given list of subsets of~$\PosInt$:
  156. \[
  157. Z_{1}, Z_{2}, Z_{3}, \dots
  158. \]
  159. We now define a set $\overline{Z}$ such that for any $n \in \PosInt$,
  160. $n \in \overline{Z}$ iff $n \notin Z_{n}$:
  161. \[
  162. \overline{Z} = \Setabs{n \in \PosInt}{n \notin Z_n}
  163. \]
  164. $\overline{Z}$ is clearly a set of positive integers, since by
  165. assumption each~$Z_n$ is, and thus $\overline{Z} \in
  166. \Pow{\PosInt}$. But $\overline{Z}$ cannot be on the list. To show
  167. this, we'll establish that for each $k \in \PosInt$, $\overline{Z} \neq
  168. Z_k$.
  170. So let $k \in \PosInt$ be arbitrary. We've defined $\overline{Z}$ so
  171. that for any $n \in \PosInt$, $n \in \overline{Z}$ iff $n \notin Z_n$.
  172. In particular, taking $n=k$, $k \in \overline{Z}$ iff $k \notin Z_k$.
  173. But this shows that $\overline{Z} \neq Z_k$, since $k$ is !!a{element}
  174. of one but not the other, and so $\overline{Z}$ and $Z_k$ have
  175. different !!{element}s. Since $k$ was arbitrary, $\overline{Z}$ is not
  176. on the list $Z_1$, $Z_2$, \dots
  177. \end{proof}
  179. \begin{explain}
  180. The preceding proof did not mention a diagonal, but you can think of
  181. it as involving a diagonal if you picture it this way: Imagine the
  182. sets $Z_1$, $Z_2$, \dots, written in an array, where each
  183. !!{element}~$j \in Z_i$ is listed in the~$j$-th column. Say the first
  184. four sets on that list are $\{1,2,3,\dots\}$, $\{2, 4, 6, \dots\}$,
  185. $\{1,2,5\}$, and $\{3,4,5,\dots\}$. Then the array would begin with
  186. \[
  187. \begin{array}{r@{}rrrrrrr}
  188. Z_1 = \{ & \mathbf{1}, & 2, & 3, & 4, & 5, & 6, & \dots\}\\
  189. Z_2 = \{ & & \mathbf{2}, & & 4, & & 6, & \dots\}\\
  190. Z_3 = \{ & 1, & 2, & & & 5\phantom{,} & & \}\\
  191. Z_4 = \{ & & & 3, & \mathbf{4}, & 5, & 6, & \dots\}\\
  192. \vdots & & & & & \ddots
  193. \end{array}
  194. \]
  195. Then $\overline{Z}$ is the set obtained by going down the diagonal,
  196. leaving out any numbers that appear along the diagonal and include
  197. those $j$ where the array has a gap in the $j$-th row/column. In the
  198. above case, we would leave out $1$ and $2$, include~$3$, leave
  199. out~$4$, etc.
  200. \end{explain}
  202. \begin{prob}
  203. Show that $\Pow{\Nat}$ is !!{nonenumerable} by a diagonal argument.
  204. \end{prob}
  206. \begin{prob}\label{sfr:siz:nen:prob:f-posint}
  207. Show that the set of functions $f \colon \PosInt \to \PosInt$ is
  208. !!{nonenumerable} by an explicit diagonal argument. That is, show that
  209. if $f_1$, $f_2$, \dots, is a list of functions and each $f_i\colon
  210. \PosInt \to \PosInt$, then there is some $\overline{f}\colon \PosInt \to
  211. \PosInt$ not on this list.
  212. \end{prob}
  214. \end{document}

content/sets-functions-relations/size-of-sets/pairing-alt.tex

114 lines; SHA-256 fd523f5306e1fd0e5c03f4c572d244fb017d1c0be27939f180bc6867a214e425. Open the preserved source file.

  1. % Part:sets-functions-relations
  2. % Chapter: size-of-sets
  3. % Section: pairing-alt
  5. \documentclass[../../../include/open-logic-section]{subfiles}
  7. \begin{document}
  9. \olfileid{sfr}{siz}{pai-alt}
  11. \olsection{An Alternative Pairing Function}
  13. \begin{explain}
  14. There are other enumerations of $\Nat^2$ that make it easier to
  15. figure out what their inverses are. Here is one. Instead of
  16. visualizing the enumeration in an array, start with the list of
  17. positive integers associated with (initially) empty spaces. Imagine
  18. filling these spaces successively with pairs $\tuple{n,m}$ as follows.
  19. Starting with the pairs that have~$0$ in the first place (i.e., pairs
  20. $\tuple{0,m}$), put the first (i.e., $\tuple{0,0}$) in the first empty
  21. place, then skip an empty space, put the second (i.e., $\tuple{0,2}$)
  22. in the next empty place, skip one again, and so forth. The
  23. (incomplete) beginning of our enumeration now looks like this
  24. \[\small
  25. \begin{array}{@{}c c c c c c c c c c c@{}}
  26. \mathbf 1 & \mathbf 2 & \mathbf 3 & \mathbf 4 & \mathbf 5 & \mathbf 6 & \mathbf 7 & \mathbf 8 & \mathbf 9 & \mathbf{10} & \dots \\ \\
  27. \tuple{0,0} & & \tuple{0,1} & & \tuple{0,2} & & \tuple{0,3} & & \tuple{0,4} & & \dots \\
  28. \end{array}
  29. \]
  30. Repeat this with pairs $\tuple{1,m}$ for the place that still remain
  31. empty, again skipping every other empty place:
  32. \[\small
  33. \begin{array}{@{}c c c c c c c c c c c@{}}
  34. \mathbf 1 & \mathbf 2 & \mathbf 3 & \mathbf 4 & \mathbf 5 & \mathbf 6 & \mathbf 7 & \mathbf 8 & \mathbf 9 & \mathbf{10} & \dots \\ \\
  35. \tuple{0,0} & \tuple{1,0} & \tuple{0,1} & & \tuple{0,2} & \tuple{1,1} &
  36. \tuple{0,3} & & \tuple{0,4} & \tuple{1,2} & \dots \\
  37. \end{array}
  38. \]
  39. Enter pairs $\tuple{2,m}$, $\tuple{2,m}$, etc., in the same way. Our
  40. completed enumeration thus starts like this:
  41. \[\small
  42. \begin{array}{@{}cc c c c c c c c c c@{}}
  43. \mathbf 1 & \mathbf 2 & \mathbf 3 & \mathbf 4 & \mathbf 5 & \mathbf 6 & \mathbf 7 & \mathbf 8 & \mathbf 9 & \mathbf{10} & \dots \\ \\
  44. \tuple{0,0} & \tuple{1,0} & \tuple{0,1} & \tuple{2,0} & \tuple{0,2} &
  45. \tuple{1,1} & \tuple{0,3} & \tuple{3,0} & \tuple{0,4} & \tuple{1,2} & \dots \\
  46. \end{array}
  47. \]
  48. If we number the cells in the array above according to this
  49. enumeration, we will not find a neat zig-zag line, but this
  50. arrangement:
  51. \[
  52. \begin{array}{ c | c | c | c | c | c | c | c }
  53. & \mathbf 0 & \mathbf 1 & \mathbf 2 & \mathbf 3 & \mathbf 4 & \mathbf 5 & \dots \\
  54. \hline
  55. \mathbf 0 & 1 & 3 & 5 & 7 & 9 & 11 & \dots \\
  56. \hline
  57. \mathbf 1 & 2 & 6 & 10 & 14 & 18 & \dots & \dots \\
  58. \hline
  59. \mathbf 2 & 4 & 12 & 20 & 28 & \dots & \dots & \dots \\
  60. \hline
  61. \mathbf 3 & 8 & 24 & 40 & \dots & \dots & \dots & \dots \\
  62. \hline
  63. \mathbf 4 & 16 & 48 & \dots & \dots & \dots & \dots & \dots \\
  64. \hline
  65. \mathbf 5 & 32 & \dots & \dots & \dots & \dots & \dots & \dots \\
  66. \hline
  67. \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots\\
  68. \end{array}
  69. \]
  70. We can see that the pairs in row~$0$ are in the odd numbered places of
  71. our enumeration, i.e., pair $\tuple{0,m}$ is in place $2m+1$; pairs in
  72. the second row, $\tuple{1,m}$, are in places whose number is the
  73. double of an odd number, specifically, $2 \cdot (2m+1)$; pairs in the
  74. third row, $\tuple{2,m}$, are in places whose number is four times an
  75. odd number, $4 \cdot (2m+1)$; and so on. The factors of $(2m+1)$ for
  76. each row, $1$, $2$, $4$, $8$, \dots, are exactly the powers of~$2$:
  77. $1= 2^0$, $2 = 2^1$, $4 = 2^2$, $8 = 2^3$, \dots\@ In fact, the
  78. relevant exponent is always the first member of the pair in
  79. question. Thus, for pair $\tuple{n,m}$ the factor is $2^n$. This
  80. gives us the general formula: $2^n \cdot (2m+1)$. However, this is a
  81. mapping of pairs to \emph{positive} integers, i.e., $\tuple{0,0}$ has
  82. position~$1$. If we want to begin at position~$0$ we must subtract~$1$
  83. from the result. This gives us:
  84. \end{explain}
  86. \begin{ex}
  87. The function $h\colon \Nat^2 \to \Nat$ given by
  88. \[
  89. h(n,m) = 2^n (2m+1) - 1
  90. \]
  91. is a pairing function for the set of pairs of natural numbers~$\Nat^2$.
  92. \end{ex}
  94. \begin{explain}
  95. Accordingly, in our second enumeration of $\Nat^2$, the pair
  96. $\tuple{0,0}$ has code $h(0,0) = 2^0(2\cdot 0+1) - 1 = 0$;
  97. $\tuple{1,2}$ has code $2^{1} \cdot (2 \cdot 2 + 1) - 1 = 2
  98. \cdot 5 - 1 = 9$; $\tuple{2,6}$ has code $2^{2} \cdot (2
  99. \cdot 6 + 1) - 1 = 51$.
  100. \end{explain}
  102. Sometimes it is enough to encode pairs of natural numbers~$\Nat^2$
  103. without requiring that the encoding is surjective. Such encodings have
  104. inverses that are only partial functions.
  106. \begin{ex}
  107. The function $j\colon \Nat^2 \to \Nat^+$ given by
  108. \[
  109. j(n,m) = 2^n3^m
  110. \]
  111. is !!a{injective} function $\Nat^2 \to \Nat$.
  112. \end{ex}
  114. \end{document}

content/sets-functions-relations/size-of-sets/pairing.tex

115 lines; SHA-256 345a39184e28af727e378d5b5883b5e7d2e1c27cd729329376d19426ddaed484. Open the preserved source file.

  1. % Part:sets-functions-relations
  2. % Chapter: size-of-sets
  3. % Section: pairing
  5. \documentclass[../../../include/open-logic-section]{subfiles}
  7. \begin{document}
  9. \olfileid{sfr}{siz}{pai}
  10. \olsection{Pairing Functions and Codes}
  12. \begin{explain}
  13. Cantor's zig-zag method makes the enumerability of $\Nat^n$ visually
  14. evident. But let us focus on our array depicting $\Nat^2$. Following
  15. the zig-zag line in the array and counting the places, we can check
  16. that $\tuple{1,2}$ is associated with the number~$7$. However, it would
  17. be nice if we could compute this more directly. That is, it would be
  18. nice to have to hand the \emph{inverse} of the zig-zag enumeration,
  19. $g\colon \Nat^2 \to \Nat$, such that
  20. \[
  21. g(\tuple{0,0}) = 0, \;
  22. g(\tuple{0,1}) = 1, \;
  23. g(\tuple{1,0}) = 2, \; \dots,
  24. g(\tuple{1,2}) = 7, \; \dots
  25. \]
  26. This would enable us to calculate exactly where $\tuple{n, m}$ will occur
  27. in our enumeration.
  29. In fact, we can define $g$ directly by making two observations. First:
  30. if the $n$th row and $m$th column contains value~$v$, then the
  31. $(n+1)$st row and $(m-1)$st column contains value $v + 1$. Second: the
  32. first row of our enumeration consists of the triangular numbers,
  33. starting with $0$, $1$, $3$, $6$, etc. The $k$th triangular number is
  34. the sum of the natural numbers $< k$, which can be computed as
  35. $k(k+1)/2$. Putting these two observations together, consider this
  36. function:
  37. \[
  38. g(n,m) = \frac{(n+m+1)(n+m)}{2} + n
  39. \]
  40. We often just write $g(n, m)$ rather that $g(\tuple{n, m})$, since it
  41. is easier on the eyes. This tells you first to determine the
  42. $(n+m)^\text{th}$ triangle number, and then add $n$ to it. And
  43. it populates the array in exactly the way we would like. So in
  44. particular, the pair $\tuple{1, 2}$ is sent to $\frac{4 \times 3}{2} +
  45. 1 = 7$.
  47. This function $g$ is the \emph{inverse} of an enumeration of a set of
  48. pairs. Such functions are called \emph{pairing functions}.
  49. \end{explain}
  51. \begin{defn}[Pairing function]
  52. A function $f\colon A \times B \to \Nat$ is an arithmetical
  53. \emph{pairing function} if $f$ is injective. We also say that $f$
  54. \emph{encodes} $A \times B$, and that $f(x,y)$ is the
  55. \emph{code} for $\tuple{x,y}$.
  56. \end{defn}
  58. \begin{explain}
  59. We can use pairing functions to encode, e.g., pairs of natural numbers;
  60. or, in other words, we can represent each \emph{pair} of elements
  61. using a \emph{single} number. Using the inverse of the pairing
  62. function, we can \emph{decode} the number, i.e., find out which
  63. pair it represents.
  64. \end{explain}
  66. \begin{prob}
  67. Give an enumeration of the set of all non-negative rational numbers.
  68. \end{prob}
  70. \begin{prob}
  71. Show that $\Rat$ is !!{enumerable}. Recall that any rational number
  72. can be written as a fraction $z/m$ with $z \in \Int$, $m \in \Nat^+$.
  73. \end{prob}
  75. \begin{prob}
  76. Define an enumeration of $\Bin^*$.
  77. \end{prob}
  79. \begin{prob}
  80. Recall from your introductory logic course that each possible truth
  81. table expresses a truth function. In other words, the truth functions
  82. are all functions from $\Bin^k \to \Bin$ for some~$k$. Prove that the
  83. set of all truth functions is enumerable.
  84. \end{prob}
  86. \begin{prob}
  87. Show that the set of all finite subsets of an arbitrary infinite
  88. !!{enumerable} set is !!{enumerable}.
  89. \end{prob}
  91. \begin{prob}
  92. A subset of $\Nat$ is said to be \emph{cofinite} iff it is the
  93. complement of a finite set $\Nat$; that is, $A \subseteq \Nat$ is
  94. cofinite iff $\Nat\setminus A$ is finite. Let $I$ be the set whose
  95. !!{element}s are exactly the finite and cofinite subsets of $\Nat$.
  96. Show that $I$ is !!{enumerable}.
  97. \end{prob}
  99. \begin{prob}
  100. Show that the !!{enumerable} union of !!{enumerable} sets is
  101. !!{enumerable}. That is, whenever $A_1$, $A_2$, \dots{} are sets, and
  102. each $A_i$ is !!{enumerable}, then the union $\bigcup_{i=1}^\infty
  103. A_i$ of all of them is also !!{enumerable}. [NB: this is hard!]
  104. \end{prob}
  106. \begin{prob}
  107. Let $f \colon A \times B \to \Nat$ be an arbitrary pairing function.
  108. Show that the inverse of $f$ is an enumeration of $A \times B$.
  109. \end{prob}
  111. \begin{prob}
  112. Specify a function that encodes $\Nat^3$.
  113. \end{prob}
  115. \end{document}

content/sets-functions-relations/size-of-sets/reduction-alt.tex

140 lines; SHA-256 46381b85c0e9a1ab48cb9301518de91f073d649c3b1119325c1409f5a6c1d663. Open the preserved source file.

  1. % Part:sets-functions-relations
  2. % Chapter: size-of-sets
  3. % Section: reduction-alt
  5. \documentclass[../../../include/open-logic-section]{subfiles}
  7. \begin{document}
  9. \olfileid{sfr}{siz}{red-alt}
  11. \olsection{Reduction}
  13. \begin{editorial}
  14. This section proves non-enumerability by reduction, matching the
  15. results in \olref[nen-alt]{sec}. An alternative, slightly more
  16. elaborate version matching the results in \olref[nen]{sec} is
  17. provided in \olref[red]{sec}.
  18. \end{editorial}
  20. We proved that $\Bin^\omega$ is !!{nonenumerable} by a diagonalization
  21. argument. We used a similar diagonalization argument to show that
  22. $\Pow{\Nat}$ is !!{nonenumerable}. But here's another way we can prove
  23. that $\Pow{\Nat}$ is !!{nonenumerable}: show that \emph{if
  24. $\Pow{\Nat}$ is !!{enumerable} then $\Bin^\omega$ is also
  25. !!{enumerable}}. Since we know $\Bin^\omega$ is !!{nonenumerable}, it
  26. will follow that $\Pow{\Nat}$ is too.
  28. This is called \emph{reducing} one problem to another. In this case,
  29. we reduce the problem of enumerating $\Bin^\omega$ to the problem of
  30. enumerating $\Pow{\Nat}$. A solution to the latter---an enumeration
  31. of $\Pow{\Nat}$---would yield a solution to the former---an
  32. enumeration of $\Bin^\omega$.
  34. To reduce the problem of enumerating a set~$B$ to that of enumerating
  35. a set~$A$, we provide a way of turning an enumeration of~$A$ into an
  36. enumeration of~$B$. The easiest way to do that is to define
  37. !!a{surjection} $f\colon A \to B$. If $x_1$, $x_2$, \dots{}
  38. enumerates~$A$, then $f(x_1)$, $f(x_2)$, \dots{} would enumerate~$B$.
  39. In our case, we are looking for !!a{surjection} $f\colon \Pow{\Nat}
  40. \to \Bin^\omega$.
  42. \begin{prob}
  43. Show that if there is an !!{injective} function $g\colon B \to A$, and
  44. $B$~is !!{nonenumerable}, then so is~$A$. Do this by showing how you
  45. can use~$g$ to turn an enumeration of~$A$ into one of~$B$.
  46. \end{prob}
  48. \begin{proof}[Proof of {\olref[nen-alt]{thm:nonenum-pownat}} by reduction]
  49. For a reduction, suppose that $\Pow{\Nat}$ is !!{enumerable}, and thus that
  50. there is an enumeration of it, $N_{1}$, $N_{2}$, $N_{3}$, \dots
  52. Define the function $f \colon \Pow{\Nat} \to \Bin^\omega$ by letting
  53. $f(N)$ be the string $s_{k}$ such that $s_{k}(n) = 1$ iff $n \in N$,
  54. and $s_k(n) = 0$ otherwise.
  56. This clearly defines a function, since whenever $N \subseteq \Nat$,
  57. any $n \in \Nat$ either is !!a{element} of $N$ or isn't. For
  58. instance, the set $2\Nat = \Setabs{2n}{n \in \Nat} = \{0,2, 4, 6,
  59. \dots\}$ of even naturals gets mapped to the string $1010101\dots$;
  60. $\emptyset$ gets mapped to $0000\dots$; $\Nat$ gets mapped to
  61. $1111\dots$.
  63. It is also !!{surjective}: every string of $0$s and $1$s corresponds
  64. to some set of natural numbers, namely the one which has as its
  65. members those natural numbers corresponding to the places where the string
  66. contains a~$1$s. More precisely, if $s \in \Bin^\omega$, then define $N
  67. \subseteq \Nat$ by:
  68. \[
  69. N = \Setabs{n \in \Nat}{s(n) = 1}
  70. \]
  71. Then $f(N) = s$, as can be verified by consulting the definition
  72. of~$f$.
  74. Now consider the list
  75. \[
  76. f(N_1), f(N_2), f(N_3), \dots
  77. \]
  78. Since $f$ is !!{surjective}, every member of $\Bin^\omega$ must
  79. appear as a value of~$f$ for some argument, and so must appear on the
  80. list. This list must therefore enumerate all of~$\Bin^\omega$.
  82. So if $\Pow{\Nat}$ were !!{enumerable}, $\Bin^\omega$ would be
  83. !!{enumerable}. But $\Bin^\omega$ is !!{nonenumerable}
  84. (\olref[nen-alt]{thm:nonenum-bin-omega}). Hence $\Pow{\Nat}$ is
  85. !!{nonenumerable}.
  86. \end{proof}
  88. %\begin{explain}
  89. %It is easy to be confused about the direction the reduction goes in.
  90. %For instance, !!a{surjective} function $g \colon \Bin^\omega \to X$
  91. %does \emph{not} establish that $X$ is !!{nonenumerable}. (Consider $g
  92. %\colon \Bin^\omega \to \Bin$ defined by $g(s) = s(1)$, the function
  93. %that maps a sequence of $0$'s and $1$'s to its first !!{element}. It
  94. %is surjective, because some sequences start with $0$ and some start
  95. %with $1$. But $\Bin$ is finite.) Note also that the function $f$ must
  96. %be surjective, or otherwise the argument does not go through:
  97. %$f(x_1)$, $f(x_2)$, \dots{} would then not be guaranteed to include
  98. %all the !!{element}s of~$Y$. For instance, $h\colon \Nat \to
  99. %\Bin^\omega$ defined by
  100. %\[
  101. %h(n) = \underbrace{000\dots0}_{\text{$n$ $0$'s}}
  102. %\]
  103. %is a function, but $\Nat$ is !!{enumerable}.
  104. %\end{explain}
  106. \begin{prob}\label{sfr:siz:red:prob:nat-nat}
  107. Show that the set~$X$ of all functions $f\colon \Nat \to \Nat$ is
  108. !!{nonenumerable} by a reduction argument (Hint: give a surjective
  109. function from $X$ to~$\Bin^\omega$.)
  110. \end{prob}
  112. \begin{prob}
  113. Show that the set of all \emph{sets of} pairs of natural numbers,
  114. i.e., $\Pow{\Nat \times \Nat}$, is !!{nonenumerable} by a reduction
  115. argument.
  116. \end{prob}
  118. \begin{prob}
  119. Show that $\Nat^\omega$, the set of infinite sequences of natural
  120. numbers, is !!{nonenumerable} by a reduction argument.
  121. \end{prob}
  123. %\begin{prob}
  124. %Let $P$ be the set of functions from $\Nat$ to the set $\{0\}$, and let $Q$ be the set of \emph{partial}
  125. %functions from the set of positive integers to the set $\{0\}$. Show
  126. %that $P$~is !!{enumerable} and $Q$~is not. (Hint: reduce the problem
  127. %of enumerating $\Bin^\omega$ to enumerating~$Q$).
  128. %\end{prob}
  130. \begin{prob}
  131. Let $S$ be the set of all !!{surjection}s from $\Nat$ to the set
  132. $\{0,1\}$, i.e., $S$ consists of all !!{surjection}s~$f \colon \Nat
  133. \to \Bin$. Show that $S$ is !!{nonenumerable}.
  134. \end{prob}
  136. \begin{prob}
  137. Show that the set~$\Real$ of all real numbers is !!{nonenumerable}.
  138. \end{prob}
  140. \end{document}

content/sets-functions-relations/size-of-sets/reduction.tex

138 lines; SHA-256 33f0cbb35c8c1fa3ff0e4f44fa626fdc298d1c4612aeaafb41bcb920e5d18ac8. Open the preserved source file.

  1. % Part:sets-functions-relations
  2. % Chapter: sets
  3. % Section: reduction
  5. \documentclass[../../../include/open-logic-section]{subfiles}
  7. \begin{document}
  9. \olfileid{sfr}{siz}{red}
  11. \olsection{Reduction}
  13. \begin{editorial}
  14. This section proves non-enumerability by reduction, matching the
  15. results in \olref[nen]{sec}. An alternative, slightly more condensed
  16. version matching the results in \olref[nen-alt]{sec} is provided in
  17. \olref[red-alt]{sec}.
  18. \end{editorial}
  20. We showed $\Pow{\PosInt}$ to be !!{nonenumerable} by a diagonalization
  21. argument. We already had a proof that $\Bin^\omega$, the set of all
  22. infinite sequences of $0$s and $1$s, is !!{nonenumerable}. Here's
  23. another way we can prove that $\Pow{\PosInt}$ is !!{nonenumerable}:
  24. Show that \emph{if $\Pow{\PosInt}$ is !!{enumerable} then $\Bin^\omega$
  25. is also !!{enumerable}}. Since we know $\Bin^\omega$ is not
  26. !!{enumerable}, $\Pow{\PosInt}$ can't be either. This is called
  27. \emph{reducing} one problem to another---in this case, we reduce the
  28. problem of enumerating $\Bin^\omega$ to the problem of enumerating
  29. $\Pow{\PosInt}$. A solution to the latter---an enumeration of
  30. $\Pow{\PosInt}$---would yield a solution to the former---an enumeration
  31. of $\Bin^\omega$.
  33. How do we reduce the problem of enumerating a set~$B$ to that of
  34. enumerating a set~$A$? We provide a way of turning an enumeration
  35. of~$A$ into an enumeration of~$B$. The easiest way to do that is to
  36. define !!a{surjective} function $f\colon A \to B$. If $x_1$, $x_2$,
  37. \dots{} enumerates~$A$, then $f(x_1)$, $f(x_2)$, \dots{} would
  38. enumerate~$B$. In our case, we are looking for a surjective
  39. function $f\colon \Pow{\PosInt} \to \Bin^\omega$.
  41. \begin{prob}
  42. Show that if there is an !!{injective} function $g\colon B \to A$, and
  43. $B$~is !!{nonenumerable}, then so is~$A$. Do this by showing how you
  44. can use~$g$ to turn an enumeration of~$A$ into one of~$B$.
  45. \end{prob}
  47. \begin{proof}[Proof of {\olref[nen]{thm:nonenum-pownat}} by reduction]
  48. Suppose that $\Pow{\PosInt}$ were !!{enumerable}, and thus that
  49. there is an enumeration of it, $Z_{1}$, $Z_{2}$, $Z_{3}$, \dots
  51. Define the function $f \colon \Pow{\PosInt} \to \Bin^\omega$ by letting
  52. $f(Z)$ be the sequence $s_{k}$ such that $s_{k}(n) = 1$ iff $n \in Z$,
  53. and $s_k(n) = 0$ otherwise. This clearly defines a function, since
  54. whenever $Z \subseteq \PosInt$, any $n \in \PosInt$ either is
  55. !!a{element} of $Z$ or isn't. For instance, the set $2\PosInt = \{2,
  56. 4, 6, \dots\}$ of positive even numbers gets mapped to the sequence
  57. $010101\dots$, the empty set gets mapped to $0000\dots$ and the set
  58. $\PosInt$ itself to $1111\dots$.
  60. It also is !!{surjective}: Every sequence of $0$s and $1$s corresponds
  61. to some set of positive integers, namely the one which has as its
  62. members those integers corresponding to the places where the sequence
  63. has~$1$s. More precisely, suppose $s \in \Bin^\omega$. Define $Z
  64. \subseteq \PosInt$ by:
  65. \[
  66. Z = \Setabs{n \in \PosInt}{s(n) = 1}
  67. \]
  68. Then $f(Z) = s$, as can be verified by consulting the definition
  69. of~$f$.
  71. Now consider the list
  72. \[
  73. f(Z_1), f(Z_2), f(Z_3), \dots
  74. \]
  75. Since $f$ is !!{surjective}, every member of $\Bin^\omega$ must
  76. appear as a value of~$f$ for some argument, and so must appear on the
  77. list. This list must therefore enumerate all of~$\Bin^\omega$.
  79. So if $\Pow{\PosInt}$ were !!{enumerable}, $\Bin^\omega$ would be
  80. !!{enumerable}. But $\Bin^\omega$ is !!{nonenumerable}
  81. (\olref[nen]{thm:nonenum-bin-omega}). Hence $\Pow{\PosInt}$ is
  82. !!{nonenumerable}.
  83. \end{proof}
  85. \begin{explain}
  86. It is easy to be confused about the direction the reduction goes in.
  87. For instance, !!a{surjective} function $g \colon \Bin^\omega \to B$
  88. does \emph{not} establish that $B$ is !!{nonenumerable}. (Consider $g
  89. \colon \Bin^\omega \to \Bin$ defined by $g(s) = s(1)$, the function
  90. that maps a sequence of $0$'s and $1$'s to its first !!{element}. It
  91. is !!{surjective}, because some sequences start with $0$ and some start
  92. with $1$. But $\Bin$ is finite.) Note also that the function~$f$ must
  93. be !!{surjective}, or otherwise the argument does not go through:
  94. $f(x_1)$, $f(x_2)$, \dots{} would then not be guaranteed to include
  95. all the !!{element}s of~$B$. For instance,
  96. \[
  97. h(n) = \underbrace{000\dots0}_{\text{$n$ $0$'s}}
  98. \]
  99. defines a function $h\colon \PosInt \to
  100. \Bin^\omega$, but $\PosInt$ is !!{enumerable}.
  101. \end{explain}
  103. \begin{prob}
  104. Show that the set of all \emph{sets of} pairs of positive integers is
  105. !!{nonenumerable} by a reduction argument.
  106. \end{prob}
  108. \begin{prob}\label{sfr:siz:red:prob:nat-nat}
  109. Show that the set~$X$ of all functions $f\colon \Nat \to \Nat$ is
  110. !!{nonenumerable} by a reduction argument (Hint: give a surjective
  111. function from $X$ to~$\Bin^\omega$.)
  112. \end{prob}
  114. \begin{prob}
  115. Show that $\Nat^\omega$, the set of infinite sequences of
  116. natural numbers, is !!{nonenumerable} by a reduction argument.
  117. \end{prob}
  119. \begin{prob}
  120. Let $P$ be the set of functions from the set of positive
  121. integers to the set $\{0\}$, and let $Q$ be the set of \emph{partial}
  122. functions from the set of positive integers to the set $\{0\}$. Show
  123. that $P$~is !!{enumerable} and $Q$~is not. (Hint: reduce the problem
  124. of enumerating $\Bin^\omega$ to enumerating~$Q$).
  125. \end{prob}
  127. \begin{prob}
  128. Let $S$ be the set of all !!{surjective} functions from the set of
  129. positive integers to the set \{0,1\}, i.e., $S$ consists of all
  130. !!{surjective}~$f\colon \PosInt \to \Bin$. Show that $S$ is
  131. !!{nonenumerable}.
  132. \end{prob}
  134. \begin{prob}
  135. Show that the set~$\Real$ of all real numbers is !!{nonenumerable}.
  136. \end{prob}
  138. \end{document}

content/sets-functions-relations/size-of-sets/schroder-bernstein.tex

53 lines; SHA-256 7b99b3e032e24e425383734ce80ad9a5cc37d018c09205e02f37b927d50bb56a. Open the preserved source file.

  1. % Part:sets-functions-relations
  2. % Chapter: sets
  3. % Section: schroder-bernstein
  5. \documentclass[../../../include/open-logic-section]{subfiles}
  7. \begin{document}
  9. \olfileid{sfr}{siz}{sb}
  11. \olsection{The Notion of Size, and Schr\"oder-Bernstein}
  13. \begin{explain}
  14. Here is an intuitive thought: if $A$ is no larger than $B$ and $B$ is
  15. no larger than $A$, then $A$ and $B$ are equinumerous. To be honest,
  16. if this thought were \emph{wrong}, then we could scarcely justify the
  17. thought that our defined notion of equinumerosity has anything to do
  18. with comparisons of ``sizes'' between sets!{} Fortunately, though,
  19. the intuitive thought is correct. This is justified by the
  20. Schr\"oder-Bernstein Theorem.
  21. \end{explain}
  23. \begin{thm}[Schr\"oder-Bernstein]
  24. \ollabel{thm:schroder-bernstein}
  25. If $\cardle{A}{B}$ and $\cardle{B}{A}$,
  26. then $\cardeq{A}{B}$.
  27. \end{thm}
  29. \begin{explain}
  30. In other words, if there is !!a{injection} from $A$ to~$B$, and
  31. !!a{injection} from $B$ to~$A$, then there is !!a{bijection} from $A$
  32. to~$B$.
  34. This result, however, is really rather \emph{difficult} to prove.
  35. Indeed, although Cantor stated the result, others proved
  36. it.\footnote{For more on the history, see e.g.,
  37. \citet[pp.~165--6]{Potter2004}.}
  38. \oliflabeldef{sfr:cardinals:card-sb:sec}{We will only be in
  39. a position to \emph{prove} Schr\"oder-Bernstein in
  40. \olref[sfr][cardinals][card-sb]{sec}.}{}%
  41. For now, you can (and must)
  42. take it on trust.
  44. Fortunately, Schr\"oder-Bernstein is \emph{correct}, and it
  45. vindicates our thinking of the relations we defined, i.e.,
  46. $\cardeq{A}{B}$ and $\cardle{A}{B}$, as having something to do with
  47. ``size''. Moreover, Schr\"oder-Bernstein is very \emph{useful}. It
  48. can be difficult to think of !!a{bijection} between two equinumerous
  49. sets. The Schr\"oder-Bernstein Theorem allows us to break the comparison
  50. down into cases so we only have to think of !!a{injection} from the
  51. first to the second, and vice-versa.
  52. \end{explain}
  53. \end{document}

content/sets-functions-relations/size-of-sets/size-of-sets-complete.tex

55 lines; SHA-256 d2b1a2f68e99efc2e5fd9f15316db26d7f898bd61135213309f61d28a6f00a60. Open the preserved source file.

  1. % Part: sets-functions-relations
  2. % Chapter: size-of-sets-complete
  4. \documentclass[../../../include/open-logic-chapter]{subfiles}
  6. \begin{document}
  8. \olchapter{sfr}{siz}{The Size of Sets}
  10. \begin{editorial}
  11. This chapter discusses enumerations, countability and uncountability.
  12. Several sections come in two versions: a more elementary one, that
  13. takes enumerations to be lists, or surjections from $\PosInt$; and a
  14. more abstract one that defines enumerations as bijections with $\Nat$.
  15. \end{editorial}
  17. \olimport{introduction}
  19. \olimport{enumerability}
  21. \olimport{zig-zag}
  23. \olimport{pairing}
  25. \olimport{pairing-alt}
  27. \olimport{non-enumerability}
  29. \olimport{reduction}
  31. \olimport{equinumerous-sets}
  33. \olimport{comparing-size}
  35. \olimport{schroder-bernstein}
  37. \begin{editorial}
  38. The following \olref[sfr][siz][enm-alt]{sec},
  39. \olref[sfr][siz][nen-alt]{sec}, \olref[sfr][siz][red-alt]{sec} are
  40. alternative versions of \olref[sfr][siz][enm]{sec},
  41. \olref[sfr][siz][nen]{sec}, \olref[sfr][siz][red]{sec} due to Tim
  42. Button for use in his Open Set Theory text. They are slightly more
  43. advanced and use a difference definition of enumerability more
  44. suitable in a set theory context (i.e., bijection with $\Nat$ or an
  45. initial segment, rather than being listable or being the range of a
  46. surjective function from $\PosInt$).
  47. \end{editorial}
  49. \olimport{enumerability-alt}
  50. \olimport{non-enumerability-alt}
  51. \olimport{reduction-alt}
  53. \OLEndChapterHook
  55. \end{document}

content/sets-functions-relations/size-of-sets/zig-zag.tex

126 lines; SHA-256 18bf058d52e22b9dbc7a08af314b58c81f35dd4009c0ccf726a0d00aec391dee. Open the preserved source file.

  1. % Part:sets-functions-relations
  2. % Chapter: size-of-sets
  3. % Section: zig-zag
  5. \documentclass[../../../include/open-logic-section]{subfiles}
  7. \begin{document}
  9. \olfileid{sfr}{siz}{zigzag}
  11. \olsection{Cantor's Zig-Zag Method}
  13. \begin{explain}
  14. We've already considered some ``easy'' enumerations. Now we will
  15. consider something a bit harder. Consider the set of pairs of natural
  16. numbers\oliflabeldef{sfr:set:pai:sec}{, which we defined in
  17. \olref[set][pai]{sec} thus:}{defined by:}
  18. \[
  19. \Nat \times \Nat = \Setabs{\tuple{n,m}}{n,m \in \Nat}
  20. \]
  21. We can organize these ordered pairs into an \emph{array}, like so:
  22. \[
  23. \begin{array}{ c | c | c | c | c | c}
  24. & \mathbf 0 & \mathbf 1 & \mathbf 2 & \mathbf 3 & \dots \\
  25. \hline
  26. \mathbf 0 & \tuple{0,0} & \tuple{0,1} & \tuple{0,2} & \tuple{0,3} & \dots \\
  27. \hline
  28. \mathbf 1 & \tuple{1,0} & \tuple{1,1} & \tuple{1,2} & \tuple{1,3} & \dots \\
  29. \hline
  30. \mathbf 2 & \tuple{2,0} & \tuple{2,1} & \tuple{2,2} & \tuple{2,3} & \dots \\
  31. \hline
  32. \mathbf 3 & \tuple{3,0} & \tuple{3,1} & \tuple{3,2} & \tuple{3,3} & \dots \\
  33. \hline
  34. \vdots & \vdots & \vdots & \vdots & \vdots & \ddots\\
  35. \end{array}
  36. \]
  37. Clearly, every ordered pair in $\Nat \times \Nat$ will appear
  38. exactly once in the array. In particular, $\tuple{n,m}$ will appear in
  39. the $n$th row and $m$th column. But how do we organize the elements of
  40. such an array into a ``one-dimensional'' list? The pattern in the array below
  41. demonstrates one way to do this (although of course there are many other options):
  42. \[
  43. \begin{array}{ c | c | c | c | c | c | c}
  44. & \mathbf 0 & \mathbf 1 & \mathbf 2 & \mathbf 3 & \mathbf 4 &\dots \\
  45. \hline
  46. \mathbf 0 & 0 & 1& 3 & 6& 10 &\ldots \\
  47. \hline
  48. \mathbf 1 &2 & 4& 7 & 11 & \dots &\ldots \\
  49. \hline
  50. \mathbf 2 & 5 & 8 & 12 & \ldots & \dots&\ldots \\
  51. \hline
  52. \mathbf 3 & 9 & 13 & \ldots & \ldots & \dots & \ldots \\
  53. \hline
  54. \mathbf 4 & 14 & \ldots & \ldots & \ldots & \dots & \ldots \\
  55. \hline
  56. \vdots & \vdots & \vdots & \vdots & \vdots&\ldots & \ddots\\
  57. \end{array}
  58. \]\noindent
  59. This pattern is called \emph{Cantor's zig-zag method}. It enumerates
  60. $\Nat \times \Nat$ as follows:
  61. \[
  62. \tuple{0,0}, \tuple{0,1}, \tuple{1,0}, \tuple{0,2}, \tuple{1,1},
  63. \tuple{2,0}, \tuple{0,3}, \tuple{1,2}, \tuple{2,1}, \tuple{3,0}, \dots
  64. \]
  65. And this establishes the following:
  66. \end{explain}
  68. \begin{prop}\ollabel{natsquaredenumerable}
  69. $\Nat \times \Nat$ is !!{enumerable}.
  70. \end{prop}
  72. \begin{proof}
  73. Let $f \colon \Nat \to \Nat\times\Nat$ take each $k \in \Nat$ to the
  74. tuple $\tuple{n,m} \in \Nat \times \Nat$ such that $k$ is the value of
  75. the $n$th row and $m$th column in Cantor's zig-zag array.
  76. \end{proof}
  78. \begin{explain}
  79. This technique also generalises rather nicely. For example, we can use
  80. it to enumerate the set of ordered triples of natural numbers, i.e.:
  81. \[
  82. \Nat \times \Nat \times \Nat = \Setabs{\tuple{n,m,k}}{n,m,k \in \Nat}
  83. \]
  84. We think of $\Nat \times \Nat \times \Nat$ as the Cartesian
  85. product of $\Nat \times \Nat$ with $\Nat$, that is,
  86. \[
  87. \Nat^3 = (\Nat \times \Nat) \times \Nat =
  88. \Setabs{\tuple{\tuple{n,m},k}}{n, m, k
  89. \in \Nat }
  90. \]
  91. and thus we can enumerate $\Nat^3$ with an array by labelling one
  92. axis with the enumeration of $\Nat$, and the other axis with the
  93. enumeration of $\Nat^2$:
  94. \[
  95. \begin{array}{ c | c | c | c | c | c}
  96. & \mathbf 0 & \mathbf 1 & \mathbf 2 & \mathbf 3 & \dots \\
  97. \hline
  98. \mathbf{\tuple{0,0}} & \tuple{0,0,0} & \tuple{0,0,1} & \tuple{0,0,2} & \tuple{0,0,3} & \dots \\
  99. \hline
  100. \mathbf{\tuple{0,1}} & \tuple{0,1,0} & \tuple{0,1,1} & \tuple{0,1,2} & \tuple{0,1,3} & \dots \\
  101. \hline
  102. \mathbf{\tuple{1,0}} & \tuple{1,0,0} & \tuple{1,0,1} & \tuple{1,0,2} & \tuple{1,0,3} & \dots \\
  103. \hline
  104. \mathbf{\tuple{0,2}} & \tuple{0,2,0} & \tuple{0,2,1} & \tuple{0,2,2} & \tuple{0,2,3} & \dots\\
  105. \hline
  106. \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\
  107. \end{array}
  108. \]
  109. Thus, by using a method like Cantor's zig-zag method, we may similarly
  110. obtain an enumeration of~$\Nat^3$. And we can keep going, obtaining
  111. enumerations of $\Nat^n$ for any natural number $n$. So, we have:
  112. \end{explain}
  114. \begin{prop}
  115. $\Nat^n$ is !!{enumerable}, for every $n \in \Nat$.
  116. \end{prop}
  118. \begin{prob}\label{sfr:siz:zigzag:prob:posint-n}
  119. Show that $(\PosInt)^n$ is !!{enumerable}, for every $n \in \Nat$.
  120. \end{prob}
  122. \begin{prob}\label{sfr:siz:zigzag:prob:posint-star}
  123. Show that $(\PosInt)^*$ is !!{enumerable}. You may assume \cref{sfr:siz:zigzag:prob:posint-n}.
  124. \end{prob}
  126. \end{document}