Schranken

 Ordnungsbegriffe werden in der Mathematik an vielen verschiedenen Stellen verwendet, der Leser denke etwa an das Maximum in der Definition des größten gemeinsamen Teilers, das Supremum einer beschränkten nichtleeren Menge von reellen Zahlen oder an kürzeste Kantenzüge in der Graphentheorie. Viele Begriffe lassen sich allgemein für partielle Ordnungen einführen. Die folgende Definition versammelt einige davon.

Definition (Schranken in partiellen Ordnungen)

Sei < eine Ordnung auf A. Weiter seien a  ∈  A und B ⊆ A. Dann heißt

(i)

a eine obere Schranke von B, in Zeichen B ≤ a, falls ∀b  ∈  B b ≤ a,

(ii)

a eine untere Schranke von B, in Zeichen a ≤ B, falls ∀b  ∈  B a ≤ b,

(iii)

a das Maximum oder größte Element von B, in Zeichen a = max(B), falls a  ∈  B ∧ B ≤ a,

(iv)

a das Minimum oder kleinste Element von B, in Zeichen a = min(B), falls a  ∈  B ∧ a ≤ B,

(v)

a das Supremum oder die kleinste obere Schranke von B, in Zeichen a = sup(B), falls a = min({ s | B ≤ s }),

(vi)

a das Infimum oder die größte untere Schranke von B, in Zeichen a = inf (B), falls a = max({ s | s ≤ B }),

(vii)

a maximal in B, falls a  ∈  B ∧ ¬ ∃b  ∈  B a < b,

(viii)

a minimal in B, falls a  ∈  B ∧ ¬ ∃b  ∈  B b < a,

(ix)

B nach oben beschränkt, falls eine obere Schranke von B existiert,

(x)

B nach unten beschränkt, falls eine untere Schranke von B existiert,

(xi)

B beschränkt, falls B nach oben und unten beschränkt ist.

 Wir betrachten einige Beispiele.

Beispiele

(1)

Die Menge der natürlichen Zahlen hat unter der üblichen Ordnung das kleinste Element 0. Ein größtes Element existiert nicht. Jede nichtleere Teilmenge besitzt ein Minimum.

(2)

In ℚ mit der üblichen Ordnung hat die beschränkte Menge

Q = { q > 0 | q2 ≤ 2 }

aufgrund der Irrationalität von 2 kein Supremum.

(3)

Wir betrachten die partielle Ordnung der Teilbarkeit auf { 1, …, 20 }, dargestellt durch ein Hasse-Diagramm:

ema22-AbbID3-2-14

Das Minimum der Ordnung ist 1, ein Maximum existiert nicht. Dagegen sind 11, …, 20 maximale Elemente der Ordnung. Die Elemente 6, 12 und 18 sind die oberen Schranken von { 2, 3 }. Das Supremum von { 2, 3 } ist 6.

(4)

Für die partielle Ordnung der Inklusion auf A = ℘({ 1, 2, 3 }) und die Menge B = { { 1 }, { 1, 2 }, { 3 }} gilt:

{ 1 } und { 3 } sind minimal in B,

{ 1, 2 } und { 3 } sind maximal in B,

max(B) und min(B) existieren nicht,

sup(B)  =  { 1, 2, 3 },  inf (B)  =  { }.

(5)

Sei A = { 0, 1 } und SeqA linear geordnet durch <lex. Dann ist die leere Folge ( ) das Minimum der Ordnung, ein Maximum existiert nicht. Ist

B  =  { 0, 00, 000, 0000, … },

so ist jede Folge der Form 0…01 eine obere Schranke von B. Die Menge B besitzt kein Supremum.

(6)

Die Ordnung <KB auf SeqA hat das größte Element ( ) und kein kleinstes Element. Denn für jede Folge s ist jede echte Fortsetzung t von s (d. h. jedes t mit s ⊲ t) kleiner als s.

(7)

Sei (A, <) eine endliche lineare Ordnung und SeqA linear geordnet durch die Short-Lex-Ordnung. Dann besitzt jede nichtleere Teilmenge B von SeqA ein kleinstes Element: Wir betrachten die kleinste Stufe des Baumes SeqA, auf der sich Elemente von B befinden. Unter diesen suchen wir das lexikographisch kleinste. Dieses Element ist das Minimum von B.