Partial ordering (posets)

See also: Mathematical Analysis - index, and in particular:

• relational graphs & relations


• preorder


• equivalence

---

A relational graph  T  is called weakly antisymmetric  [;\Leftarrow:\Rightarrow;]
[;\bullet\quad\quad \forall_{\ x\ y}\ \left(\ \left(\left(x\ y\right) \in T\ \ \&\ \ \left(y\ x\right) \in T\right)\quad\Rightarrow\quad x=y\ \right);]

A relational graph  [;T;]  is called strongly antisymmetric   [;\Leftarrow:\Rightarrow;]

[;\bullet\quad\quad \forall_{\ x}\ (x\ x) \notin T;]

The following two properties of a relation  [;\mathbf{T} := (X\ X\ T);]  are equivalent:

• [;\mathbf{T};]  is an equivalence and it is weakly antisymmetric;


• [;T = \Delta_X;]

---

A partially ordered set, or a poset for short, is a preordered relation  [;\mathbf{T} := (X\ X\ T);],  which is (weakly) antisymmetric; thus, to write the same explicitly, a poset is characterized by the following three properties:

1. transitivity;
2. reflexivity
3. weak antisymmetry

---

Posets admit a similar notion of sharp posets. First we define a sharp partial order relational graph  [;S;]  as transitive and strongly antisymmetric in the above sense:

[;\bullet\quad\quad\quad \forall_x (x\ x)\ \notin\ S;]

A relation  [;(X\ X\ T);]  is called a sharp poset  [;\Leftarrow :\Rightarrow;]  [;T;] is a sharp partial order relational graph.

Given relations  [;\mathbf{S} := (X\ X\ S);]  and  [;\mathbf{T} := (X\ X\ T);]  the following two equivalences hold:

• [;\mathbf{S};] is a sharp poset  [;\Leftrightarrow;]  [;\mathbf{T};] is a poset  such that [;S = T \backslash \Delta_X;];


• [;\mathbf{T};] is a poset  [;\Leftrightarrow;]  [;\mathbf{S};] is a sharp poset  such that [;T = S \cup \Delta_X;];

Equivalence

See also: Mathematical Analysis

---

Let's recall that a relation is said to be a preorder  [;\Leftarrow : \Rightarrow ;] it is reflexive and transitive.

Two important classes of preorders are equivalences and partial orders called also posets (for partially ordered sets). This post is concerned with equivalences. But first the notion of commutativity is defined (in the context of relations).

---

A relational graph  T  is called commutative (or symmetric)  [;\Leftarrow : \Rightarrow ;]

[; :\quad\quad \forall_{x\ \ y}\ ((x\ y)\in T\quad\Leftrightarrow\quad (y\ x)\in T) ;]

REMARK 0  It's amusing (to me) that by replacing  [;\Leftrightarrow ;]  by  [;\Rightarrow ;]  we would obtain a differently looking definition of the same class of commutative relational graphs.

We may describe the same commutativity notion via reversed relational graphs, where the reversed relation graph  [;T^\circ;]  reversed to a relational graph  [;T;]  is defined as follows:

[; :\quad\quad T^\circ := \{(y\ x) : (x\ y) \in T\} ;]

THEOREM 0   A relational graph  [;T;]  is commutative   [;\Leftrightarrow\quad T^\circ = T ;].

---

A relation  [;\mathbf{T} := (X\ X\ T) ;]  is called commutative (or symmetric)  [;\Leftarrow : \Rightarrow ;]  [;T;]  is a commutative relational graph.

DEFINITION 0  A relation  [;\mathbf{T} := (X\ X\ T) ;]  is said to be an equivalence  [;\Leftarrow : \Rightarrow ;]  the relational graph  [;T;]  is transitive, commutative and reflexive.

In other words, for a relation to be an equivalence is the same as to be a commutative preorder.

---

A family of sets  [;\mathbf{P};]  is called a partition of a set  [;X;]  [;\Leftarrow : \Rightarrow ;]  the following two statements hold:

1. [;\cup \mathbf{P} = X ;]       ([;\mathbf{P};]  covers  [;X;]  exactly)


2. [; \forall_{A\ B\ \in\ \mathbf{P}}\ (A=B\ \ \vee\ \ A\cap B = \emptyset) ;]

With every partition  [;\mathbf{P};]  of set  [;X;] there is associated canonically an equivalence relation  [;\equiv_\mathbf{P};]  in  [;X;]  defined as follows:

