Ordnungsbeweis

07.12.2020, 19:55

Yasminx3

Ordnungsbeweis

[attach]52251[/attach]

Leider habe ich wirklich keinen Ansatz oder überhaupt einen Plan davon, wie ich das beweisen soll. Ich bin dankbar für jeden Tipp und für jede Hilfe, die ich bekomme.

08.12.2020, 12:49

Elvis

Auf diesen Beitrag antworten »

Sicher weißt du, dass man eine Äquivalenz ("genau dann wenn") $\begin{eqnarray*} \Leftrightarrow \end{eqnarray*}$ dadurch beweist, dass man die beiden Implikationen ("wenn dann") $\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ und $\begin{eqnarray*} \Leftarrow \end{eqnarray*}$ beweist. Damit hast du schon einen Plan, wie die Beweise zu führen sind. Außerdem sind dir die Definitionen "Menge", "Mächtigkeit einer Menge", "identische Relation" und "Ordnungsrelation" bekannt, also hast du auch einen Ansatz für die Beweise. Du darfst nicht glauben, dass Beweise spontane Ideen sind, die sich beim Betrachten von Aufgaben wie von selbst einstellen. Beweise muss man sich durch Nachdenken, Schreiben, Probieren und Korrigieren erarbeiten.

08.12.2020, 18:14

Yasminx3

Auf diesen Beitrag antworten »

Hey Elvis, ja ich tue mich immer so schwer mit Beweisen.

Ich versuchs mal:

