Die Mathe-Redaktion - 09.12.2019 13:41 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 848 Gäste und 15 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von mire2 StrgAltEntf
Logik, Mengen & Beweistechnik » Relationen und Abbildungen » Äquivalenzrelationen und Äquivalenzklassen
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Äquivalenzrelationen und Äquivalenzklassen
spniti
Junior Letzter Besuch: im letzten Monat
Dabei seit: 21.11.2019
Mitteilungen: 5
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-11-21 19:14


Hey :)

wir haben in der letzten Vorlesung über geordnete Paare, Korrespondenzen, Relationen, Äquivalenzrelationen und Äquivalenzklassen geredet. Geordnete Paare habe ich noch verstanden, Korrespondenzen habe ich glaube ich mittlerweile auch halbwegs verstanden aber den Rest, von dem leider auch unser aktuelles Übungsblatt handelt, kann ich noch nicht so ganz nachvollziehen.

Es wäre sehr nett, wenn mir jemand zu den Aufgaben sagen könnte was man machen muss und warum, denn aus den Folien, Internetseiten und Videos erschließt sich mir bisher nicht viel.

1)
Überprüfen Sie, ob die folgenden Relationen R auf der Menge M die in Definition 3.7(i)−(v) erklärten Eigenschaften (reflexiv, symmetrisch, antisymmetrisch, transitiv und total) besitzen:
a) M={1,2,3,4,5,6,7,8}⊂ℕ     R={(n,m)∈ MxM :(∃k∈ℤ)[n=2^k ⋅m]}

Ich habe verstanden, wieso genau gerade diese Eigenschaften gelten sollen, an so Beispielen wie "ist Anna in einer Klasse mit Bert und Bert in einer mit Charly, dann sind An∩a und Charly auch in einer Klasse" usw. die ich im Internet zu hauf gefunden habe. Ich verstehe nur nicht, wie man das auf Mengen oder besser so eine Aufgabe übertragen kann und wie ich überhaupt vorgehen soll.

2)
Bestimmen Sie alle Äquivalenzrelationen auf der Menge M für
a) M={a,b,c}

Diese Aufgabe habe ich glaube ich halbwegs verstanden. Man muss zuerst die Menge M in alle möglichen Äquivalenzklassen aufteilen. Das macht man meines Verständnisses nach so, dass man versucht die drei Elemente aus M so auf Teilmengen aufzuteilen s.d. jedes Element genau einmal in einer Menge vergeben ist. Das würde die Äquivalenzklassen :

1. {1,2,3}
2. {1}{2,3}
3. {2}{1,3}
4. {3}{1,2}
5. {1}{2}{3}

liefern. Wie man eine Äquivalenzklasse jetzt formal aufschreibt weiß ich leider auch nicht genau. Auf jeden Fall guckt man jetzt, wie die geordneten Paare der einzelnen Mengen jeweils aussehen würden und schreibt diese als Menge auf, was die Äquivalenzrelation der jeweiligen Äquivalenzklasse liefert :

1. R={(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)}
2. R={(1,1),(2,2),(2,3),(3,2),(3,3)}
3. R={(1,1),(1,3),(3,1),(3,3),(2,2)}
4. R={(1,1),(1,2),(2,1),(2,2),(3,3)}
5. R={(1,1),(2,2),(3,3)}

Wäre die Aufgabe damit erledigt oder müsste man die 5 Relationen irgendwie zu einer zusammenfassen bzw. ist es so überhaupt ansatzweise richtig ?

Ich bin für jede Hilfe wirklich SEHR dankbar ! :D

LG



  Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 2538
Aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-11-21 19:26


2019-11-21 19:14 - spniti im Themenstart schreibt:
1)
Überprüfen Sie, ob die folgenden Relationen R auf der Menge M die in Definition 3.7(i)−(v) erklärten Eigenschaften (reflexiv, symmetrisch, antisymmetrisch, transitiv und total) besitzen:
a) M={1,2,3,4,5,6,7,8}⊂ℕ     R={(n,m)∈ MxM :(∃k∈ℤ)[n=2^k ⋅m]}

Bestimme alle Paare $(n,m)$ mit $n,m\in M$, sodass eine ganze Zahl $k$ mit $n=2^k\cdot m$ existiert. Es gilt beispielsweise $(8,1)\in R$, da $8=2^3\cdot 1$ ist. Ist aber auch $(1,8)$ in $R$? Du stellst dir also die Frage, ob es eine ganze Zahl $k$ mit $1=2^k\cdot 8$ gibt.


2)
Bestimmen Sie alle Äquivalenzrelationen auf der Menge M für
a) M={a,b,c}

Diese Aufgabe habe ich glaube ich halbwegs verstanden. Man muss zuerst die Menge M in alle möglichen Äquivalenzklassen aufteilen. Das macht man meines Verständnisses nach so, dass man versucht die drei Elemente aus M so auf Teilmengen aufzuteilen s.d. jedes Element genau einmal in einer Menge vergeben ist. Das würde die Äquivalenzklassen :

