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 ,
and
by
. The order and number of occurrences does not matter:
.
iff
Empty set: . For every
we have
.
To denote large or infinite sets we can use set comprehensions: is set of all objects with property
.
\[
y \in \{ x. P(x) \} \ \leftrightarrow\ P(y)
\]
Notation for set comprehension:
Sometimes the binder can be inferred from context so we write simply
. In general there is ambiguity in which variables are bound. (Example: what does the
in
refer to in the expression:
\[
\{a \} \cup \{ f(a,b) \mid P(a,b) \}
\]
does it refer to the outerone as in
or is it a newly bound variable? The notation with dot and bar resolves this ambiguity.
Subset: means
\[
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 (we define
):
are associative, commutative, idempotent
- neutral and zero elements:
,
- absorption:
,
- deMorgan laws:
,
- complement as partition of universal set:
,
- double complement:
Which axioms are sufficient?
Infinte Unions and Intersections
Note that sets can be nested. Consider, for example, the following set
\[
S = \{ \{ p, \{q, r\} \}, r \}
\]
This set has two elements. The first element is another set. We have . Note that it is not the case that
Suppose that we have a set that contains other sets. We define union of the sets contained in
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 are computed by a set comprehension of the form
.
We then write
\[
\bigcup_{i \in J} f(i)
\] and the meaning is \[
\bigcup \{ f(i).\ i \in J \}
\]
Therefore, is equivalent to
.
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, is equivalent to
.
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 is simply a subset of
, that is
.
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
, is given by
\[
\Delta_A = \{(x,x) \mid x \in A\}
\]
Set operations
Relations are sets of pairs, so operations 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 together with relation composition and
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 and
we define image of a set
under relation
as
\[
S\bullet r = \{ y.\ \exists x. x \in S \land (x,y) \in r \}
\]
Transitive Closure
Iterated composition let .
\[
\begin{array}{l}
r^0 = \Delta_A \\ r^{n+1} = r \circ r^n
\end{array}
\]
So, is n-fold composition of relation with itself.
Transitive closure: \[
r^* = \bigcup_{n \geq 0} r^n
\]
Equivalent statement: is equal to the least relation
(with respect to
) that satisfies
\[
\Delta_A\ \cup\ (s \circ r)\ \subseteq\ s
\]
or, equivalently, the least relation (with respect to
) that satisfies
\[
\Delta_A\ \cup\ (r \circ s)\ \subseteq\ s
\]
or, equivalently, the least relation (with respect to
) 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 can be represented as a directed graph
with nodes
and edges
- Graphical representation of
,
, and
Equivalence relation is relation with these properties:
- reflexive:
- symmetric:
- transitive:
Equivalence classes are defined by \[
x/r = \{y \mid (x,y) \in r
\]
The set is a partition:
- each set non-empty
- sets are disjoint
- their union is
Conversely: each collection of sets 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:
- transitive
Functions
Example: an example function for
,
is
\[
f = \{ (a,3), (b,2), (c,3) \}
\]
Definition of function, injectivity, surjectivity.
- the set of all functions from
to
. For
it is a strictly bigger set than
.
(think of exponentiation on numbers)
Note that is isomorphic to
, they are two ways of representing functions with two arguments.
There is also isomorphism between
- n-tuples
and
- functions
, where
Function update
Function update operator takes a function and two values
,
and creates a new function
that behaves like
in all points except at
, where it has value
. 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 we define domain and range of
:
\[
dom(r) = \{ x.\ \exists y. (x,y) \in r \}
\] \[
ran(r) = \{ y.\ \exists x. (x,y) \in r \}
\]
Clearly, and
.
Partial Function
Notation: means
.
Partial function is relation
such that
\[
\forall x \in A. \exists^{\le 1} y.\ (x,y)\in f
\]
Generalization of function update is override of partial functions,
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