Äquivalenz-beweis < Aussagenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:59 Sa 20.11.2010 | | Autor: | mztic |
| Aufgabe | Sei R [mm] \subset [/mm] M [mm] \times [/mm] M eine Äquivalenzrelation.
Zeigen Sie, daß die Aussagen [mm] \bar{x} [/mm] = [mm] \bar{y} [/mm] und xRy äquivalent sind.
Zeigen Sie auch, daß [mm] \neg(xRy) [/mm] äquivalent ist zu [mm] \bar{x} \cap \bar{y} [/mm] = [mm] \emptyset [/mm] . |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Ich weiß nicht, wie ich es beweisen soll...
ich hab zwar nun auf meinem Blatt stehen, dass es was mit Symmetrie zu tun hat, also:
[mm] \forall [/mm] x,y [mm] \in [/mm] M: xRy [mm] \Rightarrow [/mm] yRx
zudem halt, die Formel R [mm] \subset [/mm] M [mm] \times [/mm] M:
[mm] \forall [/mm] (x,y) ((x [mm] \in [/mm] R) [mm] \wedge [/mm] (y [mm] \in [/mm] R) [mm] \Rightarrow [/mm] (x [mm] \in [/mm] M) [mm] \wedge [/mm] (y [mm] \in [/mm] M))
und [mm] \bar{x} [/mm] = [mm] \bar{y}:
[/mm]
(y [mm] \in [/mm] M | yRx) [mm] \gdw [/mm] (x [mm] \in [/mm] M | xRy)
wobei ich nicht weiß, ob die Angaben überhaupt stimmen, bin mir da leider nciht sicher.. Ich brauch grade echt denkanstöße bzw. Hilfe. wäre echt nett!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:04 Sa 20.11.2010 | | Autor: | Sax |
Hi,
weißt du, dass du hier einen der ganz grundlegenden Sätze über Äquivalenzrelationen und Klasseneinteilungen beweist ? Es ist immer gut, sich die Aussage eines Satzes anschaulich klar zu machen, bevor man sich in den technischen Einzelheiten eines Beweises verliert.
Du sollst beweisen, dass jede Äquivalenzrelation auf M eine Klasseneinteilung von M erzeugt. (Umgekehrt stimmt es übrigens auch, jede Klasseneinteilung definiert eine Äquivalenzrelation.)
Konkret geht es um folgendes :
Zwischen den Elementen von M gibt es ein gewisses "Gleichheits-Merkmal", welches gewisse Paare (aus M [mm] \times [/mm] M) auszeichnet. Z.B. könnte ein solches Gleichheitsmerkmal für die Punkte des Raumes darin bestehen, dass sie den gleichen Abstand zum Koordtnaten-Nullpunkt haben, oder bei ganzen Zahlen darin bestehen, dass sie bei Division durch 5 denselben Rest lassen oder bei den Schülern meiner Klasse darin bestehen, dass sie verwandt sind.
Mathematiker kennzeichnen ein solches Gleichheits-Merkmal durch eine Äquivalenzrelation R, die durch die drei bekannten Forderungen (Reflexivität, Symmetrie, Trnsitivität) charakterisiert wird.
R ist eine Teilmenge aller möglichen Paare, nämlich der ausgezeichneten.
Mein erstes Beispiel von oben mal veranschaulicht :
[Dateianhang nicht öffentlich]
B und D haben denselben Abstand zum Nullpunkt, also gehört das Paar (B,D) zur Relation R, ebenso gehört (E,F) dazu oder auch (E,E). Die Paare (A,B) oder (D,F) gehören jedoch nicht dazu. Statt " (B,D) [mm] \in [/mm] R " wird oft die Schreibweise BRD oder B~D bevorzugt.
Man kann nun Teilmengen von M, sogenannte Äquivalenzklassen definieren, indem man diejenigen Elemente von M zusammenfasst, die in der Relation R zueinander stehen. Im obigen Beispiel würden alle Punkte, die gleichweit vom Nullpunkt entfernt sind, zu einer Klasse zusammengefasst, es sind dies offenbar Kugelflächen mit O als Mittelpunkt.
Drei Äquivalenzklassen sind hier eingezeichnet :
[Dateianhang nicht öffentlich]
Z.B. besteht die Äquivalenzklasse, in der B liegt, geschrieben [mm] \overline{B} [/mm] oder auch [B] aus allen Punkten, die in Relation R zu B stehen, also aus B, D und vielen weiteren; [mm] \overline{C} [/mm] ={C, E, F, ...} ; [mm] \overline{F} [/mm] = [mm] \overline{E}.
[/mm]
Diesen Sachverhalt sollst du im ersten Teil ganz allgemein beweisen :
Wenn zwei Äquivalenzklassen gleich sind, dann stehen ihre Namenspatrone in der Relation R zueinander und umgekehrt. Der Beweis erfordert also zwei Schritte, nämlich " => " und " <= " .
Wie du siehst, schneiden sich die einzelnen Kugeloberflächen nicht, der ganze Raum wird also in disjunkte (elementfremde) Teilmengen zerlegt. Eine solche Partition heißt Klasseneinteilung und ist typisch für jede Einteilung in Äquivalenzklassen: Entweder sind zwei Äquivalenzklassen gleich oder sie haben keine Elemente gemeinsam.
Das sollst du im zweiten Teil beweisen. Am besten geht das wahrscheinlich durch Kontraposition, denn die Aussage " [mm] \neg(xRy) [/mm] ist äquivalent ist zu [mm] \bar{x} \cap \bar{y} [/mm] = [mm] \emptyset [/mm] " ist gleichbedeutend mit " xRy [mm] \gdw \bar{x} \cap \bar{y} \not= \emptyset [/mm] ".
>
> Ich weiß nicht, wie ich es beweisen soll...
> ich hab zwar nun auf meinem Blatt stehen, dass es was mit
> Symmetrie zu tun hat, also:
> [mm]\forall[/mm] x,y [mm]\in[/mm] M: xRy [mm]\Rightarrow[/mm] yRx
>
Wahrscheinlich wirst du im Verlauf des Beweises alle drei Eigenschaften der Äquivalenzrelation (s.o.) benutzen müssen, unter anderem auch die Symmetrie, denn nur Äquivalenzrelationen haben die zu beweisende Eigenschaft.
> zudem halt, die Formel R [mm]\subset[/mm] M [mm]\times[/mm] M:
>
> [mm]\forall[/mm] (x,y) ((x [mm]\in[/mm] R) [mm]\wedge[/mm] (y [mm]\in[/mm] R) [mm]\Rightarrow[/mm] (x
> [mm]\in[/mm] M) [mm]\wedge[/mm] (y [mm]\in[/mm] M))
>
Diese "Formel" ist eine Definition, die wir selbstverständlich voraussetzen.
> und [mm]\bar{x}[/mm] = [mm]\bar{y}:[/mm]
> (y [mm]\in[/mm] M | yRx) [mm]\gdw[/mm] (x [mm]\in[/mm] M | xRy)
Hier ist offenbar Folgendes gemeint :
Die Äquivalenzklasse [mm] \bar{x} [/mm] besteht aus allen Elementen a von M, die in der Relarion R zu x stehen, also [mm] \bar{x} [/mm] = { a [mm] \in [/mm] M | aRx } nach Definition, deshalb
$ [mm] \bar{x} [/mm] = [mm] \bar{y} [/mm] $ [mm] \gdw [/mm] { a [mm] \in [/mm] M | aRx } = { b [mm] \in [/mm] M | bRy }
Ich habe mal die Buchstaben a und b eingeführt, um die Doppelbedeutung von x und y in deiner Zeile zu umgehen.
>
> wobei ich nicht weiß, ob die Angaben überhaupt stimmen,
> bin mir da leider nciht sicher.. Ich brauch grade echt
> denkanstöße bzw. Hilfe. wäre echt nett!
>
>
Gruß Sax.
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
Anhang Nr. 2 (Typ: png) [nicht öffentlich]
|
|
|
|
