The Open Logic Text — accessible offline edition

Relations — Source and provenance

Relations

Source and provenance

These are all nine files in the frozen Relations source boundary, shown line by line and copied byte-for-byte for download. The packaged authority ledgers retain the exact line, column, offset, delimiter, expression binding, speech, meaning, and native MathML for all 515 formula occurrences.

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

83 lines; SHA-256 0b2167d0a9633938fd173d396f9e92b795826821471ff111483f7c7088a4be46. Open the preserved source file.

  1. % Part: sets-functions-relations
  2. % Chapter: relations
  3. % Section: equivalence-relations
  5. \documentclass[../../../include/open-logic-section]{subfiles}
  7. \begin{document}
  9. \olfileid{sfr}{rel}{eqv}
  11. \olsection{Equivalence Relations}
  13. The identity relation on a set is reflexive, symmetric, and
  14. transitive. Relations~$R$ that have all three of these properties are very
  15. common.
  17. \begin{defn}[Equivalence relation]
  18. A relation $R \subseteq A^2$ that is reflexive, symmetric, and
  19. transitive is called an \emph{equivalence relation}. !!^{element}s $x$
  20. and $y$ of~$A$ are said to be \emph{$R$-equivalent} if~$Rxy$.
  21. \end{defn}
  23. Equivalence relations give rise to the notion of an \emph{equivalence
  24. class}. An equivalence relation ``chunks up'' the domain into
  25. different partitions. Within each partition, all the objects are
  26. related to one another; and no objects from different partitions
  27. relate to one another. Sometimes, it's helpful just to talk about
  28. these partitions \emph{directly}. To that end, we introduce a
  29. definition:
  31. \begin{defn}\ollabel{def:equivalenceclass}
  32. Let $R \subseteq A^2$ be an equivalence relation. For each $x \in A$,
  33. the \emph{equivalence class} of $x$ in~$A$ is the set $\equivrep{x}{R}
  34. = \Setabs{y \in A}{Rxy}$. The \emph{quotient} of $A$ under~$R$ is
  35. $\equivclass{A}{R} = \Setabs{\equivrep{x}{R}}{x \in A}$, i.e., the set
  36. of these equivalence classes.
  37. \end{defn}
  39. The next result vindicates the definition of an equivalence class, in
  40. proving that the equivalence classes are indeed the partitions of~$A$:
  42. \begin{prop}
  43. If $R \subseteq A^2$ is an equivalence relation, then $Rxy$ iff
  44. $\equivrep{x}{R} = \equivrep{y}{R}$.
  45. \end{prop}
  47. \begin{proof}
  48. For the left-to-right direction, suppose $Rxy$, and let $z \in
  49. \equivrep{x}{R}$. By definition, then, $Rxz$. Since $R$ is an
  50. equivalence relation, $Ryz$. (Spelling this out: as $Rxy$ and~$R$ is
  51. symmetric we have $Ryx$, and as $Rxz$ and~$R$ is transitive we
  52. have~$Ryz$.) So $z \in \equivrep{y}{R}$. Generalising,
  53. $\equivrep{x}{R} \subseteq \equivrep{y}{R}$. But exactly similarly,
  54. $\equivrep{y}{R} \subseteq \equivrep{x}{R}$. So $\equivrep{x}{R} =
  55. \equivrep{y}{R}$, by extensionality.
  57. For the right-to-left direction, suppose $\equivrep{x}{R} =
  58. \equivrep{y}{R}$. Since $R$ is reflexive, $Ryy$, so $y \in
  59. \equivrep{y}{R}$. Thus also $y \in \equivrep{x}{R}$ by the assumption
  60. that $\equivrep{x}{R} = \equivrep{y}{R}$. So $Rxy$.
  61. \end{proof}
  63. \begin{ex}
  64. A nice example of equivalence relations comes from modular arithmetic.
  65. For any $a$, $b$, and $n \in \PosInt$, say that $a \equiv_n b$ iff
  66. dividing $a$ by~$n$ gives the same remainder as dividing $b$ by~$n$.
  67. (Somewhat more symbolically: $a \equiv_n b$ iff, for some $k \in
  68. \Int$, $a - b = kn$.) Now, $\equiv_n$ is an equivalence relation, for
  69. any~$n$. And there are exactly $n$ distinct equivalence classes
  70. generated by~$\equiv_n$; that is, $\equivclass{\Nat}{\equiv_n}$ has
  71. $n$ !!{element}s. These are: the set of numbers divisible by $n$
  72. without remainder, i.e., $\equivrep{0}{\equiv_n}$; the set of numbers
  73. divisible by $n$ with remainder~$1$, i.e., $\equivrep{1}{\equiv_n}$;
  74. \ldots; and the set of numbers divisible by~$n$ with remainder~$n-1$,
  75. i.e.,~$\equivrep{n-1}{\equiv_n}$.
  76. \end{ex}
  78. \begin{prob}
  79. Show that $\equiv_n$ is an equivalence relation, for any $n \in
  80. \PosInt$, and that $\equivclass{\Nat}{\equiv_n}$ has exactly $n$ members.
  81. \end{prob}
  83. \end{document}

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