[;:\quad\quad (x\ y)\ \in\ \ \equiv_{\mathbf{P}}\quad\Leftarrow : \Rightarrow\quad \exists_{A\in\mathbf{P}}\ x\ y\in A ;]

i.e.

[;:\quad\quad\quad \equiv_{\mathbf{P}}\ \ :=\ \cup_{A\in \mathbf{P}}\ A\times A ;]

And conversely, every equivalence  [;\mathbf{T};]  in a set  [;X;]  canonically leads to a partition  [;\mathbf{P}_{\mathfb{T}};]  of  [;X;]  defined as a family of equivalence classes as follows:

[;:\quad\quad \mathbf{P}_{\mathfb{T}}\ :=\ \{[x] : x\in X\} ;]

where the equivalence class  [;[x];]  is given by equality:

[;:\quad\quad\quad [x]\ :=\ \{ y\in X\ :\ (x\ y)\in\mathbf{T} \} ;]

This completes a description of a one to one canonical correspondence between equivalence relations and partitions.

---

Two extremal examples of equivalences:

• [;(X\ X\ \Delta_X);]  is the so called strongest equivalence relation in a set  [;X;];


• [;(X\ X\ X\!\times\! X);]  is the so called weakest equivalence relation in a set  [;X;].

Every equivalence relation  [;(X\ X\ T;]  is contained between the two above in the following sense:

[;\bullet\quad\quad\quad \Delta_X\ \subset T\ \subset\ X\!\times\! X ;]

Transitivity reflexivity preorder

See also: Mathematical Analysis - index

---

A relational graph [;T;] is called transitive  [;\Leftarrow : \Rightarrow;] 

• 
  [; \forall_{x\ y\ z} (((x\ y) \in T\ \ \&\ \ (y\ z) \in T)\quad (x\ z) \in T) ;]
  

A relation [;\mathbf{T} := (X\ X\ T);] is called transitive  [;\Leftarrow : \Rightarrow;]  the relational graph  [;T;]  is transitive.

REMARK 0  Transitivity is defined only for relations for which codomain coincides with the domain (we have  [;X=Y;]  so to speak). When codomain coincides with the domain, say  [;X=Y;],  then we say that the relation is in  [;X;]  (rather than in  [;X\ Y;]).

---

A relational graph  [;T;]  is called reflexive  [;\Leftarrow : \Rightarrow;] 

• [;\forall_{x\ y} ( (x\ y) \in T\quad\Rightarrow\quad ((x\ x)\in T\ \ \&\ \ (y\ y) \in T) ;]

---

Let  [;X;]  be an arbitrary set. Then the following set  [;\Delta_{X};]  is called the diagonal of  [;X;]:

[;: \quad\quad \Delta_{X} := \{ (x\ x) : x\in X \} ;]

We see that  [;\Delta_{X};]  is a relational graph, and that

[;: \quad\quad \mathbf{\Delta}_{X}\ \ :=\ \ (X\ X\ \Delta_{X}) ;]

is a relation in  [;X;].

A relation [;\mathbf{T} := (X\ X\ T);] is called reflexive  [;\Leftarrow : \Rightarrow;]  the relational graph  [;T;]  contains the diagonal:  [;\Delta_X \subseteq T;].

REMARK 1  Reflexivity is defined only for relations for which codomain coincides with the domain.

REMARK 2  The relational graph of any reflexive relation is reflexive, while the inverse claim fails: a relation may have a reflexive graph without being reflexive, as for instance the empty relation in a non-empty set  [;X;]:

[;:\quad\quad(X\ X\ \emptyset) ;]

THEOREM 0  Let  [;\mathbf{T} := (X\ X\ T);]  be a transitive relation. Then the relational graph

[; :\quad\quad\underline{T} := T\cup\Delta_X ;]

is both transitive and reflexive. Furthermore

[; :\quad\quad\underline{\mathbf{T}} := (X\ X\ \underline{T});]

is a transitive and reflexive relation

---

A relation which is both transitive and reflexive is called a preorder.

We saw that each transitive relation in  [;X;]  leads to a preorder by extending it by the diagonal  [; \Delta_X;].

Diagonal  [;\Delta_{X};]  itself is a preorder. And so is the complete relation in  [;X;],  which has  [;X\times X;]  for its relational graph.