Week 4 - Relations, Equivalence Relations and Partial Orders (DM24, §3.3–3.5.2)

Sources

• Lecture A (Monday): what a relation is, inverse, composition, the special properties of relations, transitive closure (§3.3).
• Lecture B (Wednesday): equivalence relations, the quotient set, the construction of $\mathbb{Q}$, partial orders, Hasse diagrams and an old exam question (§3.4–3.5.2).
• Numbering follows the lecture notes (DM24 script). In the auto-generated transcript, “Konkurrenz” is a transcription error for congruence (Kongruenz) ${\equiv }_m$.

Discrepancies between lecture and script (corrected in these notes)

• Transitive closure (correction at the start of Lecture B): at the end of Lecture A, the board definition of $\bigcup \mathcal{A}$ was written wrongly. As written, it just gave back $\mathcal{A}$. The correct definition is $\bigcup \mathcal{A}=\{a\mid \exists A\in \mathcal{A}:a\in A\}$.
• The lecturer called the partition theorem “Theorem 3.1”. In the script it is Theorem 3.11.
• When he checked that $\ge$ is a partial order, he said it is “reflexive, transitive, symmetric, antisymmetric”. $\ge$ is not symmetric ($2\ge 1$ but $1\ngeqq 2$). He meant reflexive, antisymmetric and transitive.
• About divisibility he once said “we say this relation is a total order”. He meant the opposite. Divisibility is not a total order (3 and 5 are incomparable), and the rest of his explanation says so.
• In the proof of the rational-numbers lemma he said “commutativity” and corrected himself to “symmetry”.
• The $\le \circ \le$ discussion in Lecture A is garbled in the recording. It is reconstructed in §4 below: $\le \circ \le =\le$ always holds, while $<\circ <$ differs from $<$ on $\mathbb{N}$ but equals it on $\mathbb{Q}$ and $\mathbb{R}$.
• In the exam-question proof the transcript says “2 mal 3, das nennen wir 5”. It is actually (1) and (3) that give (5) by transitivity.

---

1. Executive Overview & Core Objectives

A relation (Relation) is just a set of ordered pairs, a subset of $A\times B$. All of the machinery this week follows from that one definition: inverse, composition, and the properties reflexive, symmetric, antisymmetric and transitive. Two combinations of these properties matter most. Equivalence relations (reflexive, symmetric, transitive) correspond exactly to partitions of a set and let us build new objects as quotient sets; for example, $\mathbb{Q}=(\mathbb{Z}\times (\mathbb{Z}\setminus \{0\}))/\sim$. Partial orders (reflexive, antisymmetric, transitive) model “comparison” and are drawn as Hasse diagrams.

Learning objectives. After this week you should be able to:

• State and use Def. 3.9–3.12: relation, identity relation, inverse, composition. Know the order convention of $\rho \circ \sigma$.
• Prove set identities between relations, such as Lemma 3.8 $\widehat{\rho \sigma }=\hat{\sigma }\hat{\rho }$, using chains of equivalences.
• Check, or disprove with a counterexample, each of the properties reflexive, irreflexive, symmetric, antisymmetric and transitive. Know their set-theoretic characterisations.
• Prove Lemma 3.9: $\rho$ is transitive $⟺{\rho }^2\subseteq \rho$.
• Define the transitive closure ${\rho }^{\ast }$ and use it to express “ancestor”.
• Prove that a given relation is an equivalence relation, including the case split in the $\mathbb{Q}$ construction.
• Compute equivalence classes and quotient sets. State and prove Theorem 3.11 (the classes form a partition).
• Check partial-order axioms, distinguish partial and total orders, find covers and draw Hasse diagrams.
• Solve the exam-type question “Is $\prec$ transitive?” with a full proof.

---

2. Core Concepts & Formal Definitions

2.0 Follow-up on ordered pairs (from §3.2, Example 3.1)

Ordered pair as a set

$(a,b)\stackrel{\text{def}}{=}\{\{a\},\{a,b\}\}$
With this definition, $(a,b)=(c,d)⟺a=c\wedge b=d$. Both components can be reconstructed from the set.

A student asked what goes wrong with the “simpler” definition $(a,b):=\{a,\{b\}\}$. Here is a real collision:
$(\{1\},2)=\{\{1\},\{2\}\}=\{\{2\},\{1\}\}=(\{2\},1),$
yet $\{1\}\ne \{2\}$. The first component can no longer be recovered, so this definition is unusable. With the correct definition, ordered pairs behave exactly as expected and you never need to think about the encoding again.

2.1 Relations

Definition 3.9 (Relation)

A (binary) relation $\rho$ from a set $A$ to a set $B$ (also called an $(A,B)$-relation) is a subset
$\rho \subseteq A\times B.$
If $A=B$, $\rho$ is called a relation on $A$. Instead of $(a,b)\in \rho$ we write $a\rho b$, and we write $a/\rho b$ if $(a,b)\notin \rho$.

Recall the Cartesian product (kartesisches Produkt): $A\times B=\{(a,b)\mid a\in A\wedge b\in B\}$ (Def. 3.8). A relation is itself a set, namely the set of pairs that are “related”. Not every pair needs to be in it, and which subset it is defines the relation.

Definition 3.10 (Identity relation)

For any set $A$, the identity relation (Identitätsrelation) on $A$ is
${\mathrm{id}}_A=\{(a,a)\mid a\in A\}.$

In the lecture, a student asked whether the identity relation is the same as equality. Yes: since everything is a set, “equality” means set equality, and ${\mathrm{id}}_A$ is exactly equality restricted to $A$. The lecturer prefers to write $\mathrm{id}$ rather than $=$ for the relation, so that "$=$" is never ambiguous between a set equation and a relation symbol.

Further examples from the script:

• Ex. 3.10: on $\mathbb{Z}$ we have $=,\ne ,\le ,\ge ,<,>,\mid ,\nmid$.
• Ex. 3.12: $\{(x,y)\mid x^2+y^2=1\}$ on $\mathbb{R}$ is the unit circle.
• Ex. 3.13: $\subseteq$ is a relation on $\mathcal{P}(S)$.
• Ex. 3.14: the empty relation $\varnothing$ and the complete relation $A\times B$.

Example 3.11 / Definition (Congruence modulo $m$)

For $m\in \mathbb{N}$, $m\ge 1$, the relation ${\equiv }_m$ on $\mathbb{Z}$ is
$a{\equiv }_{m}b\stackrel{\text{def}}{⟺}a-b=km\text{ for some }k\in \mathbb{Z},$
i.e. $m$ divides $a-b$, i.e. $a$ and $b$ leave the same remainder when divided by $m$. ($m=1$ is allowed but uninteresting, since then every pair is related.)

2.2 Representations of relations (§3.3.2)

There are two representations: a Boolean matrix and a directed graph.

