Binary Relations and Their Properties

Binary Relations

Definition

A binary relation $R$ on $A$ is a subset of $A \times A$. We write $aRb$ or $(a, b) \in R$.

Properties:

• Reflexivity: $aRa$ for all $a$.
• Antireflexivity: not $aRa$ for any $a$.
• Symmetry: $aRb \to bRa$.
• Antisymmetry: $aRb$ and $bRa \to a = b$.
• Transitivity: $aRb$ and $bRc \to aRc$.

Equivalence Relations

Reflexive + symmetric + transitive = equivalence relation ($\sim$).

Equivalence class: $[a] = {b: b \sim a}$. The classes form a partition of $A$ (pairwise disjoint, cover $A$).

Examples: Equality modulo $n$: $a \sim b \iff n \mid (a-b)$. Classes: ${0, n, 2n, \ldots}$, ${1, n+1, 2n+1, \ldots}$, ..., ${n-1, 2n-1, \ldots}$.

Congruence of triangles (by three sides/angles).

Order Relations

Partial order (poset): reflexive, antisymmetric, transitive. Example: divisibility on $\mathbb{N}$.

Linear order: additionally comparability: for any $a, b$: $aRb$ or $bRa$. Example: usual $\le$ on $\mathbb{R}$.

Least element and infimum: Minimal $\ne$ least (least is less than all, minimal — none less). In partially ordered sets, there may be several minimal elements.

Hasse Diagrams

For finite posets: points are elements; edges from bottom to top — if $a < b$ and there is no $c$ with $a < c < b$. A visual representation of the order structure.

The Boolean lattice $2^{{1,2,3}}$: all subsets of ${1,2,3}$ with inclusion. 8 elements. The diagram is a cube.

Properties of Order Relations: Minima and Maxima

In partially ordered sets, it is important to distinguish several concepts. The least element (minimum) is an element $m$ that is less than all others: $m \le x$ for all $x$. A minimal element is an element $m$ with none less: there does not exist $x < m$. In a linear order these coincide, but in a partial order they do not. For example, in the poset ${a, b, c}$ with $a < c$ and $b < c$ (but $a$ and $b$ are incomparable), elements $a$ and $b$ are both minimal, but neither is the least.

The least upper bound (sup, supremum) of a set $S$ is the smallest element greater than or equal to all elements of $S$. The greatest lower bound (inf, infimum) is the largest of the lower bounds. In the field $\mathbb{R}$ with the usual order: $\sup{x : x^2 < 2} = \sqrt{2} \in \mathbb{R}$, though $\sqrt{2} \notin \mathbb{Q}$ — this is one way to construct real numbers from rationals (Dedekind cuts).

Functions and Their Properties

A function $f: A \to B$ is called an injection (monomorphism) if $f(a_1) = f(a_2) \implies a_1 = a_2$ (different elements map to different ones). A surjection (epimorphism) if for each $b \in B$ there exists $a \in A$ with $f(a) = b$ (the image coincides with $B$). A bijection if both injection and surjection. A bijection $f: A \to B$ means $|A| = |B|$.

The number of injections from an $n$-element to an $m$-element set ($m \ge n$): $m!/(m-n)! = A(m, n)$ (arrangements). Number of surjections: $\sum_{k=0}^m (-1)^k C(m, k) (m-k)^n$ (inclusion-exclusion formula). Number of functions: $m^n$.

Applications of Relation Theory in Computer Science

Order relations are ubiquitous in programming. Topological sort is a linear extension of a partial order (task dependencies, compile-order in build systems). Kahn's algorithm: iteratively remove vertices with zero in-degree — works in $O(V + E)$. If the graph is a DAG (directed acyclic graph), this defines a partial order.

Equivalence relations are used in type theory and programming language semantics. Two expressions are observationally equivalent if no program context can distinguish them. This is an equivalence relation, and equivalence classes are "behavioral types" of programs. In version control systems (git), commits form a partial order under the "is ancestor of" relation; the merge operation computes the supremum of two branches.

Euler's Functions and Rings of Residues

In number-theoretic applications, order and equivalence relations are closely connected with arithmetic structures. Euler's function $\varphi(n)$ = the number of integers from 1 to $n$ that are coprime to $n$. Formula: $\varphi(n) = n \cdot \prod_{p|n}(1 - 1/p)$. $\varphi(p) = p-1$ for prime $p$. Euler's theorem: $a^{\varphi(n)} \equiv 1 \pmod n$ for $\gcd(a, n) = 1$ — a generalization of Fermat's little theorem.

The ring of residues $\mathbb{Z}_n = \mathbb{Z}/n\mathbb{Z}$ is the set of equivalence classes modulo $n$. The group of units $\mathbb{Z}_n^* = {a: \gcd(a, n) = 1}$ is the multiplicative group of order $\varphi(n)$. The discrete logarithm in $\mathbb{Z}_n^*$ (problem: find $x$ such that $g^x \equiv h \mod p$) is a computationally hard problem underlying the Diffie-Hellman algorithm and DSA. RSA, unlike these, is based on the problem of factoring large numbers, not the discrete logarithm.

Lattices and Applications to Cryptography

A lattice is a partially ordered set in which every two elements have exact upper and lower bounds. Boolean algebra is a distributive lattice with complement. In cryptography: the closest vector problem (CVP) and shortest vector problem (SVP) in integer lattices are NP-hard problems underlying post-quantum cryptography (the CRYSTALS-Kyber algorithm, standardized by NIST in 2024).

Numerical Example: Equivalence Relations and Partial Order

Problem: (a) Check that congruence modulo 3 is an equivalence relation. (b) Is "divides" an order on ${1,2,3,6}$?

Step 1 (equiv.): $R =,$ " $a \equiv b \pmod 3$ ". Reflexivity: $3 \mid (a-a) = 0$ ✓. Symmetry: $3 \mid (a-b) \to 3 \mid (b-a)$ ✓. Transitivity: $3 \mid (a-b)$, $3 \mid (b-c) \to 3 \mid (a-c)$ ✓. $R$ is an equivalence relation.

Step 2 (equiv.): Classes: $[0]={\ldots,-3,0,3,6,\ldots}$, $[1]={\ldots,-2,1,4,\ldots}$, $[2]={\ldots,-1,2,5,\ldots}$. Factor set $\mathbb{Z}/3\mathbb{Z} = {[0],[1],[2]}$.

Step 3 (order): $R =,$ "$a \mid b

quot; on ${1,2,3,6}$: refr. ($a|a$) ✓, antisym. ($a|b, b|a \to a=b$ for naturals) ✓, trans. ($1|2, 2|6 \to 1|6$) ✓. Partial order.

Step 4: Hasse diagram: $1 \to 2 \to 6$ and $1 \to 3 \to 6$. $2$ and $3$ are incomparable. Lattice: $\sup{2,3}=6$, $\inf{2,3}=1$. Linear extensions: 2 ($1,2,3,6$ or $1,3,2,6$). Connection to cryptography: lattices over $\mathbb{Z}_n$ model LWE (Learning With Errors) problems — the basis of Kyber.