CommeUnJeu · L1 MPSI

Binary Relations

⌚ ~51 min ▢ 6 blocks ✓ 18 exercises ➣ Prerequisites : Sets

A binary relation on a set $E$ is the most general way to express a link between two elements of $E$: a rule that decides, for any pair $(x, y) \in E \times E$, whether $x$ is « in relation with » $y$ or not. The order $\le$ on $\mathbb{R}$, the equality $=$ on any set, the inclusion $\subset$ on $\mathcal{P}(E)$, the divisibility $\mid$ on $\mathbb{N}$, and the parity-equivalence on $\mathbb{Z}$ are all binary relations.

Such relations may combine four basic structural properties: reflexivity, symmetry, anti\-symmetry and transitivity. Two specific combinations give rise to the great families that organize the rest of the chapter:

Equivalence relations (reflexive + symmetric + transitive). They group elements that are « the same up to some criterion » --- parity, sign, congruence, having the same image under a map. Equivalence classes form a partition of the underlying set, and that partition theorem is the cornerstone of the chapter.
Order relations (reflexive + antisymmetric + transitive). They hierarchize elements and let us speak of « smaller » and « larger ». They generalize $\le$ on $\mathbb{R}$ and admit two flavors: total (any two elements compare) and partial (some elements are incomparable). Hasse diagrams visualize partial orders cleanly.

The chapter closes with the standard arithmetic example of equivalence: congruences in $\mathbb{Z}$ (the basis of modular arithmetic) and in $\mathbb{R}$ (which formalizes « angles modulo $2\pi$ »).

I Binary relations and their properties

Definition — Binary relation

A binary relation $\mathcal{R}$ on a set $E$ is any subset of $E \times E$. We write $x \, \mathcal{R} \, y$ to mean $(x, y) \in \mathcal{R}$, read « $x$ is in relation with $y$ ». A relation may have any combination of the following properties:

reflexive: $\forall x \in E, \ x \, \mathcal{R} \, x$;
symmetric: $\forall (x, y) \in E^2, \ x \, \mathcal{R} \, y \implies y \, \mathcal{R} \, x$;
antisymmetric: $\forall (x, y) \in E^2, \ (x \, \mathcal{R} \, y \text{ and } y \, \mathcal{R} \, x) \implies x = y$;
transitive: $\forall (x, y, z) \in E^3, \ (x \, \mathcal{R} \, y \text{ and } y \, \mathcal{R} \, z) \implies x \, \mathcal{R} \, z$.

Example

Equality $=$ on any set $E$ is reflexive, symmetric, antisymmetric, transitive.
The order $\le$ on $\mathbb{R}$ is reflexive, antisymmetric, transitive (not symmetric: $1 \le 2$ but $2 \not\le 1$).
Strict order $<$ on $\mathbb{R}$ is antisymmetric and transitive but not reflexive ($1 \not< 1$).
Divisibility $\mid$ on $\mathbb{N}$ is reflexive, transitive, antisymmetric. On $\mathbb{Z}$, it is no longer antisymmetric: $2 \mid -2$ and $-2 \mid 2$ but $2 \ne -2$.
« To have the same parity as » on $\mathbb{N}$ is reflexive, symmetric, transitive (not antisymmetric: $2$ and $4$ are related, but $2 \ne 4$).

Skills to practice

Testing the four basic properties

II Equivalence relations

Equivalence relations are the « weakest reasonable identification »: they let us say « $x$ and $y$ are the same up to a chosen criterion » without forcing any structure. The three axioms (reflexive, symmetric, transitive) capture exactly the three properties one expects of an « identification »: every $x$ is identified with itself, identification is two-sided, and chains of identifications collapse. The pay-off is the partition theorem: the equivalence classes carve $E$ into disjoint pieces.

Definition — Equivalence relation

A binary relation $\mathcal{R}$ on $E$ is an equivalence relation if it is reflexive, symmetric, and transitive. Equivalence relations are typically denoted by symbols like $\sim$, $\equiv$, $\approx$.

Method — To prove $\sim$ is an equivalence relation

Verify the three axioms in turn, each on its own bullet:

Reflexivity. For every $x \in E$, $x \sim x$.
Symmetry. For every $x, y \in E$, if $x \sim y$ then $y \sim x$.
Transitivity. For every $x, y, z \in E$, if $x \sim y$ and $y \sim z$, then $x \sim z$.

Skipping any one of the three axioms leaves a relation that may behave very differently (an order is reflexive + transitive but not symmetric; the strict order $<$ is transitive only; etc.).

Definition — Equivalence class

Let $\sim$ be an equivalence relation on $E$ and $x \in E$. The equivalence class of $x$ for $\sim$ is the set $$ \operatorname{cl}(x) = \{ y \in E \ \mid \ x \sim y \}. $$ Other notations: $[x]$, $\bar{x}$, $\dot{x}$. Reflexivity gives $x \in \operatorname{cl}(x)$, so the class is non-empty. Two equivalent elements have the same class: $x \sim y \iff \operatorname{cl}(x) = \operatorname{cl}(y)$.