• Matrix representation. For finite $A$ and $B$, take the $|A|\times |B|$ matrix $M^{\rho }$ with $M_{a,b}^{\rho }=1⟺a\rho b$, and $0$ otherwise. This was added at the start of Lecture B.
  • Example: $\mathrm{id}$ on $A=\{1,2,3\}$ is the identity matrix $\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]$.
  • On $\{1,\dots ,5\}$, $\le$ is the upper triangular matrix and $\ge$ the lower triangular one (Ex. 3.16).
  • Union, intersection and complement of relations are entry-wise OR, AND and NOT.
  • Inverse = transpose.
  • Composition = matrix product, after which every entry $>1$ is set back to $1$ (a Boolean product). The lecturer stressed that an ordinary integer product can produce entries $>1$, so it is “similar to but not the same as” composition until you convert back to $0/1$.
• Graph representation. Draw a directed edge $a\to b$ iff $a\rho b$. For a relation on $A$, loops $a\to a$ are allowed.

2.3 Inverse and composition

Definition 3.11 (Inverse relation)

The inverse (Umkehrrelation / inverse Relation) of a relation $\rho$ from $A$ to $B$ is the relation from $B$ to $A$
$\hat{\rho }\stackrel{\text{def}}{=}\{(b,a)\mid (a,b)\in \rho \}.$
So $b\hat{\rho }a⟺a\rho b$. An alternative notation is ${\rho }^{-1}$.

In the graph, the inverse reverses all arrows. In the matrix, it transposes.

Definition 3.12 (Composition)

Let $\rho$ be a relation from $A$ to $B$ and $\sigma$ a relation from $B$ to $C$. The composition (Komposition / Verknüpfung) $\rho \circ \sigma$ (also written $\rho \sigma$) is the relation from $A$ to $C$
$\rho \circ \sigma \stackrel{\text{def}}{=}\{(a,c)\mid \exists b\in B:(a,b)\in \rho \wedge (b,c)\in \sigma \}.$
For a relation $\rho$ on $A$, ${\rho }^n$ is the $n$-fold composition of $\rho$ with itself (${\rho }^2=\rho \circ \rho$, …).

Exam Trap: order of composition

$\rho \circ \sigma$ means first $\rho$, then $\sigma$. You read left to right, following the arrows. This is the opposite of function composition $f\circ g$ (“first $g$, then $f$”). The types must match: the target set of $\rho$ must be the source set of $\sigma$.

The lecturer pointed out that using $\exists$ (“there is some connecting middle element”) is a design choice. One could have demanded “for all middle elements” instead. The $\exists$ version has the natural reading “there is a path $a\to b\to c$”.

Lemma 3.7 (Associativity)

$\rho \circ (\sigma \circ \phi )=(\rho \circ \sigma )\circ \phi .$

This is an equality of two subsets of $A\times D$ (for $\rho :A\to B$, $\sigma :B\to C$, $\phi :C\to D$). Intuitively it means we can compose relations without worrying about brackets, just as with $+$ or $\cdot$. The lecture did not prove it; the script’s proof is in §3.

Lemma 3.8 (Inverse of a composition)

For $\rho$ from $A$ to $B$ and $\sigma$ from $B$ to $C$:
$\widehat{\rho \circ \sigma }=\hat{\sigma }\circ \hat{\rho }.$

As with inverting a product of matrices or a composition of functions, the order reverses. The lecture proved this (§3). In the script it is an exercise.

2.4 Special properties of relations on a set $A$ (§3.3.6)

Definition 3.13 (Reflexive)

$\rho$ on $A$ is reflexive (reflexiv) if $a\rho a$ for all $a\in A$, i.e.
${\mathrm{id}}_A\subseteq \rho .$
In the matrix, the diagonal is all 1s. In the graph, every vertex has a loop.

Definition 3.14 (Irreflexive)

$\rho$ is irreflexive (irreflexiv) if $a/\rho a$ for all $a\in A$, i.e.
$\rho \cap {\mathrm{id}}_A=\varnothing .$

Definition 3.15 (Symmetric)

$\rho$ is symmetric (symmetrisch) if $a\rho b⟺b\rho a$ for all $a,b\in A$, i.e.
$\rho =\hat{\rho }.$
The matrix is symmetric, and the graph can be drawn undirected.

Definition 3.16 (Antisymmetric)

$\rho$ is antisymmetric (antisymmetrisch) if $a\rho b\wedge b\rho a⟹a=b$ for all $a,b\in A$, i.e.
$\rho \cap \hat{\rho }\subseteq {\mathrm{id}}_A.$
Graph: there is no cycle of length 2 between distinct vertices.

Definition 3.17 (Transitive)

$\rho$ is transitive (transitiv) if $a\rho b\wedge b\rho c⟹a\rho c$ for all $a,b,c\in A$.
Set-theoretic equivalent (Lemma 3.9): ${\rho }^2\subseteq \rho$.

Property	Formula	Set-theoretic form	Examples	Non-examples
reflexive	$\forall a:a\rho a$	$\mathrm{id}\subseteq \rho$	$\mathrm{id}$, $\le$, $\ge$, ${\equiv }_m$, $\mid$ on $\mathbb{N}\setminus \{0\}$	$<$, $>$
irreflexive	$\forall a:\neg (a\rho a)$	$\rho \cap \mathrm{id}=\varnothing$	$<$, $>$, $\ne$	$\le$
symmetric	$\forall a,b:a\rho b\leftrightarrow b\rho a$	$\rho =\hat{\rho }$	$\mathrm{id}$, ${\equiv }_m$, “married to”	$\le$
antisymmetric	$\forall a,b:(a\rho b\wedge b\rho a)\to a=b$	$\rho \cap \hat{\rho }\subseteq \mathrm{id}$	$\le$, $\ge$, $<$, $>$, $\mid$ on $\mathbb{N}$	${\equiv }_m$, $\mid$ on $\mathbb{Z}$
transitive	$\forall a,b,c:(a\rho b\wedge b\rho c)\to a\rho c$	${\rho }^2\subseteq \rho$	$\le$, $<$, $\mid$, ${\equiv }_m$, ancestor	”knows”, parent

Exam Trap: "ir-" and "anti-" are not negations

• Not reflexive $\ne$ irreflexive. On $\{1,2\}$, $\rho =\{(1,1)\}$ is neither.
• Not symmetric $\ne$ antisymmetric. On distinct $a,b,c$, take $\rho =\{(a,a),(a,b),(a,c),(c,a)\}$. It is not symmetric, because $(a,b)\in \rho$ but $(b,a)\notin \rho$. It is not antisymmetric either, because $(a,c),(c,a)\in \rho$ but $a\ne c$. This was the lecturer’s example in Lecture B.
• Both at once is possible. ${\mathrm{id}}_A$ is symmetric and antisymmetric. So are $\varnothing$ and any relation on a one-element set.
• All four combinations occur: neither, only one, the other only, both.

Exam Trap: $<$ is antisymmetric

$a<b\wedge b<a$ is never true, so the implication in the definition is vacuously true. Equivalently, $<\cap \widehat{<}=\varnothing \subseteq \mathrm{id}$. So $<$ is irreflexive, antisymmetric and transitive, but it is not a partial order because it is not reflexive.

2.5 Transitive closure (§3.3.7)

Definition 3.18 (Transitive closure)

