Namespaces
Variants
Actions

Difference between revisions of "Totally ordered set"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(also: linear order)
 
(3 intermediate revisions by the same user not shown)
Line 1: Line 1:
''chain''
+
''chain, linear order''
  
A [[Partially ordered set|partially ordered set]] in which for any two elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093500/t0935001.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093500/t0935002.png" /> either <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093500/t0935003.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093500/t0935004.png" />. A subset of a totally ordered set is itself a totally ordered set. Every maximal (minimal) element of a totally ordered set is a largest (smallest) element. An important special case of totally ordered sets are the well-ordered sets (cf. [[Well-ordered set|Well-ordered set]]). Among the subsets of a partially ordered set that are totally ordered sets, a particularly important role is played by a [[Composition sequence|composition sequence]]. A cut of a totally ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093500/t0935005.png" /> is a partition of it into two subsets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093500/t0935006.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093500/t0935007.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093500/t0935008.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093500/t0935009.png" /> is empty, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093500/t09350010.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093500/t09350011.png" />, where
+
A [[partially ordered set]] in which for any two elements $a$ and $b$ either $a \le b$ or $b \le a$. A subset of a totally ordered set is itself a totally ordered set. Every maximal (minimal) element of a totally ordered set is a largest (smallest) element. An important special case of totally ordered sets are the well-ordered sets (cf. [[Well-ordered set]]). Among the subsets of a partially ordered set that are totally ordered sets, a particularly important role is played by a [[composition sequence]]. A cut of a totally ordered set $P$ is a partition of it into two subsets $A$ and $B$ such that $A \cup B = P$, $A \cap B$ is empty, $A \subseteq B^\nabla$ and $B \subseteq A^\Delta$, where
 
+
$$
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093500/t09350012.png" /></td> </tr></table>
+
B^\nabla = \{ x \in P : x \le b \ \text{for all}\ b \in B \} \ ,
 
+
$$
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093500/t09350013.png" /></td> </tr></table>
+
$$
 
