2.9. Binary relations on a set

A binary relation on a set E is a relation with both domains equal to E, thus formalized by a graph R ⊂ E×E. Let us abbreviate E×E as E2 and (x,y) ∈ R as x R y

Preimages and products

For any function f : E → F and any binary relation R on F, the preimage of R by f is the binary relation f⋆(R) on E defined as

{(x,y)∈E2 | f(x) R f(y)}

For any family of a binary relations (Ri)i∈I on respective sets Fi, their product is the binary relation on P = ∏i∈I Fi defined as

{(x,y)∈P2 | ∀i∈I, xi Ri yi} = ⋂i∈I πi⋆(Ri).

(It is actually in canonical bijection with the product of sets ∏i∈I Ri)
In particular with a constant family : any binary relation on a set F defines one on any FI.

Both operations can be combined in one step: for any family of functions fi : E → Fi, the relation

{(x,y)∈E2 | ∀i∈I, fi(x) Ri fi(y)} = ⋂i∈I fi⋆(Ri)

is the preimage of the product relation of the Ri on P, by the function ⊓i∈I fi : E → P.

These concepts will be later generalized to other first-order structures.

Basic properties

A binary relation R on a set E will be said

reflexive  ⇔  ∀x∈E, xRx ⇔  𝛿E ⊂ R ⇒ Dom R = Im R = E
irreflexive  ⇔   ∀x∈E, ¬(xRx)
symmetric  ⇔  (∀x,y∈E, xRy ⇒ yRx) ⇔ R ⊂ tR ⇔ R = tR ⇔ (R⃗) = (R⃖)
antisymmetric  ⇔   ∀x,y∈E, (xRy ∧ yRx) ⇒ x = y
transitive  ⇔   ∀x,y,z∈E, (xRy ∧ yRz) ⇒ xRz

These properties are preserved by transposition, preimages and products, except that the preimage of an antisymmetric relation by a non-injective function may not be antisymmetric, and the empty product (I=∅) is not irreflexive.
In particular for F ⊂ E, the restriction of a relation R ⊂ E×E to F, namely R∩(F×F), is its preimage by IdF : F ↪ E, thus preserves all properties.

Example. Let A ⊂ EE and R = ⋃f∈A Gr f. Then

(IdE ∈ A) ⇒ R is reflexive
(∀f,g∈A, g⚬f ∈ A) ⇒ R is transitive
(∀f∈A, f : E↔E ∧ f -1∈ A) ⇒ R is symmetric

For any transitive binary relation R we denote x R y R z ⇔ (x R y ∧ y R z) ⇒ x R z.

Preorders and orders

A preorder is a reflexive and transitive binary relation. An order is an antisymmetric preorder.
A preordered set is (an ordered pair of) a set with a chosen preorder on it.
An ordered set is a set with a chosen order, usually written as ≤ or ≤E. The formula x ≤ y can be read «x is less than y», or «y is greater than x».
Two elements x, y of an ordered set are said comparable when (x≤y ∨ y≤x).

On the class of sets, the meta-relation ⥬ (existence of a canonical bijection) is a meta-preorder.
The Boolean pair V2 is naturally ordered by ⇒ which coincides there with the usual order between numbers.
The resulting product order on V2E ⥬ ℘(E) (and thus any set of sets) is that of inclusion (⊂).

Any relation R ⊂ E×F defines a preorder on E as the preimage by R⃗ of the inclusion order:

{(x,y)∈E2 | R⃗(x) ⊂ R⃗(y)}.

Conversely, any preorder R on a set E is so definable from itself in both ways (exchanged by transposition):

∀x,y∈E, R⃗(y) ⊂ R⃗(x) ⇔ x R y ⇔ R⃖(x) ⊂ R⃖(y)

Proof. Transitivity is equivalent to (∀x,y∈E, x R y ⇒ R⃗(y) ⊂ R⃗(x)) and to (∀x,y∈E, x R y ⇒ R⃖(x) ⊂ R⃖(y)).
Reflexivity is equivalent to the converses:

∀x∈E, (∀y∈E, R⃗(x) ⊂ R⃗(y) ⇒ y R x) ⇔ x R x ⇔ (∀y∈E, R⃖(x) ⊂ R⃖(y) ⇒ x R y). ∎

Thus R is the preimage of ⊂ by (R⃖). Moreover,

∀x,y∈E, R⃖(x) = R⃖(y) ⇔ (R⃖(x) ⊂ R⃖(y) ∧ R⃖(y) ⊂ R⃖(x)) ⇔ (xRy ∧ yRx)

so that (R⃖) is injective if and only if R is an order.
The idea of considering only one order written ≤ on each set E, may be formalized by replacing the ordered set (E,R) by (Im(R⃖), ⊂), though this does not exactly fit the following convention : any subset of an ordered set will be implicitly also ordered by restriction.

Strict and total orders

A strict order is a binary relation both transitive and irreflexive; and thus also antisymmetric.

Strict orders < bijectively correspond to orders ≤ by

x < y ⇔ (x ≤ y ∧ x ≠ y).
x ≤ y ⇔ (x < y ∨ x = y).

A total order on a set E is an order where all elements are comparable (∀x,y∈E, x ≤ y ∨ y ≤ x), i.e. (≤ ∪ t≤) = E×E.
Equivalent definitions: A strict total order on a set E is a strict order associated with a total order, i.e. any transitive relation < such that, equivalently