The transitive closure (transitiver Abschluss) of a relation $\rho$ on $A$ is
${\rho }^{\ast }={\bigcup }_{n\in \mathbb{N}\setminus \{0\}}{\rho }^n=\rho \cup {\rho }^2\cup {\rho }^3\cup \cdots$
Here $\bigcup \mathcal{A}=\{a\mid \exists A\in \mathcal{A}:a\in A\}$ for the set system $\mathcal{A}=\{{\rho }^n\mid n\ge 1\}$. This is the corrected definition from the start of Lecture B.

In the graph, $a{\rho }^{k}b$ iff there is a walk of length $k$ from $a$ to $b$. So ${\rho }^{\ast }$ is the reachability relation: $a{\rho }^{\ast }b$ iff some finite path leads from $a$ to $b$.

Points from the student questions:

• ${\rho }^0$ was deliberately not defined. If it were, it would be ${\mathrm{id}}_A$, and it is explicitly excluded from the union.
• Does ${\rho }^{\ast }$ exist? The lecturer admitted that “I cheated a bit”. That the set $\{{\rho }^n\mid n\ge 1\}$ exists (it needs an inductive definition) does not follow from the set axioms introduced so far. In effect, the definition postulates it.
• Is ${\rho }^{\ast }$ the smallest transitive relation containing $\rho$? In the lecture it was simply defined as the union, “not a limit”. It is in fact the smallest transitive superset of $\rho$; see Self-Assessment Q5.
• Ex. 3.30 (script): for convex paper polygons, “obtainable with at most one straight cut” is reflexive and antisymmetric but not transitive. Its transitive closure is the covering relation $⊒$ (“can be completely covered by”), which is a partial order.

2.6 Equivalence relations (§3.4)

Definition 3.19 (Equivalence relation)

An equivalence relation (Äquivalenzrelation) on $A$ is a relation that is reflexive, symmetric and transitive. These are usually denoted $\theta$ (the “T” hints at transitivity) or $\sim$, $\equiv$.

Definition 3.20 (Equivalence class)

For an equivalence relation $\theta$ on $A$ and $a\in A$, the equivalence class (Äquivalenzklasse) of $a$ is
$[a{]}_{\theta }\stackrel{\text{def}}{=}\{b\in A\mid b\theta a\}.$
The subscript $\theta$ may be dropped when it is clear from context.

The lecturer said “all $b$ that are related to $a$” without fixing an order. Because $\theta$ is symmetric, $b\theta a$ and $a\theta b$ are the same, so this makes no difference.

Facts:

• By reflexivity, $a\in [a{]}_{\theta }$.
• Every element of a class can serve as its representative: if $b\in [a]$ then $[b]=[a]$ (see the proof of Theorem 3.11).
• There are two trivial equivalence relations. $A\times A$ has a single class, $A$ itself. ${\mathrm{id}}_A$ has only singleton classes $\{a\}$.

Definition 3.21 (Partition)

A partition (Partition) of $A$ is a set $\{S_i\mid i\in I\}$ of subsets of $A$ such that
$S_i\cap S_j=\varnothing \text{ for }i\ne j\text{and}{\bigcup }_{i\in I}{S}_i=A.$
The blocks are pairwise disjoint and together cover $A$.

Definition 3.22 (Quotient set)

$A/\theta \stackrel{\text{def}}{=}\{[a{]}_{\theta }\mid a\in A\}$
is the quotient set (Quotientenmenge) of $A$ by $\theta$, read ”$A$ modulo $\theta$”. Its elements are the classes themselves, which are sets.

Theorem 3.11

For an equivalence relation $\theta$ on $A$, the quotient set $A/\theta$ is a partition of $A$.

Converse. Every partition gives an equivalence relation: $a\equiv b$ iff $a$ and $b$ lie in the same block. So equivalence relations and partitions are the same abstraction.

Lemma 3.10

The intersection of two equivalence relations on the same set is an equivalence relation.

The lecture gave an example instead of a proof: ${\equiv }_2\cap {\equiv }_3={\equiv }_6$ and ${\equiv }_3\cap {\equiv }_6={\equiv }_6$, not ${\equiv }_{18}$. In general ${\equiv }_m\cap {\equiv }_n={\equiv }_{\mathrm{lcm}(m,n)}$ (Ex. 3.18). Script Ex. 3.34: ${\equiv }_5\cap {\equiv }_3={\equiv }_{15}$. This “smells like” the least common multiple, which comes back in the number-theory chapter.

2.7 Partial orders (§3.5)

Definition 3.23 (Partial order, poset)

A partial order (Ordnungsrelation / partielle Ordnung) on $A$ is a relation that is reflexive, antisymmetric and transitive. A set with a partial order, written $(A;⪯)$, is a partially ordered set (poset).

This is the equivalence-relation definition with symmetric replaced by antisymmetric. In the graph, a partial order has no cycles apart from loops, though “no cycles” alone does not characterise partial orders.

Strict relation $\prec$

For a partial order $⪯$:
$a\prec b\stackrel{\text{def}}{⟺}a⪯b\wedge a\ne b,\text{i.e.}\prec =⪯\setminus {\mathrm{id}}_A.$
$\prec$ is never a partial order on a non-empty $A$, because it is irreflexive. On $A=\varnothing$ “all sorts of strange things happen” and every condition holds vacuously.

Definition 3.24 (Comparable)

In a poset $(A;⪯)$, $a$ and $b$ are comparable (vergleichbar) if $a⪯b$ or $b⪯a$. Otherwise they are incomparable.

Definition 3.25 (Total order)

$⪯$ is a total order (Totalordnung), or linear order, if any two elements are comparable:
$\forall a,b\in A:a⪯b\vee b⪯a.$
Every total order is a partial order, but not conversely.

Divisibility

For $a\ne 0$: $a\mid b⟺\exists k:b=a\cdot k$. Whether $0$ divides anything is left aside; $0$ is excluded so nothing strange happens. $b=0$ is fine, since every $a$ divides $0$.

Definition 3.26 (Cover)

In a poset $(A;⪯)$, $b$ covers (überdeckt) $a$ if $a\prec b$ and there is no $c$ with $a\prec c\prec b$. In words, $b$ is a “smallest” element strictly above $a$.

Script Ex. 3.41: in a company hierarchy, ”$b$ covers $a$” means $b$ is the direct superior of $a$.

Definition 3.27 (Hasse diagram)

The Hasse diagram (Hasse-Diagramm) of a finite poset $(A;⪯)$ is the directed graph on $A$ with an edge $a\to b$ iff $b$ covers $a$. It is drawn so that larger elements sit higher, which lets us omit the arrowheads.

---

3. Step-by-Step Derivations & Mathematical Proofs

3.1 Lemma 3.7 (associativity). Script proof; not done in lecture

We prove $\rho (\sigma \phi )\subseteq (\rho \sigma )\phi$. The other inclusion is analogous. Let $(a,d)\in \rho (\sigma \phi )$.

