# Differences

This shows you the differences between two versions of the page.

 sav08:sets_and_relations [2009/03/10 20:29]vkuncak sav08:sets_and_relations [2015/04/21 17:30] (current) Both sides previous revision Previous revision 2010/02/26 22:03 vkuncak 2010/02/26 21:56 vkuncak 2009/03/10 20:29 vkuncak 2009/03/10 20:29 vkuncak 2009/03/10 20:27 vkuncak 2009/03/10 14:13 vkuncak 2009/03/10 14:13 vkuncak 2009/03/10 14:02 vkuncak 2009/03/10 13:58 vkuncak 2009/03/10 13:57 vkuncak 2009/03/10 13:52 vkuncak 2009/03/04 17:03 vkuncak 2009/03/04 17:02 vkuncak 2009/03/04 17:02 vkuncak 2009/03/04 17:01 vkuncak 2009/03/04 16:57 vkuncak 2009/03/04 11:02 vkuncak 2009/03/04 10:25 vkuncak 2009/02/25 19:36 vkuncak 2009/02/25 13:17 vkuncak 2009/02/25 13:16 vkuncak 2009/02/25 13:12 vkuncak 2009/02/25 10:12 vkuncak 2009/02/25 10:11 vkuncak 2009/02/25 09:57 vkuncak 2009/02/25 09:57 vkuncak 2009/02/25 09:52 vkuncak 2009/02/25 09:47 vkuncak 2009/02/25 09:46 vkuncak Next revision Previous revision 2010/02/26 22:03 vkuncak 2010/02/26 21:56 vkuncak 2009/03/10 20:29 vkuncak 2009/03/10 20:29 vkuncak 2009/03/10 20:27 vkuncak 2009/03/10 14:13 vkuncak 2009/03/10 14:13 vkuncak 2009/03/10 14:02 vkuncak 2009/03/10 13:58 vkuncak 2009/03/10 13:57 vkuncak 2009/03/10 13:52 vkuncak 2009/03/04 17:03 vkuncak 2009/03/04 17:02 vkuncak 2009/03/04 17:02 vkuncak 2009/03/04 17:01 vkuncak 2009/03/04 16:57 vkuncak 2009/03/04 11:02 vkuncak 2009/03/04 10:25 vkuncak 2009/02/25 19:36 vkuncak 2009/02/25 13:17 vkuncak 2009/02/25 13:16 vkuncak 2009/02/25 13:12 vkuncak 2009/02/25 10:12 vkuncak 2009/02/25 10:11 vkuncak 2009/02/25 09:57 vkuncak 2009/02/25 09:57 vkuncak 2009/02/25 09:52 vkuncak 2009/02/25 09:47 vkuncak 2009/02/25 09:46 vkuncak 2009/02/25 09:43 vkuncak 2009/02/25 09:42 vkuncak 2009/02/25 09:41 vkuncak 2009/02/22 17:03 vkuncak 2009/02/22 17:01 vkuncak 2009/02/22 16:59 vkuncak 2009/02/22 16:58 vkuncak 2009/02/22 16:57 vkuncak 2009/02/22 16:53 vkuncak 2009/02/22 16:51 vkuncak 2009/02/22 16:51 vkuncak 2009/02/18 10:19 vkuncak 2009/02/18 10:18 vkuncak 2009/02/18 10:17 vkuncak 2009/02/18 10:17 vkuncak 2008/03/05 20:59 vkuncak 2008/03/05 20:57 vkuncak 2008/03/05 20:56 vkuncak 2008/03/05 15:29 vkuncak 2008/03/05 15:29 vkuncak 2008/03/05 15:24 vkuncak 2008/02/26 17:59 vkuncak Line 13: Line 13: To denote large or infinite sets we can use set comprehensions:​ $\{ x.\ P(x) \}$ is set of all objects with property $P$. To denote large or infinite sets we can use set comprehensions:​ $\{ x.\ P(x) \}$ is set of all objects with property $P$. - $+ \begin{equation*} y \in \{ x. P(x) \} \ \leftrightarrow\ P(y) y \in \{ x. P(x) \} \ \leftrightarrow\ P(y) -$ + \end{equation*} Notation for set comprehension:​ $\{ f(x)|x. P(x) \} = \{ y. (\exists x. y=f(x) \land P(x)) \}$ Notation for set comprehension:​ $\{ f(x)|x. P(x) \} = \{ y. (\exists x. y=f(x) \land P(x)) \}$ Sometimes the binder $x$ can be inferred from context so we write simply $\{ f(x) | P(x) \}$.  In general there is ambiguity in which variables are bound. (Example: what does the $a$ in $f(a,b)$ refer to in the expression: Sometimes the binder $x$ can be inferred from context so we write simply $\{ f(x) | P(x) \}$.  In general there is ambiguity in which variables are bound. (Example: what does the $a$ in $f(a,b)$ refer to in the expression: - $+ \begin{equation*} \{a \} \cup \{ f(a,b) \mid P(a,b) \} \{a \} \cup \{ f(a,b) \mid P(a,b) \} -$ + \end{equation*} does it refer to the outerone $a$ as in $\{a\}$ or is it a newly bound variable? The notation with dot and bar resolves this ambiguity. does it refer to the outerone $a$ as in $\{a\}$ or is it a newly bound variable? The notation with dot and bar resolves this ambiguity. Subset: $A \subseteq B$ means $\forall x. x \in A \rightarrow x \in B$ Subset: $A \subseteq B$ means $\forall x. x \in A \rightarrow x \in B$ - $+ \begin{equation*} A \cup B = \{ x. x \in A \lor x \in B \} A \cup B = \{ x. x \in A \lor x \in B \} -$ + \end{equation*} - $+ \begin{equation*} A \cap B = \{ x. x \in A \land x \in B \} A \cap B = \{ x. x \in A \land x \in B \} -$ + \end{equation*} - $+ \begin{equation*} A \setminus B = \{ x. x \in A \land x \notin B \} A \setminus B = \{ x. x \in A \land x \notin B \} -$ + \end{equation*} Boolean algebra of subsets of some set $U$ (we define $A^c = U \setminus A$): Boolean algebra of subsets of some set $U$ (we define $A^c = U \setminus A$): Line 55: Line 55: Note that sets can be nested. Consider, for example, the following set $S$ Note that sets can be nested. Consider, for example, the following set $S$ - $+ \begin{equation*} S = \{ \{ p, \{q, r\} \}, r \} S = \{ \{ p, \{q, r\} \}, r \} -$ + \end{equation*} This set has two elements. The first element is another set. We have $\{ p, \{q, r\} \} \in S$. Note that it is not the case that This set has two elements. The first element is another set. We have $\{ p, \{q, r\} \} \in S$. Note that it is not the case that Suppose that we have a set $B$ that contains other sets.  We define union of the sets contained in $B$ as follows: Suppose that we have a set $B$ that contains other sets.  We define union of the sets contained in $B$ as follows: - $+ \begin{equation*} ​\bigcup B = \{ x.\ \exists a. a \in B \land x \in a \} ​\bigcup B = \{ x.\ \exists a. a \in B \land x \in a \} -$ + \end{equation*} As a special case, we have As a special case, we have - $+ \begin{equation*} ​\bigcup \{ a_1, a_2, a_3 \} = a_1 \cup a_2 \cup a_3 ​\bigcup \{ a_1, a_2, a_3 \} = a_1 \cup a_2 \cup a_3 -$ + \end{equation*} Often the elements of the set $B$ are computed by a set comprehension of the form $B = \{ f(i).\ i \in J \}$. Often the elements of the set $B$ are computed by a set comprehension of the form $B = \{ f(i).\ i \in J \}$. We then write We then write - $+ \begin{equation*} ​\bigcup_{i \in J} f(i) ​\bigcup_{i \in J} f(i) -$ + \end{equation*} and the meaning is and the meaning is - $+ \begin{equation*} ​\bigcup \{ f(i).\ i \in J \} ​\bigcup \{ f(i).\ i \in J \} -$ + \end{equation*} Therefore, $x \in \bigcup \{ f(i).\ i \in J \}$ is equivalent to $\exists i.\ i \in J \land x \in f(i)$. Therefore, $x \in \bigcup \{ f(i).\ i \in J \}$ is equivalent to $\exists i.\ i \in J \land x \in f(i)$. We analogously define intersection of elements in the set: We analogously define intersection of elements in the set: - $+ \begin{equation*} ​\bigcap B = \{ x. \forall a. a \in B \rightarrow x \in a \} ​\bigcap B = \{ x. \forall a. a \in B \rightarrow x \in a \} -$ + \end{equation*} As a special case, we have As a special case, we have - $+ \begin{equation*} ​\bigcap \{ a_1, a_2, a_3 \} = a_1 \cap a_2 \cap a_3 ​\bigcap \{ a_1, a_2, a_3 \} = a_1 \cap a_2 \cap a_3 -$ + \end{equation*} We similarly define intersection of an infinite family We similarly define intersection of an infinite family - $+ \begin{equation*} ​\bigcap_{i \in J} f(i) ​\bigcap_{i \in J} f(i) -$ + \end{equation*} and the meaning is and the meaning is - $+ \begin{equation*} ​\bigcap \{ f(i).\ i \in J \} ​\bigcap \{ f(i).\ i \in J \} -$ + \end{equation*} Therefore, $x \in \bigcap \{ f(i).\ i \in J \}$ is equivalent to $\forall i.\ i \in J \rightarrow x \in f(i)$. Therefore, $x \in \bigcap \{ f(i).\ i \in J \}$ is equivalent to $\forall i.\ i \in J \rightarrow x \in f(i)$. Line 101: Line 101: Pairs: Pairs: - $+ \begin{equation*} (a,b) = (u,v) \iff (a = u \land b = v) (a,b) = (u,v) \iff (a = u \land b = v) -$ + \end{equation*} Cartesian product: Cartesian product: - $+ \begin{equation*} A \times B = \{ (x,y) \mid x \in A \land y \in B \} A \times B = \{ (x,y) \mid x \in A \land y \in B \} -$ + \end{equation*} Relations $r$ is simply a subset of $A \times B$, that is $r \subseteq A \times B$. Relations $r$ is simply a subset of $A \times B$, that is $r \subseteq A \times B$. Note: Note: - $+ \begin{equation*} A \times (B \cap C) = (A \times B) \cap (A \times C) A \times (B \cap C) = (A \times B) \cap (A \times C) -$ + \end{equation*} - $+ \begin{equation*} A \times (B \cup C) = (A \times B) \cup (A \times C) A \times (B \cup C) = (A \times B) \cup (A \times C) -$ + \end{equation*} === Diagonal relation === === Diagonal relation === $\Delta_A \subseteq A \times A$, is given by $\Delta_A \subseteq A \times A$, is given by - $+ \begin{equation*} ​\Delta_A = \{(x,x) \mid x \in A\} ​\Delta_A = \{(x,x) \mid x \in A\} -$ + \end{equation*} ==== Set operations ==== ==== Set operations ==== Line 132: Line 132: ==== Relation Inverse ==== ==== Relation Inverse ==== - $+ \begin{equation*} r^{-1} = \{(y,x) \mid (x,y) \in r \} r^{-1} = \{(y,x) \mid (x,y) \in r \} -$ + \end{equation*} ==== Relation Composition ==== ==== Relation Composition ==== - $+ \begin{equation*} r_1 \circ r_2 = \{ (x,z) \mid \exists y. (x,y) \in r_1 \land (y,z) \in r_2\} r_1 \circ r_2 = \{ (x,z) \mid \exists y. (x,y) \in r_1 \land (y,z) \in r_2\} -$ + \end{equation*} Note: relations on a set $A$ together with relation composition and $\Delta_A$ form a //monoid// structure: Note: relations on a set $A$ together with relation composition and $\Delta_A$ form a //monoid// structure: - $+ \begin{equation*} \begin{array}{l} \begin{array}{l} r_1 \circ (r_2 \circ r_3) = (r_1 \circ r_2) \circ r_3 \\ r_1 \circ (r_2 \circ r_3) = (r_1 \circ r_2) \circ r_3 \\ r \circ \Delta_A = r = \Delta_A \circ r r \circ \Delta_A = r = \Delta_A \circ r \end{array} \end{array} -$ + \end{equation*} Moreover, Moreover, - $+ \begin{equation*} ​\emptyset \circ r = \emptyset = r \circ \emptyset ​\emptyset \circ r = \emptyset = r \circ \emptyset -$ + \end{equation*} - $+ \begin{equation*} r_1 \subseteq r_2 \rightarrow r_1 \circ s \subseteq r_2 \circ s r_1 \subseteq r_2 \rightarrow r_1 \circ s \subseteq r_2 \circ s -$ + \end{equation*} - $+ \begin{equation*} r_1 \subseteq r_2 \rightarrow s \circ r_1 \subseteq s \circ r_2 r_1 \subseteq r_2 \rightarrow s \circ r_1 \subseteq s \circ r_2 -$ + \end{equation*} Line 166: Line 166: When $S \subseteq A$ and $r \subseteq A \times A$ we define **image** of a set $S$ under relation $A$ as When $S \subseteq A$ and $r \subseteq A \times A$ we define **image** of a set $S$ under relation $A$ as - $+ \begin{equation*} ​S\bullet r = \{ y.\ \exists x. x \in S \land (x,y) \in r \} ​S\bullet r = \{ y.\ \exists x. x \in S \land (x,y) \in r \} -$ + \end{equation*} Line 174: Line 174: Iterated composition let $r \subseteq A \times A$. Iterated composition let $r \subseteq A \times A$. - $+ \begin{equation*} \begin{array}{l} \begin{array}{l} r^0 = \Delta_A \\ r^0 = \Delta_A \\ r^{n+1} = r \circ r^n r^{n+1} = r \circ r^n \end{array} \end{array} -$ + \end{equation*} So, $r^n$ is n-fold composition of relation with itself. So, $r^n$ is n-fold composition of relation with itself. Transitive closure: Transitive closure: - $+ \begin{equation*} r^* = \bigcup_{n \geq 0} r^n r^* = \bigcup_{n \geq 0} r^n -$ + \end{equation*} Equivalent statement: $r^*$ is equal to the least relation $s$ (with respect to $\subseteq$) that satisfies Equivalent statement: $r^*$ is equal to the least relation $s$ (with respect to $\subseteq$) that satisfies - $+ \begin{equation*} \Delta_A\ \cup\ (s \circ r)\ \subseteq\ s \Delta_A\ \cup\ (s \circ r)\ \subseteq\ s -$ + \end{equation*} or, equivalently,​ the least relation $s$ (with respect to $\subseteq$) that satisfies or, equivalently,​ the least relation $s$ (with respect to $\subseteq$) that satisfies - $+ \begin{equation*} \Delta_A\ \cup\ (r \circ s)\ \subseteq\ s \Delta_A\ \cup\ (r \circ s)\ \subseteq\ s -$ + \end{equation*} or, equivalently,​ the least relation $s$ (with respect to $\subseteq$) that satisfies or, equivalently,​ the least relation $s$ (with respect to $\subseteq$) that satisfies - $+ \begin{equation*} \Delta_A\ \cup\ r \cup (s \circ s)\ \subseteq\ s \Delta_A\ \cup\ r \cup (s \circ s)\ \subseteq\ s -$ + \end{equation*} ==== Some Laws in Algebra of Relations ==== ==== Some Laws in Algebra of Relations ==== - $+ \begin{equation*} (r_1 \circ r_2)^{-1} = r_2^{-1} \circ r_1^{-1} (r_1 \circ r_2)^{-1} = r_2^{-1} \circ r_1^{-1} -$ + \end{equation*} ​ - $+ \begin{equation*} r_1 \circ (r_2 \cup r_3) = (r_1 \circ r_2) \cup (r_1 \circ r_3) r_1 \circ (r_2 \cup r_3) = (r_1 \circ r_2) \cup (r_1 \circ r_3) -$ + \end{equation*} - $+ \begin{equation*} (r^{-1})^{*} = (r^{*})^{-1} (r^{-1})^{*} = (r^{*})^{-1} -$ + \end{equation*} Binary relation $r \subseteq A\times A$ can be represented as a directed graph $(A,r)$ with nodes $A$ and edges $r$ Binary relation $r \subseteq A\times A$ can be represented as a directed graph $(A,r)$ with nodes $A$ and edges $r$ Line 221: Line 221: Equivalence classes are defined by Equivalence classes are defined by - $+ \begin{equation*} x/r = \{y \mid (x,y) \in r x/r = \{y \mid (x,y) \in r -$ + \end{equation*} The set $\{ x/r \mid x \in A \}$ is a partition: The set $\{ x/r \mid x \in A \}$ is a partition: * each set non-empty * each set non-empty Line 229: Line 229: * their union is $A$ * their union is $A$ Conversely: each collection of sets $P$ that is a partition defines equivalence class by Conversely: each collection of sets $P$ that is a partition defines equivalence class by - $+ \begin{equation*} r = \{ (x,y) \mid \exists c \in P. x \in c \land y \in c \} r = \{ (x,y) \mid \exists c \in P. x \in c \land y \in c \} -$ + \end{equation*} Congruence: equivalence that agrees with some set of operations.  ​ Congruence: equivalence that agrees with some set of operations.  ​ Line 243: Line 243: **Example:​** an example function $f : A \to B$ for $A = \{a,b,c\}$, $B=\{1,​2,​3\}$ is **Example:​** an example function $f : A \to B$ for $A = \{a,b,c\}$, $B=\{1,​2,​3\}$ is - $+ \begin{equation*} f = \{ (a,3), (b,2), (c,3) \} f = \{ (a,3), (b,2), (c,3) \} -$ + \end{equation*} Definition of function, injectivity,​ surjectivity. Definition of function, injectivity,​ surjectivity. Line 265: Line 265: Function update operator takes a function $f : A \to B$ and two values $a_0 \in A$, $b_0 \in B$ and creates a new function $f[a_0 \mapsto b_0]$ that behaves like $f$ in all points except at $a_0$, where it has value $b_0$. ​ Formally, Function update operator takes a function $f : A \to B$ and two values $a_0 \in A$, $b_0 \in B$ and creates a new function $f[a_0 \mapsto b_0]$ that behaves like $f$ in all points except at $a_0$, where it has value $b_0$. ​ Formally, - $+ \begin{equation*} f[a_0 \mapsto b_0](x) = \left\{\begin{array}{l} f[a_0 \mapsto b_0](x) = \left\{\begin{array}{l} b_0, \mbox{ if } x=a_0 \\ b_0, \mbox{ if } x=a_0 \\ f(x), \mbox{ if } x \neq a_0 f(x), \mbox{ if } x \neq a_0 -$ + \end{equation*} ==== Domain and Range of Relations and Functions ==== ==== Domain and Range of Relations and Functions ==== For relation $r \subseteq A \times B$ we define domain and range of $r$: For relation $r \subseteq A \times B$ we define domain and range of $r$: - $+ \begin{equation*} dom(r) = \{ x.\ \exists y. (x,y) \in r \} dom(r) = \{ x.\ \exists y. (x,y) \in r \} -$ + \end{equation*} - $+ \begin{equation*} ran(r) = \{ y.\ \exists x. (x,y) \in r \} ran(r) = \{ y.\ \exists x. (x,y) \in r \} -$ + \end{equation*} Clearly, $dom(r) \subseteq A$ and $ran(r) \subseteq B$. Clearly, $dom(r) \subseteq A$ and $ran(r) \subseteq B$. Line 288: Line 288: **Partial function** $f : A \hookrightarrow B$ is relation $f \subseteq A \times B$ such that **Partial function** $f : A \hookrightarrow B$ is relation $f \subseteq A \times B$ such that - $+ \begin{equation*} \forall x \in A. \exists^{\le 1} y.\ (x,y)\in f \forall x \in A. \exists^{\le 1} y.\ (x,y)\in f -$ + \end{equation*} Generalization of function update is override of partial functions, $f \oplus g$ Generalization of function update is override of partial functions, $f \oplus g$ + Line 299: Line 300: ==== Range, Image, and Composition ==== ==== Range, Image, and Composition ==== - $+ The following properties follow from the definitions:​ - S \bullet r = ran(\Delta_S \circ r) + \begin{equation*} -$ + - $+ (S \bullet r_1) \bullet r_2 = S \bullet (r_1 \circ r_2) (S \bullet r_1) \bullet r_2 = S \bullet (r_1 \circ r_2) -$ + \end{equation*} + \begin{equation*} + S \bullet r = ran(\Delta_S \circ r) + \end{equation*} ===== Further references ===== ===== Further references ===== + * [[sav08:​discrete_mathematics_by_rosen|Discrete Mathematics by Rosen]] * [[:Gallier Logic Book]], Chapter 2 * [[:Gallier Logic Book]], Chapter 2