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 ;]
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.
Saturday, October 16, 2010
Partial ordering (posets)
See also: Mathematical Analysis - index, and in particular:
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:
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:
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:
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:
- transitivity;
- reflexivity
- 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;];
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.
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.
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.
Subscribe to:
Posts (Atom)