Beweise, dass die im Bild definierte Relation ≤ eine Totalordnung auf N×N ist.

Question

Aufgabe:

Wir betrachten auf der Menge \( \mathbf{N} \times \mathbf{N} \) die folgende Relation.

$$ \leq=\left\{((a, b),(c, d)) \in(\mathbf{N} \times \mathbf{N})^{2} |(a<c) \vee((a=c) \wedge(b \leq d))\right\} $$

Zeigen Sie, dass \( \leq \) eine Totalordnung auf \( \mathbf{N} \times \mathbf{N} \) ist.

Answer 1

Du musst nur die 4 Eigenschaften einer Totalord. prüfen:

1. reflexsiv:   also für jedes (x;y) aus IN²  muss gelten

(x;y) ≤ (x;y)   also nach der Definition zu prüfen

( x<x ) v ( x=x)  ∧ ( y ≤ y )

Da  x=x  und  y ≤ y   ist das wahr,

2. Antisymm:   Es müsste also gelten

(a;b) ≤ (x;y)   und  (x;y) ≤ (a;b)   ⇒  (a;b) = (x;y) 

Dazu wieder die Def. aufschreiben:

(a;b) ≤ (x;y)   und  (x;y) ≤ (a;b)  


⇒  (( a<x ) v ( a=x)  ∧ ( b ≤ y ) )

            und  (( x<a ) v ( x=a)  ∧ ( y ≤ b ) )


also insbesondere  ( b ≤ y )und ( y ≤ b ) also   y=b

und auch   (( a<x ) v ( a=x) ) und  (( x<a ) v ( x=a))

Da a<x und x<a nicht gleichzeitig gelten können

ist in mindestens einem Teil der "und"-Verbindung das  x=a wahr,

also x=a.  Und wenn  x=a und y=b dann ist (x;y) = (a;b)   q.e.d.

transitiv:   .....

total  .....