$$\begin{array}{rlrl}(a,d)\in \rho (\sigma \phi )& ⟹\exists b((a,b)\in \rho \wedge (b,d)\in \sigma \phi )& & \text{def. of }\circ \\ & ⟹\exists b((a,b)\in \rho \wedge \exists c((b,c)\in \sigma \wedge (c,d)\in \phi ))& & \text{def. of }\circ \\ & ⟹\exists b\exists c((a,b)\in \rho \wedge (b,c)\in \sigma \wedge (c,d)\in \phi )& & \exists x(F\wedge G)\equiv F\wedge \exists xG,x\notin F\\ & ⟹\exists c\exists b(((a,b)\in \rho \wedge (b,c)\in \sigma )\wedge (c,d)\in \phi )& & \text{swap }\exists \text{’s, regroup }\wedge \\ & ⟹\exists c(\exists b((a,b)\in \rho \wedge (b,c)\in \sigma )\wedge (c,d)\in \phi )& & \text{pull }\exists b\text{ inward}\\ & ⟹\exists c((a,c)\in \rho \sigma \wedge (c,d)\in \phi )& & \text{def. of }\circ \\ & ⟹(a,d)\in (\rho \sigma )\phi & & \text{def. of }\circ \end{array}$$

The key logical fact is $\exists x(F\wedge G)\equiv F\wedge \exists xG$ when $x$ does not occur free in $F$ (Chapter 6).

3.2 Lemma 3.8: $\widehat{\rho \sigma }=\hat{\sigma }\hat{\rho }$ (proved in lecture)

Setup. $\rho \subseteq A\times B$ and $\sigma \subseteq B\times C$, so $\rho \sigma \subseteq A\times C$ and $\widehat{\rho \sigma }\subseteq C\times A$. Also $\hat{\sigma }\subseteq C\times B$ and $\hat{\rho }\subseteq B\times A$, so $\hat{\sigma }\hat{\rho }\subseteq C\times A$. The types match.

Strategy. This is an equality of sets, so we show that a pair $(c,a)$ is in the left side iff it is in the right side. Every step below is an equivalence ($⟺$) with the same justification in both directions, so one chain proves both inclusions at once.

Heuristic from the lecture. Always start by applying the definition of the outermost operation. Since the target contains $\hat{\rho }$ and $\hat{\sigma }$, it is a good sign whenever these appear.

$$\begin{array}{rlrl}c\widehat{\rho \sigma }a& ⟺a(\rho \sigma )c& & \text{def. of inverse (outermost operation)}\\ & ⟺\exists b:a\rho b\wedge b\sigma c& & \text{def. of composition}\\ & ⟺\exists b:b\hat{\rho }a\wedge c\hat{\sigma }b& & \text{def. of inverse, applied twice}\\ & ⟺\exists b:c\hat{\sigma }b\wedge b\hat{\rho }a& & \text{commutativity of }\wedge \\ & ⟺c(\hat{\sigma }\hat{\rho })a& & \text{def. of composition}\end{array}$$

The commutativity step was suggested by a student. It is exactly what is needed to bring the expression into the pattern "$\exists b:x\alpha b\wedge b\beta y$", which is the definition of $x(\alpha \beta )y$. $■$

Intuition

To undo “first $\rho$, then $\sigma$”, you undo the last step first: go back along $\sigma$, then back along $\rho$. It is like taking off socks and shoes.

3.3 Lemma 3.9: $\rho$ transitive $⟺{\rho }^2\subseteq \rho$ (proved in lecture)

Lemma 3.9

A relation $\rho$ on $A$ is transitive if and only if ${\rho }^2\subseteq \rho$.

($\Rightarrow$) Assume $\rho$ is transitive. To show ${\rho }^2\subseteq \rho$, take an arbitrary element of ${\rho }^2$, i.e. $a{\rho }^{2}c$, and show $a\rho c$.

1. $a{\rho }^{2}c$ means $a(\rho \circ \rho )c$. By the definition of composition there is some $b$ with $a\rho b\wedge b\rho c$.
2. By transitivity, $a\rho b\wedge b\rho c⟹a\rho c$.
3. So $(a,c)\in \rho$.

($\Leftarrow$) Assume ${\rho }^2\subseteq \rho$. Let $a\rho b$ and $b\rho c$; we must show $a\rho c$.

1. There exists a middle element (namely $b$) with $a\rho b\wedge b\rho c$. By the definition of composition, $a{\rho }^{2}c$, i.e. $(a,c)\in {\rho }^2$.
2. Since ${\rho }^2\subseteq \rho$, we get $(a,c)\in \rho$, i.e. $a\rho c$. $■$

3.4 Theorem 3.11: equivalence classes form a partition

The lecture skipped this proof and only gave intuition. Here is the script’s proof, including the part left as an exercise. It is exam-relevant.

Covering. By reflexivity, $a\in [a]$ for every $a\in A$. Hence ${\bigcup }_{a\in A}[a]=A$; the inclusion "$\subseteq$" holds because all classes are subsets of $A$.

Disjointness. It suffices to show, for fixed $a,b$:
$\text{(i)}a\theta b⟹[a]=[b],\text{(ii)}a/\theta b⟹[a]\cap [b]=\varnothing .$
Then any two classes are either equal or disjoint.

(i), inclusion $[a]\subseteq [b]$. Let $c\in [a]$.
$c\in [a]⟺c\theta a⟹c\theta b⟺c\in [b]$
The middle step uses $c\theta a$, $a\theta b$ and transitivity.

(i), inclusion $[b]\subseteq [a]$. This is the exercise. Let $c\in [b]$, so $c\theta b$. From $a\theta b$, symmetry gives $b\theta a$. Transitivity on $c\theta b$ and $b\theta a$ gives $c\theta a$, so $c\in [a]$.

(ii), by contradiction. Suppose $a/\theta b$ but there is some $c\in [a]\cap [b]$. Then $c\theta a$ and $c\theta b$. Symmetry gives $a\theta c$, and transitivity with $c\theta b$ gives $a\theta b$. Contradiction. $■$

The contradiction step uses $\neg (A\to B)\equiv A\wedge \neg B$.

Converse (partition $\Rightarrow$ equivalence relation). Define $a\equiv b$ iff $a$ and $b$ lie in the same block.

• Reflexive: every element lies in some block, which contains it.
• Symmetric: “in the same block as” is symmetric.
• Transitive: if $a,b$ share block $S$ and $b,c$ share block $S^{\prime }$, then $b\in S\cap S^{\prime }$. Blocks are disjoint, so $S=S^{\prime }$ and $a,c$ share a block.

3.5 Lemma 3.10: intersection of equivalence relations (exercise in script)

Let ${\theta }_1,{\theta }_2$ be equivalence relations on $A$ and $\theta ={\theta }_1\cap {\theta }_2$.

• Reflexive: $\mathrm{id}\subseteq {\theta }_1$ and $\mathrm{id}\subseteq {\theta }_2$, so $\mathrm{id}\subseteq {\theta }_1\cap {\theta }_2$.
• Symmetric: if $(a,b)\in \theta$, then $(a,b)\in {\theta }_i$ for $i=1,2$. Hence $(b,a)\in {\theta }_i$ for both $i$, so $(b,a)\in \theta$.
• Transitive: if $(a,b),(b,c)\in \theta$, both pairs lie in each ${\theta }_i$. So $(a,c)\in {\theta }_i$ for both $i$, hence $(a,c)\in \theta$. $■$

