# Differences

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

 sav08:sets_and_relations [2010/02/26 22:03]vkuncak sav08:sets_and_relations [2015/04/21 17:30] Line 1: Line 1: - ====== Sets and Relations ====== - - ===== Sets ===== - - Sets are unordered collection of elements. - - We denote a finite set containing only elements $a$, $b$ and $c$ by $\{ a, b, c \}$.  The order and number of occurrences does not matter: - $\{ a, b, c \} = \{ c, a, b \} = \{ a, b, b, c \}$. - * $a \in \{ a,b,c \}$ - * $d \notin \{a,b,c\}$ iff $d \neq a \land d \neq b \land d \neq c$ - - Empty set: $\emptyset$. For every $x$ we have $x \notin \emptyset$. - - To denote large or infinite sets we can use set comprehensions:​ $\{ x.\ P(x) \}$ is set of all objects with property $P$. - $- y \in \{ x. P(x) \} \ \leftrightarrow\ P(y) -$ - - 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: - $- \{a \} \cup \{ f(a,b) \mid P(a,b) \} -$ - 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$ - - $- A \cup B = \{ x. x \in A \lor x \in B \} -$ - $- A \cap B = \{ x. x \in A \land x \in B \} -$ - $- A \setminus B = \{ x. x \in A \land x \notin B \} -$ - - Boolean algebra of subsets of some set $U$ (we define $A^c = U \setminus A$): - * $\cup, \cap$ are associative,​ commutative,​ idempotent - * neutral and zero elements: $A \cup \emptyset = A$, $A \cap \emptyset = \emptyset$ - * absorption: $A \cup A = A$, $A \cap A = A$ - * deMorgan laws: $(A \cup B)^c = A^c \cap B^c$, $(A \cap B)^c = A^c \cup B^c$ - * complement as partition of universal set: $A \cap A^c = \emptyset$, $A \cup A^c = U$ - * double complement: $(A^c)^c = A$ - - Which axioms are sufficient? - * [[http://​citeseer.ist.psu.edu/​57459.html|William McCune: Solution of the Robbins Problem. J. Autom. Reasoning 19(3): 263-276 (1997)]] - - - - - - ==== Infinte Unions and Intersections ==== - - Note that sets can be nested. Consider, for example, the following set $S$ - $- S = \{ \{ p, \{q, r\} \}, r \} -$ - 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: - $- ​\bigcup B = \{ x.\ \exists a. a \in B \land x \in a \} -$ - As a special case, we have - $- ​\bigcup \{ a_1, a_2, a_3 \} = a_1 \cup a_2 \cup a_3 -$ - 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 - $- ​\bigcup_{i \in J} f(i) -$ - and the meaning is - $- ​\bigcup \{ f(i).\ i \in J \} -$ - 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: - $- ​\bigcap B = \{ x. \forall a. a \in B \rightarrow x \in a \} -$ - As a special case, we have - $- ​\bigcap \{ a_1, a_2, a_3 \} = a_1 \cap a_2 \cap a_3 -$ - We similarly define intersection of an infinite family - $- ​\bigcap_{i \in J} f(i) -$ - and the meaning is - $- ​\bigcap \{ f(i).\ i \in J \} -$ - Therefore, $x \in \bigcap \{ f(i).\ i \in J \}$ is equivalent to $\forall i.\ i \in J \rightarrow x \in f(i)$. - - - ===== Relations ===== - - Pairs: - $- (a,b) = (u,v) \iff (a = u \land b = v) -$ - Cartesian product: - $- A \times B = \{ (x,y) \mid x \in A \land y \in B \} -$ - - Relations $r$ is simply a subset of $A \times B$, that is $r \subseteq A \times B$. - - Note: - $- A \times (B \cap C) = (A \times B) \cap (A \times C) -$ - $- A \times (B \cup C) = (A \times B) \cup (A \times C) -$ - - === Diagonal relation === - - $\Delta_A \subseteq A \times A$, is given by - $- ​\Delta_A = \{(x,x) \mid x \in A\} -$ - - ==== Set operations ==== - - Relations are sets of pairs, so operations $\cap, \cup, \setminus$ apply. - - ==== Relation Inverse ==== - - $- r^{-1} = \{(y,x) \mid (x,y) \in r \} -$ - - ==== Relation Composition ==== - - $- r_1 \circ r_2 = \{ (x,z) \mid \exists y. (x,y) \in r_1 \land (y,z) \in r_2\} -$ - - Note: relations on a set $A$ together with relation composition and $\Delta_A$ form a //monoid// structure: - $- \begin{array}{l} - 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 - \end{array} -$ - - Moreover, - $- ​\emptyset \circ r = \emptyset = r \circ \emptyset -$ - $- r_1 \subseteq r_2 \rightarrow r_1 \circ s \subseteq r_2 \circ s -$ - $- r_1 \subseteq r_2 \rightarrow s \circ r_1 \subseteq s \circ r_2 -$ - - - - ==== Relation Image ==== - - When $S \subseteq A$ and $r \subseteq A \times A$ we define **image** of a set $S$ under relation $A$ as - $- ​S\bullet r = \{ y.\ \exists x. x \in S \land (x,y) \in r \} -$ - - - ==== Transitive Closure ==== - - Iterated composition let $r \subseteq A \times A$. - $- \begin{array}{l} - r^0 = \Delta_A \\ - r^{n+1} = r \circ r^n - \end{array} -$ - So, $r^n$ is n-fold composition of relation with itself. - - Transitive closure: - $- r^* = \bigcup_{n \geq 0} r^n -$ - - Equivalent statement: $r^*$ is equal to the least relation $s$ (with respect to $\subseteq$) that satisfies - $- \Delta_A\ \cup\ (s \circ r)\ \subseteq\ s -$ - or, equivalently,​ the least relation $s$ (with respect to $\subseteq$) that satisfies - $- \Delta_A\ \cup\ (r \circ s)\ \subseteq\ s -$ - or, equivalently,​ the least relation $s$ (with respect to $\subseteq$) that satisfies - $- \Delta_A\ \cup\ r \cup (s \circ s)\ \subseteq\ s -$ - - ==== Some Laws in Algebra of Relations ==== - - $- (r_1 \circ r_2)^{-1} = r_2^{-1} \circ r_1^{-1} -$ - $- r_1 \circ (r_2 \cup r_3) = (r_1 \circ r_2) \cup (r_1 \circ r_3) -$ - $- (r^{-1})^{*} = (r^{*})^{-1} -$ - - Binary relation $r \subseteq A\times A$ can be represented as a directed graph $(A,r)$ with nodes $A$ and edges $r$ - * Graphical representation of $r^{-1}$, $r^{*}$, and $(r \cup r^{-1})^{*}$ - - Equivalence relation $r$ is relation with these properties: - * reflexive: $\Delta_A \subseteq r$ - * symmetric: $r^{-1} \subseteq r$ - * transitive: $r \circ r \subseteq r$ - - Equivalence classes are defined by - $- x/r = \{y \mid (x,y) \in r -$ - The set $\{ x/r \mid x \in A \}$ is a partition: - * each set non-empty - * sets are disjoint - * their union is $A$ - Conversely: each collection of sets $P$ that is a partition defines equivalence class by - $- r = \{ (x,y) \mid \exists c \in P. x \in c \land y \in c \} -$ - - Congruence: equivalence that agrees with some set of operations.  ​ - - Partial orders: - * reflexive - * antisymmetric:​ $r \cap r^{-1} \subseteq \Delta_A$ - * transitive - - ===== Functions ===== - - **Example:​** an example function $f : A \to B$ for $A = \{a,b,c\}$, $B=\{1,​2,​3\}$ is - $- f = \{ (a,3), (b,2), (c,3) \} -$ - - Definition of function, injectivity,​ surjectivity. - - - $2^B = \{ A \mid A \subseteq B \}$ - - $(A \to B) = B^A$ - the set of all functions from $A$ to $B$.  For $|B|>2$ it is a strictly bigger set than $B$. - - $(A \to B \to C) = (A \to (B \to C))$ (think of exponentiation on numbers) - - Note that $A \to B \to C$ is [[isomorphism|isomorphic]] to $A \times B \to C$, they are two ways of representing functions with two arguments. ​ $(C^B)^A = C^{B \times A}$ - - There is also isomorphism between ​ - * n-tuples $(x_1,​\ldots,​x_n) \in A^n$ and - * functions $f : \{1,​\ldots,​n\} \to A$, where $f = \{(1,​x_1),​\ldots,​(n,​x_n) \}$ - - ==== Function update ===== - - 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, - $- f[a_0 \mapsto b_0](x) = \left\{\begin{array}{l} - b_0, \mbox{ if } x=a_0 \\ - f(x), \mbox{ if } x \neq a_0 -$ - - ==== Domain and Range of Relations and Functions ==== - - For relation $r \subseteq A \times B$ we define domain and range of $r$: - $- dom(r) = \{ x.\ \exists y. (x,y) \in r \} -$ - $- ran(r) = \{ y.\ \exists x. (x,y) \in r \} -$ - Clearly, $dom(r) \subseteq A$ and $ran(r) \subseteq B$. - - - ==== Partial Function ==== - - Notation: $\exists^{\leq 1} x. P(x)$ means $\forall x. \forall y. (P(x) \land P(y))\rightarrow x=y$. - - **Partial function** $f : A \hookrightarrow B$ is relation $f \subseteq A \times B$ such that - $- \forall x \in A. \exists^{\le 1} y.\ (x,y)\in f -$ - - Generalization of function update is override of partial functions, $f \oplus g$ - - - - - - ==== Range, Image, and Composition ==== - - The following properties follow from the definitions:​ - $- (S \bullet r_1) \bullet r_2 = S \bullet (r_1 \circ r_2) -$ - $- S \bullet r = ran(\Delta_S \circ r) -$ - - ===== Further references ===== - - * [[sav08:​discrete_mathematics_by_rosen|Discrete Mathematics by Rosen]] - * [[:Gallier Logic Book]], Chapter 2