The Open Logic Text — accessible offline edition

Sets — Source and provenance

Sets

Source and provenance

These are all seven files in the frozen Sets source boundary, shown line by line and copied byte-for-byte for download. Formula records additionally retain exact line, column, byte-offset, delimiter, TeX, expression binding, speech, meaning, and native MathML data in the packaged authority ledgers.

content/sets-functions-relations/sets/sets.tex

24 lines; SHA-256 eea34d38bb52811468a0025d348457a0f4d3f44aae4b7cabb28551d6328e2785. Open the preserved source file.

  1. % Part: sets-functions-relations
  2. % Chapter: sets
  4. \documentclass[../../../include/open-logic-chapter]{subfiles}
  6. \begin{document}
  8. \olchapter{sfr}{set}{Sets}
  10. \olimport{basics}
  12. \olimport{subsets}
  14. \olimport{important-sets}
  16. \olimport{unions-and-intersections}
  18. \olimport{pairs-and-products}
  20. \olimport{russells-paradox}
  22. \OLEndChapterHook
  24. \end{document}

content/sets-functions-relations/sets/basics.tex

103 lines; SHA-256 8bc9151af0985e6e20c374aa38cddd1add7a8dffbabccc94b89f324f62c40f8c. Open the preserved source file.

  1. % Part: sets-functions-relations
  2. % Chapter: sets
  3. % Section: basics
  5. \documentclass[../../../include/open-logic-section]{subfiles}
  7. \begin{document}
  9. \olfileid{sfr}{set}{bas}
  10. \olsection{Extensionality}
  12. A \emph{set} is a collection of objects, considered {as} a single
  13. object. The objects making up the set are called \emph{elements} or
  14. \emph{members} of the set. If $x$ is !!a{element} of a set~$A$, we
  15. write $x \in A$; if not, we write $x \notin A$. The set which has no
  16. !!{element}s is called the \emph{empty} set and
  17. denoted~``$\emptyset$''.
  19. \begin{explain}
  20. It does not matter how we \emph{specify} the set, or how we
  21. \emph{order} its !!{element}s, or indeed how \emph{many times} we
  22. count its !!{element}s. All that matters are what its !!{element}s
  23. are. We codify this in the following principle.
  24. \end{explain}
  26. \begin{defn}[Extensionality]
  27. If $A$ and $B$ are sets, then $A = B$ iff
  28. every !!{element} of~$A$ is also !!a{element} of~$B$, and vice
  29. versa.
  30. \end{defn}
  32. Extensionality licenses some notation. In general, when we have some
  33. objects $a_{1}$, \dots, $a_{n}$, then $\{a_{1}, \dots, a_{n}\}$ is
  34. \emph{the} set whose !!{element}s are $a_1, \ldots, a_n$. We emphasise
  35. the word ``\emph{the}'', since extensionality tells us that there can
  36. be only \emph{one} such set. Indeed, extensionality also licenses the
  37. following:
  38. \[
  39. \{a, a, b\} = \{a, b\} = \{b,a\}.
  40. \]
  41. This delivers on the point that, when we consider sets, we don't care
  42. about the order of their !!{element}s, or how many times they are
  43. specified.
  45. \begin{tagblock}{novice}
  46. \begin{ex}
  47. Whenever you have a bunch of objects, you can collect them together in
  48. a set. The set of Richard's siblings, for instance, is a set that
  49. contains one person, and we could write it as $S=\{\textrm{Ruth}\}$.
  50. The set of positive integers less than $4$ is $\{1, 2, 3\}$, but it
  51. can also be written as $\{3, 2, 1\}$ or even as $\{1, 2, 1, 2, 3\}$.
  52. These are all the same set, by extensionality. For every !!{element}
  53. of $\{1, 2, 3\}$ is also !!a{element} of $\{3, 2, 1\}$ (and of $\{1,
  54. 2, 1, 2, 3\}$), and vice versa.
  55. \end{ex}
  56. \end{tagblock}
  58. Frequently we'll specify a set by some property that its !!{element}s
  59. share. We'll use the following shorthand notation for that:
  60. $\Setabs{x}{\phi(x)}$, where the $\phi(x)$ stands for the property
  61. that~$x$ has to have in order to be counted among the !!{element}s of
  62. the set.
  64. \begin{tagblock}{novice}
  65. \begin{ex}
  66. In our example, we could have specified $S$ also as
  67. \[
  68. S = \Setabs{x}{x \text{ is a sibling of Richard}}.
  69. \]
  70. \end{ex}
  71. \end{tagblock}
  73. \begin{tagblock}{math}
  74. \begin{ex}
  75. A number is called \emph{perfect} iff it is equal to the sum of its
  76. proper divisors (i.e., numbers that evenly divide it but aren't
  77. identical to the number). For instance, $6$ is perfect because its
  78. proper divisors are $1$, $2$, and~$3$, and $6 = 1 + 2 + 3$. In fact,
  79. $6$ is the only positive integer less than $10$ that is perfect. So,
  80. using extensionality, we can say:
  81. \[
  82. \{6\} = \Setabs{x}{x\text{ is perfect and }0 \leq x \leq 10}
  83. \]
  84. We read the notation on the right as ``the set of $x$'s such that $x$
  85. is perfect and $0 \leq x \leq 10$''. The identity here confirms that,
  86. when we consider sets, we don't care about how they are specified.
  87. And, more generally, extensionality guarantees that there is always
  88. only one set of $x$'s such that $\phi(x)$.
  89. So, extensionality justifies calling
  90. $\Setabs{x}{\phi(x)}$ \emph{the} set of $x$'s such that~$\phi(x)$.
  91. \end{ex}
  92. \end{tagblock}
  94. Extensionality gives us a way for showing that sets are identical: to
  95. show that $A = B$, show that whenever $x \in A$ then also $x \in B$,
  96. and whenever $y \in B$ then also $y \in A$.
  98. \begin{prob}
  99. Prove that there is at most one empty set, i.e., show that if $A$ and $B$
  100. are sets without !!{element}s, then $A = B$.
  101. \end{prob}
  103. \end{document}

