1.3 Relations · Set Theory and Logic

[1.3.1]Definition(Relation)#

A relation on a set $A$ is some subset $C \subseteq A \times A$ . We say that $x, y \in A$ are related under $C$ , denoted $xCy$ , if $(x, y) \in C$ .

[1.3.2]Example(Function as Relation)#

Note a function $f: A \to A$ determines a relation

\Gamma_f = \{(a, f(a)): a \in A\} \subseteq A \times A.

This relation is unique in that each $a \in A$ is related to precisely one element, namely $f(a)$ .

[1.3.3]Definition(Equivalence Relation)#

A relation $\sim$ on a set $A$ is said to be an equivalence relation if the following hold true.

Reflexivity. $x \sim x$ for every $x \in A$ .
Symmetry. $x \sim y \iff y \sim x$ for every $x, y \in A$ .
Transitivity. $x \sim y$ and $y \sim z \implies x \sim z$ for every $x, y, z \in A$ .

[1.3.4]Definition(Equivalence Class)#

For a set $A$ equipped with an equivalence relation $\sim$ , we may write the equivalence class of $a$ :

[a]_\sim = \{x \in A: a \sim x\}.

[1.3.5]Definition(Partition)#

A partition of some set $A$ is a set $\mathcal{E}$ such that

\bigcup_{E \in \mathcal{E}} E = A \qquad \bigcap_{E \in \mathcal{E}} E = \emptyset.

That is, $\mathcal{E}$ is a set of disjoint subsets of $A$ that, when combined, form $A$ .

[1.3.6]Theorem(Equivalence Classes Form a Partition)#

Supose $A$ is a set equipped with an equivalence relation $\sim$ . Suppose $E = [x]_\sim$ and $E' = [x']_\sim$ for some $x, x' \in A$ . $E$ and $E'$ are either disjoint or equal.

Proof.

Suppose $E \cap E' \ne 0$ , so there is some $a \in (E \cap E')$ . Then $x \sim a$ and $a \sim x'$ , so $x \sim x'$ . Thus $E \subseteq E'$ (and by symmetry, since $x \sim x'$ means $x' \sim x$ ), $E' \subseteq E$ . Thus $E = E'$ .

[1.3.7]Remark(Equivalence Relations and Partitions)#

As aforementioned, all equivalence relations partition a set. Moreover, a partition is induced by an equivalence relation. Indeed, if $\mathcal{E}$ is a partition of $A$ , we may define $\sim$ such that $x \sim y$ if and only if $x$ and $y$ belong to the same set inside $\mathcal{E}$ .

[1.3.8]Definition(Order Relation)#

A relation $C$ on a set $A$ is called an order relation (or a simple/linear order) if it has the following properties.

Comparability. If $x, y\in A$ are such that $x \ne y$ , then $xCy$ or $yCx$ .
Nonreflexivity. For any $x \in A$ , $xCx$ is false.
Transitivity. For any $x, y, z \in A$ , if $xCy$ and $yCz$ , then $xCz$ .

[1.3.9]Example(Dictionary Order Relation)#

Suppose $A, B$ are sets equipped with order relations $<_A, <_B$ . Define $<$ on $A \times B$ such that, for any $(a_1, b_1), (a_2, b_2) \in A \times B$ , it is such that

(a_1, b_1) < (a_2, b_2)

if $a_1 <_A a_2$ , or $a_1 = a_2$ and $b_1 <_B b_2$ .

[1.3.10]Definition(Greatest Lower Bound Property, Least Upper Bound Property)#

An ordered set $A$ is said to have the least upper bound property if, for any bounded $A_0 \subseteq A$ , the set of upper bounds on $A_0$ has a least element. The greatest lower bound is defined conversely.

1.3Relations