1. {1,2,3}
2. {1}{2,3}
3. {2}{1,3}
4. {3}{1,2}
5. {1}{2}{3}

liefern. Wie man eine Äquivalenzklasse jetzt formal aufschreibt weiß ich leider auch nicht genau. Auf jeden Fall guckt man jetzt, wie die geordneten Paare der einzelnen Mengen jeweils aussehen würden und schreibt diese als Menge auf, was die Äquivalenzrelation der jeweiligen Äquivalenzklasse liefert :

1. R={(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)}
2. R={(1,1),(2,2),(2,3),(3,2),(3,3)}
3. R={(1,1),(1,3),(3,1),(3,3),(2,2)}
4. R={(1,1),(1,2),(2,1),(2,2),(3,3)}
5. R={(1,1),(2,2),(3,3)}

Wäre die Aufgabe damit erledigt oder müsste man die 5 Relationen irgendwie zu einer zusammenfassen bzw. ist es so überhaupt ansatzweise richtig ?
LG

Das sieht gut aus. Mehr musst du eigentlich nicht machen. Aber kannst du zeigen, dass jede dieser Klassen eine Äquivalenzrelation ist?



  Profil  Quote  Link auf diesen Beitrag Link
spniti
Junior Letzter Besuch: im letzten Monat
Dabei seit: 21.11.2019
Mitteilungen: 5
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2019-11-21 19:52


Also wäre für Aufgabe 1 eine Taktik alle geordneten Paare (n,m) der Menge M aufzuschreiben und zu gucken welche erstmal allgemein n=2^k ⋅m erfüllen und von da aus entscheiden, ob sie die anderen Eigenschaften erfüllen, weil in deinem Beispiel die (8,1) zwar die Bedingung erfüllt aber (1,8) nicht weshalb keine Symmetrie gegeben wäre, oder nicht ?
Wie würden denn Ausschlusskriterien für die anderen Bedingungen im Aufgabenkontext aussehen ? Bzw. ist das so ein richtiges Vorgehen, bei 64 geordneten Paaren kommt mir das nicht sehr effizient vor ^^'

Und es freut mich, dass meine Aufgabe 2 so richtig wäre :D
Aber leider weiß ich nicht, wie ich zeige, dass jede der Klassen auch eine Äquivalenzrelation ist :/

Aber danke für deine Hilfe schonmal !



  Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 2538
Aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2019-11-21 19:56


2019-11-21 19:52 - spniti in Beitrag No. 2 schreibt:
Also wäre für Aufgabe 1 eine Taktik alle geordneten Paare (n,m) der Menge M aufzuschreiben und zu gucken welche erstmal allgemein n=2^k ⋅m erfüllen und von da aus entscheiden, ob sie die anderen Eigenschaften erfüllen, weil in deinem Beispiel die (8,1) zwar die Bedingung erfüllt aber (1,8) nicht weshalb keine Symmetrie gegeben wäre, oder nicht ?
Wie würden denn Ausschlusskriterien für die anderen Bedingungen im Aufgabenkontext aussehen ? Bzw. ist das so ein richtiges Vorgehen, bei 64 geordneten Paaren kommt mir das nicht sehr effizient vor!

Das machst du vor allem, wenn du versuchst etwas zu widerlegen. Doch nochmal zurück zur Symmetrie: Wie weist du nach, dass es keine ganze Zahl $k$ mit $1=2^k\cdot 8$ gibt? Magst du es einmal vorrechnen?

Wie sieht es mit der Reflexivität aus? Ist $(3,3)\in R$?



  Profil  Quote  Link auf diesen Beitrag Link
spniti
Junior Letzter Besuch: im letzten Monat
Dabei seit: 21.11.2019
Mitteilungen: 5
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2019-11-21 20:19


Ich hab tatsächlich Z mit N verwechselt. Man muss ja 1=2^k * 8 umstellen indem man zunächst durch 8 teilt und dann den Logarithmus anwendet, was log_2(0,125)=k -> k=-3 was ja Element Z ist liefert.
Also es findet sich für (1,8) und (8,1) eine Zahl k, so dass die Bedingung erfüllt ist. Es gibt also Paare für die die Eigenschaft der Symmetrie auf der Relation gegeben ist.

Mit obiger vorgehensweise nur 3 statt 1 und 8 kann man auch zeigen dass mit k=0 (3,3) Element der Relation ist. Reflexivität ist auf der Relation also auch gegeben.

Kann man die Transitivität zeigen indem man sagt (1,8) (oben gezeigt k=3) und (8,2) (k=2) liegen auf R also muss (1,2) auf R liegen was für k=-1 der Fall sit ?