content/sets-functions-relations/sets/subsets.tex

103 lines; SHA-256 5d982f62c40325cf75da4517add45ca073e23fb9463cfb3adfb9aafbb8582e46. Open the preserved source file.

  1. % Part: sets-functions-relations
  2. % Chapter: sets
  3. % Section: subsets
  5. \documentclass[../../../include/open-logic-section]{subfiles}
  7. \begin{document}
  9. \olfileid{sfr}{set}{sub}
  10. \olsection{Subsets and Power Sets}
  12. \begin{explain}
  13. We will often want to compare sets. And one obvious kind of comparison
  14. one might make is as follows: \emph{everything in one set is in the
  15. other too}. This situation is sufficiently important for us to
  16. introduce some new notation.
  17. \end{explain}
  19. \begin{defn}[Subset]
  20. If every !!{element} of a set $A$ is also !!a{element} of~$B$, then we
  21. say that $A$ is a \emph{subset} of~$B$, and write $A \subseteq B$. If
  22. $A$ is not a subset of~$B$ we write $A \not\subseteq B$.
  23. If $A \subseteq B$ but $A \neq B$, we write $A \subsetneq B$ and say
  24. that $A$ is a \emph{proper subset} of $B$.
  25. \end{defn}
  27. \begin{ex}
  28. Every set is a subset of itself, and $\emptyset$ is a subset of every
  29. set. The set of natural even numbers is a subset of the set of natural
  30. numbers. Also, $\{ a, b \} \subseteq \{ a, b, c \}$. But $\{ a, b, e
  31. \}$ is not a subset of $\{ a, b, c \}$.
  32. \end{ex}
  34. \begin{ex}
  35. The number $2$ is an !!{element} of the set of integers, whereas the
  36. set of even numbers is a subset of the set of integers. However, a set
  37. may happen to \emph{both} be !!a{element} and a subset of some other
  38. set, e.g., $\{0\} \in \{0, \{0\}\}$ and also $\{0\} \subseteq \{0,
  39. \{0\}\}$.
  40. \end{ex}
  42. Extensionality gives a criterion of identity for sets: $A = B$ iff
  43. every !!{element} of~$A$ is also !!a{element} of~$B$ and vice versa.
  44. The definition of ``subset'' defines $A \subseteq B$ precisely as the
  45. first half of this criterion: every !!{element} of~$A$ is also
  46. !!a{element} of~$B$. Of course the definition also applies if we
  47. switch $A$ and $B$: that is, $B \subseteq A$ iff every !!{element}
  48. of~$B$ is also !!a{element} of~$A$. And that, in turn, is exactly the
  49. ``vice versa'' part of extensionality. In other words, extensionality
  50. entails that sets are equal iff they are subsets of one another.
  52. \begin{prop}
  53. $A = B$ iff both $A \subseteq B$ and $B \subseteq A$.
  54. \end{prop}
  56. Now is also a good opportunity to introduce some further bits of
  57. helpful notation. In defining when $A$ is a subset of~$B$ we said that
  58. ``every !!{element} of~$A$ is \dots,'' and filled the ``$\dots$'' with
  59. ``!!a{element} of $B$''. But this is such a common \emph{shape} of
  60. expression that it will be helpful to introduce some formal notation
  61. for it.
  63. \begin{defn}\ollabel{forallxina}
  64. $(\forall x \in A)\phi$ abbreviates $\forall x(x \in A \lif
  65. \phi)$. Similarly, $(\exists x \in A)\phi$ abbreviates $\exists x(x
  66. \in A \land \phi)$.
  67. \end{defn}
  69. Using this notation, we can say that $A \subseteq B$ iff $(\forall
  70. x \in A)x \in B$.
  72. Now we move on to considering a certain kind of set: the set of all
  73. subsets of a given set.
  75. \begin{defn}[Power Set]
  76. The set consisting of all subsets of a set~$A$ is called the
  77. \emph{power set of}~$A$, written $\Pow{A}$.
  78. \[
  79. \Pow{A} = \Setabs{B}{B \subseteq A}
  80. \]
  81. \end{defn}
  83. \begin{ex}
  84. What are all the possible subsets of $\{ a, b, c \}$? They are:
  85. $\emptyset$, $\{a \}$, $\{b\}$, $\{c\}$, $\{a, b\}$, $\{a, c\}$, $\{b,
  86. c\}$, $\{a, b, c\}$. The set of all these subsets is
  87. $\Pow{\{a,b,c\}}$:
  88. \[
  89. \Pow{\{ a, b, c \}} = \{\emptyset, \{a \}, \{b\}, \{c\}, \{a, b\},
  90. \{b, c\}, \{a, c\}, \{a, b, c\}\}
  91. \]
  92. \end{ex}
  94. \begin{prob}
  95. List all subsets of $\{a, b, c, d\}$.
  96. \end{prob}
  98. \begin{prob}
  99. Show that if $A$ has $n$ !!{element}s, then $\Pow{A}$ has $2^n$
  100. !!{element}s.
  101. \end{prob}
  103. \end{document}

