Äquivalenzrelationen: Induktionsbeweis der Schnittmenge | Index

Neue Frage »

Tatze Auf diesen Beitrag antworten »
Äquivalenzrelationen: Induktionsbeweis der Schnittmenge | Index
Meine Frage:
Moin moin,

da ich immer mal meine Schwierigkeiten im Bereich der Mathematik habe durchstöbere ich des öfteren dieses Forum. Nun kam es wie es irgendwann kommen musste: Ich stecke in Schwierigkeiten und wende mich hoffnungsvoll an die Experten unter euch. :-)

Wir haben folgende Übungsaufgaben gestellt bekommen:

1).
Seien Ä1, Ä2, . . . Äquivalenzrelationen über A.
Zeigen Sie per Induktion: Für alle n 1 gilt:
Der Durchschnitt R := i=1..n Äi (Hoffe ist verständlich) ist eine Äquivalenzrelationen über A.

Zuvor sollte man zeigen dass die Schnittmenge zweier Äquivalenzrelationen auf A wieder eine Äquivalenzrelation ist. Dies habe ich gemacht indem ich Alles auf die Definition runter gebrochen habe. Bsp.:

Definition R1 und R2 sind reflexiv :


Definition Schnittmenge:

D.h.

Somit gilt:


Aber wie ich da nun weiter vorgehen soll erschließt sich mir nicht.
Reicht dies überhaupt? "Zeige" ist ja doch recht schwammig..


2).
Zu einer Äquivalenzrelation Ä über A bezeichnet man die Anzahl der Äquivalenzklassen als Index von Ä, notiert index(Ä). Seien Ä1 und Ä2 zwei Äquivalenzrelationen über A. Zeige: Wenn Ä1 ? Ä2, dann gilt index(Ä1) ? index(Ä2).


Ich habe nun einiges an Quellen durchgewälzt finde aber bisher keinen für mich schlüssigen Ansatz.
Gerade bei Aufgabe 2). mangelt es mir auch an vernünftigen Quellen.

Ich wäre über jeden Tipp dankbar!
MfG


Meine Ideen:
-
WebFritzi Auf diesen Beitrag antworten »

Fangen wir mal bei (1) an. Und diese Äs mag ich nicht. Lass uns doch stattdessen schreiben. Setze (das ist der Durchschnitt der ). Du sollst nun per Induktion zeigen, dass R eine Äquivalenzrelation ist. Man braucht hier eigentlich keine Induktion, aber ok. Wir induzieren über n. Für n=1 ist nach Voraussetzung eine Äquivalenzrelation. Also, done! Wir nehmen nun an, sei eine Äquivalenzrelation für ein . Zeige nun, dass eine Äquivalenzrelation ist. Das folgt eigentlich sofort aus dem, was du schon bewiesen hast, nämlich, dass der Schnitt zweier Äquivalenzrelationen wieder eine solche ist.
Tatze Auf diesen Beitrag antworten »

Moinsen, vielen Dank für die Mühe und Zeit! smile
Ich merk schon es hapert bei mir beim tieferen Verständnis für die Induktion. Das Gauß Beispiel kann ich mir ganz einfach herleiten aber hier hängt es.

Ich hätte folgendes gemacht:

(das +1 soll natürlich unten am r klemmen.)

Und da ich in der Aufgabe davor bewiesen habe dass die Schnittmenge wieder eine Äquivalenzrelation ist.. wäre hier Ende? Ohje, ich bin wirklich sehr verunsichert. unglücklich
WebFritzi Auf diesen Beitrag antworten »

Ja genau, so ist es aber. Denn wir haben ja im Induktionsschritt angenommen, dass der Schnitt bis r eine Äquirelation ist.

Das r+1 kriegst du in den Index, indem du geschweifte Klammern setzt: R_{r+1}.
Tatze Auf diesen Beitrag antworten »

Juhu smile

Das heißt wohl üben, üben und nochmal üben.
Ich kann mich nur noch einmal herzlich bei dir bedanken!

Vll sollte ich mir angewöhnen LaTeX zu benutzen.
Ist definitiv eine riesige Hilfe diese Probleme auf (virtuelles) Papier zu bringen.
Danke für den Hinweis.


Hättest du vll zu später Stunde noch einen kleinen Tipp für:

Zu einer Äquivalenzrelation R1 über M bezeichnet man die Anzahl der Äquivalenzklassen als Index von M, notiert index(R1). Seien R1 und R2 zwei Äquivalenzrelationen über A. Zeige: Wenn Ä1 Ä2, dann gilt index(R1) index(R2).

Habe gedacht die Definition der Teilmenge würde mich irgendwie weiterbringen.
Aber warum sollte R1 mehr Äquivalenzklassen haben als R2? Gleich viele würde ich ja noch verstehen... verwirrt
WebFritzi Auf diesen Beitrag antworten »

Beispiele erleichtern vieles. Betrachte die Äquirelationen

R1 = {(1,1),(2,2)} sowie R2 = {(1,1),(2,2),(1,2),(2,1)}.

Was sind nun die Klassen von R1 bzw. R2?
 
 
Tatze Auf diesen Beitrag antworten »

Das nennt man wahrlich Brett vorm Kopp. :Hammer:
Wenigstens bin ich da aber nicht allein - wir knobeln da zu dritt dran.

R1 = {(1,1),(2,2)}
[1], [2]

R2 = {(1,1),(2,2),(1,2),(2,1)}
[1]

Bei der Schreibweise bin ich mir nicht ganz sicher.
Irgendwie schreibt das jeder anders ( Buch, Internet, Prof..).

Aber wie wird das nun allgemein formuliert?
Ich glaub es wird zu spät für sowas. verwirrt
WebFritzi Auf diesen Beitrag antworten »

Zeige, dass jede R1-Äquivalenzklasse in einer R2-Äquivalenzklasse enthalten ist.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »