Ordnung, geordnetes Paar (M, R), so daß (M, M, R), R ⊆ M × M, eine Relation darstellt, die den folgenden drei Bedingungen genügt (wie üblich wird im folgenden für zwei in Relation stehende Elemente x, y die Bezeichnung x ~ y anstatt (x, y) ∈ R verwendet):

1. Reflexivität: \begin{eqnarray}\mathop{\bigwedge }\limits_{x\in M}x\sim x,\end{eqnarray} d. h., jedes Element steht zu sich selbst in Relation.

2. Antisymmetrie: \begin{eqnarray}\mathop{\bigwedge }\limits_{x\in M}(x\sim y\wedge y\sim x)\Rightarrow x=y,\end{eqnarray} d. h., stehen sowohl x und y als auch y und x in Relation, so sind x und y gleich.

3. Transitivität: \begin{eqnarray}\mathop{\bigwedge }\limits_{x,y,z\in M}(x\sim y\wedge y\sim z\Rightarrow x\sim z),\end{eqnarray} d. h., stehen sowohl x und y als auch y und z in Relation, so auch x und z.

Eine Abschwächung des Begriffes der Ordnungsrelation ist der Begriff der Partialordnung, Halbordnung oder partiell geordneten Menge. Hier wird lediglich verlangt, daß die Relation R reflexiv und transitiv ist. Man beachte, daß es in der Literatur auch vorkommt, daß der hier als Ordungsrelation definierte Begriff als Partialordnung oder als Halbordnung bezeichnet wird.

R heißt strenge Ordnungsrelation genau dann, wenn R transitiv und asymmetrisch ist. Dabei heißt R genau dann asymmetrisch, wenn \begin{eqnarray}\mathop{\bigwedge }\limits_{x,y\in M}x\sim y\Rightarrow \neg (y\sim x),\end{eqnarray} d. h., wenn x nur dann zu y in Relation steht, wenn y nicht zu x in Relation steht.

Eine Ordnungsrelation und eine strenge Ordnungsrelation unterscheiden sich genau durch die Diagonale \begin{eqnarray}{\rm{\Delta }}(M)=\{(x,x):x\in M\},\end{eqnarray} d. h., ist R eine Ordungsrelation, so ist R\∆(M) eine strenge Ordnungsrelation, und ist R eine strenge Ordungsrelation, so ist R ∪ ∆(M) eine Ordnungsrelation.

Für Ordnungsrelationen und Partialordnungen ist es üblich, das Symbol „≤“ (lies: „kleiner oder gleich“) anstatt des Symbols „~“ zu verwenden. Im Fall strenger Ordnungsrelationen wird das Symbol „<“ (lies: „kleiner“ oder „echt kleiner“) benutzt.

Beispiel: Es sei \({\mathcal{M}}:={\mathcal{P}}({{\mathbb{N}}}_{0})\) die Potenzmenge der natürlichen Zahlen. Durch \begin{eqnarray}M\le N:\iff \#M\le \#N\end{eqnarray} wird auf \( {\mathcal M} \) eine Partialordnung definiert. M ≤ N bedeutet dann, daß M höchstens so viele Elemente hat wie N. „≤“ ist keine Ordnungsrelation, da z. B. {0} ≤ {1} und {1} ≤ {0} gelten, obwohl die Mengen {0} und {1} verschieden sind. Definiert man hingegen M ≤₀N genau dann, wenn M = N oder #M< #N gilt, so handelt es sich bei „≤₀“ um eine Ordnungsrelation. Für die zugehörige strenge Ordnungsrelation „<₀“ gilt dann M<₀N genau dann, wenn M weniger Elemente hat als N.

Eine Partialordnung (M, ≤) läßt sich häufig in einem Ordnungsdiagramm (gelegentlich auch Hasse-Diagramm genannt) veranschaulichen. Dabei werden die Elemente der partiell geordneten Menge M als Punkte der Zeichenebene dargestellt, für a ≤ b wird a unterhalb oder auf gleicher Höhe von b gezeichnet, und a wird mit b verbunden. Der Übersichtlichkeit halber ist es üblich, Punkte nicht zu verbinden, wenn sie schon über andere Punkte verbunden sind.

Stellt ein Ordnungsdiagramm eine Partialordnung dar, so werden i. allg. waagrechte Linien auftreten. In Veranschaulichungen von Ordnungsrelationen lassen sich waagrechte Linien hingegen vermeiden, wenn man für verschiedene Elemente a, b mit a ≤ b den Punkt a immer unterhalb des Punktes b zeichnet.

Beispiele:

1. In Abbildung 1 ist ein Ordnungsdiagramm der durch Inklusion geordneten Menge \(\{{\mathbb{N}},\,{{\mathbb{Z}}}^{-},\,{\mathbb{Z}},\,{{\mathbb{Q}}}^{-},\,{\mathbb{Q}},\,{\mathbb{R}},\,{\mathbb{A}}\text{,}\,{\mathbb{C}}\}\) dargestellt.

2. Man betrachte die Menge \begin{eqnarray}{\mathcal{M}}:=\{\emptyset,\{0\},\{1\},\{0,1\},\{0,2\},\{0,1,2\}\}.\end{eqnarray}

Dann wird genau wie oben durch M ≤ N :⇔ #M ≤ #N eine Partialordnung auf \( {\mathcal M} \) definiert. Abbildung 2 liefert die Veranschaulichung in einem Ordnungsdiagramm.

Sind M₁, M₂ mit den Partialordnungen „≤₁“ bzw. „≤₂“ versehene Mengen, so heißt eine Abbildungf : M₁ → M₂ isoton genau dann, wenn für alle x, y ∈ M₁ aus x ≤₁y folgt, daß f (x) ≤₂f (y).

Eine Abbildung f : M₁ → M₂ heißt antiton genau dann, wenn für alle x, y ∈ M₁ aus x ≤₁y folgt, daß f(y) ≤₂f(x).

Für die Definition streng isotoner bzw. streng antitoner Abbildungen sind in der Definition isotoner bzw. antitoner Abbildungen die Partialordnungen „≤₁“ und „≤₂“ durch strenge Ordnungsrelationen „≤₁“ und „≤₂“ zu ersetzen.

Die Abbildung f heißt genau dann ähnlich oder ordnungstreu, wenn f bijektiv ist und sowohl f als auch f⁻¹ isoton sind. In diesem Fall werden auch die Partialordnungen (M₁, ≤₁) und (M₂, ≤₂) bzw. die partiell geordneten Mengen M₁ und M₂ ähnlich genannt.

Beispiele:

4. Betrachtet man die in den Abbildungen 3 bzw. 2 dargestellten Partialordnungen \(( {\mathcal M} \text{,}{\le }_{o})\) und \(( {\mathcal M} \text{,}\le )\), so ist die Identität auf \( {\mathcal M} \) isoton, jedoch nicht ähnlich, da die Umkehrabbildung nicht isoton ist (da z. B. {1} ≤ {0}, jedoch nicht {1} ≤₀ {0}).

5. Die Abbildung f : ℝ → ℝ, x ↦ mx + n, ist isoton genau dann, wenn m ≥ 0, antiton genau dann, wenn m ≤ 0, streng isoton sowie ähnlich genau dann, wenn m > 0, und streng antiton genau dann, wenn m< 0.

(M, ≤) wird nun als Partialordnung vorausgesetzt. Man spricht von Vergleichbarkeit der Elemente x, y ∈ M genau dann, wenn x ≤ y oder y ≤ x gilt, und von Kompatibilität der Elemente x, y ∈ M genau dann, wenn es ein Element z ∈ M mit z ≤ x und z ≤ y gibt.

Der Begriff der Kompatibilität ist stärker als der der Vergleichbarkeit: Sind zwei Elemente vergleichbar, so sind sie auch kompatibel; die Umkehrung gilt jedoch i. allg. nicht. So sind ℚ⁻ und ℤ in Abbildung 1 kompatibel, jedoch nicht vergleichbar.

Eine Menge K ⊆ M heißt Kette genau dann, wenn alle Elemente aus K paarweise im oben definierten Sinne vergleichbar sind.

Eine Menge A ⊆ M heißt Antikette genau dann, wenn je zwei verschiedene Elemente aus A nicht kompatibel sind.

In Abbildung 1 ist z. B. die Menge \(\{{{\mathbb{Z}}}^{-},\,{\mathbb{Z}},\,{\mathbb{Q}},\,{\mathbb{A}}\}\) eine Kette und die Menge {ℤ⁻, ℕ} eine Antikette. Ein weiteres Beispiel für eine Kette ist die zur Abbildung 2 gehörige Menge \( {\mathcal M} \).