77 lines; SHA-256 a538018608ce97d0b371a392912c3d6825d8f3b17719bceca5744a77ace26351. Open the preserved source file.

  1. % Part: sets-functions-relations
  2. % Chapter: relations
  3. % Section: graphs
  5. \documentclass[../../../include/open-logic-section]{subfiles}
  7. \begin{document}
  9. \olfileid{sfr}{rel}{grp}
  10. \olsection{Graphs}
  12. A \emph{graph} is a diagram in which points---called ``nodes'' or
  13. ``vertices'' (plural of ``vertex'')---are connected by edges. Graphs
  14. are a ubiquitous tool in discrete mathematics and in computer science.
  15. They are incredibly useful for representing, and visualizing,
  16. relationships and structures, from concrete things like networks of
  17. various kinds to abstract structures such as the possible outcomes of
  18. decisions. There are many different kinds of graphs in the literature
  19. which differ, e.g., according to whether the edges are directed or
  20. not, have labels or not, whether there can be edges from a node to the
  21. same node, multiple edges between the same nodes, etc. \emph{Directed
  22. graphs} have a special connection to relations.
  24. \begin{defn}[Directed graph]
  25. A \emph{directed graph} $G = \tuple{V, E}$ is a set of
  26. \emph{vertices}~$V$ and a set of \emph{edges}~$E \subseteq V^2$.
  27. \end{defn}
  29. \begin{explain}
  30. According to our definition, a graph just is a set together with a
  31. relation on that set. Of course, when talking about graphs, it's only
  32. natural to expect that they are graphically represented: we can draw a
  33. graph by connecting two vertices~$v_1$ and $v_2$ by an arrow iff
  34. $\tuple{v_1, v_2} \in E$. The only difference between a relation by
  35. itself and a graph is that a graph specifies the set of vertices,
  36. i.e., a graph may have isolated vertices. The important point,
  37. however, is that every relation~$R$ on a set~$X$ can be seen as a
  38. directed graph $\tuple{X, R}$, and conversely, a directed
  39. graph~$\tuple{V, E}$ can be seen as a relation $E \subseteq V^2$ with
  40. the set $V$ explicitly specified.
  41. \end{explain}
  43. \begin{ex}
  44. The graph $\tuple{V, E}$ with $V = \{1, 2, 3, 4\}$ and $E =
  45. \{\tuple{1,1}, \allowbreak \tuple{1, 2}, \allowbreak \tuple{1, 3},
  46. \allowbreak \tuple{2, 3}\}$ looks like this:
  47. \begin{align*}
  48. & \begin{tikzpicture}[->,node distance=2cm]
  49. \node[draw,circle] (A) {$1$};
  50. \node[draw,circle] (B) [right of=A] {$2$};
  51. \node[draw,circle] (C) [below of=B] {$3$};
  52. \node[draw,circle] (D) [right of=B] {$4$};
  53. \draw (A) to [loop above] (A);
  54. \draw (A) to (B);
  55. \draw (A) to (C);
  56. \draw (B) to (C);
  57. \end{tikzpicture}
  58. \intertext{This is a different graph than $\tuple{V', E}$ with $V' =
  59. \{1, 2, 3\}$, which looks like this:}
  60. & \begin{tikzpicture}[->,node distance=2cm]
  61. \node[draw,circle] (A) {$1$};
  62. \node[draw,circle] (B) [right of=A] {$2$};
  63. \node[draw,circle] (C) [below of=B] {$3$};
  64. \draw (A) to [loop above] (A);
  65. \draw (A) to (B);
  66. \draw (A) to (C);
  67. \draw (B) to (C);
  68. \end{tikzpicture}
  69. \end{align*}
  70. \end{ex}
  72. \begin{prob}
  73. Consider the less-than-or-equal-to relation~$\le$ on the set $\{1,
  74. 2, 3, 4\}$ as a graph and draw the corresponding diagram.
  75. \end{prob}
  77. \end{document}

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

71 lines; SHA-256 5e6f57e9ddf53e1624955adabd594ea3855ad787c1074ba12421b0025b432372. Open the preserved source file.

  1. % Part: sets-functions-relations
  2. % Chapter: relations
  3. % Section: operations
  5. \documentclass[../../../include/open-logic-section]{subfiles}
  7. \begin{document}
  9. \olfileid{sfr}{rel}{ops}
  10. \olsection{Operations on Relations}
  12. It is often useful to modify or combine relations. In
  13. \olref[sfr][rel][ord]{prop:stricttopartial}, we considered the \emph{union}
  14. of relations, which is just the union of two relations considered as
  15. sets of pairs. Similarly, in \olref[sfr][rel][ord]{prop:partialtostrict},
  16. we considered the relative difference of relations. Here are some
  17. other operations we can perform on relations.
  19. \begin{defn}\ollabel{relationoperations}
  20. Let $R$, $S$ be relations, and $A$ be any set.
  22. The \emph{inverse} of $R$ is $R^{-1} = \Setabs{\tuple{y, x}}{\tuple{x,
  23. y} \in R}$.
  25. The \emph{relative product} of $R$ and $S$ is $(R \mid S) =
  26. \{\tuple{x, z} : \exists y(Rxy \land Syz)\}$.
  28. The \emph{restriction} of $R$ to $A$ is $\funrestrictionto{R}{A}= R
  29. \cap A^2$.
  31. The \emph{application} of $R$ to $A$ is $\funimage{R}{A} = \{y :
  32. (\exists x \in A)Rxy\}$
  33. \end{defn}
  35. \begin{ex}
  36. Let $S \subseteq \Int^2$ be the successor relation on~$\Int$, i.e.,
  37. $S = \Setabs{\tuple{x, y} \in \Int^2}{x + 1 = y}$, so that $Sxy$ iff $x + 1 = y$.
  39. $S^{-1}$ is the predecessor relation on $\Int$, i.e.,
  40. $\Setabs{\tuple{x,y}\in\Int^2}{x -1 =y}$.
  42. $S\mid S$ is
  43. $ \Setabs{\tuple{x,y}\in\Int^2}{x + 2 =y}$
  45. $\funrestrictionto{S}{\Nat}$ is the successor relation on~$\Nat$.
  47. $\funimage{S}{\{1,2,3\}}$ is $\{2, 3, 4\}$.
  48. \end{ex}
  50. \begin{defn}[Transitive closure]Let $R \subseteq A^2$ be a binary relation.
  52. The \emph{transitive closure} of~$R$ is $R^+ = \bigcup_{0 < n \in
  53. \Nat} R^n$, where we recursively define $R^1 = R$ and $R^{n+1} = R^n
  54. \mid R$.
  56. The \emph{reflexive transitive closure} of $R$ is $R^* = R^+ \cup
  57. \Id{A}$.
  58. \end{defn}
  60. \begin{ex}
  61. Take the successor relation $S \subseteq \Int^2$. $S^2xy$ iff $x + 2 =
  62. y$, $S^3xy$ iff $x + 3 = y$, etc. So $S^+xy$ iff $x + n = y$ for some
  63. $n \geq 1$. In other words, $S^+xy$ iff $x < y$, and $S^*xy$ iff $x \le
  64. y$.
  65. \end{ex}
  67. \begin{prob}
  68. Show that the transitive closure of $R$ is in fact transitive.
  69. \end{prob}
  71. \end{document}

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

168 lines; SHA-256 c6b7f7f49379f9cac28d844270639eae141152978ef8ad68065d0cfd83ccbd38. Open the preserved source file.

  1. % Part: sets-functions-relations
  2. % Chapter: relations
  3. % Section: orders
  5. \documentclass[../../../include/open-logic-section]{subfiles}
  7. \begin{document}
  9. \olfileid{sfr}{rel}{ord}
  10. \olsection{Orders}
  12. \begin{explain}
  13. Many of our comparisons involve describing some objects as being
  14. ``less than'', ``equal to'', or ``greater than'' other objects, in a
  15. certain respect. These involve \emph{order} relations. But there are
  16. different kinds of order relations. For instance, some require that
  17. any two objects be comparable, others don't. Some include identity
  18. (like~$\le$) and some exclude it (like~$<$). It will help us to have a
  19. taxonomy here.
  20. \end{explain}
  22. \begin{defn}[Preorder]
  23. A relation which is both reflexive and transitive is called a
  24. \emph{preorder.}
  25. \end{defn}
  27. \begin{defn}[Partial order]
  28. A preorder which is also anti-symmetric is called a
  29. \emph{partial order}.
  30. \end{defn}
  32. \begin{defn}[Linear order]\ollabel{def:linearorder}
  33. A partial order which is also connected is called a
  34. \emph{total order} or \emph{linear order.}
  35. \end{defn}
  37. \begin{ex}
  38. Every linear order is also a partial order, and every partial order is
  39. also a preorder, but the converses don't hold. The universal relation
  40. on~$A$ is a preorder, since it is reflexive and transitive. But, if
  41. $A$ has more than one !!{element}, the universal relation is not
  42. anti-symmetric, and so not a partial order.
  43. \end{ex}
  45. \begin{ex}
  46. Consider the \emph{no longer than} relation $\preccurlyeq$
  47. on~$\Bin^*$: $x \preccurlyeq y$ iff $\len{x} \le \len{y}$. This is a
  48. preorder (reflexive and transitive), and even connected, but not a
  49. partial order, since it is not anti-symmetric. For instance, $01
  50. \preccurlyeq 10$ and $10 \preccurlyeq 01$, but $01 \neq 10$.
  51. \end{ex}
  53. \begin{ex}
  54. An important partial order is the relation $\subseteq$ on a set of
  55. sets. This is not in general a linear order, since if $a \neq b$ and
  56. we consider $\Pow{\{a, b\}} = \{\emptyset, \{a\}, \{b\}, \{a,b\}\}$,
  57. we see that $\{a\} \nsubseteq \{b\}$ and $\{a\} \neq \{b\}$ and $\{b\}
  58. \nsubseteq \{a\}$.
  59. \end{ex}
  61. \begin{ex}
  62. The relation of \emph{divisibility without remainder} gives us a
  63. partial order which isn't a linear order. For integers $n$ and~$m$, we
  64. write $n \mid m$ to mean $n$ (evenly) divides $m$, i.e., iff there is
  65. some integer~$k$ so that $m = kn$. On~$\Nat$, this is a partial order,
  66. but not a linear order: for instance, $2 \nmid 3$ and also $3 \nmid
  67. 2$. Considered as a relation on $\Int$, divisibility is only a
  68. preorder since it is not anti-symmetric: $1 \mid -1$ and $-1 \mid 1$
  69. but $1 \neq -1$.
  70. \end{ex}
  72. \begin{ex}
  73. The \emph{extension} relation on a set of sequences~$A^*$ is the
  74. following: $s \sqsubseteq s'$ iff $s = \emptyseq$ (the empty
  75. sequence), $s = s'$, or $s = \tuple{s_1, \dots, s_n}$ and $s' =
  76. \tuple{s_1, \dots, s_n, s_{n+1}, \dots, s_m}$. If $s \sqsubseteq s'$
  77. we also say that $s$ is an \emph{initial segment} of~$s'$. The
  78. extension relation on $A^*$ is a partial order but not a linear order,
  79. e.g., if $a \neq b$, then $ab \not\sqsubseteq ba$ and $ba \not\sqsubseteq ab$.
  80. \end{ex}
  82. \begin{defn}[Strict order]
  83. A \emph{strict order} is a relation which is irreflexive, asymmetric,
  84. and transitive.
  85. \end{defn}
  87. \begin{defn}[Strict linear order]\ollabel{def:strictlinearorder}
  88. A strict order which is also connected is called a
  89. \emph{strict total order} or \emph{strict linear order.}
  90. \end{defn}
  92. \begin{ex}
  93. $\le$ is the linear order corresponding to the strict linear
  94. order~$<$. $\subseteq$ is the partial order corresponding to the
  95. strict order~$\subsetneq$.
  96. \end{ex}
  98. Any strict order $R$ on~$A$ can be turned into a partial order by
  99. adding the diagonal $\Id{A}$, i.e., adding all the pairs~$\tuple{x,
  100. x}$. (This is called the \emph{reflexive closure} of~$R$.)
  101. Conversely, starting from a partial order, one can get a strict order
  102. by removing~$\Id{A}$. These next two results make this precise.
  104. \begin{prop}\ollabel{prop:stricttopartial}
  105. If $R$ is a strict order on~$A$, then $R^+ = R \cup \Id{A}$ is a
  106. partial order. Moreover, if $R$ is a strict linear order, then $R^+$ is
  107. a linear order.
  108. \end{prop}
  110. \begin{proof}
  111. Suppose $R$ is a strict order, i.e., $R \subseteq A^2$ and $R$ is
  112. irreflexive, asymmetric, and transitive. Let $R^+ = R \cup \Id{A}$. We
  113. have to show that $R^+$ is reflexive, anti-symmetric, and transitive.
  115. $R^+$ is clearly reflexive, since $\tuple{x, x} \in \Id{A} \subseteq
  116. R^+$ for all $x \in A$.
  118. To show $R^+$ is anti-symmetric, suppose for reductio that $R^+xy$ and
  119. $R^+yx$ but $x \neq y$. Since $\tuple{x,y} \in R \cup \Id{A}$, but
  120. $\tuple{x, y} \notin \Id{A}$, we must have $\tuple{x, y} \in R$, i.e.,
  121. $Rxy$. Similarly,~$Ryx$. But this contradicts the assumption
  122. that $R$ is asymmetric.
  124. To establish transitivity, suppose that $R^+xy$ and $R^+yz$. If both
  125. $\tuple{x, y} \in R$ and $\tuple{y,z} \in R$, then $\tuple{x, z} \in
  126. R$ since $R$~is transitive. Otherwise, either $\tuple{x, y} \in
  127. \Id{A}$, i.e., $x = y$, or $\tuple{y, z} \in \Id{A}$, i.e., $y = z$.
  128. In the first case, we have that $R^+yz$ by assumption, $x = y$, hence
  129. $R^+xz$. Similarly in the second case. In either case, $R^+xz$, thus,
  130. $R^+$ is also transitive.
  132. Concerning the ``moreover'' clause, suppose that $R$ is also connected.
  133. So for all $x \neq y$, either $Rxy$ or~$Ryx$, i.e., either
  134. $\tuple{x, y} \in R$ or $\tuple{y, x} \in R$. Since $R \subseteq R^+$,
  135. this remains true of $R^+$, so $R^+$ is connected as well.
  136. \end{proof}
  138. \begin{prop}\ollabel{prop:partialtostrict}
  139. If $R$ is a partial order on~$A$, then $R^- = R \setminus \Id{A}$ is a
  140. strict order. Moreover, if $R$ is a linear order, then $R^-$ is a strict
  141. linear order.
  142. \end{prop}
  144. \begin{proof}
  145. This is left as an exercise.
  146. \end{proof}
  148. \begin{prob}
  149. Give a proof of \olref[sfr][rel][ord]{prop:partialtostrict}.
  150. \end{prob}
  152. The following simple result establishes that strict linear orders
  153. satisfy an extensionality-like property:
  155. \begin{prop}\ollabel{prop:extensionality-strictlinearorders}
  156. If $<$ is a strict linear order on $A$, then:
  157. \[
  158. (\forall a, b \in A)((\forall x \in A)(x < a \liff x < b) \lif a = b).
  159. \]
  160. \end{prop}
  162. \begin{proof}
  163. Suppose $(\forall x \in A)(x < a \liff x < b)$. If $a < b$, then $a <
  164. a$, contradicting the fact that $<$ is irreflexive; so $a \nless b$.
  165. Exactly similarly, $b \nless a$. So $a = b$, as $<$ is connected.
  166. \end{proof}
  168. \end{document}

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