3.6 Lemma (§3.4.3): $\sim$ on $\mathbb{Z}\times (\mathbb{Z}\setminus \{0\})$ is an equivalence relation (proved in lecture)

Setup

$A=\mathbb{Z}\times (\mathbb{Z}\setminus \{0\})$: pairs of integers whose second component is non-zero. Elements of $A$ are already pairs, so $(a,b)\sim (c,d)$ relates two elements, each of which is a pair.
$(a,b)\sim (c,d)\stackrel{\text{def}}{⟺}ad=bc.$

We must show the three properties.

1. Reflexivity. We need $(a,b)\sim (a,b)$, i.e. by definition $a\cdot b=b\cdot a$. This holds by commutativity of multiplication. ✓

2. Symmetry. Assume $(a,b)\sim (c,d)$.

$$\begin{array}{rlrl}(a,b)\sim (c,d)& ⟺ad=bc& & \text{definition}\\ & ⟺bc=ad& & \text{symmetry of }=\\ & ⟺cb=da& & \text{commutativity of }\cdot \text{ (twice)}\\ & ⟺(c,d)\sim (a,b)& & \text{definition}✓\end{array}$$

3. Transitivity. Assume $(a,b)\sim (c,d)$ and $(c,d)\sim (e,f)$. We want $(a,b)\sim (e,f)$, i.e. $af=be$. By definition:
$ad=bc(1)cf=de(2)$
Important: $b,d,f\ne 0$, because they are second components of elements of $A$. Case split on $c$:

Case $c=0$.

• From (1): $ad=b\cdot 0=0$. Since $d\ne 0$, we get $a=0$.
• From (2): $0=0\cdot f=de$. Since $d\ne 0$, we get $e=0$.
• So $af=0\cdot f=0=b\cdot 0=be$. ✓

Case $c\ne 0$. Multiply (1) and (2) side by side:
$ad\cdot cf=bc\cdot de.$

• $c\ne 0$ appears on both sides, so we may cancel it (an elementary property of $\mathbb{Z}$: if $xz=yz$ and $z\ne 0$ then $x=y$): $adf=bde$.
• $d\ne 0$ appears on both sides; cancel it: $af=be$. ✓

The script cancels $d$ first, which always works, and then splits on $c$. The lecture split first. Both are fine.

Why split cases? In the case $c=0$ we cannot cancel $c$. Cancelling by $0$ would be a division by zero, and that is where a naive proof breaks. $■$

Meaning. $(a,b)$ is the fraction $\frac{a}{b}$, with $a$ the numerator (Zähler) and $b$ the denominator (Nenner), and $ad=bc$ is exactly the rule for when two fractions are equal ($\frac{a}{b}=\frac{c}{d}$). Hence
$\mathbb{Q}\stackrel{\text{def}}{=}(\mathbb{Z}\times (\mathbb{Z}\setminus \{0\}))/\sim .$
A rational number is an equivalence class of fractions. For example, $[(1,2)]=\{(1,2),(2,4),(-3,-6),\dots \}$ is “one half”.

Remarks from the Q&A:

• Arithmetic on $\mathbb{Q}$ (addition, multiplication, inverses, taking care with $0$ in the denominator) could be defined on representatives, but the course does not do it.
• $\mathbb{Z}$ itself was not formally constructed. One could, for instance, use explicit signs modulo the relation ”$-0$ equals $0$”.
• $\mathbb{R}$ will not be defined. The point is that such a foundation exists, and the usual arithmetic rules can then be used.

3.7 Divisibility is a partial order on $\mathbb{N}\setminus \{0\}$ (lecture)

• Reflexive: $a=a\cdot 1$, so $a\mid a$.
• Antisymmetric: if $a\mid b$ and $b\mid a$ with $a,b>0$, then either $a=b$, or the divisor is strictly smaller ($a<b$ and $b<a$), which is impossible. Formally: $b=a{k}_1$ and $a=b{k}_2$ give $a=a{k}_1{k}_2$, so $k_1{k}_2=1$. With positive integers this forces $k_1=k_2=1$.
• Transitive: $b=a{k}_1$ and $c=b{k}_2$ give $c=a(k_1{k}_2)$, so $a\mid c$.
• Not total: $3\nmid 5$ and $5\nmid 3$.

Exam Trap: divisibility on $\mathbb{Z}$

On $\mathbb{Z}\setminus \{0\}$, $\mid$ is not antisymmetric: $2\mid -2$ and $-2\mid 2$ but $2\ne -2$. Here $k_1{k}_2=1$ also allows $k_1=k_2=-1$. So $(\mathbb{Z}\setminus \{0\};\mid )$ is not a poset. Always check the underlying set.

3.8 Exam question: is $\prec$ transitive? (old exam, end of Lecture B)

Question

Let $(A;⪯)$ be a poset and $\prec =⪯\setminus {\mathrm{id}}_A$. Is $\prec$ transitive? Prove it or give a counterexample.

Answer: yes. The lecturer stressed that this is not “obviously true”. The proof must use antisymmetry, and an answer that just says “obviously” gets no marks.

Direct proof. Assume $a\prec b$ and $b\prec c$; we must show $a\prec c$. Unfold the definition of $\prec$:
$a⪯b(1)a\ne b(2)b⪯c(3)b\ne c(4)$
From (1), (3) and transitivity of $⪯$:
$a⪯c(5)$
It remains to show $a\ne c$; this is the main part. Suppose, for contradiction, $a=c$.

• Substituting $a=c$ into (1) gives $c⪯b$.
• Together with (3), $b⪯c$, antisymmetry of $⪯$ gives $b=c$.
• This contradicts (4).

So $a\ne c$. With (5) this is exactly $a\prec c$. $■$

Why antisymmetry is essential

For a relation that is only reflexive and transitive (a preorder), the claim fails. On $A=\{a,b\}$, take $⪯=A\times A$. Then $a\prec b$ and $b\prec a$, but $a\nprec a$. So $\prec$ is not transitive. Antisymmetry is exactly what rules out “going up and coming back”.

---

4. Worked Examples & Applications

4.1 Students, courses, lecturers (Lecture A; Ex. 3.8)

Sets: $S=\{S_1,\dots ,S_4,\dots \}$ (students), $K=\{K_1,\dots ,K_4,\dots \}$ (courses), $D=\{D_1,\dots ,D_4,\dots \}$ (lecturers). The board’s arrows are reconstructed from the transcript:

• $\text{BEL}\subseteq S\times K$ (“takes”, belegt) $=\{(S_1,K_1),(S_1,K_3),(S_2,K_2),(S_2,K_3)\}$. For example, $(S_1,K_2)\notin \text{BEL}$.
• $\text{UNT}\subseteq D\times K$ (“teaches”, unterrichtet) $=\{(D_1,K_1),(D_1,K_2),(D_2,K_2),(D_2,K_4)\}$. $D_1$ and $D_2$ co-teach $K_2$; $D_3$ and $D_4$ teach nothing.