Und reicht es für jede Eigenschaft ein Beispiel zu finden ? Das wäre ja recht ausprobierlastig, also schätze ich einfach mal, dass die Frage obsolet ist und es eine schöne allgemeine Form gibt auf ein bündiges Ergebnis zu kommen :D



  Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 2538
Aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2019-11-21 20:40


Nein, es genügt nicht Beispiele zu finden.
Theoretisch würde es als Beweis zählen, wenn du bei allen 64 Paaren überprüfst, ob sie in $R$ enthalten sind und dann aufschreibst, welche Eigenschaften gelten.

Es geht aber auch anders. Bleiben wir mal bei der Reflexivität. Kannst du zeigen, dass für jede Zahl $n\in M$ eine ganze Zahl $k$ mit $n=2^k\cdot n$ finden? Diese muss gar nicht so explizit von $n$ abhängen.

Für die Symmetrie finde für jedes Paar $(n,m)\in M\times M$, sodass $n=2^k\cdot m$ für eine ganze Zahl $k$ gilt auch eine ganze Zahl $\ell$ mit $m=2^\ell\cdot n$.



  Profil  Quote  Link auf diesen Beitrag Link
spniti
Junior Letzter Besuch: im letzten Monat
Dabei seit: 21.11.2019
Mitteilungen: 5
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2019-11-21 21:02


Also bei der Reflexivität zeigt man, dass allgemein für beliebiges n aus M gilt n=2^k ⋅n was sich ja einfach zu log_2(1)=k also k=0 umschreiben lässt. Also für jedes Element n aus M gilt die Eigenschaft der Reflexivität mit k=0.

Bei der Symmetrie kann man ja sagen n=2^k ⋅m und m=2^l ⋅n mit k, l aus Z
Setzt man in die erste Gleichung statt m einfach 2^l ⋅n  ein erhält man
n=2^k * 2^l ⋅ n man teilt durch n und wendet ein Potenzgesetz an und erhält 1=2^l+k und da l und k aus Z sind ist ihre Summe auch in Z nennen wir sie mal s heißt 1=2^s was sich ja wieder zu log_2(1)=s -> s=0 umschreiben lässt. Also wenn l+k=0 <-> l=-k ist ist auch Symmetrie gegeben ?



  Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 2538
Aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2019-11-21 21:13


Ja, das stimmt alles, aber du musst nicht unbedingt den Logarithmus anwenden.

Für alle $n\in M$ gilt $(n,n)\in R$, da $n=2^0\cdot n$ für alle $n\in M$ gilt. Somit ist $R$ reflexiv.

Sei $(n,m)\in R$ beliebig, so gibt es ein $k\in \mathbb{Z}$ mit $n=2^k\cdot m$. Wenn wir beide Seiten mit $2^{-k}$ multiplizieren, folgt
\[2^{-k}\cdot n=2^{-k}\cdot 2^k\cdot m=2^{-k+k}\cdot m=2^0\cdot m=m.\] Es ist $m  =2^{-k}\cdot n$. Wir erhalten also $(m,n)\in R$. Da $(n,m)\in R$ beliebig gewählt war, ist $R$ symmetrisch.

Versuche nun selbst die Transitivität zu zeigen. Es ist nicht notwendig den Logarithmus zu bilden.



  Profil  Quote  Link auf diesen Beitrag Link
spniti
Junior Letzter Besuch: im letzten Monat
Dabei seit: 21.11.2019
Mitteilungen: 5
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2019-11-21 21:26


Also es soll gelten mit k,l aus Z
n=2^k ⋅m
m=2^l ⋅o
und das daraus n=2^d ⋅o mit d aus Z folgt sollen wir zeigen
setzt man 2^l ⋅o für m in n ein folgt :
n=2^k ⋅ 2^l ⋅o
-> n= 2^(k+l) ⋅o
heißt für d=k+l gilt auch die Transitivität auf der Relation. Transitivität, Reflexivität und Symmetrie sind also bewiesen fehlen noch antisymmetrie und total als Eigenschaft.

Dass die Relation total ist haben wir als
(∀ x,y ∈ M)[(x, y) ∈ R ∨ (y, x) ∈ R] ist wahr
definiert. Also wenn ein paar von (x,y) oder (x,y) auf R liegt ist das bewiesen ?



  Profil  Quote  Link auf diesen Beitrag Link
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
Er/sie war noch nicht wieder auf dem Matheplaneten
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 2538
Aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2019-11-22 09:22


Hi, dein Beweis zur Transitivität ist nicht vollständig. Was sind m,n und o?

Danach hast du gezeigt, dass R eine Äquivalenzrelation ist. Kannst du ihre Äquivalenzklassen aufschreiben? Davon gibt es nicht so viele. Danach klären wir, ob soe total ist. Möglicherweise kannst du es aus den Äquivalenzklassen sehen.



  Profil  Quote  Link auf diesen Beitrag Link
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]