See also: Mathematical Analysis - index
A relational graph [;F;] is said to be functional (a functional graph) [;\Leftarrow :\Rightarrow;]
[;\bullet\quad\quad\quad \forall_{\ x\ y\ z}\ \left(\ (x\ y)\ (x\ z)\ \in\ F\ \ \Rightarrow\ \ y=z\ \right);]
EXAMPLE 0 The diagonal [;\Delta_X;] of any set [;X;] is a functional graph.
EXAMPLE 1 The following relational graph
[;\bullet\quad\quad\quad C_{X\,c}\ :=\ X\times \{c\};]
is functional.
On the other hand, when set [;A;] is non-empty, and set [;B;] has more than one element, then their cartesian product [;A\times B;] is a relational graph which is not functional.
A relation [;f := (X\ Y\ F);] is said to be a function from [;X;] to [;Y;] [;\Leftarrow :\Rightarrow;] [;F;] is a functional graph such that
[;\bullet\quad\quad\quad\forall_{\ x\in X}\ \exists_{\ y\in Y}\ (x\ y) \in F;]
NOTATION: When [;f := (X\ Y\ F);] is a function, and [;(x\ y)\in F;] then we write [;y = f(x);]. (the value [;f(x);] is defined uniquely because graph [;F;] is functional). We also write [;f : X \rightarrow Y;], and
[;\bullet\quad\quad\quad graph(f) := F;]
Thus
[;\bullet\quad\quad\quad graph(f)\ =\ \{ (x\ f(x)) : x\in X \};]
EXAMPLE 2 (compare with Example 0) The identity relation
[;\bullet\quad\quad\quad I_X := (X\ X\ \Delta_X);]
is a function, called the identity function in [;X;]. Now another way to define function [;I_X : X \rightarrow X;] is:
[;\bullet\quad\quad\quad \forall_{x \in X}\ I_X(x) := x;]
EXAMPLE 3 (compare with Example 1) Let [;c\in Y;]. The relation
[;\bullet\quad\quad\quad \gamma\ := (X\ Y\ C_{X\,c});]
is a function called the constant function on [;X;] (and into [;Y;]), with constant value [;c;].
We will see in a next post that general functions can be constructed using more special functions, namely canonical surjections, bijections, and canonical injections. The definitions of (arbitrary) surjections, bijections, and (arbitrary) injections are provided already below.
A function [;f : X \rightarrow Y;] is said to be surjective [;\Leftrightarrow\quad \forall_{y\in Y}\exists_{x\in X}\ f(x)=y;].
A function [;f : X \rightarrow Y;] is said to be injective [;\Leftrightarrow\quad \forall_{x'\,x"\in X}\ (f(x')=f(x")\ \Rightarrow\ x'=x");].
A function [;f : X \rightarrow Y;] is said to be bijective [;\Leftrightarrow;] [;f;] is both surjective and injective.
Going back to surjections, let [;\mathbf{T} := (X\ X\ T);] be an equivalence relation. Let [;X/\mathbf{T};] be the set of the equivalence classes of [;\mathbf{T};]. Then the canonical projection is defined as a function
[;\bullet\quad\quad\quad \pi : X \rightarrow X/\mathbf{T};]
defined by equality:
[;\bullet\quad\quad\quad \forall_{x\in X}\ \pi(x) := [x] ;]
where [;[x];] is the equivalence class of [;x;] with respect to the equivalence relation [;\mathbf{T};].
Going back to injections, let [;A \subseteq X;]. Then the canonical embedding of [;A;] into [;X;] is defined as a function:
[;\bullet\quad\quad\quad i_A : A \rightarrow X;]
such that
[;\bullet\quad\quad\quad \forall_{x\in X}\ i_A(x) := x ;]
Showing posts with label relation. Show all posts
Showing posts with label relation. Show all posts
Wednesday, October 20, 2010
Sunday, October 17, 2010
Linear ordering (losets)
See also: Mathematical Analysis - index, and in particular:
For partial order relational graphs we will use symbols like [;\le;], in which case we adopt the convention:
[;\bullet\quad\quad\quad x\ \le\ y\quad\Leftarrow : \Rightarrow\quad (x\ y) \in\ \le ;]
A poset [;(X\ X\ \le);] is called a linear ordering or a loset [;\Leftarrow : \Rightarrow;]
[;\bullet\quad\quad\quad \forall_{\ x\ y\ \in\ X}\ (x\le y\quad\vee\quad y\le x);]
In the same vein, a sharp poset [;(X\ X\ \le);] is called a sharp linear ordering or a sharp loset [;\Leftarrow : \Rightarrow;]
[;\bullet\quad\quad\quad \forall_{\ x\ y\ \in\ X}\ (x < y\quad\vee\quad x=y\quad\vee\quad y < x);]
As in the case of posets and sharp posets, also the linear order [;\le;] and sharp linear order [;<;] relational graphs in a set [;X;] come in pairs such that, which satisfy the following equivalent statements:
in which case we tend to identify [;(X\ X\ \le);] as the same object as [;(X\ X\ <);].
An pair [;(A\ B);] is a partition of a set [;X;] [;\Leftarrow :\Rightarrow;] [; A\cap B = \emptyset\ \ \&\ \ A\cup B = X;]. Now let [;(X\ X\ \le);] be a loset. A partition is called proper [;\Leftarrow :\Rightarrow;] both sets [;A\ B;] are non-empty. Finally, a proper partition [;(A\ B);] is called a Dedekind partition [;\Leftarrow :\Rightarrow;]
[;\bullet\quad\quad\quad\forall_{a\in A}\forall_{b \in B}\ a \le b;]
Each Dedekind partition is of exactly one of the following three types:
In plain English this means that
A loset [;\mathbf{L};] is called relatively complete [;\Leftarrow : \Rightarrow\quad\mathbf{L};] has no holes. A relatively complete loset is called complete [;\Leftarrow : \Rightarrow\quad\mathbf{L};] has both its minimal and maximal elements.
A relatively complete loset [;\mathbf{L};] is called a Dedekind loset [;\Leftarrow : \Rightarrow\quad\mathbf{L};] has no jumps; or more directly (but equivalently), a loset [;\mathbf{L};] is Dedekind [;\Leftrightarrow;] every Dedekind partition in [;\mathbf{L};] has its Dedekind section.
For partial order relational graphs we will use symbols like [;\le;], in which case we adopt the convention:
[;\bullet\quad\quad\quad x\ \le\ y\quad\Leftarrow : \Rightarrow\quad (x\ y) \in\ \le ;]
A poset [;(X\ X\ \le);] is called a linear ordering or a loset [;\Leftarrow : \Rightarrow;]
[;\bullet\quad\quad\quad \forall_{\ x\ y\ \in\ X}\ (x\le y\quad\vee\quad y\le x);]
In the same vein, a sharp poset [;(X\ X\ \le);] is called a sharp linear ordering or a sharp loset [;\Leftarrow : \Rightarrow;]
[;\bullet\quad\quad\quad \forall_{\ x\ y\ \in\ X}\ (x < y\quad\vee\quad x=y\quad\vee\quad y < x);]
As in the case of posets and sharp posets, also the linear order [;\le;] and sharp linear order [;<;] relational graphs in a set [;X;] come in pairs such that, which satisfy the following equivalent statements:
- [;<\quad =\quad\le\ \backslash\ \Delta_X;]
- [;\le\quad =\quad <\ \cup\ \Delta_X;]
in which case we tend to identify [;(X\ X\ \le);] as the same object as [;(X\ X\ <);].
An pair [;(A\ B);] is a partition of a set [;X;] [;\Leftarrow :\Rightarrow;] [; A\cap B = \emptyset\ \ \&\ \ A\cup B = X;]. Now let [;(X\ X\ \le);] be a loset. A partition is called proper [;\Leftarrow :\Rightarrow;] both sets [;A\ B;] are non-empty. Finally, a proper partition [;(A\ B);] is called a Dedekind partition [;\Leftarrow :\Rightarrow;]
[;\bullet\quad\quad\quad\forall_{a\in A}\forall_{b \in B}\ a \le b;]
Each Dedekind partition is of exactly one of the following three types:
- a hole: [;\forall_{a\in A} \exists_{a'\in A}\ a < a'\quad\quad\&\quad\quad\forall_{b\in B} \exists_{b'\in B}\ b' < b;]
- a continuity, where one of the two conditions holds:
- [;\exists_{a\in A} \forall_{a'\in A}\ a' \le a\quad\quad\&\quad\quad\forall_{b\in B} \exists_{b'\in B}\ b' < b;]
- [;\forall_{a\in A} \exists_{a'\in A}\ a < a'\quad\quad\&\quad\quad\exists_{b\in B} \forall_{b'\in B}\ b \le b';]
- a jump: [;\exists_{a\in A} \forall_{a'\in A}\ a' \le a\quad\quad\&\quad\quad\exists_{b\in B} \forall_{b'\in B}\ b \le b';]
In plain English this means that
- in the case of a hole neither A has a maximal element nor B has a minimal element;
- in the continuous case either A has a maximal element [;a;] or B has a minimal element [;b;], but not both; that unique maximal [;a;] or minimal [;b;] is called the Dedekind section of the Dedekind partition [;(A\ B);] of [;X;];
- in the case of a jump the set [;A;] has its maximal element, and [;B;] has its minimal element.
A loset [;\mathbf{L};] is called relatively complete [;\Leftarrow : \Rightarrow\quad\mathbf{L};] has no holes. A relatively complete loset is called complete [;\Leftarrow : \Rightarrow\quad\mathbf{L};] has both its minimal and maximal elements.
A relatively complete loset [;\mathbf{L};] is called a Dedekind loset [;\Leftarrow : \Rightarrow\quad\mathbf{L};] has no jumps; or more directly (but equivalently), a loset [;\mathbf{L};] is Dedekind [;\Leftrightarrow;] every Dedekind partition in [;\mathbf{L};] has its Dedekind section.
Thursday, September 30, 2010
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:
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:
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 ;]
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 ;]
Wednesday, September 29, 2010
Transitivity reflexivity preorder
See also: Mathematical Analysis - index
A relational graph [;T;] is called transitive [;\Leftarrow : \Rightarrow;]
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;]
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.
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:
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.
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.
Subscribe to:
Posts (Atom)