2.7. Binary relations, ordered sets

A binary relation on E is a graph RE×E. Denoting x R y ⇔ (x,y) ∈ R and letting the domain E of quantifiers implicit, it will be said
reflexive  ⇔   ∀xx R x
irreflexive  ⇔   ∀x, ¬(x R x)
symmetric  ⇔   RtRR = tRR =R
antisymmetric  ⇔   ∀x,y, (x R yy R x)⇒x=y
transitive  ⇔   ∀x,y,z, (x R yy R z)⇒x R z

For any transitive binary relation R we denote x R y R z ⇔ ((x R y)∧(y R z))⇒x R z.
Example. Let AEE and R=fA Gr f. Then
(IdEA) ⇒ R is reflexive
(∀f,gA, gfA) ⇒ R is transitive
(∀fA, f:EEf−1A) ⇒ R is symmetric

Preorder. A preorder R on a set E is a reflexive and transitive binary relation on E. Equivalently,
x,yEx R y ⇔R(x) ⊂R(y)
Proof: ∀x,yExR(x) ⊂ R(y) ⇒ x R y ;
transitivity says x R yR(x) ⊂R(y). ∎

Then tR is also a preorder: x R yR(y) ⊂ R(x).

Ordered set. An order is an antisymmetric preorder. A preordered set is a set E with a chosen preorder R. An ordered set is a set with an order, usually written as .

For x,y in an ordered set E, the formula xy can be read «x is less than y», or «y is greater than x». The elements x and y are said incomparable when ¬(xyyx). (This implies xy).

Any subset F of a set E with an order (resp. a preorder) RE×E, is also ordered (resp. preordered) by its restriction R∩(F×F) (which is an order, resp. preorder, on F).

Strict order. It is a binary relation both transitive and irreflexive; and thus also antisymmetric.

Strict orders < bijectively correspond to orders ≤ by
x < y ⇔ (xyxy).
The inverse correspondence is defined by xy ⇔ (x < yx = y).

Total order. A total order on a set E is an order R on E without any pair of incomparable elements : x,yE, xyyx, i.e. RtR = E×E.

Equivalent definitions:
A strict order associated with a total order, called a strict total order, is any transitive relation < on E such that
x,yE, x < y ⇎ (y < xx=y)
or equivalently ∀x,yE, x=y ⇎ (y < xx < y)).

Monotone, antitone, strictly monotone functions

Between ordered sets E and F, a function f : EF will be said :
Any composite of a chain of monotone or antitone functions, is monotone if the number of antitone functions in the chain is even, or antitone if it is odd. Any strictly monotone or strictly antitone function is injective. If fFE and gEF are both monotone (resp. both antitone) and gf=IdE, then f is strictly monotone (resp. strictly antitone).

Order on sets of functions

For all sets E, F where F is ordered, the set FE (and thus any subset of FE) is ordered by

fg ⇔ (∀xE, f(x) ≤ g(x))

Then, ∀f,gFE, ∀hEG, fgfhgh, i.e. ffh is always monotone.
The particular case F=V2 is that ℘(E) (and thus any set of sets) is naturally ordered by ⊂ , and that h* is monotone from ℘(E) to ℘(G).
If F and G are ordered and uGF is monotone (resp. antitone) then FEfufGE is monotone (resp. antitone).
In an ordered set E, a function fEE is said extensive if
xE, xf(x)
i.e. IdEf. The composite of two extensive functions is extensive.

Set theory and Foundations of Mathematics

1. First foundations of mathematics
 2. Set theory (continued)
2.1. Tuples, families
2.2. Boolean operators on families of sets
2.3. Products, graphs and composition
2.4. Uniqueness quantifiers, functional graphs
2.5. The powerset axiom
2.6. Injectivity and inversion
2.7. Properties of binary relations on a set ; ordered sets
2.8. Canonical bijections
2.9. Equivalence relations and partitions
2.10. Axiom of choice
2.11. Notion of Galois connection
3. Model theory