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.

Relational graphs and relations

See also: Mathematical Analysis — index

---

Let's start with three definitions:

• The Cartesian product  [;X\times Y;]  of two sets  [;X\ Y;]  is defined as the set of all ordered pairs such that their first and second terms belong respectively to  [;X\ Y;]:
  
  [;:\quad\quad X\times Y\ \ :=\ \ \{(x\ y)\ :\ x\in X\ \ \&\ \ y\in Y\};]
  
• 
  A set [;T;] is said to be a relational graph  [; \Leftarrow : \Rightarrow ;]  every element of [;T;] is an ordered pair.
  
• 
  An ordered triple  [;\mathbf{T} := (X\ Y\ T);]  is said to be a relation  [; \Leftarrow : \Rightarrow\ \ T ;]  is a relational graph such that [;T \subseteq X\times Y ;].  Such a relation  [;\mathbf{T};]  is said to be a relation in the sets  [;X\ \ Y;],  where  [;X;]  is called the domain of relation  [;\mathbf{T};],  and  [;Y;] is called the codomain or the target of [;\mathbf{T};].
  

REMARK  We could define a relation in fewer words: an ordered triple  [;\mathbf{T} := (X\ Y\ T);]  is said to be a relation  [; \Leftarrow : \Rightarrow\ \ T \subseteq X\times Y ;].

We see that a relation is an ordered triple of the form:

          (domain  codomain  rel_graph)

where rel_graph is a relational graph contained in the Cartesian product of the domain and codomain.

Observe that  [;(X \ Y\ X\times\ Y);]  is a relation in the sets  [;X\ \ Y;];  its relational graph contains the relational graph of any other relation in the sets  [;X\ \ Y;].  Also the empty set is a relational graph. It is contained in any other relational graph. Thus any relational graph of any relation in the sets  [;X\ \ Y;];  is contained between these two relational graphs.

Kuratowski ordered pairs

See also: Mathematical Analysis — index

---

An unordered pair is simply a 2-element set, say  [;\{a\ \ b\};],  where  [;a \ne b ;]  (note that when  [; a = b ;]  then  [;\{a\ \ b\};],  is a 1-element set).

Notation for ordered pairs is  [;(a\ \ b);],  where  [;a\ \ b;]  are arbitrary--they can be different or they may coincide. The ordered pairs satisfy the following axiom:

[; :\quad\quad (a\ \ b)\ =\ (c\ \ d)\ \ \ \Leftrightarrow\ \ \ (a=c\ \ \&\ \ b=d) ;]

An elegant constructive definition of an ordered pair in the set-theoretical term was given by Kazimierz Kuratowski:

[; :\quad\quad (a\ \ b)\ :=\ \{ \{ a \}\ \{a\ \ b\}\} ;]

---

Now we can define an ordered triple [;(a\ \ b\ \ c);]. It can be done in many different ways. For many purposes the details of an exact constructive definition are irrelevant. Then it is important only that ordered triples satisfy the following axiom:

[; :\quad\quad (a\ \ b\ \ c)\ =\ (x\ \ y\ \z)\ \ \ \Leftrightarrow\ \ \ (a=x\ \ \&\ \ b=y\ \ \&\ \ c=z) ;]

A definition in the Kuratowski's style is:

[; :\quad\quad (a\ \ b\ \ c)\ :=\ \{ \{ a \}\ \{a\ \ b\}\ \{a\ \ b\ \ c\}\} ;]

We may use Kuratowski pairs to define an ordered triple as a sequence of length 3:

[; :\quad\quad (a\ \ b\ \ c)\ :=\ \{ (0\ a)\ \ (1\ b)\ \ (2\ c) \} ;]

or as a string (again of length 3):

[; :\quad\quad (a\ \ b\ \ c)\ := (a\ \ (b\ \ c)) ;]

where  [;a;]  is called the head of the string, and [;(b\ \ c);] is the tail of the string.

Different types of the triples of the same three elements [;a\ b\ c;] are not equal. Thus be consistent, don't mix them. And if you do then use different notation for each type.