77 lines; SHA-256 1f94c1032eaedb73b1de69e6f010b8e0c7437fe240ab280583ff358896fa4b27. Open the preserved source file.

  1. % Part: sets-functions-relations
  2. % Chapter: relations
  3. % Section: reflections
  4. %
  5. \documentclass[../../../include/open-logic-section]{subfiles}
  7. \begin{document}
  9. \olfileid{sfr}{rel}{ref}
  10. \olsection{Philosophical Reflections}
  12. In \olref[set]{sec}, we defined relations as certain sets. We should
  13. pause and ask a quick philosophical question: what is such a
  14. definition \emph{doing}? It is extremely doubtful that we should want
  15. to say that we have \emph{discovered} some metaphysical identity
  16. facts; that, for example, the order relation on $\Nat$ \emph{turned
  17. out} to be the set $R= \Setabs{\tuple{n,m}}{n, m \in \Nat\text{ and }
  18. n < m}$ that we defined in \olref[set]{sec}. Here are three
  19. reasons why.
  21. First: in \olref[set][pai]{wienerkuratowski}, we defined $\tuple{a, b} =
  22. \{\{a\}, \{a, b\}\}$. Consider instead the definition $\lVert a,
  23. b\rVert = \{\{b\}, \{a, b\}\} = \tuple{b,a}$. When $a \neq b$, we have
  24. that $\tuple{a, b} \neq \lVert a,b\rVert$. But we could equally have
  25. regarded $\lVert a,b\rVert$ as our definition of an ordered pair,
  26. rather than $\tuple{a,b}$. Both definitions would have worked equally
  27. well. So now we have two equally good candidates to ``be'' the order
  28. relation on the natural numbers, namely:
  29. \begin{align*}
  30. R &= \Setabs{\tuple{n,m}}{n, m \in \Nat \text{ and }n < m}\\
  31. S &= \Setabs{\lVert n,m\rVert}{n, m \in \Nat \text{ and }n < m}.
  32. \end{align*}
  33. Since $R \neq S$, by extensionality, it is clear that they cannot
  34. \emph{both} be identical to the order relation on~$\Nat$. But it would
  35. just be arbitrary, and hence a bit embarrassing, to claim that $R$
  36. rather than $S$ (or vice versa) \emph{is} the ordering relation, as a
  37. matter of fact. (This is a very simple instance of an argument against
  38. set-theoretic reductionism which Benacerraf made famous in
  39. \citeyear{Benacerraf1965}. We will revisit it several times.)
  41. Second: if we think that \emph{every} relation should be identified
  42. with a set, then the relation of set-membership itself, $\in$, should
  43. be a particular set. Indeed, it would have to be the set
  44. $\Setabs{\tuple{x,y}}{x \in y}$. But does this set exist? Given
  45. Russell's Paradox, it is a non-trivial claim that such a set exists.
  46. In fact, \oliflabeldef{cumul:::part}{the theory of sets which we develop in
  47. \olref[cumul][][]{part} will \emph{deny} the existence of this
  48. set.\footnote{Skipping ahead, here is why. For reductio, suppose $I =
  49. \Setabs{\tuple{x,y}}{x \in y}$ exists. Then $\bigcup \bigcup I$ is the
  50. universal set, contradicting
  51. \olref[sfr][z][sep]{thm:NoUniversalSet}.}}{it is possible to
  52. develop set theory in a rigorous way as an axiomatic theory, and that
  53. theory will indeed deny the existence of this set.}
  54. So, even if some relations can be treated as sets, the relation of
  55. set-membership will have to be a special case.
  57. Third: when we ``identify'' relations with sets, we said that we would
  58. allow ourselves to write $Rxy$ for $\tuple{x,y} \in R$. This is fine,
  59. provided that the membership relation, ``$\in$'', is treated \emph{as}
  60. a predicate. But if we think that ``$\in$'' stands for a certain kind
  61. of set, then the expression ``$\tuple{x,y} \in R$'' just consists of
  62. three singular terms which stand for sets: ``$\tuple{x,y}$'',
  63. ``$\in$'', and ``$R$''. And such a list of names is no more capable of
  64. expressing a proposition than the nonsense string: ``the cup penholder
  65. the table''. Again, even if some relations can be treated as sets, the
  66. relation of set-membership must be a special case. (This rolls
  67. together a simple version of Frege's concept \emph{horse} paradox, and
  68. a famous objection that Wittgenstein once raised against Russell.)
  70. So where does this leave us? Well, there is nothing \emph{wrong} with
  71. our saying that the relations on the numbers are sets. We just have to
  72. understand the spirit in which that remark is made. We are not stating
  73. a metaphysical identity fact. We are simply noting that, in certain
  74. contexts, we can (and will) \emph{treat} (certain) relations as
  75. certain sets.
  77. \end{document}

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