z.z. $\begin{eqnarray*} R^{'} \end{eqnarray*}$ ist genau dann eine Ordnung, wenn $\begin{eqnarray*} R \end{eqnarray*}$ eine Ordnung ist.

" $\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ ": Wenn $\begin{eqnarray*} R^{'} \end{eqnarray*}$ eine Ordnung ist, gilt für $\begin{eqnarray*} R^{'} \end{eqnarray*}$ die Reflexivität, Antisymmetrie und Transitivität.

Jetzt muss ich bestimmt irgendwie die Definitionen benutzen. Hmm, aber wie genau? verwirrt

08.12.2020, 19:08

Elvis

Auf diesen Beitrag antworten »

Wie genau ? Hinschreiben, was man weiß, und damit spielen, bis das dasteht, was man wissen will. Du darfst nicht bei den allgemeinen Worten "Ordnung" und "Reflexivität" stehen bleiben, du musst weiter machen und konkret werden. Du musst dich immer wieder fragen, was heißt das hier und jetzt in diesem Zusammenhang. Grübeln dauert Stunden und bringt nichts ein, machen dauert Sekunden und führt immer zum Ziel.

$\begin{eqnarray*} R' \end{eqnarray*}$ reflexiv $\begin{eqnarray*} \Rightarrow \forall a,b\in A: (a,b)R'(a,b)\Rightarrow \forall a,b\in A:aRa\wedge bRb\Rightarrow\forall a\in A:aRa\Rightarrow R \end{eqnarray*}$ reflexiv.

08.12.2020, 19:48

Yasminx3

Auf diesen Beitrag antworten »

Ok, habs mal weiter versucht. Kann man es so aufschreiben? verwirrt

$\begin{eqnarray*} R^{'} \end{eqnarray*}$ antisymmetrisch $\begin{eqnarray*} \Rightarrow \forall a,b\in A: (a,b)R'(b,a) \wedge (b,a)R'(a,b) \Rightarrow a=b \Rightarrow \forall a,b\in A:aRb\wedge bRa \Rightarrow a=b \Rightarrow R \end{eqnarray*}$ ist antisymmetrisch.

$\begin{eqnarray*} R^{'} \end{eqnarray*}$ transitiv $\begin{eqnarray*} \Rightarrow \forall a,b,c,d,f \in A: (a,b)R'(b,c) \wedge (b,c) R'(d,f) \Rightarrow (a,b)R'(d,f) \Rightarrow \forall a,b,f\in A:aRb\wedge bRf \Rightarrow \forall a,b,f\in A:aRf \Rightarrow R \end{eqnarray*}$ ist transitiv.

08.12.2020, 20:09

Elvis

Auf diesen Beitrag antworten »

Nein, du hast das Prinzip noch nicht verstanden. R' ist eine Relation zwischen Paaren, also musst du die Eigenschaften einer Ordnungsrelation für Paare formulieren. Dann übersetzt die Äquivalenz zwischen R' und R diese Eigenschaften in Eigenschaften von R. Bei allen Definitionen musst du viel sorgfältiger vorgehen, und bei allen Folgerungen musst du wissen, was du tust. Beides ist nicht der Fall, du definierst unkorrekt und schließt unlogisch. Bitte mehr Zeit investieren und mehr Sorgfalt anwenden, du hast meinen Vorschlag nicht bedacht, dass man das was man versucht, auch korrigieren muss ("Schreiben, Probieren und Korrigieren").

Nachtrag. Wie z.B. die Antisymmetrie für R aus der Antisymmetrie für R' folgt.
$\begin{eqnarray*} aRb\wedge bRa\Rightarrow bRa\wedge aRb \end{eqnarray*}$ ist trivial. Also $\begin{eqnarray*} (a, b) R'(b, a) \wedge (b, a) R'(a, b) \end{eqnarray*}$ wegen der Definition. Also $\begin{eqnarray*} (a, b) =(b, a) \end{eqnarray*}$ weil $\begin{eqnarray*} R' \end{eqnarray*}$ antisymmetrisch. Also $\begin{eqnarray*} a=b \end{eqnarray*}$ , also $\begin{eqnarray*} R \end{eqnarray*}$ antisymmetrisch.

08.12.2020, 23:41

Yasminx3

Auf diesen Beitrag antworten »

Zitat:

Du hast recht. In den meisten Fällen mache ich mir echt kaum Gedanken über bestimmte Dinge, aber weil ich manchmal an sowas verzweifele. Hier in dem Fall habe ich einfach die Definitionen willkürlich aufgeschrieben, in der Hoffnung, dass am Ende etwas rauskommt, was richtig ist. Aber ich merke, dass ich dadurch nichts lerne. Ohne es zu verstehen und allgemein, was überhaupt da abgeht, schieße ich mir nur selber ins eigene Tor.

Ich glaube, ich muss mir erst klarmachen, warum das überhaupt gilt, bevor ich versuche es zu beweisen. Ich habe mir einfach überlegt ein Beispiel anzugeben:

$\begin{eqnarray*} A = \{1,2\} \end{eqnarray*}$ und $\begin{eqnarray*} A \times A = \{(1,1),(2,2),(1,2),(2,1)\} \end{eqnarray*}$

$\begin{eqnarray*} R=\{(1,1),(2,2)\} \end{eqnarray*}$ , woraufhin sich dann $\begin{eqnarray*} R^{'}=\{(1,2),(1,2)\} \end{eqnarray*}$ ergibt. Wenn ich jetzt darüber nachdenke bzgl. der Reflexivität für $\begin{eqnarray*} R^{'} \end{eqnarray*}$ , müssen in $\begin{eqnarray*} R \end{eqnarray*}$ die Identitätspaare drin sein. Dieser Fall ist für mich irgendwie nicht ganz trivial, gilt hier überhaupt die Reflexivität? Ich gehe stark davon aus, dass mein $\begin{eqnarray*} R^{'} \end{eqnarray*}$ falsch ist.

09.12.2020, 07:06

Elvis

Auf diesen Beitrag antworten »

Wenn der in der Aufgabe formulierte und von dir zu beweisende Satz wahr ist, dann kannst du nicht ein Beispiel machen, in dem R' und R nicht in der definierten Relation zueinander stehen. Ist doch klar, dass bei Verletzung der Voraussetzungen der Satz nicht notwendig wahr ist. Zutreffende Beispiele können das Verständnis für wahre Aussagen unterstützen, zutreffende Gegenbeispiele beweisen, dass eine Aussage falsch ist. Falsche Beispiele widerlegen keinen wahren Satz, falsche Gegenbeispiele widerlegen keine falsche Aussage. Fazit : Beweise sind primär, Beispiele sekundär. Du musst Beweise verstehen und selbst machen. Danach sind treffende Beispiele wichtig und hilfreich.

Gut gemeinter Rat: Fange jetzt an zu arbeiten, später ist zu spät.

09.12.2020, 13:15

Yasminx3

Auf diesen Beitrag antworten »

Elvis, ich weiß, ich kann echt eine harte Nuss sein. Tut mir dafür echt leid. Aber für die Transitivität hab ich echt diese Methode genutzt: ("Schreiben, Probieren und Korrigieren")

Transitivität:
Sei noch $\begin{eqnarray*} c_1,c_2 \in A \end{eqnarray*}$ , da $\begin{eqnarray*} R^{'} \end{eqnarray*}$ transitiv $\begin{eqnarray*} \Rightarrow (\text{*}) \ (a_1,a_2)R^{'}(b_1,b_2) \wedge (b_1,b_2)R^{'}(c_1,c_2) \Rightarrow (\text{i}) \ (a_1,a_2)R^{'}(c_1,c_2) \Rightarrow \end{eqnarray*}$ nach $\begin{eqnarray*} (\text{*}) \end{eqnarray*}$ und Definition gilt erstmal für $\begin{eqnarray*} R \end{eqnarray*}$ : $\begin{eqnarray*} a_1Rb_1 \wedge a_2Rb_2 \end{eqnarray*}$ und $\begin{eqnarray*} b_1Rc_1 \wedge b_2Rc_2. \end{eqnarray*}$ Und nach (i), $\begin{eqnarray*} (\text{*}) \end{eqnarray*}$ und der Definition gilt auch für $\begin{eqnarray*} R \end{eqnarray*}$ : $\begin{eqnarray*} a_1Rc_1 \wedge a_2Rc_2 \end{eqnarray*}$ $\begin{eqnarray*} \Rightarrow R \end{eqnarray*}$ ist transitiv.

Hmm, stimmt das soweit?

09.12.2020, 14:21

Elvis

Auf diesen Beitrag antworten »

Zitat:

Original von Yasminx3
Elvis, ich weiß, ich kann echt eine harte Nuss sein.

Das sehe ich nicht so, du musst noch viel härter gegen dich selbst werden. Augenzwinkern

Zitat:

Original von Yasminx3
Tut mir dafür echt leid.

"Mathematics means never having to say you're sorry."

Abgesehen von der unvollständigen Definition der Variablen und der etwas undeutlichen Verwendung von (i) und (*) ist dieser kleine Beweisteil korrekt. Ich verstehe jedenfalls, was du meinst, und es passt alles zusammen.

09.12.2020, 16:44

Yasminx3

Auf diesen Beitrag antworten »

Zitat:

Das sehe ich nicht so, du musst noch viel härter gegen dich selbst werden.

Werde ich!

Zitat:

Abgesehen von der unvollständigen Definition der Variablen und der etwas undeutlichen Verwendung von (i) und (*) ist dieser kleine Beweisteil korrekt. Ich verstehe jedenfalls, was du meinst, und es passt alles zusammen.

Pure Erleichterung. Tanzen

Beweis:

" $\begin{eqnarray*} \Leftarrow \end{eqnarray*}$ "

Reflexivität:
Da $\begin{eqnarray*} R \end{eqnarray*}$ reflexiv ist, gilt für $\begin{eqnarray*} \forall a,b \in R: aRa \wedge bRb \end{eqnarray*}$ . Somit gilt nach Definition für $\begin{eqnarray*} R^{'} \end{eqnarray*}$ folgendes: $\begin{eqnarray*} \forall a,b \in R^{'}: (a,b)R^{'}(a,b) \Rightarrow \end{eqnarray*}$ $\begin{eqnarray*} R^{'} \end{eqnarray*}$ ist reflexiv.

Antisymmetrie:
Da $\begin{eqnarray*} R \end{eqnarray*}$ antisymmetrisch ist, gilt für $\begin{eqnarray*} \forall a,b \in R: aRb \wedge bRa \Rightarrow a=b \end{eqnarray*}$ , nach Definition gilt für $\begin{eqnarray*} R^{'} \end{eqnarray*}$ folgendes: $\begin{eqnarray*} (a,b)R^{'}(b,a) \end{eqnarray*}$ und da $\begin{eqnarray*} R \end{eqnarray*}$ antisymmetrisch ist und wir vorher $\begin{eqnarray*} a=b \end{eqnarray*}$ gefolgert haben, gilt auch für $\begin{eqnarray*} R^{'} \end{eqnarray*}$ folgendes: $\begin{eqnarray*} (a,b)=(b,a) \end{eqnarray*}$ , also gilt für $\begin{eqnarray*} R^{'} \end{eqnarray*}$ die Antisymmetrie.

Transitivität:
Da $\begin{eqnarray*} R \end{eqnarray*}$ transitiv ist, gilt für $\begin{eqnarray*} \forall a,b,c \in R: aRb \wedge bRc \Rightarrow aRc \end{eqnarray*}$ , dann gilt für $\begin{eqnarray*} R^{'} \end{eqnarray*}$ nach Definition: $\begin{eqnarray*} (a,b)R^{'}(b,c) \end{eqnarray*}$

Bei der Transitivität haperts irgendwie. Ich weiß nicht, wie ich da jetzt was folgern kann. verwirrt

Aber der Nachweis für Reflexivität und Antisymmetrie müsste eigentlich stimmen. verwirrt

09.12.2020, 18:09

Elvis

Auf diesen Beitrag antworten »

Reflexivität muss stets für alle a,bin A gelten; a,b in R oder R' ist sinnlos, weil die Paare (a,b) in R und die Paare ((a,b),(c,d)) in R' liegen.
Bei den anderen Eigenschaften musst du ebenfalls für alle Variablen in A formulieren, die in der entsprechenden Relation stehen.

Reflexivität und Symmetrie sind im Prinzip richtig. Für die Transitivität muss man mehr tun, wenn und weil es nicht immer nach dem gleichen Schema geht.

$\begin{eqnarray*} \forall a,b,c,d,e,f\in A: (a,b)R'(c,d) \wedge (c,d)R'(e,f)\Rightarrow aRc\wedge bRd\wedge cRe \wedge dRf \end{eqnarray*}$ nach Def.
$\begin{eqnarray*} \Rightarrow aRc\wedge cRe\wedge bRd \wedge dRf\Rightarrow aRe\wedge bRf \end{eqnarray*}$ weil $\begin{eqnarray*} R \end{eqnarray*}$ transitiv
$\begin{eqnarray*} \Rightarrow (a,b)R'(e,f) \end{eqnarray*}$ nach Def.
also $\begin{eqnarray*} R' \end{eqnarray*}$ transitiv falls $\begin{eqnarray*} R \end{eqnarray*}$ transitiv. qed.

(Meine Vorgehensweise: hinschreiben, was ich weiß ... hinschreiben, was ich will ... Lücken von oben nach unten und von unten nach oben ausfüllen. MaW: Nachdenken, Schreiben, Probieren und Korrigieren.)

09.12.2020, 22:47

Yasminx3

Auf diesen Beitrag antworten »

b)

Beweis:

" $\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ "

Wenn $\begin{eqnarray*} R^{'} \end{eqnarray*}$ eine lineare Ordnung ist, gilt für $\begin{eqnarray*} R^{'} \end{eqnarray*}$ die Konnexität, Antisymmetrie und Transitivität.

Konnexität: $\begin{eqnarray*} \forall a_1, a_2, b_1, b_2 \in A: (a_1,a_2) R^{'}(b_1,b_2) \vee (b_1,b_2)R^{'}(a_1,a_2) \end{eqnarray*}$ , dann gilt nach Definition für $\begin{eqnarray*} R \end{eqnarray*}$ folgendes: $\begin{eqnarray*} \forall a_1, a_2, b_1, b_2 \in A: (a_1Rb_1 \wedge a_2Rb_2) \vee (b_1Ra_1 \wedge b_2Ra_2) \end{eqnarray*}$

Hier bin ich sehr skeptisch, entweder bin ich komplett auf dem falschen Dampfer oder meine Vermutung liegt nahe, dass eben nicht $\begin{eqnarray*} R=id_{A} \end{eqnarray*}$ ist. In der Theorie hätte man als $\begin{eqnarray*} R \end{eqnarray*}$ ein einziges Element und das wäre das eine Identitätspaar, da die Kardinalität von $\begin{eqnarray*} A \end{eqnarray*}$ eins beträgt, aber die Folgerung oben besagt ja, dass wir mehrere vergleichbare Elemente haben. verwirrt

10.12.2020, 06:20

Elvis

Auf diesen Beitrag antworten »

Die Theorie sagt nicht, dass die Elemente von A paarweise verschieden sind. Zu einem Namen gehört ein Objekt, ein Objekt kann beliebig viele Namen haben. So ist es in der Mathematik. In der Realität ist es nicht so, aber das ist eine andere Geschichte.

10.12.2020, 09:09

Mathice

Auf diesen Beitrag antworten »

Du hast tatsächlich recht. Oben hast du bewiesen, dass es sich nicht um eine konnexe Relation handeln kann, obwohl deine Menge A nur ein einiziges Element besitzt.

Somit bist du so gut wie fertig. smile

10.12.2020, 09:48

Elvis

Auf diesen Beitrag antworten »

Unsinn. Jede Ordnungsrelation ist reflexiv, also gilt sowohl (a,a)R'(a,a) als auch aRa. Für A={a} sind das zwei prima lineare Ordnungsrelationen auf AxA und A. Yasminx3 ist nicht fertig, sie hat noch nicht einmal angefangen.

10.12.2020, 19:03

Yasminx3

Auf diesen Beitrag antworten »

Hätte mich ehrlich gesagt auch gewundert. Big Laugh

Beginnen wir nun mal mit dem Beweis:

z.z Wenn $\begin{eqnarray*} R=id_{A} \end{eqnarray*}$ und $\begin{eqnarray*} ||A||=1 \end{eqnarray*}$ ist $\begin{eqnarray*} \Rightarrow R^{'} \end{eqnarray*}$ ist Ordnung.

Wenn $\begin{eqnarray*} R=id_{A} \end{eqnarray*}$ und $\begin{eqnarray*} ||A||=1 \end{eqnarray*}$ , gilt $\begin{eqnarray*} \forall a \in A:aRa \wedge aRa \Rightarrow aRa \end{eqnarray*}$ , da $\begin{eqnarray*} aRa \wedge aRa \equiv aRa \end{eqnarray*}$ , also gilt nach Definiton erstmal: $\begin{eqnarray*} (a,a)R^{'}(a,a) \Rightarrow R^{'} \end{eqnarray*}$ ist konnex. Und da auch $\begin{eqnarray*} a=a \end{eqnarray*}$ und $\begin{eqnarray*} (a,a)=(a,a) \end{eqnarray*}$ gilt Antisymmetrie.
Die Transitivität ist wie ich finde irgendwie trivial.

Ist erstmal mein Beweis soweit korrekt? verwirrt

10.12.2020, 19:14

Elvis

Auf diesen Beitrag antworten »

Trivial ja, so trivial, dass man es schneller hinschreiben kann als man "trivial" sagen kann. Augenzwinkern

$\begin{eqnarray*} A=\{a\}\Rightarrow (\forall (a,a)\in A\times A: (a,a)R'(a,a)\wedge (a,a)R'(a,a)\Rightarrow (a,a)R'(a,a)) \end{eqnarray*}$ , also $\begin{eqnarray*} R' \end{eqnarray*}$ transitiv.

Du bist schon mal auf dem richtigen Weg. Die eine Richtung ist also trivial, man sollte sich aber auch und gerade bei trivialen Beweisen die Mühe machen, die Beweise zu schreiben, das übt enorm, denn man lernt daran korrektes Schreiben, und genau das braucht man 10 Sekunden später für die nichttrivialen Beweise. Wo sollen denn die notwendigen Fähigkeiten herkommen, wenn man sie nicht an einfachen Beispielen übt ?

10.12.2020, 19:34

Yasminx3

Auf diesen Beitrag antworten »

Ja, true. Ich hätte ehrlich gesagt auch niemals gedacht, dass ich bestimmte Dinge schaffe zu lösen.

Die andere Richtung:

$\begin{eqnarray*} R^{'} \end{eqnarray*}$ ist lineare Ordnung $\begin{eqnarray*} \Rightarrow ||A||=1 \wedge R=id_{A} \end{eqnarray*}$

Diese Richtung ist irgendwie ein Rätsel für mich. Wenn wir annehmen, dass $\begin{eqnarray*} R^{'} \end{eqnarray*}$ eine lineare Ordnung ist, dann können wir nicht daraus schließen, $\begin{eqnarray*} \Rightarrow ||A||=1 \wedge R=id_{A} \end{eqnarray*}$ , denn unser $\begin{eqnarray*} A \end{eqnarray*}$ kann vorher alles gewesen sein, es kann natürlich auch sein, dass unser $\begin{eqnarray*} ||A||=1 \end{eqnarray*}$ ist, muss aber nicht sein. Deshalb würde ich hier in dem Fall sagen, dass nur die Gegenrichtung gilt.

Gegenbeweis für die obige Richtung:

$\begin{eqnarray*} A=\{1,2\} \end{eqnarray*}$ , $\begin{eqnarray*} R^{'}=\{(1,1),(2,2),(1,2)\} \end{eqnarray*}$ ist eine lineare Ordnung.

Dann gilt nach Definition für $\begin{eqnarray*} 1,2 \in A:1R2 \wedge 1R2 \wedge 2R1 \wedge 2R2 \end{eqnarray*}$ , aber $\begin{eqnarray*} R\neq id_{A} \end{eqnarray*}$ und $\begin{eqnarray*} ||A||\neq1 \end{eqnarray*}$ .

Ich weiß, ich bin so schlecht im aufschreiben, aber ist das soweit korrekt? verwirrt

10.12.2020, 22:11

Elvis

Auf diesen Beitrag antworten »

Nein. Wenn 1R2 und 2R1, dann ist 1=2, weil die Ordnungsrelation antisymmetrisch ist. Das ist ein guter Versuch aber kein Gegenbeispiel. Ich würde an deiner Stelle einen Beweis versuchen. Es muss nicht immer alles trivial sein.

10.12.2020, 22:40

Yasminx3

Auf diesen Beitrag antworten »

Ok, ich versuchs mal. smile

Wenn $\begin{eqnarray*} R^{'} \end{eqnarray*}$ eine lineare Ordnung ist, gilt $\begin{eqnarray*} \forall a,b \in A: (a,b)R^{'}(a,b) \end{eqnarray*}$ und wegen Antisymmetrie auch $\begin{eqnarray*} (a,b)=(a,b) \end{eqnarray*}$ , aber Fallunterscheidung:

Fall 1: $\begin{eqnarray*} ||A|| = 1 \end{eqnarray*}$ und $\begin{eqnarray*} R^{'} = id_{A} \end{eqnarray*}$ , dann gilt für $\begin{eqnarray*} R \end{eqnarray*}$ nach Definiton $\begin{eqnarray*} \forall a,b \in A: aRa \wedge bRb \end{eqnarray*}$ , somit gilt $\begin{eqnarray*} R= id_{A} \wedge ||A|| = 1 \end{eqnarray*}$ .

Fall 2: $\begin{eqnarray*} ||A|| > 1 \end{eqnarray*}$ und $\begin{eqnarray*} R^{'} = id_{A} \end{eqnarray*}$ , dann gilt für $\begin{eqnarray*} R \end{eqnarray*}$ nach Definiton $\begin{eqnarray*} \forall a,b \in A: aRa \wedge bRb \end{eqnarray*}$ , somit gilt zwar $\begin{eqnarray*} R= id_{A} \end{eqnarray*}$ , aber wegen Annahme $\begin{eqnarray*} ||A|| > 1 \end{eqnarray*}$ gilt eben nicht $\begin{eqnarray*} ||A|| \neq 1 \end{eqnarray*}$ . Somit erhalten wir einen Widerspruch.

Passt das so? verwirrt

Ich muss sagen, es macht echt Spaß so logische Schlüsse aufzuschreiben und darüber nachzudenken. smile

11.12.2020, 07:04

Elvis

Auf diesen Beitrag antworten »

Leider alles falsch. (a,b)=(a,b) gilt immer. Nicht R' sondern R soll die Identität sein.
1.Fall aRa und bRb gilt wegen Reflexivitaet von R immer.
2.Fall Für a=b hat A={a,b} nur ein Element.

Hinweis. Wieder einmal ist "genau dann wenn" zu beweisen, also 2 Implikationen. Schreibe jeweils alle Voraussetzungen auf und versuche, logisch korrekte Folgerungen zu ziehen.

Wenn ich dir einen Beweis mache, wirst du glauben, dass das trivial ist. Das ist es auch, aber erst, wenn man den Beweis hat und nicht für jeden vorher. Wenn es für dich noch nicht trivial ist, musst Du und nur Du einen Beweis machen.

11.12.2020, 10:21

Yasminx3

Auf diesen Beitrag antworten »

Ich finde diese Richtung irgendwie sehr anspruchsvoll. Ich danke dir für deine Geduld.

Beweis:

Zitat:

Hinweis. Wieder einmal ist "genau dann wenn" zu beweisen, also 2 Implikationen. Schreibe jeweils alle Voraussetzungen auf und versuche, logisch korrekte Folgerungen zu ziehen.

Meinst du diese zwei Implikationen?

(1) $\begin{eqnarray*} R=id_{A} \end{eqnarray*}$ und $\begin{eqnarray*} ||A||=1 \end{eqnarray*}$ $\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ $\begin{eqnarray*} R^{'} \end{eqnarray*}$ ist lineare Ordnung.

Diese (1) Implikation haben wir bereits gezeigt. verwirrt

(2) $\begin{eqnarray*} R^{'} \text{ist lineare Ordnung} \end{eqnarray*}$ $\begin{eqnarray*} \Rightarrow R=id_{A} \text{und} ||A||=1 \end{eqnarray*}$ .

Wenn $\begin{eqnarray*} R^{'} \end{eqnarray*}$ eine lineare Ordnung ist, gilt $\begin{eqnarray*} \forall a,b \in A: (a,b)R^{'}(a,b) \end{eqnarray*}$ , wegen Antisymmetrie gilt zwar $\begin{eqnarray*} (a,b)=(a,b) \end{eqnarray*}$ , aber $\begin{eqnarray*} a \neq b \end{eqnarray*}$ und nach Definition gilt dann für $\begin{eqnarray*} R \end{eqnarray*}$ folgendes $\begin{eqnarray*} \forall a,b \in A: aRa \wedge bRb \Rightarrow R = id_{A} \end{eqnarray*}$ , da aber $\begin{eqnarray*} a \neq b \end{eqnarray*}$ , gilt $\begin{eqnarray*} ||A|| > 1 \end{eqnarray*}$ .

Moment, nur fürs Verständnis ist (2) auch richtig? Weil ich versuche die ganze Zeit das zu widerlegen. ^^

11.12.2020, 11:13

Elvis

Auf diesen Beitrag antworten »

(1) wo und wie ?
(2) Dein Beweisversuch ist von vorne bis hinten falsch. Jede Ordnungsrelation ist reflexiv, also (a,b)R'(a,b) selbstverständlich. (a,b)=(a,b) gilt für jedes Paar und nicht wegen Antisymmetrie. R ist selbstverständlich reflexiv und nicht weil es aus irgend etwas folgt. Aus Trivialitäten folgt gar nichts. Warum soll a ungleich b sein, a=b ist genau so gut möglich.

11.12.2020, 12:49

Yasminx3

Auf diesen Beitrag antworten »

So, habs nochmal versucht. Erstmal die eine Richtung. Wieso muss beweisen so schwer sein? Vielleicht liegts einfach an mir.

(1) $\begin{eqnarray*} R=id_{A} \ \text{und} \ ||A||=1 \Rightarrow R^{'} \end{eqnarray*}$ ist lineare Ordnung.

(2) $\begin{eqnarray*} R^{'} \text{ist lineare Ordnung} \Rightarrow R=id_{A} \ \text{und} \ ||A||=1 \end{eqnarray*}$

Beweis:
(1):
Wenn $\begin{eqnarray*} R=id_{A} \ \text{und} \ ||A||=1 \end{eqnarray*}$ , dann gilt $\begin{eqnarray*} \forall a \in A:aRa \equiv aRa \wedge aRa \end{eqnarray*}$ , dann gilt nach Definition für $\begin{eqnarray*} R^{'} \end{eqnarray*}$ folgendes: $\begin{eqnarray*} \forall a \in A: (a,a)R^{'}(a,a) \Rightarrow R^{'} \end{eqnarray*}$ ist konnex.

Und aufgrund $\begin{eqnarray*} a=a \end{eqnarray*}$ , gilt auch $\begin{eqnarray*} (a,a) = (a,a) \end{eqnarray*}$ , somit gilt auch die Antisymmetrie für $\begin{eqnarray*} R^{'} \end{eqnarray*}$ .

Da $\begin{eqnarray*} ||A||=1 \end{eqnarray*}$ , gilt immer die Transitivität, da $\begin{eqnarray*} \forall a,b,c,d,f \in A: aRb \wedge bRc \wedge bRc \wedge cRf \end{eqnarray*}$ , dann gilt für $\begin{eqnarray*} R^{'} \end{eqnarray*}$ folgendes: $\begin{eqnarray*} \forall a,b,c,d,e,f \in A: (a,b)R^{'}(b,c) \wedge (b,c)R^{'}(c,f) \end{eqnarray*}$ , da aber $\begin{eqnarray*} ||A||=1 \Rightarrow a=b=c=d=f \Rightarrow aRc \wedge bRf \end{eqnarray*}$ für $\begin{eqnarray*} R \end{eqnarray*}$ und für $\begin{eqnarray*} R^{'} \end{eqnarray*}$ gilt: $\begin{eqnarray*} (a,b) = (b,c) = (c,f) \Rightarrow (a,b)R^{'}(c,f) \end{eqnarray*}$ , also $\begin{eqnarray*} R^{'} \end{eqnarray*}$ transitiv.

Somit haben wir die drei Eigenschaften gezeigt, die für eine lineare Ordnung notwendig sind und alle drei Eigenschaften sind aus $\begin{eqnarray*} R=id_{A} \ \text{und} \ ||A||=1 \Rightarrow R^{'} \end{eqnarray*}$ gefolgt. $\begin{eqnarray*} \square \end{eqnarray*}$

11.12.2020, 13:27

Elvis

Auf diesen Beitrag antworten »

Zitat:

Original von Elvis
Unsinn. Jede Ordnungsrelation ist reflexiv, also gilt sowohl (a,a)R'(a,a) als auch aRa. Für A={a} sind das zwei prima lineare Ordnungsrelationen auf AxA und A. Yasminx3 ist nicht fertig, sie hat noch nicht einmal angefangen.

Hier hatte ich bereits den Beweis für (1) versteckt. Schade, dass du es nicht gemerkt hast. Dein Beweisversuch ist nicht ganz verständlich.

(2) Die Behauptung (2a) " R' linear, dann |A|=1 und R=id "
ist wegen " R ungleich id, dann |A|>1 " äquivalent zur
Behauptung (2b) " R ungleich id, dann ist |A|>1 und R' nicht linear ".
(Nach 3 Versuchen (je DIN A5), mittelschwerer Verzweiflung, intensivem Nachdenken, Schreiben, Probieren, Rechnen und Zeichnen ist mir soeben ein eleganter Beweis für (2b) gelungen. Tanzen

Hau ran, es macht Spaß, wenn's gelingt. Ironie der Geschichte: Nachdem man die Voraussetzungen sauber aufgeschrieben hat, ist der Beweis ein Einzeiler, also trivial.)

12.12.2020, 02:33

Yasminx3

Auf diesen Beitrag antworten »

Heißt diese Methode Kontraposition? verwirrt

Wenn $\begin{eqnarray*} R \neq id_{A} \end{eqnarray*}$ und $\begin{eqnarray*} ||A|| > 1 \end{eqnarray*}$ , dann gilt für $\begin{eqnarray*} \forall a \in A:a\not Ra \wedge a\not Ra \end{eqnarray*}$ , dann gilt nach Definition für $\begin{eqnarray*} R^{'} \end{eqnarray*}$ folgendes: $\begin{eqnarray*} \forall a \in A: (a,a)\not R^{'} (a,a) \Rightarrow R^{'} \end{eqnarray*}$ keine lineare Ordnung, wegen nicht reflexiv.

Sag mir bitte nicht, dass man es einfach so zeigen kann. Also meine so einfach. Bitte sag, dass ich falsch liege und es anders beweisen muss. Big Laugh

12.12.2020, 07:09

Elvis

Auf diesen Beitrag antworten »

Ja, die von mir vorgeschlagene Methode ist ein Beweis durch Widerspruch, also ein Beweis durch Kontraposition. Deiner Bitte komme ich gerne nach, du liegst vollkommen falsch. Jede Ordnungsrelation ist per Definition reflexiv, es gilt immer aRa und (a,a)R'(a,a) für alle a in A, egal wie viele Elemente A hat.

Tipp. Eine Menge mit genau einem Element unterscheidet sich von einer Menge mit mehr als einem Element. Es ist nicht so schwer, diesen Unterschied festzustellen.

12.12.2020, 11:22

Yasminx3

Auf diesen Beitrag antworten »

Zitat:

Jede Ordnungsrelation ist per Definition reflexiv, es gilt immer aRa und (a,a)R'(a,a) für alle a in A, egal wie viele Elemente A hat.

Ah. Deshalb der Widerspruchsbeweis. Dann reicht das doch für den Beweis, also dieser Satz? verwirrt

12.12.2020, 13:56

Elvis

Auf diesen Beitrag antworten »

Nein, das reicht nicht.

Behauptung (2b) " R ungleich id, dann ist |A|>1 und R' nicht linear ".

Du musst beweisen, dass R' nicht linear ist. Wo ist dein Beweis ?

12.12.2020, 21:08

Yasminx3

Auf diesen Beitrag antworten »

Diese Aufgabe bringt mich so zum verzweifeln, ich will mir garnicht vorstellen, was noch so auf mich zukommt. ^^

Versuch Beweis:

Wenn $\begin{eqnarray*} R \neq id_{A} \wedge ||A|| > 1 \end{eqnarray*}$ gilt erstmal: $\begin{eqnarray*} \forall a,b\in A:\underbrace{aRa \wedge bRb}_{\text{Wegen Reflexivität}} \wedge bRa \end{eqnarray*}$ , somit gilt nach Definition für $\begin{eqnarray*} R^{'} \end{eqnarray*}$ folgendes: $\begin{eqnarray*} \forall a,b \in A: (b,b)R^{'}(b,a) \end{eqnarray*}$ , da aber wegen $\begin{eqnarray*} ||A|| > 1 \end{eqnarray*}$ und $\begin{eqnarray*} a \neq b \Rightarrow (b,b) \neq (b,a) \Rightarrow R^{'} \end{eqnarray*}$ nicht antisymmetrisch, also keine lineare Ordnung.

12.12.2020, 21:59

Elvis

Auf diesen Beitrag antworten »

Hast du vergessen, dass in Aufgabe a) bewiesen wurde, dass R' eine Ordnungsrelation ist? Jede Ordnungsrelation ist antisymmetrisch. Warum ignorierst du meine Hinweise und versuchst stattdessen etwas zu beweisen, das unmöglich wahr sein kann? Wie kommst du auf die Idee, dass bRa für alle a, b in A wahr sein sollte? Ich gebe zu, dass diese Übung nicht ganz einfach ist, aber wenn man sich etwas mehr Mühe gibt, dann ist es machbar. Bedenke, dass die Mathematik eine Wissenschaft ist, die keinen Fehler erlaubt, da muss immer alles stimmen, was nicht vollkommen richtig ist, ist vollkommen falsch.

12.12.2020, 22:12

Yasminx3

Auf diesen Beitrag antworten »

Das ist mir im Nachhinein aufgefallen, dass das einfach Käse ist, was ich da geschrieben habe.
Tut mir wirklich leid.

Nur fürs Verständnis:

$\begin{eqnarray*} R \neq id_{A} \end{eqnarray*}$ schließt nicht aus, dass in R doch die Identitätspaare drin sein können? verwirrt

Zitat:

" R ungleich id, dann ist |A|>1 und R' nicht linear ".

Wir können hier nicht als Voraussetzung benutzen, dass R linear ist. Wir wissen nur, dass R eine Relation ist. Oder? verwirrt

Wenn das der Fall ist, könnte man doch eine Relation basteln, die genau zeigt, dass R' keine lineare Ordnung ist. oder? verwirrt

Also mit der Voraussetzung, dass $\begin{eqnarray*} R \neq id_{A} \end{eqnarray*}$ ist.

12.12.2020, 22:24

Elvis

Auf diesen Beitrag antworten »

R ist eine Ordnungsrelation, also reflexiv. Was heißt also R ungleich id?

12.12.2020, 22:36

Yasminx3

Auf diesen Beitrag antworten »

R ist nicht reflexiv, wenn die Identitätspaare nicht drin sind.

Warte mal bitte kurz, sag mir bitte nicht, dass $\begin{eqnarray*} R \neq id_{A} \end{eqnarray*}$ heißt, dass einfach keine Identitätspaare in R drin sein dürfen.

Ich bin nämlich die ganze Zeit davon ausgegangen, dass mit ida die Menge der Identitätspaare gemeint ist, also konkret:

ida = {(a,a)}

Und dachte dann, dass wenn in R auch andere Paare drin sind, also nicht nur die Identitätspaare, dass es dann erlaubt wäre.

Nur das R nicht so aufgebaut sein darf, dass halt nur die Identitätspaare drin sind.

Sorry, konnte nicht so ganz Latex verwenden, schreibe vom Handy.

12.12.2020, 22:43

Elvis

Auf diesen Beitrag antworten »

Das hast du schon richtig verstanden, schreibe es korrekt als logische Aussage auf, damit du damit weiter arbeiten kannst. Mit ungefährem Wissen ("andere Paare drin", "erlaubt") kann man nicht arbeiten, das geht nur mit Aussagen. Aussagen müssen nicht Formeln sein, aber sie müssen klar, korrekt, verständlich und vollständig sein.

13.12.2020, 16:31

Yasminx3

Auf diesen Beitrag antworten »

Fange ich mal langsam an und schreibe die Aussage erstmal auf.

Wenn $\begin{eqnarray*} R \neq id_{A} \end{eqnarray*}$ , dann $\begin{eqnarray*} \exists (a,b) \in R \end{eqnarray*}$ , wobei $\begin{eqnarray*} a\neq b \end{eqnarray*}$ .

Stimmt das soweit?

Es muss dennoch gelten, dass $\begin{eqnarray*} ida \subset R \end{eqnarray*}$ ist, weil ja R eine Ordnung ist.

13.12.2020, 18:10

Elvis

Auf diesen Beitrag antworten »

Besser:

Sei $\begin{eqnarray*} A \end{eqnarray*}$ eine nichtleere Menge und $\begin{eqnarray*} R\neq id_{A} \end{eqnarray*}$ eine Ordnungsrelation auf $\begin{eqnarray*} A \end{eqnarray*}$ . Dann $\begin{eqnarray*} \exists a,b\in A \end{eqnarray*}$ mit $\begin{eqnarray*} a\neq b \end{eqnarray*}$ und $\begin{eqnarray*} aRb \end{eqnarray*}$ .

Was folgt daraus ? Was folgt für $\begin{eqnarray*} a \end{eqnarray*}$ und $\begin{eqnarray*} b \end{eqnarray*}$ und $\begin{eqnarray*} R \end{eqnarray*}$ ? Definiere dann $\begin{eqnarray*} R' \end{eqnarray*}$ und berechne, was für $\begin{eqnarray*} a \end{eqnarray*}$ und $\begin{eqnarray*} b \end{eqnarray*}$ und $\begin{eqnarray*} R' \end{eqnarray*}$ folgt. Ziehe daraus korrekte logische Schlüsse. Beachte im letzten Teil, dass die Linearität von $\begin{eqnarray*} R' \end{eqnarray*}$ zu widerlegen ist, gib also auch insbesondere deren Definition an.

Versuche noch langsamer und noch ausführlicher und noch vollständiger zu werden. Alles was du nicht in den Beweis schreibst, existiert nicht, denn niemand hat Lust, immer wieder in der Aufgabe nachzulesen und niemand kann deine Gedanken lesen.
Für Beweise braucht man viel Geduld. Der Beweis für den großen Satz von Fermat hat 300 Jahre gedauert, wobei Andrew Wiles alleine 7 Jahre lang nichts anderes gemacht hat, nachdem er eine gute Idee von Gerhard Frey geschenkt bekam.

15.12.2020, 00:47

Yasminx3

Auf diesen Beitrag antworten »

Sorry, für die späte Rückmeldung. Ich saß heute sieben Stunden an einem Programm. :/

Ich habe eine kleine Verständnisfrage. Wir nehmen bei b) ja an, dass es sich um eine Ordnung handelt. Richtig?

Können wir das überhaupt? Weil wir bei a) ja angenommen haben, dass wenn R eine Ordnung ist, daraus resultiert das auch R' eine Ordnung ist, aber wenn wir diese Annahme nicht treffen, sondern nicht gegeben ist, dass es sich um eine Ordnung handelt, sondern einfach um eine Relation, kann man das dann noch als Voraussetzung nehmen?

15.12.2020, 07:13

Elvis

Auf diesen Beitrag antworten »

Wenn R keine Ordnungsrelation ist, dann ist auch R' keine Ordnungsrelation und folglich keine lineare Ordnungsrelation. Nach allgemeinem Sprachgebrauch gehen wir davon aus, dass beide Relationen Ordnungsrelationen sind, weil die Aufgabe b) sonst sinnlos wäre.

12 nächste Seite »

Neue Frage »

Antworten »

Ordnungsbeweis

Verwandte Themen