Äquivalenzrelationen < Abbildungen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | A1.) Welche der folgenden Relationen sind Äquivalenzrelationen?
a.) Relation [mm] $\sim$ [/mm] auf [mm] $\mathbb{Z}$ [/mm] gegeben durch $a [mm] \sim [/mm] b [mm] \Leftrightarrow [/mm] a + b$ ist gerade
b.) Relation [mm] $\sim$ [/mm] auf [mm] $\mathbb{Z}$ [/mm] gegeben durch $a [mm] \sim [/mm] b [mm] \Leftrightarrow [/mm] a + b$ ist ungerade
c.) Relation [mm] $\sim_f$ [/mm] auf $M := [mm] \{r \in \mathbb{R} | r \geq 0\}$ [/mm] gegeben durch die Funktion $f : M [mm] \rightarrow [/mm] M: x [mm] \mapsto x^2$.
[/mm]
d.) Relation [mm] $\sim$ [/mm] auf [mm] $2^M$ [/mm] für eine Menge M gegeben durch $N [mm] \sim [/mm] M [mm] \Leftrightarrow [/mm] N [mm] \subseteq [/mm] M$. |
Hallo,
heute ein neues Problem zu den Äquivalenzrelationen. Habe mich an den neuen Übungsaufgaben versucht, aber leider scheitert es schon teilweise im Verständnis. Mir ist klar, dass eine Äq'relation reflexiv, symmetrisch und transitiv sein muss - z.B. x kongruent y mod n. Wie ist es aber in diesen Fällen, hier mal mein Ansatz:
a.) reflexiv: $a [mm] \sim [/mm] a [mm] \Leftrightarrow [/mm] a + a = 2k$
symmetrisch: $a [mm] \sim [/mm] b [mm] \Leftrightarrow [/mm] a + b = 2k [mm] \Leftrightarrow [/mm] b + a = 2k [mm] \Leftrightarrow [/mm] b [mm] \sim [/mm] a$ (Kommutativität der Addition)
transitiv: $a [mm] \sim [/mm] b [mm] \sim [/mm] c [mm] \Leftrightarrow [/mm] a + b = 2k [mm] \land [/mm] b + c = 2k'$ - hier weiß ich nicht wie ich das zeigen soll - sind überhaupt die anderen Sachen richtig gezeigt?
b.) analog zu a, bloß mit Ergebnis $2k + 1$
c.) Hier stehe ich auf dem Schlauch. Die Funktion ist bijektiv, macht das eine Äq'relation in diesem Fall aus?
d.) [mm] $2^M$ [/mm] ist die Potenzmenge von M, daher enthält sie auch alle Teilmengen von M, sodass $N [mm] \sim [/mm] M [mm] \Leftrightarrow [/mm] N [mm] \subseteq [/mm] M$ - allgemeingültig ist, da $N [mm] \in 2^M$ [/mm] und daher $N [mm] \subseteq [/mm] M$.
Wie ihr seht, fehlt mir zur Zeit so ein knackiges Beispiel an dem ich die Prozedur korrekt verstehen würde. Die [mm] $\leq$-Relation [/mm] ist ja z.B. keine Äq'relation, da sie nicht symmetrisch ist - wie sieht es bei obigen Relationen aus?
Grüße
Joe
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:34 Sa 03.11.2012 | | Autor: | Marcel |
Hallo,
> A1.) Welche der folgenden Relationen sind
> Äquivalenzrelationen?
>
> a.) Relation [mm]\sim[/mm] auf [mm]\mathbb{Z}[/mm] gegeben durch [mm]a \sim b \Leftrightarrow a + b[/mm]
> ist gerade
> b.) Relation [mm]\sim[/mm] auf [mm]\mathbb{Z}[/mm] gegeben durch [mm]a \sim b \Leftrightarrow a + b[/mm]
> ist ungerade
> c.) Relation [mm]\sim_f[/mm] auf [mm]M := \{r \in \mathbb{R} | r \geq 0\}[/mm]
> gegeben durch die Funktion [mm]f : M \rightarrow M: x \mapsto x^2[/mm].
>
> d.) Relation [mm]\sim[/mm] auf [mm]2^M[/mm] für eine Menge M gegeben durch [mm]N \sim M \Leftrightarrow N \subseteq M[/mm].
>
> Hallo,
>
> heute ein neues Problem zu den Äquivalenzrelationen. Habe
> mich an den neuen Übungsaufgaben versucht, aber leider
> scheitert es schon teilweise im Verständnis. Mir ist klar,
> dass eine Äq'relation reflexiv, symmetrisch und transitiv
> sein muss - z.B. x kongruent y mod n. Wie ist es aber in
> diesen Fällen, hier mal mein Ansatz:
>
> a.) reflexiv: [mm]a \sim a \Leftrightarrow a + a = 2k[/mm]
hier musst Du definitiv ergänzen, dass $a [mm] \sim [/mm] a$ FÜR ALLE $a [mm] \in \IZ$
[/mm]
eben gilt, weil für jedes $a [mm] \in \IZ$ [/mm] eben [mm] $a+a=2a\,$ [/mm] und $2a [mm] \in \IZ$
[/mm]
eine gerade Zahl ist!
>
> symmetrisch: [mm]a \sim b \Leftrightarrow a + b = 2k \Leftrightarrow b + a = 2k \Leftrightarrow b \sim a[/mm]
> (Kommutativität der Addition)
Auch hier sollte irgendwo stehen: Seien $a,b [mm] \in \IZ\,$ [/mm] und es gelte $a [mm] \sim b\,.$ [/mm]
Wegen $a [mm] \sim [/mm] b$ ist dann [mm] $a+b\,$ [/mm] eine gerade ganze Zahl. Damit ist
auch wegen [mm] $b+a=a+b\,$ [/mm] (Komm. der Add.) dann [mm] $b+a\,$ [/mm] eine gerade
ganze Zahl, also folgt $b [mm] \sim a\,.$ [/mm]
Wenn Du das machst wie oben, dann schreibe halt,
dass man [mm] $a+b=2k\,$ [/mm] mit einem $k [mm] \in \IZ$ [/mm] schreiben kann wegen $a [mm] \sim b\,,$
[/mm]
und erwähne, dass [mm] $2k\,$ [/mm] dann offensichtlich eine gerade Zahl ist.
> transitiv: [mm]a \sim b \sim c \Leftrightarrow a + b = 2k \land b + c = 2k'[/mm]
Auch hier wieder: $a,b,c [mm] \in \IZ$ [/mm] ... Wegen $a [mm] \sim [/mm] b$ existiert ein $k [mm] \in \IZ$
[/mm]
so, dass [mm] $a+b=2k\,.$ [/mm] Analog ex. $k' [mm] \in \IZ\,$ [/mm] so, dass ...
> - hier weiß ich nicht wie ich das zeigen soll - sind
> überhaupt die anderen Sachen richtig gezeigt?
Ja, im Wesentlichen schon. An der "Ausführlichkeit" solltest Du arbeiten!
Nun aber zur Trans.:
Hier hilft etwa
[mm] $$a+c=(a+b)+(c-b)=(a+b)+(b+c)-2b\,.$$
[/mm]
(Alternativ kann man auch zeigen: Wenn $b [mm] \sim c\,,$ [/mm] dann gilt auch
$-b [mm] \sim c\,.$ [/mm] Anders gesagt: Wenn [mm] $b+c\,$ [/mm] eine gerade Zahl ist, dann
muss auch [mm] $-b+c\,$ [/mm] gerade sein!)
> b.) analog zu a, bloß mit Ergebnis [mm]2k + 1[/mm]
Aber hier wird die Transitivität versagen:
Es ist $1 [mm] \sim [/mm] 2$ und $2 [mm] \sim 3\,,$ [/mm] aber gilt auch $1 [mm] \sim [/mm] 3$?
> c.) Hier stehe ich auf dem Schlauch. Die Funktion ist
> bijektiv, macht das eine Äq'relation in diesem Fall aus?
Wie habt ihr [mm] $\sim_f$ [/mm] definiert? $x [mm] \sim_f [/mm] y [mm] \gdw [/mm] f(x)=f(y)$ für $x,y [mm] \in D_f$? [/mm]
[mm] ($D_f=$Definitionsbereich [/mm] von [mm] $f\,.$)
[/mm]
> d.) [mm]2^M[/mm] ist die Potenzmenge von M, daher enthält sie auch
> alle Teilmengen von M, sodass [mm]N \sim M \Leftrightarrow N \subseteq M[/mm]
> - allgemeingültig ist, da [mm]N \in 2^M[/mm] und daher [mm]N \subseteq M[/mm].
??
Gehe lieber das durch, was Du durchzugehen hast: Für alle $A [mm] \subseteq [/mm] M$
gilt sicher $A [mm] \subseteq A\,,$ [/mm] also gilt für alle $A [mm] \in 2^M$ [/mm] auch $A [mm] \sim A\,.$
[/mm]
Und jetzt zur Symmetrie:
Es gelte $A [mm] \sim [/mm] B$ für $A,B [mm] \in 2^M\,,$ [/mm] also für $A,B [mm] \subseteq M\,.$
[/mm]
Das besagt nach Definition von [mm] $\sim\,,$ [/mm] dass dann $A [mm] \subseteq B\,$
[/mm]
gilt. Nun müßtest Du daraus folgern können, dass auch $B [mm] \subseteq [/mm] A$
gilt, wenn Du $B [mm] \sim [/mm] A$ zeigen willst.
I.A. wird Dir das nicht gelingen. Tipp: Betrachte etwa [mm] $M:=\{1\}\,,$
[/mm]
[mm] $A:=\emptyset$ [/mm] und [mm] $B:=\{1\}\,.$
[/mm]
Natürlich kannst Du auch ein "weniger triviales Beispiel" basteln...
Gruß,
Marcel
|
|
|
| |
|
Hallo Marcel,
ich danke dir für deine Antwort. Du hast recht meine Ausführungen sind nicht ausführlich genug, es handelt sich aber ohnehin nur um Multiple Choice Aufgaben und habe daher mich etwas kurzgefasst. Verstehe jetzt vor allem die Trans. dank dem Ansatz $-b [mm] \sim [/mm] c$ - logisch :)
Bei b muss man doch gar nicht erst zur Transitivität kommen (was natürlich einleuchtend ist), denn b kann doch gar nicht reflexiv sein, denn es gibt kein $a [mm] \in \mathbb{Z}$, [/mm] sodass $a [mm] \sim [/mm] a [mm] \Leftrightarrow [/mm] a + a = 2a [mm] \Rightarrow [/mm] 2a$ ist ungerade. 2a ist ja schließlich eine gerade Zahl.
Mal eine ganz "dumme" Zwischenfrage, wenn man beispielsweise von einer Relation [mm] $\sim$ [/mm] spricht auf [mm] $\mathbb{Q}$ [/mm] gegeben durch $a [mm] \sim [/mm] b [mm] \Leftrightarrow [/mm] a [mm] \geq [/mm] b$ dann sind mit $a [mm] \sim [/mm] b$ nur diejenigen a und b gemeint, die die zweite Bedingung (also $a [mm] \geq [/mm] b$) erfüllen können oder?
Zur c. Wir haben definiert: Ist $f : A [mm] \rightarrow [/mm] B$ eine Abbildung, so wird durch $a [mm] \sim_f [/mm] a' [mm] :\Leftrightarrow [/mm] f(a) = f(a')$ eine Äquivalenzrelation [mm] $\sim_f$ [/mm] auf A definiert. - Also im Grunde genauso wie du es aufgezeigt hast.
Sagt mir alleine diese Definition, dass es sich um eine Äq'relation handeln muss? Im Grunde nicht, denn die Quadrate von zwei reellen Zahlen größer als 0 sind auf jeden Fall unterschiedlich - Reflexivität wäre kein Problem zu zeigen.
d.) OK meine Definition war ein bisschen zu einfach :) Ich dachte das M in der Relation steht konstant für die oben definierte Menge M, deren Potenzmenge wir betrachten.
Man müsste also in der Symmetrie nachweisen können, dass wenn man zwei Teilmengen A,B aus der Potenzmenge nimmt, dass diese äquivalent sind, denn $A [mm] \subseteq [/mm] B [mm] \land [/mm] B [mm] \subseteq [/mm] A [mm] \Leftrightarrow [/mm] A = B$ (doppelte Inklusion). Das ist im Allgemeinen sicherlich nicht möglich, Gegenbsp: Sei $M := [mm] \{1,2,3\}$ [/mm] und [mm] $A:=\{1\}$, [/mm] $B := [mm] \{1,2\}$, [/mm] so gilt $A,B [mm] \in 2^M$, [/mm] $A [mm] \subseteq [/mm] B$, aber keinesfalls $B [mm] \subseteq [/mm] A$.
Grüße
Joe
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:56 Sa 03.11.2012 | | Autor: | tobit09 |
Hallo JoeSunnex,
> Bei b muss man doch gar nicht erst zur Transitivität
> kommen (was natürlich einleuchtend ist), denn b kann doch
> gar nicht reflexiv sein,
Genau.
> denn es gibt kein [mm]a \in \mathbb{Z}[/mm],
> sodass [mm]a \sim a \Leftrightarrow a + a = 2a \Rightarrow 2a[/mm]
> ist ungerade. 2a ist ja schließlich eine gerade Zahl.
Eine Spitzfindigkeit: Wenn [mm] $\sim$ [/mm] eine Relation auf [mm] $\emptyset$ [/mm] ist, so ist [mm] $\sim$ [/mm] reflexiv, obwohl es kein [mm] $a\in\emptyset$ [/mm] mit [mm] $a\sim [/mm] a$ gibt.
Es genügt also i.A. nicht, zu zeigen, dass KEIN a zu sich selbst in Relation steht; zu zeigen ist vielmehr, dass MINDESTENS EIN a NICHT zu sich selbst in Relation steht.
Schreibe also einfach z.B.: 1+1=2 ist keine ungerade Zahl, also gilt nicht [mm] $1\sim [/mm] 1$, also ist die Relation nicht reflexiv.
> Mal eine ganz "dumme" Zwischenfrage, wenn man
> beispielsweise von einer Relation [mm]\sim[/mm] spricht auf
> [mm]\mathbb{Q}[/mm] gegeben durch [mm]a \sim b \Leftrightarrow a \geq b[/mm]
> dann sind mit [mm]a \sim b[/mm] nur diejenigen a und b gemeint, die
> die zweite Bedingung (also [mm]a \geq b[/mm]) erfüllen können
> oder?
Mit [mm] $a\sim [/mm] b$ meint man dann genau die Aussage [mm] $a\ge [/mm] b$.
> Zur c. Wir haben definiert: Ist [mm]f : A \rightarrow B[/mm] eine
> Abbildung, so wird durch [mm]a \sim_f a' :\Leftrightarrow f(a) = f(a')[/mm]
> eine Äquivalenzrelation [mm]\sim_f[/mm] auf A definiert. - Also im
> Grunde genauso wie du es aufgezeigt hast.
> Sagt mir alleine diese Definition, dass es sich um eine
> Äq'relation handeln muss? Im Grunde nicht, denn die
> Quadrate von zwei reellen Zahlen größer als 0 sind auf
> jeden Fall unterschiedlich - Reflexivität wäre kein
> Problem zu zeigen.
Auch die Symmetrie und Transitivität kriegst du bestimmt gezeigt!
> d.) OK meine Definition war ein bisschen zu einfach :) Ich
> dachte das M in der Relation steht konstant für die oben
> definierte Menge M, deren Potenzmenge wir betrachten.
Da war auch ein Fehler in der Aufgabenstellung. Aber sicherlich ist die Aufgabe so gemeint, wie Marcel sie interpretiert hat.
> Man müsste also in der Symmetrie nachweisen können, dass
> wenn man zwei Teilmengen A,B aus der Potenzmenge nimmt,
> dass diese äquivalent sind, denn [mm]A \subseteq B \land B \subseteq A \Leftrightarrow A = B[/mm]
> (doppelte Inklusion). Das ist im Allgemeinen sicherlich
> nicht möglich, Gegenbsp: Sei [mm]M := \{1,2,3\}[/mm] und [mm]A:=\{1\}[/mm],
> [mm]B := \{1,2\}[/mm], so gilt [mm]A,B \in 2^M[/mm], [mm]A \subseteq B[/mm], aber
> keinesfalls [mm]B \subseteq A[/mm].
![[ok]](/images/smileys/ok.gif "[ok]") Genau. Nur im Falle [mm] $M=\emptyset$ [/mm] liegt eine Äquivalenzrelation vor.
Viele Grüße
Tobias
|
|
|
| |
|
Hallo Tobias,
danke für deine Antwort, also reicht es aus bei einer nicht zutreffenden Aussage einfach ein Gegenbeispiel zu formulieren.
zu c.) Reflexivität: [mm] $\forall [/mm] a [mm] \in [/mm] M: a [mm] \sim_f [/mm] a [mm] \Leftrightarrow [/mm] f(a) = f(a)$
Symmetrie: $a,b [mm] \in [/mm] M: a [mm] \sim_f [/mm] b [mm] \Leftrightarrow [/mm] f(a) = f(b) [mm] \Leftrightarrow [/mm] f(b) = f(a) [mm] \Leftrightarrow [/mm] b [mm] \sim_f [/mm] a$ - meiner Meinung widerspricht das doch der bijektiven Natur des Definitions- und Zielbereichs. Denn hier wird ausgesagt, dass zwei verschiedene Werte (a und b sind verschieden nehme ich an) das gleiche Bild unter f haben.
Transitivität: $a,b,c [mm] \in [/mm] M: a [mm] \sim_f [/mm] b [mm] \sim_f [/mm] c [mm] \Leftrightarrow [/mm] f(a) = f(b) [mm] \land [/mm] f(b) = f(c) [mm] \Rightarrow [/mm] f(a) = f(c)$. Das passt zwar auch, aber widerspricht ebenfalls der Bijektivität der Funktion oder überlese ich etwas?
Grüße
Joe
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:46 Sa 03.11.2012 | | Autor: | JoeSunnex |
Danke Tobias, so simpel ist das :) Meine Güte, ich dachte, es wäre auf der Bijektion unmöglich - naja.
Grüße
Joe
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:42 Sa 03.11.2012 | | Autor: | Marcel |
Hallo,
> Hallo Marcel,
>
> ich danke dir für deine Antwort. Du hast recht meine
> Ausführungen sind nicht ausführlich genug, es handelt
> sich aber ohnehin nur um Multiple Choice Aufgaben und habe
> daher mich etwas kurzgefasst. Verstehe jetzt vor allem die
> Trans. dank dem Ansatz [mm]-b \sim c[/mm] - logisch :)
>
> Bei b muss man doch gar nicht erst zur Transitivität
> kommen (was natürlich einleuchtend ist), denn b kann doch
> gar nicht reflexiv sein, denn es gibt kein [mm]a \in \mathbb{Z}[/mm],
> sodass [mm]a \sim a \Leftrightarrow a + a = 2a \Rightarrow 2a[/mm]
> ist ungerade. 2a ist ja schließlich eine gerade Zahl.
da hast Du natürlich auch Recht, aber ich habe ja auch nicht gesagt, dass
man nicht auch anders begründen kann, dass das keine ÄR ist 
P.S. Tobi hat das gut ergänzt, dass Du bei der Nichtreflexivität "a bissl
mehr" zeigen solltest.
Gruß,
Marcel
|
|
|
|