Inverse. $\widehat{\text{UNT}}\subseteq K\times D$ is “is taught by”, with the same arrows reversed.

Composition. $\text{BEL}\circ \widehat{\text{UNT}}\subseteq S\times D$ (first BEL, then $\widehat{\text{UNT}}$). Here $s$ is related to $d$ iff there is a course that $s$ takes and $d$ teaches.

Pair	Connecting course?	In relation?
$(S_1,D_1)$	$K_1$	yes
$(S_1,D_2)$	$S_1$ takes $K_1,K_3$; $D_2$ teaches $K_2,K_4$; no overlap	no
$(S_2,D_1)$	$K_2$	yes
$(S_2,D_2)$	$K_2$	yes
$(S_2,D_3)$	$D_3$ teaches nothing	no

4.2 $\le$ on $\mathbb{N}$ (Lecture A)

• Inverse of $\le$: the answer is $\ge$, not $>$. A student answered "$>$", which is wrong: $(1,1)\in \le$, so the swapped pair $(1,1)$ is in $\hat{\le }$, but $1\ngtr 1$.
• Decomposition: $\le =<\cup \mathrm{id}$, since $a\le b⟺a<b\vee a=b$.
• $\le \circ \le =\le$, as a student correctly answered.
  • "$\supseteq$": given $a\le c$, choose the middle element $b=a$. Then $a\le a$ and $a\le c$.
  • "$\subseteq$": this is transitivity (Lemma 3.9).
  • In general, a reflexive and transitive $\rho$ satisfies ${\rho }^2=\rho$.
  • A student suggested $\mathrm{id}$; that is far too restrictive.
• $<\circ <$ is the reconstructed part of the discussion. It consists of the pairs $(a,c)$ with an element strictly between them.
  • On $\mathbb{N}$: $<\circ <=\{(a,c)\mid c\ge a+2\}⊊<$. For example, $(0,1)\in <$ but nothing lies strictly between $0$ and $1$.
  • On $\mathbb{Q}$ or $\mathbb{R}$: $<\circ <=<$, because $\frac{a+c}{2}$ always lies between $a$ and $c$ (density).
  • Lesson: the result depends on the underlying set.

4.3 Properties of ${\equiv }_m$ on $\mathbb{Z}$ (both lectures)

• Reflexive (${\mathrm{id}}_{\mathbb{Z}}\subseteq {\equiv }_m$): $a-a=0=m\cdot 0$, and $0$ is a multiple of every $m$.
• Symmetric ($\widehat{{\equiv }_m}={\equiv }_m$): if $a-b=km$, then $b-a=(-k)m$.
• Transitive: if $a-b=k_{1}m$ and $b-c=k_{2}m$, then
  $a-c=(a-b)+(b-c)=(k_1+k_2)m.$
• Hence ${\equiv }_m$ is an equivalence relation (Ex. 3.31).

Classes for $m=5$ (Lecture B):

$$\begin{array}{rl}[0]& =\{\dots ,-10,-5,0,5,10,\dots \}\\ [1]& =\{\dots ,-9,-4,1,6,11,\dots \}\\ [2]& =\{\dots ,-8,-3,2,7,12,\dots \}\\ [3]& =\{\dots ,-7,-2,3,8,13,\dots \}\\ [4]& =\{\dots ,-6,-1,4,9,14,\dots \}\end{array}$$

In the lecture, a student suggested $-6\in [1]$. This is wrong: $1-(-6)=7$ is not a multiple of $5$. The correct entries are $-4$ and $-9$.

Note that $[5]=[0]$. ”$x-5$ is a multiple of $5$” is the same condition as ”$x-0$ is a multiple of $5$”, because only the factor changes by one. Therefore
$\mathbb{Z}/{\equiv }_5=\{[0],[1],[2],[3],[4]\},$
which has exactly 5 elements, even though each class is infinite.

Q&A: must the blocks be the same size?

No. Here all classes are “equally infinite”; Week 6 makes “sizes of infinity” precise. In general you can take any unbalanced partition of a finite set and get an equivalence relation from it.

4.4 Equivalence relations on the set $H$ of humans (Lecture B)

Candidate	Reflexive	Symmetric	Transitive	Equivalence?
“knows”	arguable (assume yes)	no (a fan knows a star, not vice versa)	no	no
full siblings incl. oneself (both parents equal)	yes (by fiat)	yes	yes	yes
half siblings (≥ 1 common parent)	yes	yes	no: $x,y$ share a mother, $y,z$ share a father	no
same age	yes	yes	yes	yes

And on $\mathbb{R}$, from a student suggestion: $a\theta b⟺a-b\in \mathbb{Q}$. This is reflexive ($0\in \mathbb{Q}$), symmetric ($-(a-b)\in \mathbb{Q}$) and transitive ($a-c=(a-b)+(b-c)$, a sum of rationals). So it is an equivalence relation.

Intuition: equivalence relations as a coarsening (Vergröberung)

In every example, an equivalence relation sorts elements into boxes: people by age, integers by remainder. Within a box we “forget” all differences.

4.5 Family relations via relation algebra (Lecture A; Ex. 3.9, 3.20, 3.23)

On $H$ (idealised humans), let $x\text{Child}y$ mean ”$x$ is a child of $y$”.

• $\widehat{\text{Child}}=\text{Parent}$: $x\text{Parent}y$ iff $x$ is a parent of $y$.
• ${\text{Parent}}^2=\text{Parent}\circ \text{Parent}=\text{Grandparent}$, as answered in lecture.
• Siblings (student suggestion): $\text{Child}\circ \widehat{\text{Child}}=\text{Child}\circ \text{Parent}$. Here $x$ is related to $y$ iff $\exists z:x\text{Child}z\wedge z\text{Parent}y$, i.e. $x$ and $y$ have a common parent $z$. Two caveats:
  • This gives half-siblings: one common parent suffices.
  • Everyone is related to themselves. To exclude that, use $(\text{Child}\circ \widehat{\text{Child}})\setminus {\mathrm{id}}_H$.
• The other order, $\widehat{\text{Child}}\circ \text{Child}=\text{Parent}\circ \text{Child}$, means ”$x$ and $y$ have a common child”, which is something entirely different.
• Ancestor: in predicate logic this needed an infinite disjunction (“parent or grandparent or great-grandparent or …”). A student suggested ${\text{Parent}}^n$; the lecturer’s reply was “then what is $n$?”. A finite union $\text{Parent}\cup \cdots \cup {\text{Parent}}^n$ still needs a bound. The transitive closure solves this cleanly:
  $\text{Ancestor}={\text{Parent}}^{\ast }.$

4.6 Hasse diagrams (Lecture B; Ex. 3.43, 3.44)

Divisors of 24 under $\mid$ (Ex. 3.43): $A=\{1,2,3,4,6,8,12,24\}$.

Cover edges: $1-2$, $1-3$, $2-4$, $2-6$, $3-6$, $4-8$, $4-12$, $6-12$, $8-24$, $12-24$.

graph BT
    n1["1"] --- n2["2"]
    n1 --- n3["3"]
    n2 --- n4["4"]
    n2 --- n6["6"]
    n3 --- n6
    n4 --- n8["8"]
    n4 --- n12["12"]
    n6 --- n12
    n8 --- n24["24"]
    n12 --- n24

