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.
No comments:
Post a Comment