Zeigen Sie, dass ≤lex eine partielle Ordnung auf N × N ist.

Question

Aufgabe:

Die lexikographische Ordnung auf geordneten Paaren natürlicher Zahlen ist definiert wie folgt:
(n, m) ≤lex (n´, m´) ⇔df n < n´ ∨ (n = n´ ∧ m ≤ m´).
Es gilt also beispielsweise (1, 7) ≤lex (2, 0) und (7, 2) ≤lex (7, 3).
Zeigen Sie, dass ≤lex eine partielle Ordnung auf N × N ist.
Problem/Ansatz:

Answer 1

Die Eigenschaften abarbeiten, die in der Definition von partiellen Ordnungen genannt werden.

Reflexivität. Sei \((n,m)\in \mathbb{N}\times \mathbb{N}\). Begründe warum \((n,m) \leq (n,m)\) ist.

Antisymmetrie. Seien \((n,m), (n',m')\in \mathbb{N}\times \mathbb{N}\) mit \((n,m) \leq (n',m')\) und \((n',m')\leq (n,m)\). Begründe warum \((n,m) = (n',m')\) ist.

Transitivität. Seien \((n,m), (n',m'), (n'',m'')\in \mathbb{N}\times \mathbb{N}\) mit \((n,m) \leq (n',m')\) und \((n',m')\leq (n'',m')\). Begründe warum \((n,m) \leq (n'',m'')\) ist.