• There is no edge $4-24$, because $8$ (and also $12$) lies strictly between them: $4\mid 8\mid 24$.
• Walking up an edge always multiplies by a prime here.

$(\mathcal{P}(\{a,b,c\});\subseteq )$ (Ex. 3.44):

graph BT
    E["∅"] --- A["{a}"]
    E --- B["{b}"]
    E --- C["{c}"]
    A --- AB["{a,b}"]
    A --- AC["{a,c}"]
    B --- AB
    B --- BC["{b,c}"]
    C --- AC
    C --- BC
    AB --- ABC["{a,b,c}"]
    AC --- ABC
    BC --- ABC

• Each edge going up adds exactly one element.
• A student asked why there is no edge $\{c\}-\{a,b,c\}$. The reason is that $\{a,c\}$ (or $\{b,c\}$) lies strictly between them, so $\{a,b,c\}$ does not cover $\{c\}$.
• Purpose: draw nothing that can be inferred by transitivity, which keeps the diagram readable.

Exam Trap: drawing Hasse diagrams (a frequent exam question)

• Draw only cover edges. No loops (reflexivity is implicit), no transitive shortcuts.
• Smaller elements go below. Arrowheads are omitted.
• “Smaller” means smaller in the given order, not numerically. In $(\{2,\dots ,9\};\mid )$, $5$ and $7$ are isolated points even though $5<7$.
• Covers depend on the set. In $(\{2,3,4,5,6,7,8,9\};\mid )$ (Ex. 3.42) there is no $1$, so $2,3,5,7$ are all minimal.

---

5. Intuition & Conceptual Bridges

• A relation is a bipartite arrow picture. Relations from $A$ to $B$ are arrows from $A$ to $B$. The inverse reverses the arrows; composition follows two arrows in a row.
• Relation algebra replaces quantifiers. Each set-theoretic characterisation ($\mathrm{id}\subseteq \rho$, $\rho =\hat{\rho }$, $\rho \cap \hat{\rho }\subseteq \mathrm{id}$, ${\rho }^2\subseteq \rho$) turns a $\forall$-formula into a set inclusion. This is often the shortest way to prove things. Example: $\rho \circ \hat{\rho }$ is always symmetric (Q4).
• Equivalence relation = “same box”. It is a partition seen from another angle. The quotient set $A/\theta$ is the set of boxes. This is the way to build new mathematical objects: $\mathbb{Q}$ from fractions, and later ${\mathbb{Z}}_m$ (residues modulo $m$) in the number-theory chapter.
• Partial order = “consistent ranking with gaps”. Some pairs are simply incomparable, like coprime numbers under $\mid$ or $\{a\}$ and $\{b\}$ under $\subseteq$. Antisymmetry forbids distinct elements being “mutually below” each other, so there are no cycles; transitivity keeps the ranking consistent.
• Equivalence vs. order. Both are reflexive and transitive. Symmetric gives “same”; antisymmetric gives “ranked”. The only relations that are both are subsets of $\mathrm{id}$ (by symmetry and antisymmetry, $\rho =\rho \cap \hat{\rho }\subseteq \mathrm{id}$), and the reflexive one is $\mathrm{id}$ itself.
• Link to logic (Ch. 2/6). Relations are another view of binary predicates; a student asked exactly this. The family example shows the advantage: “ancestor”, which could not be written with a finite formula, becomes ${\text{Parent}}^{\ast }$.
• Link to the matrix view (Linear Algebra). Inverse is transpose and composition is a Boolean matrix product. Symmetric relations have symmetric matrices.
• Coming next.
  • §3.5.3–3.5.5: lexicographic order, minimal/maximal/least/greatest elements, meet, join, lattices.
  • §3.6: functions as special relations, where $\hat{f}$ becomes the inverse function and composition is written in the reverse order.
  • §3.7: countability (Week 6), which the lecturer previewed as “distinguishing infinite from more than infinite”.
  • Chapter 4: number theory, where ${\equiv }_m$ and $\mathrm{lcm}$ return.

---

6. Summary & Self-Assessment Questions

Cheat sheet

Concept	Definition / Fact
Relation	$\rho \subseteq A\times B$; $a\rho b:⟺(a,b)\in \rho$
Identity	${\mathrm{id}}_A=\{(a,a)\mid a\in A\}$
Inverse	$\hat{\rho }=\{(b,a)\mid (a,b)\in \rho \}$; matrix transpose
Composition	$\rho \circ \sigma =\{(a,c)\mid \exists b:a\rho b\wedge b\sigma c\}$; first $\rho$, then $\sigma$
Lemma 3.7	$\rho (\sigma \phi )=(\rho \sigma )\phi$
Lemma 3.8	$\widehat{\rho \sigma }=\hat{\sigma }\hat{\rho }$
Reflexive	$\mathrm{id}\subseteq \rho$
Irreflexive	$\rho \cap \mathrm{id}=\varnothing$
Symmetric	$\rho =\hat{\rho }$
Antisymmetric	$\rho \cap \hat{\rho }\subseteq \mathrm{id}$
Transitive	${\rho }^2\subseteq \rho$ (Lemma 3.9)
Transitive closure	${\rho }^{\ast }={\bigcup }_{n\ge 1}{\rho }^n$ (reachability)
Equivalence relation	reflexive + symmetric + transitive
Class / quotient	$[a{]}_{\theta }=\{b\mid b\theta a\}$; $A/\theta =\{[a{]}_{\theta }\mid a\in A\}$
Thm 3.11	$A/\theta$ is a partition; partitions $\leftrightarrow$ equivalence relations
Lemma 3.10	${\theta }_1\cap {\theta }_2$ is an equivalence relation; ${\equiv }_m\cap {\equiv }_n={\equiv }_{\mathrm{lcm}(m,n)}$
$\mathbb{Q}$	$(\mathbb{Z}\times (\mathbb{Z}\setminus \{0\}))/\sim$ with $(a,b)\sim (c,d)⟺ad=bc$
Partial order	reflexive + antisymmetric + transitive; poset $(A;⪯)$
Strict order	$a\prec b⟺a⪯b\wedge a\ne b$; transitive (exam question)
Total order	$\forall a,b:a⪯b\vee b⪯a$
Cover	$a\prec b$ and no $c$ with $a\prec c\prec b$
Hasse diagram	edges = covers only, larger elements above

Practice questions

Q1. How many relations are there on a set $A$ with $|A|=n$? How many of them are reflexive? How many are symmetric?

Solution to Question 1

All relations. A relation on $A$ is any subset of $A\times A$, and $|A\times A|=n^2$. So there are $|\mathcal{P}(A\times A)|=2^{n^2}$ relations. This answers the “(Why?)” in the script after Def. 3.10.

Reflexive. All $n$ diagonal pairs $(a,a)$ are forced in. Each of the remaining $n^2-n$ off-diagonal pairs is free, giving $2^{n^2-n}$.

Symmetric. The choices are:

