This is an old revision of the document!

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?

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 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

Gallier Logic Book, Chapter 2
Discrete Mathematics by Rosen