Order dimension

In order theory , one of the branches of mathematics , the order dimension is understood to be a certain cardinal number that is assigned to each partially ordered set . The basis of this assignment is a theorem , which goes back to the two mathematicians Ben Dushnik and Edwin W. Miller , which is known as the Dushnik-Miller theorem, and states that every partial order is the intersection of linear orders . The ordering dimension of a partially ordered set is then defined as that ${\displaystyle (X,\leq )}$smallest thickness of all systems of linear order relations , which can be represented as an average according to Dushnik – Miller's theorem. It is briefly referred to as or . ${\displaystyle X}$ ${\displaystyle \leq }$ ${\displaystyle \operatorname {odim} (X,\leq )}$ ${\displaystyle \dim(X,\leq )}$

Dushnik-Miller's theorem

It says the following:

Each partial order is the intersection of linear orders .

This means:

Is a partially ordered set, then there exists on the amount of carrier a system of linear order relations with ${\displaystyle (X,\leq )}$ ${\displaystyle X}$ ${\displaystyle {\mathfrak {L}}}$

${\displaystyle \leq \;=\,\bigcap _{L\in {\mathfrak {L}}}\,L}$.

Notes, examples, results

• Instead of the dimension of order , some authors also speak of the Dushnik – Miller dimension .
• Dushnik-Miller's theorem is closely related to Szpilrajn's lemma .
• The power set of a non-empty set , provided with the subset relation, has the order dimension . ${\displaystyle {\mathcal {P}}(X)}$ ${\displaystyle X}$ ${\displaystyle \operatorname {odim} ({\mathcal {P}}(X),\subseteq )=|X|}$
• If it is a natural number , in whose prime factorization exactly prime factors occur, and if its divisor set is provided with the divisor relation , then applies . For about is and for is . ${\displaystyle N}$ ${\displaystyle \omega (N)}$ ${\displaystyle (X,\leq )=(T_{N},\mid )}$ ${\displaystyle \operatorname {odim} (T_{N},\mid )=\omega (N)}$ ${\displaystyle N=360=2^{3}\cdot 3^{2}\cdot 5}$ ${\displaystyle \operatorname {odim} (T_{360},\mid )=\omega (360)=3}$ ${\displaystyle N=26411=7^{4}\cdot 11}$ ${\displaystyle \operatorname {odim} (T_{26411},\mid )=\omega (26411)=2}$
• There are - among many others - the following results:
  • About the relationship between the order dimension and the Sperner number : The order dimension of a partially ordered set is at most as large as its Sperner number , provided that the Sperner number is finite. ${\displaystyle (X,\leq )}$ ${\displaystyle \operatorname {w} (X,\leq )}$
  • The (according to the Japanese mathematician Toshio Hiraguchi named) inequality of Hiraguchi : For a natural number , and a finite partially ordered set with elements is the order dimension at most . ${\displaystyle n\geq 4}$ ${\displaystyle (X,\leq )}$ ${\displaystyle |X|=n}$ ${\displaystyle \operatorname {odim} (X,\leq )}$ ${\displaystyle {\frac {n}{2}}}$
  • The theorem of Hiraguchi-Ore (named after the Norwegian mathematician Øystein Ore and Toshio Hiraguchi) , which offers an alternative approach to the concept of the dimension of order: The dimension of order of a partially ordered set is equal to the smallest number of linearly ordered sets embedded in their direct product can be. ${\displaystyle (X,\leq )}$ ${\displaystyle (X,\leq )}$
  • The Harzheim theorem (named after the German mathematician Egbert Harzheim ) : If is a natural number and for every finite subset of a given partially ordered set the order dimension of the restricted order relation is at most , then is at most . ${\displaystyle N}$ ${\displaystyle E}$ ${\displaystyle (X,\leq )}$ ${\displaystyle \operatorname {odim} (E,{{E\times E}\;\cap \leq })}$ ${\displaystyle E}$ ${\displaystyle N}$ ${\displaystyle \operatorname {odim} (X,\leq )}$ ${\displaystyle N}$

literature

• Ben Dushnik, EW Miller: Partially ordered sets . In: American Journal of Mathematics . tape 63 , 1941, pp. 600-610 , doi : 10.2307 / 2371374 , JSTOR : 2371374 ( ams.org ).
• Bernhard Ganter : Discrete Mathematics: Ordered Sets (=  Springer textbook ). Springer Spectrum , Berlin, Heidelberg 2013, ISBN 978-3-642-37499-9 , pp. 47 ff ., doi : 10.1007 / 978-3-642-37500-2 .
• Egbert Harzheim : Ordered Sets (=  Advances in Mathematics . Volume 7 ). Springer Verlag, New York 2005, ISBN 0-387-24219-8 , pp. 206 ff . ( MR2127991 ).
• Wacław Sierpiński : Cardinal and Ordinal Numbers . Panstwowe Wydawnictwo Naukowe, Warsaw 1958, p. 188 ( MR0095787 ).

Individual evidence

1. ↑ is one of the arithmetic functions . ${\displaystyle N\mapsto \omega (N)}$
2. ↑ Instead of the transcription "Toshio Hiraguchi" one also finds the transcription "Tosio Hiraguti"
3. ↑ Provided with the partial order formed by components!