∀x,y∈E, x < y ⇎ (y < x ∨ x = y)
∀x,y∈E, x = y ⇎ (y < x ∨ x < y)

Equivalence relations

An equivalence relation is a symmetric preorder.
On any set E, the equality relation 𝛿E is an equivalence relation (as already expressed by the axioms of equality), and the only relation altogether symmetric, antisymmetric and reflexive.
On any product of sets, the product of equality relations is also equality.
The preimage of equality by any f : E → F is an equivalence relation on E we shall write ∼f :

∼f = {(x,y)∈E | f(x) = f(y)} = ∐(f•⚬f)
Inj f ⇔ ∼f = 𝛿E

Conversely, any equivalence relation R is so definable from itself : R = ∼R⃗. Indeed

∀x,y∈E, x R y ⇔ R⃗(y) ⊂ R⃗(x) ⇔ R⃗(x) ⊂ R⃗(y) ⇔ R⃗(x) = R⃗(y)

Quotient functions

Proposition. ∀SetE,F,G, ∀f, (f : E ↠ F) ⇒ (GF ∋ g ↦ g⚬f) : GF ↔ {h∈GE | ∼f ⊂ ∼h}.

Proof : ∀...∀f∈FE, ∀h∈GE, H = Im(f×h) ⇒

∼f ⊂ ∼h ⇔ (∀x,x'∈E, f(x) = f(x′) ⇒ h(x) = h(x′)) ⇔ (∀(y,z), (y′,z′) ∈ H, y=y′ ⇒ z=z′)
Dom H = Im f ∧ ∀g∈GF, h = g⚬f ⇔ H ⊂ Gr g. ∎

For any functions f,h such that Dom f = Dom h ∧ ∼f ⊂ ∼h, this unique g : Im f ↠ Im h such that h = g⚬f will be called the quotient of h by f:

h/f = (Im f ∋y↦ ℩h[f•(y)])
Gr (h/f) = Im (f×h)
Inj f ⇒ (f -1 = IdDom f /f ∧ h/f = h⚬f -1)
∼f = ∼h ⇔ Inj(h/f) ⇒ (h/f)-1 = f/h

In the more general case Im f ⊂ Dom g (without surjectivity of f),

h = g⚬f ⇒ (∼f ⊂ ∼h ∧ h/f = g|Im f)
⇒ (∼f  = ∼h ⇒ f = (g|Im f)−1⚬h)

The formula that ∼f is an equivalence relation,

∀x,y ∈ Dom f, x ∼f y ⇔ ∼⃗f(x) =  ∼⃗f(y)

where (∼⃗f) = f•⚬f, reflects the injectivity of (f•) which can be directly seen as

∀y∈Im f, ∀z, f•(y) = f•(z) ⇒ f•(y) ∩ f•(z) = f•(y) ≠ ∅ ⇒ y = z.

Partitions

A partition of a set E is a set of nonempty, pairwise disjoint sets, whose union is E.
In other words, it is a set P of subsets of E such that IdP is an indexed partition of E.
The image of any indexed partition is a partition of the same set: for any function f with image E, Im(f•) = f•[E] = Im(f•⚬f) is a partition of E.
∀R ⊂ E×E, if P = R⃗[E] then

(∀x,y∈E, x∈R⃗(y) ⇔ R⃗(x) = R⃗(y)) ⇔ (∀x∈E, ∀A∈P, x∈A ⇔ R⃗(x) = A) ⇔ IdP = (R⃗E•)

Thus if R is an equivalence relation then P is a partition.
Inversely, any partition P of E defines a function g and then a graph R by

Dom g = E ∧ (g•) = IdP ∴ P = Dom (g•) = Im g
R = ∐g ⊂ E×E ∴ g = R⃗E ∴ (P = R⃗[E] ∧ IdP = (R⃗E•))

thus R is an equivalence relation on E and

∀x,y∈E, xRy ⇔ y∈ ℩{A∈P | x∈A} ⇔ (∃A∈P, x∈A ∧ y∈A) ⇔ (∀A∈P, x∈A ⇒ y∈A).

For any equivalence relation R on E, the partition R⃗[E] = Im (R⃗) is called the quotient of E by R, and written E/R, so that

(R⃗) : E ↠ E/R.

For any x ∈ E, the set R⃗(x) = ℩{A∈E/R | x∈A} is called the class of x by R.
For any function f such that Dom f = E ∧ R ⊂ ∼f, let us abbreviate f/(R⃗) as f/R:

f/R : E/R ↠ Im f
Inj f/R ⇔ R = ∼f

So when R = ∼f the role of E/R may be played by Im f.
In particular, any preorder R on a set E gives an equivalence relation R∩tR, and the role of E/(R∩tR) may be played by Im (R⃖).

Set theory and Foundations of Mathematics
1. First foundations of mathematics
2. Set theory
2.1. Formalization of set theory
2.2. Set generation principle
2.3. Tuples
2.4. Uniqueness quantifiers
2.5. Families, Boolean operators on sets
2.6. Graphs
2.7. Products and powerset		 2.8. Injections, bijections ⇦
2.9. Binary relations on a set
⇨ 2.10. Axiom of choice
2.A. Time in set theory
2.B. Interpretation of classes
2.C. Concepts of truth in mathematics
3. Algebra - 4. Arithmetic - 5. Second-order foundations

Other languages:
FR : 2.9. Relations binaires sur un ensemble