Hallo ihr lieben,
Hi Matthias!
Ich habe mir bereits den Artikel zu „Lexikographische Ordnung“
in Wikipedia durchgelesen und weiß jetzt zumindest mal was
eine Lexiographische Ordnung ist. Wenn ich das also richtig
verstanden habe wird wie im Lexikon der erste Buchstabe/Zahl
verglichen, wenn eine der beiden kleiner ist, ist auch die
Zeichenkette/Zahlenpaar kleiner. Wenn beide gleich groß sind
wird der zweite Buchstabe/Zahl verglichen.
Das stimmt soweit.
Ich weiß aber nicht wie ich mit diesem Wissen den Aufgabenteil
a) zeigen kann. Steht dass nicht schon in der
Aufgabenstellung?
Das hört sich so an, als sei dir nicht ganz klar, was du beweisen sollst. Um zu zeigen, dass eine Relation eine Ordnung ist, musst du zeigen, dass sie reflexiv, transitiv und antisymmetrisch ist. Du musst also folgende drei Eigenschaften zeigen:
(m,n)\leq_{\mathbb{N}\times\mathbb{N}}(m,n)\ \forall (m,n)\in\mathbb{N}\times\mathbb{N}\text{ (Reflexivit"at)}
(a,b)\leq_{\mathbb{N}\times\mathbb{N}}(c,d)\wedge (c,d)\leq_{\mathbb{N}\times\mathbb{N}}(e,f)\ \Rightarrow\ (a,b)\leq_{\mathbb{N}\times\mathbb{N}}(e,f)\text{ (Transitivit"at)}
(a,b)\leq_{\mathbb{N}\times\mathbb{N}}(c,d)\wedge (c,d)\leq_{\mathbb{N}\times\mathbb{N}}(a,b)\ \Rightarrow\ (a,b)=(c,d)\text{ (Antisymmetrie)}
Wenn du diese drei Eigenschaften für ≤NxN nachweisen kannst, hast du bewiesen, dass es sich um eine Ordnung handelt. Um zu zeigen, dass diese Ordnung noethersch ist, musst du zeigen, dass jede Teilmenge von NxN ein bezüglich ≤NxN kleinstes Element besitzt, also
\forall T\subseteq\mathbb{N}\times\mathbb{N}\ \exists (a,b)\in T: (a,b)\leq_{\mathbb{N}\times\mathbb{N}}(c,d)\ \forall (c,d)\in T
Unser Hiwi sagte, dass bei dem Beweis viele
Fallunterscheidungen vorkämen.
Da hat er Recht. Bei der Reflexivität kommt man noch ohne aus, denn
m=m\ \forall\ m\in\mathbb{N}\ \Rightarrow\ (m,n)\leq_{\mathbb{N}\times\mathbb{N}}(m,n)\ \forall (m,n)\in\mathbb{N}\times\mathbb{N}
Der Beweis ist quasi geschenkt, aber Reflexivitätsbeweise sind meistens relativ trivial. Versuch dich mal an den anderen Beweisen und schreib, wenn du irgendwo hängen bleibst.
Viel Erfolg!
hendrik
