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
0
, m0
) ⇔df n < n0 ∨ (n = n
0 ∧ m ≤ m0
).

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.

Answer 1

Antwort mit KI erzeugt

Einführung

Eine Relation \(\leq_{\text{lex}}\) auf einer Menge \(S\) ist eine partielle Ordnung, wenn sie folgende Eigenschaften erfüllt:
1. Reflexivität: Jeder Wert ist in Beziehung zu sich selbst.
2. Antisymmetrie: Wenn zwei Werte in beide Richtungen in Beziehung stehen, dann sind sie gleich.
3. Transitivität: Wenn ein Wert in Beziehung zu einem zweiten steht und der zweite zu einem dritten, dann steht der erste auch in Beziehung zum dritten.

Unsere Aufgabe ist es, diese Eigenschaften für die lexikographische Ordnung \(\leq_{\text{lex}}\) auf \( \mathbb{N} \times \mathbb{N} \) nachzuweisen. Die Relation \(\leq_{\text{lex}}\) ist definiert durch:
\( (n, m) \leq_{\text{lex}} (n_0, m_0) \iff n < n_0 \lor (n = n_0 \land m \leq m_0) \)

1. Reflexivität

Sei \((n, m)\) ein beliebiges Paar in \( \mathbb{N} \times \mathbb{N} \). Wir müssen zeigen, dass \((n, m) \leq_{\text{lex}} (n, m)\).

Nach der Definition gilt:
\( (n, m) \leq_{\text{lex}} (n, m) \iff n < n \lor (n = n \land m \leq m) \)
Da \(n = n\) und \(m \leq m\) wahr sind, folgt:
\( n < n \lor (n = n \land m \leq m) \iff \text{wahr} \)
somit gilt \((n, m) \leq_{\text{lex}} (n, m)\), und die Reflexivität ist gezeigt.

2. Antisymmetrie

Seien \((n_1, m_1)\) und \((n_2, m_2)\) zwei Paare in \( \mathbb{N} \times \mathbb{N} \), sodass
\( (n_1, m_1) \leq_{\text{lex}} (n_2, m_2) \land (n_2, m_2) \leq_{\text{lex}} (n_1, m_1) \)

Wir müssen zeigen, dass \((n_1, m_1) = (n_2, m_2)\).

Nach Definition der lexikographischen Ordnung:
1. \((n_1, m_1) \leq_{\text{lex}} (n_2, m_2)\) bedeutet:
\( n_1 < n_2 \lor (n_1 = n_2 \land m_1 \leq m_2) \)
2. \((n_2, m_2) \leq_{\text{lex}} (n_1, m_1)\) bedeutet:
\( n_2 < n_1 \lor (n_2 = n_1 \land m_2 \leq m_1) \)

Da \(n_1 < n_2\) und \(n_2 < n_1\) nicht zugleich wahr sein können, muss gelten \(n_1 = n_2\). Unter dieser Voraussetzung bleiben die Bedingung von oben:
\( m_1 \leq m_2 \text{ und } m_2 \leq m_1. \)
Daraus folgt \(m_1 = m_2\).

Also gilt insgesamt \((n_1, m_1) = (n_2, m_2)\), womit die Antisymmetrie gezeigt ist.

3. Transitivität

Seien \((n_1, m_1)\), \((n_2, m_2)\) und \((n_3, m_3)\) drei Paare in \( \mathbb{N} \times \mathbb{N} \) solche, dass
\( (n_1, m_1) \leq_{\text{lex}} (n_2, m_2) \land (n_2, m_2) \leq_{\text{lex}} (n_3, m_3) \)

Wir müssen zeigen, dass \((n_1, m_1) \leq_{\text{lex}} (n_3, m_3)\).

Nach Definition der lexikographischen Ordnung:
1. \((n_1, m_1) \leq_{\text{lex}} (n_2, m_2)\) bedeutet:
\( n_1 < n_2 \lor (n_1 = n_2 \land m_1 \leq m_2) \)
2. \((n_2, m_2) \leq_{\text{lex}} (n_3, m_3)\) bedeutet:
\( n_2 < n_3 \lor (n_2 = n_3 \land m_2 \leq m_3) \)

Wir müssen verschiedene Fälle betrachten:
1. \(n_1 < n_2\)
- Wenn \(n_1 < n_2\) und \(n_2 \leq n_3\), dann \(n_1 < n_3\), also \((n_1, m_1) \leq_{\text{lex}} (n_3, m_3)\).

2. \(n_1 = n_2\) und \(m_1 \leq m_2\)
- Wenn \(n_1 = n_2\) und \(n_2 < n_3\), dann \(n_1 < n_3\), also \((n_1, m_1) \leq_{\text{lex}} (n_3, m_3)\).
- Wenn \(n_1 = n_2 = n_3\), dann \(m_1 \leq m_2\) und \(m_2 \leq m_3\), also \(m_1 \leq m_3\), und damit \((n_1, m_1) \leq_{\text{lex}} (n_3, m_3)\).

In allen Fällen ist die Transitivität nachgewiesen.

Zusammenfassung

Da alle drei Eigenschaften - Reflexivität, Antisymmetrie und Transitivität - erfüllt sind, ist die Relation \(\leq_{\text{lex}}\) auf \( \mathbb{N} \times \mathbb{N} \) eine partielle Ordnung.