• each of the $n$ diagonal pairs freely, and
• each unordered pair $\{a,b\}$ with $a\ne b$ “both $(a,b)$ and $(b,a)$, or neither”. There are $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ of these.

That gives $n+\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\frac{n(n+1)}{2}$ free choices, so $2^{n(n+1)/2}$ symmetric relations.

Check with $n=2$: there are $2^4=16$ relations in total, $2^2=4$ reflexive ones and $2^3=8$ symmetric ones.

Q2. Prove or disprove: if $\rho$ on $A$ is symmetric and transitive, then $\rho$ is reflexive. (Classic argument: "$a\rho b\Rightarrow b\rho a\Rightarrow a\rho a$".)

Solution to Question 2

False. Counterexample: $A=\{1\}$ and $\rho =\varnothing$.

• $\varnothing$ is symmetric and transitive vacuously: the premises $a\rho b$ are never satisfied.
• It is not reflexive, since $(1,1)\notin \rho$.

A second counterexample with a non-empty relation: $A=\{1,2\}$, $\rho =\{(1,1)\}$. It is symmetric and transitive, but $(2,2)\notin \rho$.

Where the “proof” fails. The step $a\rho b\Rightarrow b\rho a\Rightarrow a\rho a$ needs some $b$ with $a\rho b$ to exist. If an element $a$ is related to nothing, nothing forces $a\rho a$.

Correct statement. A symmetric and transitive relation is reflexive iff every $a$ is related to at least one element.

Q3. Is the union of two equivalence relations on the same set again an equivalence relation?

Solution to Question 3

No in general. Reflexivity and symmetry are preserved:

• $\mathrm{id}\subseteq {\theta }_1\subseteq {\theta }_1\cup {\theta }_2$;
• $\widehat{{\theta }_1\cup {\theta }_2}=\widehat{{\theta }_1}\cup \widehat{{\theta }_2}={\theta }_1\cup {\theta }_2$.

Transitivity can fail. Take ${\theta }_1={\equiv }_2$ and ${\theta }_2={\equiv }_3$ on $\mathbb{Z}$:

• $0{\equiv }_{2}2$, so $(0,2)\in {\theta }_1\cup {\theta }_2$;
• $2{\equiv }_{3}5$, so $(2,5)\in {\theta }_1\cup {\theta }_2$;
• but $0-5=-5$ is divisible by neither $2$ nor $3$, so $(0,5)\notin {\theta }_1\cup {\theta }_2$.

The smallest equivalence relation containing the union is its transitive closure $({\theta }_1\cup {\theta }_2{)}^{\ast }$; here this is all of $\mathbb{Z}\times \mathbb{Z}$, since $\gcd (2,3)=1$.

This contrasts with Lemma 3.10: intersection works, union does not.

Q4. Prove that for every relation $\rho$ from $A$ to $B$, the relation $\rho \circ \hat{\rho }$ on $A$ is symmetric. Interpret it in the student/course example.

Solution to Question 4

Step 1. The inverse of an inverse is the original relation:
$(a,b)\in \hat{\hat{\rho }}⟺(b,a)\in \hat{\rho }⟺(a,b)\in \rho .$
So $\hat{\hat{\rho }}=\rho$.

Step 2. By Lemma 3.8,
$\widehat{\rho \circ \hat{\rho }}=\hat{\hat{\rho }}\circ \hat{\rho }=\rho \circ \hat{\rho }.$

Step 3. So $\rho \circ \hat{\rho }$ equals its own inverse, which is the definition of symmetric (Def. 3.15). $■$

Interpretation. With $\rho =\text{BEL}$, the relation $\text{BEL}\circ \widehat{\text{BEL}}$ means “takes at least one course in common with”.

• It is symmetric, as just proved.
• It is reflexive on students who take at least one course.
• It is not transitive in general: $S_1$ and $S_2$ share $K_3$, and $S_2$ might share a course with some $S_5$ that has nothing in common with $S_1$.

This is the same phenomenon as the half-siblings relation $\text{Child}\circ \widehat{\text{Child}}$.

Q5. Prove that ${\rho }^{\ast }$ is transitive and that it is contained in every transitive relation $\tau \supseteq \rho$. So ${\rho }^{\ast }$ is the smallest transitive relation containing $\rho$.

Solution to Question 5

Transitivity. Let $a{\rho }^{\ast }b$ and $b{\rho }^{\ast }c$. By definition there are $m,n\ge 1$ with $a{\rho }^{m}b$ and $b{\rho }^{n}c$, i.e. a walk of length $m$ from $a$ to $b$ and one of length $n$ from $b$ to $c$. By the definition of composition, $a({\rho }^m\circ {\rho }^n)c$. By associativity (Lemma 3.7), ${\rho }^m\circ {\rho }^n={\rho }^{m+n}$. Hence $a{\rho }^{m+n}c$, so $a{\rho }^{\ast }c$.

Minimality. Let $\tau$ be transitive with $\rho \subseteq \tau$. We show ${\rho }^n\subseteq \tau$ for all $n\ge 1$ by induction.

• Base case $n=1$: $\rho \subseteq \tau$ by assumption.
• Inductive step: assume ${\rho }^n\subseteq \tau$. If $a{\rho }^{n+1}c$, then $\exists b$ with $a{\rho }^{n}b$ and $b\rho c$. Hence $a\tau b$ and $b\tau c$, and transitivity of $\tau$ gives $a\tau c$.

So ${\rho }^{\ast }={\bigcup }_{n\ge 1}{\rho }^n\subseteq \tau$. $■$

Corollary (script exercise in §3.3.7). Taking $\tau =\rho$ for a transitive $\rho$ gives ${\rho }^n\subseteq \rho$ for all $n\ge 1$, hence ${\rho }^{\ast }=\rho$.

Q6 (Ex. 3.45). Realise the two Hasse diagrams of Figure 3.2 as divisibility posets.

• Left: a bottom element; two elements above it; two elements above those, each connected to both lower middle elements (a crossing); a top element.
• Right: a chain of 2, then a diamond, then one more element on top.

Solution to Question 6

Left diagram: $A=\{1,2,3,12,18,36\}$ with $\mid$.

• $1$ is covered by $2$ and by $3$.
• $2\mid 12$, $2\mid 18$, $3\mid 12$, $3\mid 18$. Each of these is a cover, because $6\notin A$ and $4,9\notin A$, so nothing in $A$ lies strictly between. This gives the crossing.
• $12\mid 36$ and $18\mid 36$, both covers.
• $12$ and $18$ are incomparable, and so are $2$ and $3$.
• No extra edges: for example $2\mid 36$ is implied via $12$.

Right diagram: $A=\{1,2,4,6,12,24\}$.

• Chain: $1\prec 2$.
• Diamond: $2\prec 4$, $2\prec 6$, $4\prec 12$, $6\prec 12$, with $4$ and $6$ incomparable.
• Top: $12\prec 24$. There is no edge $4-24$ (via $12$), and $8\notin A$.

Check covers: for each drawn edge $a-b$, verify that no element of $A$ lies strictly between $a$ and $b$ under $\mid$. For each non-edge, verify that the pair is incomparable or connected via a chain.