Definition — Partition

A partition of $E$ is a set $\mathcal{U}$ of subsets of $E$ such that:

every $A \in \mathcal{U}$ is non-empty;
the elements of $\mathcal{U}$ are pairwise disjoint: for $A, B \in \mathcal{U}$ with $A \ne B$, $A \cap B = \emptyset$;
their union is $E$: $\bigcup_{A \in \mathcal{U}} A = E$.

Each $x \in E$ belongs to exactly one element of $\mathcal{U}$.

Method — To verify that $\mathcal{U}$ is a partition of $E$

Three checks, in order:

Non-emptiness. Every $A \in \mathcal{U}$ contains at least one element.
Pairwise disjointness. For $A, B \in \mathcal{U}$ with $A \ne B$, $A \cap B = \emptyset$.
Covering. Every $x \in E$ belongs to some $A \in \mathcal{U}$.

A partition can equivalently be given by a rule that, to each $x \in E$, assigns the unique piece containing it. The two viewpoints --- « list of pieces » vs. « assignment rule » --- are interchangeable.

Theorem — Classes form a partition

Let $\sim$ be an equivalence relation on $E$. The set of equivalence classes $$ \{ \operatorname{cl}(x) \ \mid \ x \in E \} $$ is a partition of $E$.

Proof

Three conditions to check.

Non-emptiness. For any $x \in E$, reflexivity gives $x \sim x$, so $x \in \operatorname{cl}(x)$, so $\operatorname{cl}(x) \ne \emptyset$.
Pairwise disjointness. Let $\operatorname{cl}(x), \operatorname{cl}(y)$ be two classes with $\operatorname{cl}(x) \cap \operatorname{cl}(y) \ne \emptyset$. Pick $z$ in the intersection: $x \sim z$ and $y \sim z$. By symmetry, $z \sim y$; by transitivity from $x \sim z$ and $z \sim y$, $x \sim y$. Hence $\operatorname{cl}(x) = \operatorname{cl}(y)$. Contrapositively, two distinct classes are disjoint.
Covering. For every $x \in E$, $x \in \operatorname{cl}(x)$, so $E \subset \bigcup_{x \in E} \operatorname{cl}(x)$. The reverse inclusion is trivial since each $\operatorname{cl}(x) \subset E$.

Example

