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:
- [;\cup \mathbf{P} = X ;] ([;\mathbf{P};] covers [;X;] exactly)
- [; \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 ;]
No comments:
Post a Comment