content/sets-functions-relations/sets/important-sets.tex

69 lines; SHA-256 b1b998cad3fa5aef48670f755245f86efe00b239d332a50e764147602405fb32. Open the preserved source file.

  1. % Part: sets-functions-relations
  2. % Chapter: sets
  3. % Section: important-sets
  5. \documentclass[../../../include/open-logic-section]{subfiles}
  7. \begin{document}
  9. \olfileid{sfr}{set}{imp}
  10. \olsection{Some Important Sets}
  12. \begin{ex}
  13. We will mostly be dealing with sets whose !!{element}s are
  14. mathematical objects. Four such sets are important enough to have
  15. specific names:
  16. \begin{multline*}
  17. \Nat = \{0, 1, 2, 3, \ldots\} \\
  18. \shoveright{\text{the set of natural numbers}}\\
  19. \shoveleft{\Int = \{\ldots, -2, -1, 0, 1, 2, \ldots\}} \\
  20. \shoveright{\text{the set of integers}}\\
  21. \shoveleft{\Rat = \Setabs{\nicefrac{m}{n}}{m, n \in \Int\text{ and }n \neq 0}}\\
  22. \shoveright{\text{the set of rationals}}\\
  23. \shoveleft{\Real = (-\infty, \infty)}\\
  24. \text{the set of real numbers (the continuum)}
  25. \end{multline*}
  26. These are all \emph{infinite} sets, that is, they each have
  27. infinitely many !!{element}s.
  29. As we move through these sets, we are adding \emph{more} numbers to
  30. our stock. Indeed, it should be clear that $\Nat \subseteq \Int
  31. \subseteq \Rat \subseteq \Real$: after all, every natural number is an
  32. integer; every integer is a rational; and every rational is a real.
  33. Equally, it should be clear that $\Nat \subsetneq \Int \subsetneq
  34. \Rat$, since $-1$ is an integer but not a natural number, and
  35. $\nicefrac{1}{2}$ is rational but not integer. It is less obvious
  36. that $\Rat \subsetneq \Real$, i.e., that there are some real numbers
  37. which are not rational\oliflabeldef{sfr:arith:real:realline}{, but we'll
  38. return to this in \olref[arith][real]{realline}}{}.
  40. We'll sometimes also use the set of positive integers $\PosInt = \{1,
  41. 2, 3, \dots\}$ and the set containing just the first two natural
  42. numbers $\Bin = \{0, 1\}$.
  43. \end{ex}
  45. \begin{tagblock}{compsci}
  46. \begin{ex}[Strings]
  47. Another interesting example is the set $A^{*}$ of \emph{finite
  48. strings} over an alphabet $A$: any finite sequence of elements of~$A$
  49. is a string over $A$. We include the \emph{empty string $\Lambda$}
  50. among the strings over~$A$, for every alphabet~$A$. For instance,
  51. \begin{multline*}
  52. \Bin^*
  53. =\{\Lambda,0,1,00,01,10,11,\\
  54. 000,001,010,011,100,101,110,111,0000,\ldots\}.
  55. \end{multline*}
  56. If $x=x_{1}\ldots x_{n}\in A^{*}$is a string consisting of $n$
  57. ``letters'' from $A$, then we say \emph{length} of the string is~$n$
  58. and write $\len{x}=n$.
  59. \end{ex}
  60. \end{tagblock}
  62. \begin{ex}[Infinite sequences]
  63. For any set $A$ we may also consider the set~$A^\omega$ of infinite
  64. sequences of !!{element}s of~$A$. An infinite sequence
  65. $a_1a_2a_3a_4\dots$ consists of a one-way infinite list of objects,
  66. each one of which is !!a{element} of~$A$.
  67. \end{ex}
  69. \end{document}

