Ordnungsrelation: Für zwei Elemente (m1,m2),(n1,n2) ∈ ℕ^2 setzen wir: (m1,m2) ≤ (n1,n2) :⇔m1 ≤ n1 und m2 ≤ n2.

Question

Für zwei Elemente (m₁,m₂),(n₁,n₂) ∈ ℕ² setzen wir:

(m₁,m₂) ≤ (n₁,n₂) :⇔m₁ ≤ n₁ und m₂ ≤ n₂.

a) Zeige, dass ≤ eine Ordnungsrelation auf ℕ²  definiert.

b) Bestimme alle Ketten der Länge 4, die in der Teilmenge {1,2} × {1,2,3} von ℕ² enthalten sind.

Answer 1

a)

Eine Ordnungsrelation muss jedenfalls transitiv sein. Welche spezielle Art einer Ordnungsrelation vorliegt, hängt dann von den weiteren Eigenschaften ab (z.B. Reflexivität, Antisymmetrie, usw.)

Zu zeigen ist also die Transitivität, also dass gilt:

(a₁,a₂) ≤ (b₁,b₂) und  (b₁,b₂) ≤ (c₁,c₂) => (a₁,a₂) ≤ (c₁,c₂)

Nun

(a₁,a₂) ≤ (b₁,b₂) <=> a₁ ≤ b₁ und a₂ ≤ b₂

(b₁,b₂) ≤ (c₁,c₂) <=> b₁ ≤ c₁ und b₂ ≤ c₂

also:

(a₁,a₂) ≤ (b₁,b₂) und  (b₁,b₂) ≤ (c₁,c₂)

<=> a₁ ≤ b₁ und a₂ ≤ b₂ und b₁ ≤ c₁ und b₂ ≤ c₂

<=> a₁ ≤ b₁ und b₁ ≤ c₁ und  a₂ ≤ b₂ und b₂ ≤ c₂

=> a₁ ≤ c₁  und a₂ ≤ c₂

<=> (a₁,a₂) ≤ (c₁,c₂)

b)

Die Teilmenge {1,2} × {1,2,3} von ℕ²  ist die Menge

{ ( 1 , 1 ) , ( 1 , 2 ) , ( 1 , 3 ) , ( 2 , 1 ) , ( 2 , 2 ) , ( 2 , 3 ) }

Folgende Ketten der Länge 4 sind in dieser Teilmenge enthalten: 

( 1 , 1 ) ≤ ( 1 , 2 ) ≤ ( 1 , 3 ) ≤ ( 2, 3 )

( 1 , 1 ) ≤ ( 1 , 2 ) ≤ ( 2 , 2 ) ≤ ( 2, 3 )

( 1 , 1 ) ≤ ( 2 , 1 ) ≤ ( 2 , 2 ) ≤ ( 2, 3 )