+
A^\Delta = \{ x \in P : x \ge a \ \text{for all}\ a \in A \} \ .
The classes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093500/t09350014.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093500/t09350015.png" /> are called the lower and upper classes of the cut. One can distinguish the following types of cuts: a jump — there is a largest element in the lower class and a smallest element in the upper class; a Dedekind cut — there is a largest (smallest) element in the lower (upper) class, but no smallest (largest) element in the upper (lower) class; a gap — there is no largest element in the lower class and no smallest element in the upper class. A totally ordered set is said to be continuous if all its cuts are Dedekind cuts. A subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093500/t09350016.png" /> of a totally ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093500/t09350017.png" /> is said to be dense if every interval of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093500/t09350018.png" /> not reducing to a single element contains elements belonging to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093500/t09350019.png" />. The totally ordered set of real numbers can be characterized as a continuous totally ordered set which has neither a largest nor a smallest element, but which contains a countable dense subset. Every countable totally ordered set is isomorphic to some subset of the totally ordered set of all binary fractions in the interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093500/t09350020.png" />. A [[Lattice|lattice]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093500/t09350021.png" /> is isomorphic to a subset of the totally ordered set of integers if and only if every sublattice of it is a [[Retract|retract]].
+
$$
 +
The classes $A$ and $B$ are called the lower and upper classes of the cut. One can distinguish the following types of cuts: a jump — there is a largest element in the lower class and a smallest element in the upper class; a [[Dedekind cut]] — there is a largest (smallest) element in the lower (upper) class, but no smallest (largest) element in the upper (lower) class; a gap — there is no largest element in the lower class and no smallest element in the upper class. A totally ordered set is said to be a [[continuous set]] if all its cuts are Dedekind cuts. A subset $D$ of a totally ordered set $P$ is said to be dense if every interval of $P$ not reducing to a single element contains elements belonging to $D$. The totally ordered set of real numbers can be characterized as a continuous totally ordered set which has neither a largest nor a smallest element, but which contains a countable dense subset. Every countable totally ordered set is isomorphic to some subset of the totally ordered set of all binary fractions in the interval $[0,1]$. A [[lattice]] $L$ is isomorphic to a subset of the totally ordered set of integers if and only if every sublattice of it is a [[Retract|retract]].
  
 
====References====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  P.S. Aleksandrov,  "Einführung in die Mengenlehre und die Theorie der reellen Funktionen" , Deutsch. Verlag Wissenschaft.  (1956)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  P.S. Aleksandrov,  "Einführung in die Mengenlehre und in die allgemeine Topologie" , Deutsch. Verlag Wissenschaft.  (1984)  (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  N. Bourbaki,  "Elements of mathematics. Theory of sets" , Addison-Wesley  (1968)  (Translated from French)</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[1]</TD> <TD valign="top">  P.S. Aleksandrov,  "Einführung in die Mengenlehre und die Theorie der reellen Funktionen" , Deutsch. Verlag Wissenschaft.  (1956)  (Translated from Russian)</TD></TR>
 +
<TR><TD valign="top">[2]</TD> <TD valign="top">  P.S. Aleksandrov,  "Einführung in die Mengenlehre und in die allgemeine Topologie" , Deutsch. Verlag Wissenschaft.  (1984)  (Translated from Russian)</TD></TR>
 +
<TR><TD valign="top">[3]</TD> <TD valign="top">  N. Bourbaki,  "Elements of mathematics. Theory of sets" , Addison-Wesley  (1968)  (Translated from French)</TD></TR>
 +
</table>
  
  
Line 18: Line 23:
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  W. Sierpiński,  "Cardinal and ordinal numbers" , PWN  (1958)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  M.M. Zuckerman,  "Sets and transfinite numbers" , Macmillan  (1974)</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  W. Sierpiński,  "Cardinal and ordinal numbers" , PWN  (1958)</TD></TR>
 +
<TR><TD valign="top">[a2]</TD> <TD valign="top">  M.M. Zuckerman,  "Sets and transfinite numbers" , Macmillan  (1974)</TD></TR>
 +
</table>
 +
 
 +
[[Category:Order, lattices, ordered algebraic structures]]

Latest revision as of 16:59, 9 January 2016

chain, linear order

A partially ordered set in which for any two elements $a$ and $b$ either $a \le b$ or $b \le a$. A subset of a totally ordered set is itself a totally ordered set. Every maximal (minimal) element of a totally ordered set is a largest (smallest) element. An important special case of totally ordered sets are the well-ordered sets (cf. Well-ordered set). Among the subsets of a partially ordered set that are totally ordered sets, a particularly important role is played by a composition sequence. A cut of a totally ordered set $P$ is a partition of it into two subsets $A$ and $B$ such that $A \cup B = P$, $A \cap B$ is empty, $A \subseteq B^\nabla$ and $B \subseteq A^\Delta$, where $$ B^\nabla = \{ x \in P : x \le b \ \text{for all}\ b \in B \} \ , $$ $$ A^\Delta = \{ x \in P : x \ge a \ \text{for all}\ a \in A \} \ . $$ The classes $A$ and $B$ are called the lower and upper classes of the cut. One can distinguish the following types of cuts: a jump — there is a largest element in the lower class and a smallest element in the upper class; a Dedekind cut — there is a largest (smallest) element in the lower (upper) class, but no smallest (largest) element in the upper (lower) class; a gap — there is no largest element in the lower class and no smallest element in the upper class. A totally ordered set is said to be a continuous set if all its cuts are Dedekind cuts. A subset $D$ of a totally ordered set $P$ is said to be dense if every interval of $P$ not reducing to a single element contains elements belonging to $D$. The totally ordered set of real numbers can be characterized as a continuous totally ordered set which has neither a largest nor a smallest element, but which contains a countable dense subset. Every countable totally ordered set is isomorphic to some subset of the totally ordered set of all binary fractions in the interval $[0,1]$. A lattice $L$ is isomorphic to a subset of the totally ordered set of integers if and only if every sublattice of it is a retract.

References

[1] P.S. Aleksandrov, "Einführung in die Mengenlehre und die Theorie der reellen Funktionen" , Deutsch. Verlag Wissenschaft. (1956) (Translated from Russian)
[2] P.S. Aleksandrov, "Einführung in die Mengenlehre und in die allgemeine Topologie" , Deutsch. Verlag Wissenschaft. (1984) (Translated from Russian)
[3] N. Bourbaki, "Elements of mathematics. Theory of sets" , Addison-Wesley (1968) (Translated from French)


Comments

Totally ordered sets are also called linearly ordered sets.

References

[a1] W. Sierpiński, "Cardinal and ordinal numbers" , PWN (1958)
[a2] M.M. Zuckerman, "Sets and transfinite numbers" , Macmillan (1974)
How to Cite This Entry:
Totally ordered set. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Totally_ordered_set&oldid=17682
This article was adapted from an original article by L.A. Skornyakov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article