content/sets-functions-relations/sets/unions-and-intersections.tex

174 lines; SHA-256 2ad0eec70308ceeff2a4158b2dee60e59a9b1cf9268fc95c4bb1da05f65ad60d. Open the preserved source file.

  1. % Part: sets-functions-relations
  2. % Chapter: sets
  3. % Section: unions-and-intersections
  5. \documentclass[../../../include/open-logic-section]{subfiles}
  7. \begin{document}
  9. \olfileid{sfr}{set}{uni}
  10. \olsection{Unions and Intersections}
  12. \begin{explain}
  13. In \olref[sfr][set][bas]{sec}, we introduced definitions of sets by
  14. abstraction, i.e., definitions of the form $\Setabs{x}{\phi(x)}$.
  15. Here, we invoke some property~$\phi$, and this property can mention
  16. sets we've already defined. So for instance, if $A$ and~$B$ are sets,
  17. the set $\Setabs{x}{x \in A \lor x \in B}$ consists of all those
  18. objects which are !!{element}s of either $A$ or~$B$, i.e., it's the
  19. set that combines the !!{element}s of $A$ and~$B$. We can visualize
  20. this as in \olref{fig:union}, where the highlighted area indicates the
  21. !!{element}s of the two sets $A$ and~$B$ together.
  23. \begin{figure}
  24. \olasset{assets/diagrams/union.tikz}
  25. \caption{The union $A \cup B$ of two sets is set of !!{element}s of
  26. $A$ together with those of~$B$.}
  27. \ollabel{fig:union}
  28. \end{figure}
  30. This operation on sets---combining them---is very useful and common,
  31. and so we give it a formal name and a symbol.
  32. \end{explain}
  34. \begin{defn}[Union]
  35. The \emph{union} of two sets $A$ and $B$, written $A \cup B$, is the
  36. set of all things which are !!{element}s of $A$, $B$, or both.
  37. \[
  38. A \cup B = \Setabs{x}{x \in A \lor x \in B}
  39. \]
  40. \end{defn}
  42. \begin{ex}
  43. Since the multiplicity of !!{element}s doesn't matter, the union of two
  44. sets which have !!a{element} in common contains that !!{element} only once,
  45. e.g., $\{ a, b, c\} \cup \{ a, 0, 1\} = \{a, b, c, 0, 1\}$.
  47. The union of a set and one of its subsets is just the bigger set: $\{a,
  48. b, c \} \cup \{a \} = \{a, b, c\}$.
  50. The union of a set with the empty set is identical to the set: $\{a,
  51. b, c \} \cup \emptyset = \{a, b, c \}$.
  52. \end{ex}
  54. \begin{prob}
  55. Prove that if $A \subseteq B$, then $A \cup B = B$.
  56. \end{prob}
  58. \begin{explain}
  59. We can also consider a ``dual'' operation to union. This is the
  60. operation that forms the set of all !!{element}s that are !!{element}s
  61. of~$A$ and are also !!{element}s of~$B$. This operation is called
  62. \emph{intersection}, and can be depicted as in \olref{fig:intersection}.
  63. \begin{figure}
  64. \olasset{assets/diagrams/intersection.tikz}
  65. \caption{The intersection $A \cap B$ of two sets is the set of
  66. !!{element}s they have in common.}
  67. \ollabel{fig:intersection}
  68. \end{figure}
  69. \end{explain}
  71. \begin{defn}[Intersection]
  72. The \emph{intersection} of two sets $A$ and $B$, written $A \cap B$, is
  73. the set of all things which are !!{element}s of both $A$ and~$B$.
  74. \[
  75. A \cap B = \Setabs{x}{x \in A \land x \in B}
  76. \]
  77. Two sets are called \emph{disjoint} if their intersection is
  78. empty. This means they have no !!{element}s in common.
  79. \end{defn}
  81. \begin{ex}
  82. If two sets have no !!{element}s in common, their intersection is empty:
  83. $\{ a, b, c\} \cap \{ 0, 1\} = \emptyset$.
  85. If two sets do have !!{element}s in common, their intersection is the set of
  86. all those: $\{a, b, c \} \cap \{a, b, d \} = \{a, b\}$.
  88. The intersection of a set with one of its subsets is just the smaller
  89. set: $\{a, b, c\} \cap \{a, b\} = \{a, b\}$.
  91. The intersection of any set with the empty set is empty: $\{a, b, c \}
  92. \cap \emptyset = \emptyset$.
  93. \end{ex}
  95. \begin{prob}
  96. Prove rigorously that if $A \subseteq B$, then $A \cap B = A$.
  97. \end{prob}
  99. \begin{explain}
  100. We can also form the union or intersection of more than two
  101. sets. An elegant way of dealing with this in general is the
  102. following: suppose you collect all the sets you want to form the union
  103. (or intersection) of into a single set. Then we can define the union
  104. of all our original sets as the set of all objects which belong to at
  105. least one !!{element} of the set, and the intersection as the set of
  106. all objects which belong to every !!{element} of the set.
  107. \end{explain}
  109. \begin{defn}
  110. If $A$ is a set of sets, then $\bigcup A$ is the set of !!{element}s of
  111. !!{element}s of~$A$:
  112. \begin{align*}
  113. \bigcup A & = \Setabs{x}{x \text{ belongs to !!a{element} of } A},
  114. \text{ i.e.,}\\
  115. & = \Setabs{x}{\text{there is a } B \in A
  116. \text{ so that } x \in B}
  117. \end{align*}
  118. \end{defn}
  120. \begin{defn}
  121. If $A$ is a set of sets, then $\bigcap A$ is the set of objects which
  122. all elements of~$A$ have in common:
  123. \begin{align*}
  124. \bigcap A & = \Setabs{x}{x \text{ belongs to every !!{element} of } A},
  125. \text{ i.e.,}\\
  126. & = \Setabs{x}{\text{for all } B \in A, x \in B}
  127. \end{align*}
  128. \end{defn}
  130. \begin{ex}
  131. Suppose $A = \{ \{ a, b \}, \{ a, d, e \}, \{ a, d \} \}$.
  132. Then $\bigcup A = \{ a, b, d, e \}$ and $\bigcap A = \{ a \}$.
  133. \end{ex}
  134. \begin{prob}
  135. Show that if $A$ is a set and $A \in B$, then $A \subseteq \bigcup B$.
  136. \end{prob}
  138. We could also do the same for a sequence of sets $A_1$, $A_2$, \dots
  139. \begin{align*}
  140. \bigcup_i A_i & = \Setabs{x}{x \text{ belongs to one of the } A_i}\\
  141. \bigcap_i A_i & = \Setabs{x}{x \text{ belongs to every } A_i}.
  142. \end{align*}
  144. When we have an \emph{index} of sets, i.e., some set $I$ such that we
  145. are considering $A_i$ for each $i \in I$, we may also use these
  146. abbreviations:
  147. \begin{align*}
  148. \bigcup_{i \in I} A_i & = \bigcup \Setabs{A_i }{i \in I}\\
  149. \bigcap_{i \in I} A_i & = \bigcap\Setabs{A_i}{i \in I}
  150. \end{align*}
  152. Finally, we may want to think about the set of all !!{element}s in~$A$
  153. which are not in~$B$. We can depict this as in \olref{difference}.
  155. \begin{figure}
  156. \olasset{assets/diagrams/difference.tikz}
  157. \caption{The difference $A \setminus B$ of two sets is the set of
  158. those !!{element}s of~$A$ which are not also !!{element}s of~$B$.}
  159. \ollabel{difference}
  160. \end{figure}
  162. \begin{defn}[Difference]
  163. The \emph{set difference}~$A \setminus B$ is the set of all !!{element}s of
  164. $A$ which are not also !!{element}s of~$B$, i.e.,
  165. \[
  166. A\setminus B = \Setabs{x}{x\in A \text{ and } x \notin B}.
  167. \]
  168. \end{defn}
  170. \begin{prob}
  171. Prove that if $A \subsetneq B$, then $B \setminus A \neq \emptyset$.
  172. \end{prob}
  174. \end{document}