125 lines; SHA-256 412c6fa44ead94f076dfea7cd23f9e3cd748b08c1882dcb129b15f8efcf5c29c. Open the preserved source file.

  1. % Part: sets-functions-relations
  2. % Chapter: relations
  3. % Section: relations-as-sets
  5. \documentclass[../../../include/open-logic-section]{subfiles}
  7. \begin{document}
  9. \olfileid{sfr}{rel}{set}
  10. \olsection{Relations as Sets}
  12. \begin{explain}
  13. In \olref[sfr][set][imp]{sec}, we mentioned some important sets:
  14. $\Nat$, $\Int$, $\Rat$, $\Real$. You will no doubt remember some
  15. interesting relations between the !!{element}s of some of these sets.
  16. For instance, each of these sets has a completely standard \emph{order
  17. relation} on it. There is also the relation \emph{is identical with}
  18. that every object bears to itself and to no other thing. There are
  19. many more interesting relations that we'll encounter, and even more
  20. possible relations. Before we review them, though, we will start by
  21. pointing out that we can look at relations as a special sort of set.
  23. For this, recall two things from \olref[sfr][set][pai]{sec}. First,
  24. recall the notion of an \emph{ordered pair}: given $a$ and $b$, we can
  25. form~$\tuple{a, b}$. Importantly, the order of elements \emph{does}
  26. matter here. So if $a \neq b$ then $\tuple{a, b} \neq \tuple{b, a}$.
  27. (Contrast this with unordered pairs, i.e., $2$-element sets, where
  28. $\{a, b\}=\{b, a\}$.) Second, recall the notion of a \emph{Cartesian
  29. product}: if $A$ and $B$ are sets, then we can form~$A \times B$, the
  30. set of all pairs $\tuple{x, y}$ with $x \in A$ and $y \in B$. In
  31. particular, $A^{2}= A \times A$ is the set of all ordered pairs
  32. from~$A$.
  34. Now we will consider a particular relation on a set: the $<$-relation
  35. on the set~$\Nat$ of natural numbers. Consider the set of all pairs of
  36. numbers $\tuple{n, m}$ where $n<m$, i.e.,
  37. \[
  38. R=\Setabs{\tuple{n, m}}{n, m \in \Nat \text{ and } n<m}.
  39. \]
  40. There is a close connection between $n$ being less than $m$, and the
  41. pair $\tuple{n, m}$ being a member of $R$, namely:
  42. \[
  43. n<m\text{ iff }\tuple{n, m} \in R.
  44. \]
  45. Indeed, without any loss of information, we can consider the set $R$
  46. to \emph{be} the $<$-relation on $\Nat$.
  48. In the same way we can construct a subset of $\Nat^{2}$ for any
  49. relation between numbers. Conversely, given any set of pairs of
  50. numbers $S \subseteq \Nat^{2}$, there is a corresponding relation
  51. between numbers, namely, the relationship $n$ bears to $m$ if and only
  52. if $\tuple{n, m} \in S$. This justifies the following definition:
  53. \end{explain}
  55. \begin{defn}[Binary relation]
  56. A \emph{binary relation} on a set $A$ is a subset of~$A^{2}$. If $R
  57. \subseteq A^{2}$ is a binary relation on~$A$ and $x, y \in A$, we
  58. sometimes write $Rxy$ (or $xRy$) for $\tuple{x, y} \in R$.
  59. \end{defn}
  61. \begin{ex}
  62. \ollabel{relations}
  63. The set $\Nat^{2}$ of pairs of natural numbers can be listed in a
  64. 2-dimensional matrix like this:
  65. \[
  66. \begin{array}{ccccc}
  67. \mathbf{\tuple{ 0,0 }} & \tuple{ 0,1 } &
  68. \tuple{ 0,2 } & \tuple{ 0,3 } & \ldots\\
  69. \tuple{ 1,0 } & \mathbf{\tuple{ 1,1 }} &
  70. \tuple{ 1,2 } & \tuple{ 1,3 } & \ldots\\
  71. \tuple{ 2,0 } & \tuple{ 2,1 } &
  72. \mathbf{\tuple{ 2,2 }} & \tuple{ 2,3 } & \ldots\\
  73. \tuple{ 3,0 } & \tuple{ 3,1 } & \tuple{ 3,2 } &
  74. \mathbf{\tuple{ 3,3 }} & \ldots\\
  75. \vdots & \vdots & \vdots & \vdots & \mathbf{\ddots}
  76. \end{array}
  77. \]
  78. We have put the diagonal, here, in bold, since the subset of $\Nat^2$
  79. consisting of the pairs lying on the diagonal, i.e.,
  80. \[
  81. \{\tuple{0,0 }, \tuple{ 1,1 }, \tuple{ 2,2 }, \dots\},
  82. \]
  83. is the \emph{identity relation on}~$\Nat$. (Since the identity
  84. relation is popular, let's define $\Id{A}=\Setabs{\tuple{ x,x }}{x \in
  85. A}$ for any set $A$.) The subset of all pairs lying above the
  86. diagonal, i.e.,
  87. \[
  88. L = \{\tuple{ 0,1 },\tuple{ 0,2 },\ldots,\tuple{ 1,2 },
  89. \tuple{ 1,3 }, \dots, \tuple{ 2,3 }, \tuple{ 2,4 },\ldots\},
  90. \]
  91. is the \emph{less than} relation, i.e., $Lnm$ iff $n<m$. The subset of
  92. pairs below the diagonal, i.e.,
  93. \[
  94. G=\{ \tuple{ 1,0 },\tuple{ 2,0 },\tuple{
  95. 2,1 }, \tuple{ 3,0 },\tuple{ 3,1 },\tuple{ 3,2 }, \dots\},
  96. \]
  97. is the \emph{greater than} relation, i.e., $Gnm$ iff $n>m$. The union
  98. of $L$ with $I$, which we might call $K=L\cup I$, is the \emph{less
  99. than or equal to} relation: $Knm$ iff $n \le m$. Similarly, $H=G \cup
  100. I$ is the \emph{greater than or equal to relation.} These relations
  101. $L$, $G$, $K$, and $H$ are special kinds of relations called
  102. \emph{orders}. $L$ and $G$ have the property that no number bears $L$
  103. or $G$ to itself (i.e., for all $n$, neither $Lnn$ nor $Gnn$).
  104. Relations with this property are called \emph{irreflexive}, and, if
  105. they also happen to be orders, they are called \emph{strict orders.}
  106. \end{ex}
  108. \begin{explain}
  109. Although orders and identity are important and natural relations, it
  110. should be emphasized that according to our definition \emph{any}
  111. subset of $A^{2}$ is a relation on~$A$, regardless of how unnatural or
  112. contrived it seems. In particular, $\emptyset$ is a relation on any
  113. set (the \emph{empty relation}, which no pair of elements bears), and
  114. $A^{2}$~itself is a relation on~$A$ as well (one which every pair
  115. bears), called the \emph{universal relation}. But also something like
  116. $E=\Setabs{\tuple{n, m}}{n>5 \text{ or } m \times n \ge 34}$ counts as
  117. a relation.
  118. \end{explain}
  120. \begin{prob}
  121. List the !!{element}s of the relation $\subseteq$ on the set
  122. $\Pow{\{a, b, c\}}$.
  123. \end{prob}
  125. \end{document}

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

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

  1. % Part: sets-functions-relations
  2. % Chapter: relations-complete
  4. \documentclass[../../../include/open-logic-chapter]{subfiles}
  6. \begin{document}
  8. \olchapter{sfr}{rel}{Relations}
  10. \olimport{relations-as-sets}
  12. \olimport{reflections}
  14. \olimport{special-properties}
  16. \olimport{equivalence-relations}
  18. \olimport{orders}
  20. \olimport{graphs}
  22. \olimport{trees}
  24. \olimport{operations}
  26. \OLEndChapterHook
  28. \end{document}

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

