Beweis: Die Ordnungsrelation I auf ℕ ist nicht linear

Question

im Buch war eine kleine Verständnisfrage, welche lautet "Ist die Ordnungsrelation I auf ℕ linear?". Durch ein Beispiel von mir "3 I 7" und "7 I 3" wurde deutlich, dass I auf ℕ nicht linear ist.
Ich versuche nun, dies per Beweis zu zeigen.

Voraussetzung: I ist eine Ordnungsrelation auf ℕ.
Behauptung: Die Ornungsrelation I ist linear auf ℕ.
Beweis (per Widerspruch):
Angenommen die Ordnungsrelation I ist linear auf ℕ. Dann gilt für alle x,y ∈ ℕ, dass x I y und y I x. oBdA Sei nun x = 2k + 1 ∈ ℕ eine beliebige ungerade Zahl. Weiterhin ist y = 2k ∈ ℕ eine beliebige gerade Zahl. Aufgrund der Annahme muss gelten x I y = (2k) / (2k + 1) und y I x = (2k + 1) / (2k). Dies ist offensichtlich ein Widerspruch, da x I y =(2k) / (2k + 1)  ∉ ℕ und y I x = (2k + 1) / (2k) ∉ ℕ sind. Folglich existiert auch keine Ordnungsrelation I auf ℕ, da sonst unmittelbar y I x und x I y folgen würde, somit war unsere Annahme falsch.

Stimmt mein Beweis? (Bzw. stört es euch, wenn ich täglich ca. drei / vier Fragen abschicke?)

LG

Answer 1

Hi MS15,

vorab: Nein es stört nicht, dafür ist das Forum ja da. Grade Fragen wie deine, bei denen immer Eigenbemühungen dabei sind, sind hier sehr gerne gesehen.

Zu deinem Beweis: (Warum wieder so allgemein, mit einem kurzen Gegenbeispiel wäre das ganze viel schneller abgehandelt :))

x I y und y I x

Es muss oder heißen, wenn beides gilt besteht Gleichheit (Antisymmetrie der Ordnungsrelation). Im weiteren Verlauf ebenso angleichen.

Dies ist offensichtlich ein Widerspruch, da x I y =(2k) / (2k + 1)  ∉ ℕ und y I x = (2k + 1) / (2k) ∉ ℕ sind

Naja, woher weißt du denn das das offensichtlich keine natürlichen Zahlen sind? Die rationalen Zahlen hast du an dieser Stelle wahrscheinlich noch gar nicht angefasst. Du musst ganz elementar (mit der Definition der betrachteten Relation und dem was du alles darüber weißt) zeigen, warum eine gerade und eine ungerade Zahl sich nicht gegenseitig teilen können.

Gruß

Comments

Ups, ja das mit "und" oder "oder" kann gleich den ganzen Beweis kaputt machen. Ich versuche es allgemein damit ich das Beweisen etwas üben kann. Sobald ich etwas sicherer mit dem Beweisen bin, reichen mir die Aufgaben am Ende vom Kapitel völlig aus :-)

Mhmm.. könntest du mir eventuell bitte einen Lösungsansatz zeigen? Mir fällt gerade nicht ein, wie ich zeigen kann, dass sich eine gerade und eine ungerade Zahl nicht teilen könne (In ℕ betrachtet). Somit könnte ich etwas von deiner Beweisführung lernen, und ich lerne sehr gerne von erfahrenen Menschen :-)

LG

---

Dann schreib mir doch einmal schnell wie genau bei dir "x|y" definiert ist :), und ob die Null bei dir auch eine natürliche Zahl ist.

---

ℕ = {1,2,3,4,5...}, also ohne die Null. "x I y" ist definiert als "x teilt y".

Nocheinmal die Definition und was zu untersuchen ist:
Definition: Eine Ordnungsrelation p einer geordneten Menge (X, p) heißt lineare oder totale Ordnungsrelation, wenn für je zwei Elemente x, y Element X gilt: x p y oder y p x.
Zu untersuchen: Ist die Ordnungsrelation I auf ℕ linear? (Per Beweis)

---

"x I y" ist definiert als "x teilt y"

Das ist keine Definition sondern nur die Notation (merke schon wo das Problem liegen könnte). Also weiter fragen. Was heißt denn "x teilt y"? Wann gilt das denn für 2 natürliche Zahlen?

---

Eine natürliche Zahl x, teilt eine natürliche Zahl y dann, wenn es ein c aus ℕ gibt, für welches ac = b gilt. Die Schreibweise hierfür ist dann "x I y".

---

Super ok. Also sei \(x,y \in \mathbb{N} \), \(x >1\) und \(y=x+1\).

Da \(cy \geq y > x \) für alle \(c \in \mathbb{N} \) kann \(y\) offensichtlich nicht \(x\) teilen (kennt man ja: eine größere Zahl kann eine kleinere Zahl nicht echt teilen).

Nehmen wir mal \(x|y\) also \(cx = x+1 \) für eine natürliche Zahl \(c\). Offensichtlich \(c \neq 1\), da \(x \neq x+1\).

Aber: für \(c \geq 2\) würde das bedeuten \((c-1)x = 1 \) was bedeutet, dass \(x|1\) was nur geht, wenn \(x = 1\) entgegen unserer Voraussetzung.

Das ganze ist natürlich super ausführlich und umständlich argumentiert. Mit den Zahlen \(2\) und \(3\) hätte man sofort schon das erste Gegenbeispiel. Aber am anfang sind solche Aufgaben (und der Sinn meiner Ausführung) einfach dafür da die Methodik der Argumentation und der Beweisführung auszuprobieren und zu testen.

Answer 2

  Wenn dein Symbol bedeuten sollte : " a teilt b "  Das ist eine ===> Halbordnung. Es gibt

   1) Halbordnung
   2) vollständige Ordnung ( Totalordnung, wer lieber auswärts spricht; aber ihr sagt ja auch " Hochpunkt " )
   3) Wohlordnung ===> Wohlordnungssatz

    Von " linearer " Ordnung habe ich noch nie gehört; die natürlichen Zahlen sind sogar wohl geordnet.

    Hier kennste den? Versteht man aber erst mit einigem Hintergrundwissen.

   " Das Auswahlaxiom ist selbstverständlich wahr. Der wohlordnungssatz KANN einfach nicht stimmen; und beim Zornschen Lemma wird man sehen ... "

Answer 3

"Ist die Ordnungsrelation I auf ℕ linear?". Durch ein Beispiel von mir "3 I 7" und "7 I 3" wurde deutlich, dass I auf ℕ nicht linear ist.

Das Gegenteil von "stimmt immer" ist: "es gibt mindestens ein Gegenbeispiel." Die Angabe eines einzigen Gegenbeispieles ist also schon der Beweis der Behauptung. Man hat den Eindruck, dass Dir das nicht klar ist.

Bei einer falschen Aussage ist i.A. damit zu rechnen, dass sie sowohl in manchen Faellen stimmt, als auch eben in manchen nicht.

Was ist also der Sinn Deines Beweises? Willst Du Gegenbeispiele konstruieren? Oder wolltest Du zeigen, dass die Aussage "a|b oder b|a" immer falsch ist (was ja nicht stimmt)?