CommeUnJeu · L1 PCSI

Binary Relations

⌚ ~35 min ▢ 4 blocks ✓ 13 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)$ and the divisibility $\mid$ on $\mathbb{N}$ are all binary relations.

Such a relation may have four basic structural properties: reflexivity, symmetry, anti\-symmetry and transitivity. These four words are the vocabulary we need to single out the central object of this chapter, the order relations (reflexive + antisymmetric + transitive): they hierarchize elements and let us speak of « smaller » and « larger », generalizing $\le$ on $\mathbb{R}$. An order may be total (any two elements compare, like $\le$ on $\mathbb{R}$) or partial (some elements are incomparable, like $\subset$ on $\mathcal{P}(E)$ or divisibility on $\mathbb{N}$), and Hasse diagrams visualize partial orders cleanly. On the way we meet one more useful relation: the congruence modulo $\alpha$ on $\mathbb{R}$, whose case $\alpha = 2\pi$ formalizes « angles modulo a full turn ».

I Binary relations and their properties

Definition — Binary relation and its properties

A binary relation $\mathcal{R}$ on a set $E$ associates, to each pair $(x, y) \in E \times E$, the answer « yes » or « no » to the question « is $x$ in relation with $y$? ». We write $x \, \mathcal{R} \, y$ when the answer is yes. Formally, $\mathcal{R}$ is given by its graph, the subset $\{(x, y) \in E \times E \mid x \, \mathcal{R} \, y\}$ of $E \times E$. Such a relation may have 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$.

These four properties are the vocabulary used below to define order relations.

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 Congruences in $\mathbb{R}$ and $\mathbb{Z}$

The congruence relation is a familiar way to identify two numbers that « agree up to a fixed step ». On $\mathbb{R}$, congruence modulo $\alpha$ links two reals whose difference is an integer multiple of $\alpha$; the case $\alpha = 2\pi$ is the standard formalization of « angles modulo a full turn », which we use constantly in trigonometry. The same idea on $\mathbb{Z}$ gives congruence modulo $n$, which links integers having the same remainder in the division by $n$.

Definition — Congruence modulo

For $\alpha \in \mathbb{R}_+^*$, the congruence modulo $\alpha$ on $\mathbb{R}$ is defined by $$ x \equiv y \pmod \alpha \iff \exists k \in \mathbb{Z}, \ x - y = k \alpha. $$ The most used case is $\alpha = 2\pi$, written $x \equiv y \, [2\pi]$.
For $n \in \mathbb{N}^*$, the congruence modulo $n$ on $\mathbb{Z}$ is defined by $$ x \equiv y \pmod n \iff \exists k \in \mathbb{Z}, \ x - y = k n. $$

In both cases the relation is reflexive, symmetric and transitive: it behaves like an « equality up to a multiple of $\alpha$ (resp. $n$) ».

Example

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}$. For instance $\dfrac{\pi}{3} \equiv \dfrac{7\pi}{3} \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}$.
In $\mathbb{Z}$ modulo $5$: $7 \equiv 2 \pmod 5$, $-3 \equiv 2 \pmod 5$ and $0 \equiv 5 \equiv 10 \pmod 5$, since the differences ($5$, $-5$, $5$, $10$) are all multiples of $5$.

Skills to practice

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

III 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