85 lines; SHA-256 f9bdfcb4c680ea58fdb209f0347c2f8055de96558caf69a26ec3ce8e1e7ce6a1. Open the preserved source file.

  1. % Part: sets-functions-relations
  2. % Chapter: relations
  3. % Section: special-properties
  5. \documentclass[../../../include/open-logic-section]{subfiles}
  7. \begin{document}
  9. \olfileid{sfr}{rel}{prp}
  10. \olsection{Special Properties of Relations}
  12. \begin{intro}
  13. Some kinds of relations turn out to be so common that they have been
  14. given special names. For instance, $\le$ and~$\subseteq$ both relate
  15. their respective domains (say, $\Nat$ in the case of~$\le$ and
  16. $\Pow{A}$ in the case of~$\subseteq$) in similar ways. To get at
  17. exactly how these relations are similar, and how they differ, we
  18. categorize them according to some special properties that relations
  19. can have. It turns out that (combinations of) some of these special
  20. properties are especially important: orders and equivalence relations.
  21. \end{intro}
  23. \begin{defn}[Reflexivity]
  24. A relation $R \subseteq A^2$ is \emph{reflexive} iff, for every $x \in
  25. A$, $Rxx$.
  26. \end{defn}
  28. \begin{defn}[Transitivity]
  29. A relation $R \subseteq A^2$ is \emph{transitive} iff, whenever $Rxy$
  30. and $Ryz$, then also $Rxz$.
  31. \end{defn}
  33. \begin{defn}[Symmetry]
  34. A relation~$R \subseteq A^2$ is \emph{symmetric} iff, whenever
  35. $Rxy$, then also~$Ryx$.
  36. \end{defn}
  38. \begin{defn}[Anti-symmetry]
  39. A relation~$R \subseteq A^2$ is \emph{anti-sym\-met\-ric} iff, whenever both
  40. $Rxy$ and $Ryx$, then $x=y$ (or, in other words: if $x\neq y$ then
  41. either $\lnot Rxy$ or $\lnot Ryx$).
  42. \end{defn}
  44. \begin{explain}
  45. In a symmetric relation, $Rxy$ and $Ryx$ always hold together, or
  46. neither holds. In an anti-symmetric relation, the only way for $Rxy$
  47. and $Ryx$ to hold together is if $x = y$. Note that this does not
  48. \emph{require} that $Rxy$ and $Ryx$ holds when $x = y$, only that it
  49. isn't ruled out. So an anti-symmetric relation can be reflexive, but
  50. it is not the case that every anti-symmetric relation is
  51. reflexive. Also note that being anti-symmetric and merely not being
  52. symmetric are different conditions. In fact, a relation can be both
  53. symmetric and anti-symmetric at the same time (e.g., the identity
  54. relation is).
  55. \end{explain}
  57. \begin{defn}[Connectivity]
  58. A relation $R \subseteq A^2$ is \emph{connected} if for all $x,y\in
  59. A$, if $x \neq y$, then either $Rxy$ or~$Ryx$.
  60. \end{defn}
  62. \begin{prob}
  63. Give examples of relations that are (a) reflexive and symmetric but
  64. not transitive, (b) reflexive and anti-symmetric, (c) anti-symmetric,
  65. transitive, but not reflexive, and (d) reflexive, symmetric, and
  66. transitive. Do not use relations on numbers or sets.
  67. \end{prob}
  69. \begin{defn}[Irreflexivity]
  70. A relation $R \subseteq A^2$ is called \emph{irreflexive} if, for all $x \in
  71. A$, not $Rxx$.
  72. \end{defn}
  74. \begin{defn}[Asymmetry]
  75. A relation $R \subseteq A^2$ is called \emph{asymmetric} if for no pair $x,y\in
  76. A$ we have both $Rxy$ and~$Ryx$.
  77. \end{defn}
  79. Note that if $A \neq \emptyset$, then no irreflexive relation on~$A$
  80. is reflexive and every asymmetric relation on~$A$ is also
  81. anti-symmetric. However, there are $R \subseteq A^2$ that are not
  82. reflexive and also not irreflexive, and there are anti-symmetric
  83. relations that are not asymmetric.
  85. \end{document}

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

