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;];
Subscribe to:
Posts (Atom)