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