content/sets-functions-relations/sets/pairs-and-products.tex

129 lines; SHA-256 3db7f0241d387b49488f70e78062c24192b813873618f761565d97bd7249431c. Open the preserved source file.

  1. % Part: sets-functions-relations
  2. % Chapter: sets
  3. % Section: pairs-and-products
  5. \documentclass[../../../include/open-logic-section]{subfiles}
  7. \begin{document}
  9. \olfileid{sfr}{set}{pai}
  10. \olsection{Pairs, Tuples, Cartesian Products}
  12. \begin{explain}
  13. It follows from extensionality that sets have no order to their
  14. elements. So if we want to represent order, we use \emph{ordered
  15. pairs} $\tuple{x, y}$. In an unordered pair $\{x, y\}$, the order does
  16. not matter: $\{x, y\} = \{y, x\}$. In an ordered pair, it does: if $x
  17. \neq y$, then $\tuple{x, y} \neq \tuple{y, x}$.
  19. How should we think about ordered pairs in set theory? Crucially, we
  20. want to preserve the idea that ordered pairs are identical iff they
  21. share the same first element and share the same second element, i.e.:
  22. \[
  23. \tuple{a, b}= \tuple{c, d}\text{ iff both }a = c \text{ and }b=d.
  24. \]
  25. We can define ordered pairs in set theory using the Wiener--Kuratowski
  26. definition.
  27. \end{explain}
  29. \begin{defn}[Ordered pair]\ollabel{wienerkuratowski}
  30. $\tuple{a, b} = \{\{a\}, \{a, b\}\}$.
  31. \end{defn}
  33. \begin{prob}
  34. Using \olref[sfr][set][pai]{wienerkuratowski}, prove that $\tuple{a,
  35. b}= \tuple{c, d}$ iff both $a = c$ and $b=d$.
  36. \end{prob}
  38. \begin{explain}
  39. Having fixed a definition of an ordered pair, we can use it to define
  40. further sets. For example, sometimes we also want ordered sequences of
  41. more than two objects, e.g., \emph{triples} $\tuple{x, y, z}$,
  42. \emph{quadruples} $\tuple{x, y, z, u}$, and so on. We can think of
  43. triples as special ordered pairs, where the first element is itself an
  44. ordered pair: $\tuple{x, y, z}$ is $\tuple{\tuple{x, y},z}$. The same
  45. is true for quadruples: $\tuple{x,y,z,u}$ is
  46. $\tuple{\tuple{\tuple{x,y},z},u}$, and so on. In general, we talk of
  47. \emph{ordered $n$-tuples} $\tuple{x_1, \dots, x_n}$.
  49. Certain sets of ordered pairs, or other ordered $n$-tuples, will be useful.
  50. \end{explain}
  52. \begin{defn}[Cartesian product]
  53. Given sets $A$ and $B$, their \emph{Cartesian product} $A \times B$ is
  54. defined by
  55. \[
  56. A \times B = \Setabs{\tuple{x, y}}{x \in A \text{ and } y \in B}.
  57. \]
  58. \end{defn}
  60. \begin{ex}
  61. If $A = \{0, 1\}$, and $B = \{1, a, b\}$, then their product is
  62. \[
  63. A \times B = \{ \tuple{0, 1}, \tuple{0, a}, \tuple{0, b},
  64. \tuple{1, 1}, \tuple{1, a}, \tuple{1, b} \}.
  65. \]
  66. \end{ex}
  68. \begin{ex}
  69. If $A$ is a set, the product of $A$ with itself, $A \times A$, is also
  70. written~$A^2$. It is the set of \emph{all} pairs $\tuple{x, y}$ with
  71. $x, y \in A$. The set of all triples $\tuple{x, y, z}$ is $A^3$, and
  72. so on. We can give a recursive definition:
  73. \begin{align*}
  74. A^1 & = A\\
  75. A^{k+1} & = A^k \times A
  76. \end{align*}
  77. \end{ex}
  79. \begin{prob}
  80. List all !!{element}s of $\{1, 2, 3\}^3$.
  81. \end{prob}
  83. \begin{prop}\ollabel{cardnmprod}
  84. If $A$ has $n$ !!{element}s and $B$ has $m$ !!{element}s, then $A
  85. \times B$ has $n\cdot m$ elements.
  86. \end{prop}
  88. \begin{proof}
  89. For every !!{element}~$x$ in~$A$, there are $m$ !!{element}s of the
  90. form $\tuple{x, y} \in A \times B$. Let $B_x = \Setabs{\tuple{x, y}}{y
  91. \in B}$. Since whenever $x_1 \neq x_2$, $\tuple{x_1, y} \neq
  92. \tuple{x_2, y}$, $B_{x_1} \cap B_{x_2} = \emptyset$. But if $A = \{x_1,
  93. \dots, x_n\}$, then $A \times B = B_{x_1} \cup \dots \cup B_{x_n}$, and so has
  94. $n\cdot m$ !!{element}s.
  96. To visualize this, arrange the !!{element}s of~$A \times B$ in a grid:
  97. \[
  98. \begin{array}{rcccc}
  99. B_{x_1} = & \{\tuple{x_1, y_1} & \tuple{x_1, y_2} & \dots & \tuple{x_1, y_m}\}\\
  100. B_{x_2} = & \{\tuple{x_2, y_1} & \tuple{x_2, y_2} & \dots & \tuple{x_2, y_m}\}\\
  101. \vdots & & \vdots\\
  102. B_{x_n} = & \{\tuple{x_n, y_1} & \tuple{x_n, y_2} & \dots & \tuple{x_n, y_m}\}
  103. \end{array}
  104. \]
  105. Since the $x_i$ are all different, and the $y_j$ are all different, no
  106. two of the pairs in this grid are the same, and there are $n\cdot m$
  107. of them.
  108. \end{proof}
  110. \begin{prob}
  111. Show, by induction on~$k$, that for all $k \ge 1$, if $A$ has $n$
  112. !!{element}s, then $A^k$ has $n^k$ !!{element}s.
  113. \end{prob}
  115. \begin{ex}
  116. If $A$ is a set, a \emph{word} over~$A$ is any sequence of
  117. !!{element}s of~$A$. A sequence can be thought of as an $n$-tuple of
  118. !!{element}s of~$A$. For instance, if $A = \{a, b, c\}$, then the
  119. sequence ``$bac$'' can be thought of as the triple~$\tuple{b, a, c}$.
  120. Words, i.e., sequences of symbols, are of crucial importance in
  121. computer science. By convention, we count !!{element}s of~$A$ as
  122. sequences of length~$1$, and $\emptyset$ as the sequence of length~$0$.
  123. The set of \emph{all} words over~$A$ then is
  124. \[
  125. A^* = \{\emptyset\} \cup A \cup A^2 \cup A^3 \cup \dots
  126. \]
  127. \end{ex}
  129. \end{document}

