Endliche Menge/Totale Ordnungen/Bemerkung

Eine totale Ordnung auf einer endlichen Menge ist durch ein Angangselement (kleinstes Element) und dadurch gegeben, dass jedem Element (außer dem größten Element) das nächstkleinste Element zugeordnet wird. In der Skizze wird nur diese Zuordnung dargestellt, die gesamte Ordnung ergibt sich, wenn man sich Selbstpfeile und transitive Pfeile dazudenkt.

Auf einer endlichen Menge ${}M$ mit ${}n$ Elementen sind die totalen Ordnungen einfach zu überschauen. Eine totale Ordnung auf ${}M$ ist das gleiche wie eine bijektive Abbildung ${}\varphi \colon {\{1,\ldots ,n\}}\rightarrow M$, also eine Nummerierung von ${}M$. Eine solche Nummerierung legt über ${}\varphi (i)\geq \varphi (j)$, falls ${}i\geq j$, eine totale Ordnung fest, und eine totale Ordnung legt eine Nummerierung fest, indem ${}1$ auf das kleinste Element von ${}M$ abgebildet wird, ${}2$ auf das zweitkleinste Element u.s.w. Insbesondere gibt es wegen Fakt ${}n!$ totale Ordnungen auf ${}M$. Es ist ziemlich schwierig, sich eine systematische Übersicht über alle (auch die nicht totalen) Ordnungen in einer endlichen Menge zu verschaffen.