On $\mathbb{Z}$ with the relation « having the same parity », there are exactly two classes: the evens $2\mathbb{Z}$ and the odds $2\mathbb{Z}+1$. They are non-empty, disjoint, and their union is $\mathbb{Z}$ --- a partition of $\mathbb{Z}$ into two pieces. On $\mathbb{R}$ with congruence modulo $2\pi$, the classes are the « angles modulo a full turn », one for each $\theta \in [0, 2\pi[$ --- infinitely many, still pairwise disjoint and covering $\mathbb{R}$.

Skills to practice

Verifying that a relation is an equivalence
Computing equivalence classes

III Congruences in $\mathbb{R}$ and $\mathbb{Z}$

Congruences are the most familiar equivalence relations. In $\mathbb{Z}$, congruence modulo $n$ identifies integers having the same remainder in the division by $n$ --- that is the basis of modular arithmetic, with applications from cryptography to error-correcting codes. In $\mathbb{R}$, congruence modulo $\alpha$ identifies reals differing by an integer multiple of $\alpha$ --- the case $\alpha = 2\pi$ is the standard formalization of « angles modulo a full turn ».

Definition — Congruence modulo

For $n \in \mathbb{N}^*$, the relation defined on $\mathbb{Z}$ by $$ x \equiv y \pmod n \iff \exists k \in \mathbb{Z}, \ x - y = k n $$ is an equivalence relation on $\mathbb{Z}$, called congruence modulo $n$.
For $\alpha \in \mathbb{R}_+^*$, the relation defined on $\mathbb{R}$ by $$ x \equiv y \pmod \alpha \iff \exists k \in \mathbb{Z}, \ x - y = k \alpha $$ is an equivalence relation on $\mathbb{R}$, called congruence modulo $\alpha$.

Example

In $\mathbb{Z}$ modulo $5$: $7 \equiv 2 \pmod 5$, $-3 \equiv 2 \pmod 5$, $0 \equiv 5 \equiv 10 \pmod 5$. There are $5$ equivalence classes, the residues $\{0, 1, 2, 3, 4\}$ modulo $5$.
In $\mathbb{R}$ modulo $2\pi$, congruence is the trigonometric identity « same angle modulo a full turn ». For all real $x$ and $y$, $\cos x = \cos y$ and $\sin x = \sin y$ if and only if $x \equiv y \pmod {2\pi}$.
Congruence modulo $1$ on $\mathbb{R}$ is « having the same fractional part »: $x \equiv y \pmod 1 \iff x - y \in \mathbb{Z}$.

Skills to practice

Computing in $\mathbb{Z}/n\mathbb{Z}$

IV Order relations

The other major family is order relations. Where equivalence captures « identification », order captures hierarchy: smaller, larger, before, after. The three axioms (reflexive, antisymmetric, transitive) carve out the right combination: every $x$ is comparable to itself; if $x \preccurlyeq y$ and $y \preccurlyeq x$ then $x = y$ (no ties between distinct elements); chains of comparisons compose. Two flavors of order coexist --- total (any two elements compare, like $\le$ on $\mathbb{R}$) and partial (some are incomparable, like $\subset$ on $\mathcal{P}(E)$ or divisibility on $\mathbb{N}$). Hasse diagrams are the canonical visualization of partial orders.

Definition — Order relation

A binary relation $\preccurlyeq$ on $E$ is an order relation (or order) if it is reflexive, antisymmetric, and transitive. The pair $(E, \preccurlyeq)$ is called an ordered set. Order relations are typically denoted $\le$, $\preccurlyeq$, $\sqsubseteq$.

Definition — Total order$\virgule$ partial order

Let $(E, \preccurlyeq)$ be an ordered set. Two elements $x, y \in E$ are comparable if $x \preccurlyeq y$ or $y \preccurlyeq x$. The order $\preccurlyeq$ is:

total if any two elements of $E$ are comparable: $\forall (x, y) \in E^2, \ x \preccurlyeq y \text{ or } y \preccurlyeq x$;
partial otherwise (some elements are incomparable).

Example

$(\mathbb{R}, \le)$, $(\mathbb{Q}, \le)$, $(\mathbb{Z}, \le)$, $(\mathbb{N}, \le)$ are totally ordered: the real line is a single line, no two reals are incomparable.
$(\mathcal{P}(E), \subset)$ is partially ordered as soon as $|E| \ge 2$: for $a \ne b$ in $E$, $\{a\}$ and $\{b\}$ are incomparable (neither contained in the other).
$(\mathbb{N}, \mid)$ (divisibility) is partially ordered: $2$ and $3$ are incomparable.

A partial order can be visualized by a Hasse diagram: nodes are elements, edges go upward from $x$ to $y$ when $x \preccurlyeq y$ with no element strictly between them.

The Hasse diagram of $(\mathcal{P}(\{1, 2, 3\}), \subset)$. The pairs $\{1\}, \{2\}, \{3\}$ are pairwise incomparable: that is the « partial » nature of the order.

Example

Another partial order: divisibility on the divisors of $12$. The set $D_{12} = \{1, 2, 3, 4, 6, 12\}$ ordered by $\mid$ has the Hasse diagram below.

Reading off the diagram: $2 \mid 4$ and $2 \mid 6$, but $4$ and $6$ are incomparable (neither divides the other). The least element is $1$, the greatest is $12$.

Definition — Greatest$\virgule$ least element

Let $(E, \preccurlyeq)$ be an ordered set, $A \subset E$ and $a \in A$.

$a$ is the greatest element of $A$ if $\forall x \in A, \ x \preccurlyeq a$. When it exists, it is unique and noted $\max(A)$.
$a$ is the least element of $A$ if $\forall x \in A, \ a \preccurlyeq x$. When it exists, it is unique and noted $\min(A)$.

Existence is not guaranteed: $\mathopen{]}0, 1[$ has no greatest and no least element in $(\mathbb{R}, \le)$. Uniqueness follows from antisymmetry: if $a, b$ are both greatest, then $a \preccurlyeq b$ and $b \preccurlyeq a$, hence $a = b$.

Definition — Upper bound$\virgule$ lower bound

Let $(E, \preccurlyeq)$ be an ordered set and $A \subset E$. An element $m \in E$ is:

an upper bound of $A$ if $\forall x \in A, \ x \preccurlyeq m$;
a lower bound of $A$ if $\forall x \in A, \ m \preccurlyeq x$.

$A$ is bounded above if it has at least one upper bound, bounded below if it has at least one lower bound, bounded if both. The greatest element of $A$, when it exists, is the unique upper bound of $A$ that belongs to $A$.

Example

In $(\mathbb{R}, \le)$:

$A = [0, 1]$. Upper bounds: $[1, +\infty[$. Lower bounds: $\mathopen{]}-\infty, 0]$. Greatest element: $1$. Least element: $0$.
$A = \mathopen{]}0, 1\mathclose{[}$. Upper bounds: $[1, +\infty[$. Lower bounds: $\mathopen{]}-\infty, 0]$. No greatest element, no least element (the bounds $0, 1$ are not in $A$).
$A = \mathbb{N}$. Lower bounds: $\mathopen{]}-\infty, 0]$. No upper bound (every real is exceeded by some integer).

In $(\mathcal{P}(\{1,2,3\}), \subset)$, the whole set $\{1,2,3\}$ is the greatest element and $\emptyset$ the least.

Skills to practice

Recognizing partial and total orders
Finding max$\virgule$ min$\virgule$ and bounds