content/sets-functions-relations/sets/russells-paradox.tex

89 lines; SHA-256 9a76315cd0d9cf89d27e90a9b87138b1c95aea98e0d26de3fe12d897b8c4d10d. Open the preserved source file.

  1. % Part: sets-functions-relations
  2. % Chapter: sets
  3. % Section: russells-paradox
  5. \documentclass[../../../include/open-logic-section]{subfiles}
  8. \begin{document}
  10. \olfileid{sfr}{set}{rus}
  11. \olsection{Russell's Paradox}
  13. Extensionality licenses the notation $\Setabs{x}{\phi(x)}$, for
  14. \emph{the} set of $x$'s such that~$\phi(x)$. However, all that
  15. extensionality \emph{really} licenses is the following thought.
  16. \emph{If} there is a set whose members are all and only the $\phi$'s,
  17. \emph{then} there is only one such set. Otherwise put: having fixed
  18. some~$\phi$, the set $\Setabs{x}{\phi(x)}$ is unique, \emph{if it
  19. exists}.
  21. But this conditional is important!{} Crucially, not every property
  22. lends itself to \emph{comprehension}. That is, some properties do
  23. \emph{not} define sets. If they all did, then we would run into
  24. outright contradictions. The most famous example of this is Russell's
  25. Paradox.
  27. Sets may be !!{element}s of other sets---for instance, the power set
  28. of a set~$A$ is made up of sets. And so it makes sense to ask or
  29. investigate whether a set is !!a{element} of another set. Can a set be
  30. a member of itself? Nothing about the idea of a set seems to rule
  31. this out. For instance, if \emph{all} sets form a collection of
  32. objects, one might think that they can be collected into a single
  33. set---the set of all sets. And it, being a set, would be !!a{element}
  34. of the set of all sets.
  36. Russell's Paradox arises when we consider the property of not having
  37. itself as !!a{element}, of being \emph{non-self-membered}. What if we
  38. suppose that there is a set of all sets that do not have themselves as
  39. !!a{element}? Does
  40. \[
  41. R = \Setabs{x}{x \notin x}
  42. \]
  43. exist? It turns out that we can prove that it does not.
  45. \begin{thm}[Russell's Paradox]\ollabel{thm:russells-paradox}
  46. There is no set $R = \Setabs{x}{x \notin x}$.
  47. \end{thm}
  49. \begin{proof}
  50. If $R = \Setabs{x}{x \notin x}$ exists, then
  51. $R \in R$ iff $R \notin R$, which is a contradiction.
  52. \end{proof}
  54. \begin{tagblock}{novice}
  55. \begin{explain}
  56. Let's run through this proof more slowly. If $R$ exists, it makes sense to ask whether $R \in
  57. R$ or not. Suppose that indeed $R \in R$. Now, $R$~was defined as the set of all
  58. sets that are not !!{element}s of themselves. So, if $R \in R$,
  59. then $R$ does not itself have $R$'s defining property. But only sets
  60. that have this property are in~$R$, hence, $R$ cannot be !!a{element}
  61. of~$R$, i.e., $R \notin R$. But $R$ can't both be and not be
  62. !!a{element} of~$R$, so we have a contradiction.
  64. Since the assumption that $R \in R$ leads to a contradiction, we have
  65. $R \notin R$. But this also leads to a contradiction!{} For if $R
  66. \notin R$, then $R$ itself does have $R$'s defining property, and so $R$ would be
  67. !!a{element} of $R$ just like all the other non-self-membered sets.
  68. And again, it can't both not be and be !!a{element} of~$R$.
  69. \end{explain}
  70. \end{tagblock}
  72. \begin{digress}
  73. How do we set up a set theory which avoids falling into
  74. Russell's Paradox, i.e., which avoids making the \emph{inconsistent}
  75. claim that $R = \Setabs{x}{x \notin x}$ exists? Well, we would need to
  76. lay down axioms which give us very precise conditions for stating when
  77. sets exist (and when they don't).
  79. The set theory sketched in this chapter doesn't do this. It's
  80. \emph{genuinely na\"ive}. It tells you only that sets obey
  81. extensionality and that, if you have some sets, you can form their
  82. union, intersection, etc. It is possible to develop set theory more
  83. rigorously than this. \oliflabeldef{cumul:::part}{That rigour will be
  84. reserved for Part \olref[cumul][][]{part}. For now, we will proceed
  85. na\"ively, and carefully try to sidestep contradictions.}{}
  86. \end{digress}
  89. \end{document}