Die abzählbare Kettenbedingung für die Partialordnung (M, ≤) ist die Aussage, daß jede Antikette A ⊆ M abzählbar ist.

Beispiel: Ist X eine Menge und M die Potenzmenge von X, aus der die leere Menge entfernt wurde, d. h., \(M={\mathcal{P}}(M)\backslash \{\emptyset \}\), und ist M durch die Inklusion von Mengen geordnet, so sind zwei Elemente aus M genau dann kompatibel, wenn sie nicht disjunkt sind. Somit erfüllt (M, ⊆) genau dann die abzählbare Kettenbedingung, wenn die Menge X abzählbar ist.

Eine Menge D ⊆ M heißt dicht in M genau dann, wenn es zu jedem x ∈ M ein Element d ∈ D mit d ≤ x gibt.

Beispiele: In Abbildung 1 ist eine Menge genau dann dicht, wenn sie die Elemente ℤ⁻ und ℕ enthält. In den Abbildungen 2 und 3 ist eine Menge genau dann dicht, wenn sie das Element ∅ enthält. ℤ ist eine dichte Teilmenge der reellen Zahlen mit der üblichen Ordnung.

Eine Menge F ⊆ M heißt Filter auf M genau dann, wenn die folgenden Bedingungen (i) und (ii) erfüllt sind:

Beispiele:

6. In Abbildung 1 ist die Menge \(\{{\mathbb{C}},{\mathbb{R}},{\mathbb{A}}\}\) kein Filter. Einen Filter erhält man, indem man der Menge das Element ℚ hinzufügt.

7. In Abbildung 2 ist die Menge {{1}, {0,2}, {0, 1, 2}} kein Filter. Einen Filter erhält man, indem man der Menge die Elemente {0} und {0, 1} hinzufügt.

8. ℕ ist ein Filter auf ℤ mit der üblichen Ordnung.

9. Ist M eine Menge und \(F\subseteq {\mathcal{P}}(M)\) ein Filter über M, so ist F ein Filter auf der Ordnungsrelation \(({\mathcal{P}}(M),\subseteq )\).

Ein Element m ∈ M heißt größtes Element genau dann, wenn für alle x ∈ M gilt x ≤ m · m heißt maximales Element genau dann, wenn für jedes x ∈ M aus m ≤ x folgt, daß x = m ist. m heißt kleinstes Element genau dann, wenn für alle x ∈ M gilt m ≤ x ist. m heißt minimales Element genau dann, wenn für jedes x ∈ M aus x ≤ m folgt, daß x = m.

Ist N ⊆ M, so heißt s ∈ M obere Schranke von N genau dann, wenn n ≤ s für alle n ∈ N gilt. N heißt dann nach oben beschränkt. Analog heißt s ∈ M untere Schranke von N genau dann, wenn s ≤ n für alle n ∈ N gilt. N heißt dann nach unten beschränkt. Ein kleinstes Element der Menge der oberen Schranken der Menge N heißt Supremum oder obere Grenze der Menge N und wird mit sup(N) bezeichnet. Entsprechend heißt ein größtes Element der Menge der unteren Schranken der Menge N Infimum oder untere Grenze der Menge N und wird mit inf(N) bezeichnet. Sofern das Supremum bzw. das Infimum existiert, ist es eindeutig bestimmt.

Beispiele:

10. Die in Abbildung 1 dargestellte Ordnungsrelation hat ℂ als größtes Element. Sie hat kein kleinstes Element, jedoch zwei minimale Elemente, nämlich ℤ⁻ und ℕ. Ist \(T:=\{{\mathbb{Z}},\,{\mathbb{Q}},\,{\mathbb{R}},\,{\mathbb{A}}\text{,}\,{\mathbb{C}}\}\), so sind ℤ⁻, ℕ und ℤ untere Schranken von T, d. h., T ist nach unten beschränkt. Es gilt inf(T) = ℤ. T ist auch nach oben beschränkt, und es gilt sup(T) = ℂ. Die Menge {ℤ⁻, ℕ} ist nicht nach unten beschränkt.

11. Die Menge \({{\mathbb{Q}}}_{0}^{+}\) hat 0 als kleinstes Element, sie hat kein größtes Element und ist nicht nach oben beschränkt. Die Menge (1, \(\sqrt{2]}\,\cap {\mathbb{Q}}\) ist in \({{\mathbb{Q}}}_{0}^{+}\) sowohl nach oben als auch nach unten beschränkt, sie hat 1 als Infimum, jedoch kein Supremum.