130 lines; SHA-256 57cc56ee55506aa19e7be6129d2cad6b8635fd2d6407399d4f774782f2cdd588. Open the preserved source file.

  1. % Part: sets-functions-relations
  2. % Chapter: relations
  3. % Section: trees
  5. \documentclass[../../../include/open-logic-section]{subfiles}
  7. \begin{document}
  9. \olfileid{sfr}{rel}{tre}
  10. \olsection{Trees}
  12. A particular kind of partial order which plays an important role in
  13. all parts of logic is a \emph{tree}. Finite trees occur in elementary
  14. parts of logic: for example, !!{formula}s can be understood in terms
  15. of their decomposition into a syntax tree, while !!{derivation}s in
  16. many !!{derivation} systems also take the form of finite trees.
  17. %
  18. Infinite trees appear already in the proof of the completeness
  19. theorems for propositional and first-order logic, and are used
  20. throughout mathematical logic.
  22. The set-theoretic concept of a tree is closely related to the notion
  23. of a tree in graph theory. Here is a picture of a (finite) tree:
  25. \begin{center}
  26. \begin{tikzpicture}[nodes={draw, circle}, -]
  27. \node{$r$} [grow'=up]
  28. child { node {$a$}
  29. child { node {$c$} }
  30. child { node {$d$} }
  31. child { node {$e$} }
  32. }
  33. child { node {$b$} };
  34. \end{tikzpicture}
  35. \end{center}
  37. The lowermost node~$r$ is the root. Every node other than $r$ has
  38. exactly one parent node immediately below it. We can think of the relation
  39. a node~$x$ stands in to a node~$y$ if $y$ can be reached from~$x$ by
  40. following edges upwards as $x$ being an \emph{ancestor} of~$y$.
  42. The ancestor relation in a tree is a strict partial order. This
  43. motivates the set-theoretic definition. To state it we need two
  44. concepts. A \emph{least element} in a set~$A$ partially ordered
  45. by~$\le$ is !!a{element} $x \in A$ such that for all $y \in A$ we have
  46. that~$x \le y$. A set is \emph{well-ordered} by~$\le$ if every one of
  47. its non-empty subsets has a least element.
  49. \begin{defn}[Tree]
  50. A \emph{tree} is a pair $T = \tuple{A, \le}$ such that $A$ is a set
  51. and $\le$ is a partial order on~$A$ with a unique least element
  52. $r \in A$ (called the \emph{root}) such that for all $x \in A$,
  53. the set $\Setabs{y}{y \le x}$ is well-ordered by~$\le$.
  54. \end{defn}
  56. \begin{defn}[Successors]
  57. Suppose $T = \tuple{A, \le}$ is a tree.
  58. If $x,y \in A$, $x < y$, and there is no $z \in A$ such that
  59. $x < z < y$, then we say that $y$ is a \emph{successor} of~$x$.
  60. \end{defn}
  62. The successors of $x \in A$ are also called its \emph{children}. If
  63. $y$ is a successor of~$x$, then we call $x$ the \emph{predecessor} or
  64. \emph{parent} of~$y$.
  66. \begin{prop}
  67. If $\tuple{A,\le}$ is a tree, then every $x \in A$ other than the root
  68. has at most one predecessor.
  69. \end{prop}
  71. \begin{proof}
  72. Suppose $y_1 < x$ and $y_2 < x$ and $y_1 \neq y_2$. Then $\{y_1,
  73. y_2\} \subseteq \Setabs{z}{z<x}$. Since $\Setabs{z}{z<x}$ is
  74. well-ordered by~$\le$, its subset $\{y_1, y_2\}$ has a least
  75. element, which obviously must be either $y_1$ or~$y_2$. So either
  76. $y_1 \le y_2$ or $y_2 \le y_1$. We assumed that $y_1 \neq y_2$, so
  77. actually either $y_1 < y_2$ or $y_2 < y_1$. Since we assumed that
  78. $y_1 < x$ and $y_2 < x$, we furthermore have that either $y_1 < y_2
  79. < x$ or $y_2 < y_1 < x$. So $y_1$ and $y_2$ cannot both be
  80. predecessors of~$x$.
  81. \end{proof}
  83. \begin{defn}
  84. A tree $T = \tuple{A, \le}$ is said to be \emph{infinite} if $A$ is an
  85. infinite set, and \emph{finite} otherwise. If $T$ is such that every
  86. $x \in A$ has only finitely many successors, then we say that $T$ is
  87. \emph{finitely branching}.
  88. \end{defn}
  90. \begin{defn}[Branches]
  91. Given a tree $T = \tuple{A, \le}$, a \emph{branch} of~$T$ is a
  92. maximal chain in~$T$, i.e., a set $B \subseteq A$ such that
  93. for any $x, y \in B$ either $x \le y$ or $y \le x$, and for any
  94. $z \in X \setminus B$ there exists $u \in B$ such that neither
  95. $z \le u$ nor $u \le z$.
  96. %
  97. We use $[T]$ to denote the set of all branches of $T$.
  98. \end{defn}
  100. \begin{ex}
  101. A classic example of a finitely branching tree is the
  102. \emph{infinite binary tree} of finite sequences of $0$s and~$1$s,
  103. sometimes denoted $\{0,1\}^*$ or~$\Bin^*$, ordered by the extension
  104. relation $\sqsubseteq$ (e.g., $101 \sqsubseteq 101101$).
  105. Since any binary string can always be extended by adding
  106. a $0$ or a $1$ on the end, this tree contains infinitely
  107. many elements: every element~$s$ has exactly two successors, $s0$ and~$s1$. Its root is the empty sequence $\emptyseq$.
  108. \end{ex}
  110. \begin{ex}
  111. Slightly more generally, the set of finite sequences of natural
  112. numbers~$\Nat^*$ with the extension relation~$\sqsubseteq$ is also a
  113. tree. It is obviously not finitely branching: every $s \in \Nat^*$ has
  114. infinitely many successors~$sn$, one for every $n \in \Nat$. Every $A
  115. \subseteq \Nat^*$ which is closed under~$\sqsubseteq$ is a
  116. \emph{subtree} of~$\Nat^*$. (That is, $A$ is such that if $s \in A$
  117. and $s' \sqsubseteq s$, then also $s' \in A$.) All finite trees can be
  118. represented as finite subtrees of~$\Nat^*$.
  119. \end{ex}
  121. \begin{prop}[K\H{o}nig's lemma]
  122. If $T = \tuple{A,\le}$ is a finitely branching infinite tree,
  123. then $T$ has an infinite branch.
  124. \end{prop}
  126. A special case of K\H{o}nig's lemma widely used in computability
  127. theory, known as \emph{weak K\H{o}nig's lemma}, is the following: any
  128. infinite subtree of $\{0,1\}^*$ has an infinite branch.
  130. \end{document}