12. Betrachtet man die Menge \begin{eqnarray}X:={{\mathbb{R}}}^{+}\cup ({{\mathbb{R}}}_{0}^{-}\times \{0\})\cup ({{\mathbb{R}}}_{0}^{-}\times \{1\})\end{eqnarray} und definiert für x, y ∈ X, daß \(x\precsim y\) genau dann, wenn x, y ∈ ℝ⁺ mit x ≤ y oder \begin{eqnarray}x\in ({{\mathbb{R}}}_{0}^{-}\times \{0\})\cup ({{\mathbb{R}}}_{0}^{-}\times \{1\}),\end{eqnarray}y ∈ ℝ⁺ oder x = (a, k), y = (b, l) mit a ≤ b und k = l, so hat die Menge ℝ⁺ bezüglich „≾“ zwei Infima, nämlich (0, 0) und (0, 1).

Nun wird (M, ≤) als Ordnungsrelation vorausgesetzt.

Die zu „≤“ inverse Ordnungsrelation wird mit „≥“ bezeichnet, d.h., es gilt a ≥ b genau dann, wenn b ≤ a.

Ist N ⊆ M und gilt x ≤_N y für x, y ∈ N genau dann, wenn x ≤ y, so bezeichnet man (N, ≤_N) als Teilordnung von (M, ≤).

Sind a, b ∈ M, a ≤ b, a ≠ b, so heißt b ein Nachfolger von a genau dann, wenn für jedes c ∈ M aus a ≤ c ≤ b entweder c = a oder c = b folgt.

Beispiele: In Abbildung 1 hat jedes Element außer ℂ mindestens einen Nachfolger. ℤ⁻ und ℚ besitzen zwei Nachfolger. Bezüglich der üblichen Ordnungen hat jedes Element von ℤ genau einen Nachfolger, jedoch hat kein Element von ℚ oder ℝ einen Nachfolger.

Man spricht bei (M, ≤) genau dann von einer linearen, konnexen, totalen oder vollständigen Ordnungsrelation und bezeichnet M als linear, konnex, total oder vollständig geordnet, wenn für alle a, b ∈ M gilt, daß a ≤ b oder b ≤ a.

Beispiele für lineare Ordnungsrelationen sind ℕ, ℤ, ℚ und ℝ mit den üblichen Ordnungen.

M heißt induktiv geordnet genau dann, wenn jede durch „≤“ linear geordnete Teilmenge von M ein Supremum besitzt.

Keine der Mengen ℕ, ℤ, ℚ und ℝ mit den üblichen Ordnungen ist induktiv geordnet. Hingegen ist ℤ⁻ induktiv geordnet. Ebenso sind alle abgeschlossenen reellen Intervalle sowie halboffene reelle Intervalle der Form (a, b] mit b ∈ ℝ, a ∈ ℝ ∪ {∞}, a< b, induktiv geordnet. Das obige Beispiel 11 zeigt, daß die Menge [0, 2] ∩ ℚ nicht induktiv geordnet ist. Die Menge aller linear unabhängigen Teilmengen eines Vektorraumes mit der Inklusion als Ordnung ist indukiv geordnet.

Ist M linear geordnet, so heißt A ⊆ M Abschnitt genau dann, wenn A genau alle Elemente enthält, die echt kleiner einem gegebenen Element x ∈ M sind.

Beispiele: Die Abschnitte der reellen Zahlen sind genau die offenen Intervalle (∞, a) mit a ∈ ℝ. Jede Ordinalzahl ist die Menge ihrer Abschnitte (Kardinalzahlen und Ordinalzahlen).

Ist die Menge M₁ durch „≤₁“ und die Menge M₂ durch „≤₂“ geordnet, so läßt sich wie folgt eine Ordnung „≤“ auf M₁ × M₂ definieren: Für a₁, b₁ ∈ M₁ und a₂, b₂ ∈ M₂ sei (a₁, a₂) ≤ (b₁, b₂) genau dann, wenn entweder a₁ ≤ b₁, a₁ ≠ b₁ oder a₁ = b₁, a₂ ≤ b₂. (M₁ × M₂, ≤) wird dann als lexikographisches Produkt von (M₁, ≤₁) und (M₂, ≤₂) bezeichnet.