Relationen < Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:06 Sa 23.01.2010 | | Autor: | a_la_fin |
| Aufgabe | | Es sei X:= {1,2}. Wie viele a) reflexive b) symmetrische c) anti-symmetrische und d) transitive Relationen gibt es auf dieser Menge? |
Hallo zusammen,
ich habe leider unerwartet große bzw. hartnäckige Probleme bei dieser eigentlich einfachen Aufgabe. Da das nun scho sooo lange her ist, dass wie das durchgenommen haben und ich in meinen Aufzeichnungen von damals nur die Definition von einer Relation bzw. reflexiv usw. gefunden habe, habe ich noch starke grundlegende Verständnisschwierigkeiten :-(. Diese möchte ich im Folgenden darlegen^^:
Mir ist klar, dass eine Relation auf nur einer Menge das Gleiche ist wie ein gerichteter Graph auf dieser Menge, das heißt alle Teilmengen die höchsten 2 Elemente haben können, nämlich eines aus jeder der beiden (hier natürlich gleichen!!!) Mengen. Was die einzelnen Eigenschaften (reflexiv usw.) bedeuten, ist mir eigentlich auch klar. Jedoch tun sich mir Folgende Fragen auf:
Ich dachte, die leere Menge muss immer in JEDER Menge mit drin sein, auch wenn die hier nicht angegeben ist. Also kann ich erstmal schreiben: X = {1,2} = [mm] {\emptyset,1,2} [/mm] (oder?). Dann ist die Relation auf X eine Teilmenge von X [mm] \times [/mm] X = [mm] {\emptyset,1,2} \times {\emptyset,1,2}. [/mm] Zur Besseren Übersicht füge ich Indexe A und B an: [mm] {\emptyset,1,2}_A \times {\emptyset,1,2}_B.
[/mm]
So. Ich wollte diese Aufgabe tatsächlich anhand von Beispielen bearbeiten, also tatsächlich die einzelnen Teilmengen alle aufschreiben, weil ich denke, dass das bei dieser kleinen Anzahl an Elementen doch möglich sein müsste (?) und aus Verständnisgründen.
Jetzt war ich mir nicht sicher, ob die Reihenfolge der Elemente in den Relationen wichtig ist? Wenn nicht müssten ja alle Relationen wie (1,1) doppelt vorkommen?? Aber das glaube ich nicht. Also wäre meine Lösung für ALLE Relationen auf X (hier nicht gefragt):
[mm] (\emptyset), (\emptyset,1), (\emptyset,2), [/mm] (1,1), [mm] (1,\emptyset), (2,\emptyset), [/mm] (1), (2), (2,2). Das sind aber nur 9. Es muss aber insgesamt 16 (nach der Formel |R| = [mm] 2^{|X|^2} [/mm] = [mm] 2^4 [/mm] = 16. Hier habe ich also die leere Menge NICHT als Element mitgezählt (warum nicht?), denn wenn ich es machen würde, würden sich ja [mm] 2^9 [/mm] = 512 (!!!!) Relationen auf {1,2} ergeben, und die krieg ich ja erstrecht nicht hin.
Wenn man die doppelten noch mitzählt (also jeweils: [mm] (1_A, 1_B) [/mm] usw. ergeben sich aber 2*9 = 18 Relationen, da ich ja dann ALLE doppelt habe (also auch 1-elementige, nämlich: [mm] {1_A}, {1_B} [/mm] usw.), das wären also 2 zuviel?? Das verwirrt mich jetzt doch sehr! :-(.
Dann weiter mit den Eigenschaften. Ich weiß, wann eine MENGE Reflexiv ist, nämlich, wenn für alle Elemente dieser Menge gilt, dass alle Paare, in denen das jeweilige Element doppelt vorkommt, auch Teilmenge der Menge sind. Hier wären diese Teilmengen ja die gesuchten Relationen. Aber wann ist denn jetzt eine von diesen Relationen reflexiv? Sind (das wäre jetzt meine Auffassung) also alle 1-Elementigen Relationen außer der leeren Menge, weil die als einzige in keinem Paar doppelt vorkommt (aha, jetzt habe ich den Fehler von oben gefunden! Und zwar sind es ja 2*9 - 2 (nämlich [mm] {\emptyset_B} [/mm] (ODER A), weil die leere Menge nur 1 Mal vorkommt und [mm] (\emptyset, \emptyset), [/mm] weil das auch nicht existiert) Relationen = 16 Relationen  (war ja aber garnicht gefragt).
Wo war ich stehengeblieben? Achso, ja, reflexive Relationen auf {1, 2} wären dann wohl: [mm] {1_A} [/mm] (weil (1,1) [mm] \in [/mm] X), [mm] {1_B} [/mm] (aus dem gleichen Grund), [mm] {2_A} [/mm] und [mm] {2_B} [/mm] = 4? Diese Antwort müsste (zumindest zahlenmäßig) stimmen, denn es gibt ja die Formel für die Anzahl der reflexiven Relationen auf einer endlichen Menge = [mm] 2^{|X|^2 - |X|} [/mm] = [mm] 2^2 [/mm] = 4.
Dann zu den symmetrischen, davon müsste es 8 Stück geben: ( [mm] \emptyset_A, 1_B), (1_A,\emptyset_B), (1_A, 1_B), (1_B, 1_A), (2_A, 2_B), (2_B, 2_A), (\emptyset_A, 2_B), (2_A, \emptyset_B). [/mm] Stimmt das so? Gibt es dazu auch eine allgemeine Formel?
Dann transitiv: Da ist die Definition (für eine transitive MENGE) ja: wenn aus (x, y) [mm] \in [/mm] X und (y, z) [mm] \in [/mm] X folgt: (x, z) [mm] \in [/mm] X. Okay, aber welche von den PAAREN sind denn dann reflexiv??? die (x,z)??? Das wäre dann also bei (1,2) (aus (0,1) und (1,2)), usw. usw. = bei allen außer bei den 1-elementigen (also 3) der Fall. [mm] \Rightarrow [/mm] es gibt 16-3 = 13 transitive Relationen?
Anti-symmetrisch sind doch dann nur die 1-elementigen und die doppelten?Also [mm] {\emptyset}, [/mm] {1}, {2}, [mm] (1_A, 1_B), (1_B, 1_A) [/mm] (wobei bei den doppelten die große Frage ist, ob [mm] 1_A [/mm] = [mm] 1_B [/mm] oder nicht?? falls nicht fallen die ja doch alle weg und es wären nur die 1-elementigen? Das kann aber nicht sein. Also nimmt man dann aus der Definition einer trasitiven MENGE: wenn (x,y) [mm] \in [/mm] X und (y,x) [mm] \in [/mm] X => x=y die beiden vorderen Paaren?? Das wären dann aber alle bis auf die 1-elemtigen also auch 13. Ich weiß jedoch, dass von der Menge der transitiven bzw. anti-symmetrsichen Menge eine 12 und eine 13 Elemente hat, also muss eine der beiden Mengen noch ein Element rausfallen (FALLS ich das bis dahin richtig hergeleitet habe natürlich nur!?), nur welches?
Und außerdem : gibt es für diese beiden letzten Eigenschaften auch so eine allgemeine Formel? Weil es ist ja gerade bei größen Mengen schon sehr anstrengend, alle Relationen einzeln aufzuzählen... 
Danke schomal fürs Verbessern und Tipps / Ratschläge / Hinweise zum Lösen solcher Aufgaben.
lG
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:44 So 24.01.2010 | | Autor: | Helbig |
Die leere Menge ist zwar Teilmenge jeder Menge aber nicht Element jeder Menge!
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:24 So 24.01.2010 | | Autor: | a_la_fin |
Okay, das heißt also, dass alle Elemente, in der die leere Menge vorkommt, wegfallen, außer die leere Menge selbst, weil das ist doch eine echte Teilmenge? Also auch eine Relation? Dann finde ich aber insgesamt nur 13 Relationen (nämlich [mm] (\emptyset), [/mm] (1), (2), (1,1), (2,2), (1,2) und (2,1), davon die letzten 6 doppelt) auf diese Menge ( X={1,2}). Stimmt das so? Aber dann fehlen ja trotzdem noch 3...!?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:58 So 24.01.2010 | | Autor: | Cybrina |
Hm. Also eine Relation auf X ist keine Teilmenge von X, sondern eine Menge von geordneten Paaren, deren Elemente aus X sind, also
[mm] R=\{(a_1,b_1),(a_2,b_2),...\} [/mm] mit [mm] a_i,b_i\in [/mm] X
Bei dir kommen als Paare genau (1,1);(1,2);(2,1);(2,2) in Frage. Jedes dieser Paare kann entweder in R enthalten sein oder eben nicht. D.h. für eine Relation gibt es 2*2*2*2=16 Möglichkeiten.
Grüße
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:54 So 24.01.2010 | | Autor: | a_la_fin |
Aaahhhh JETZT hats "Klick" gemacht!! Laut Definition ist eine Relation auf X ja eine Teilmenge R [mm] \subseteq [/mm] X [mm] \times [/mm] X also eine Teilmenge von der POTENZMENGE von X, nicht von der Menge selber! (schon erstaunlich, wie arg man manchmal auf der Leitung steht!! :-( )
ich glaub, jetz kann ich die Aufgabe lösen... vielen Dank
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:14 So 24.01.2010 | | Autor: | Helbig |
Die leere Menge ist tatsāchlich eine Relation, denn sie ist Teilmenge von [mm] $M\times [/mm] M$.
Du mußt alle Teilmengen von [mm] $M\times [/mm] M$ aufschreiben. Da $M$ zwei Elemente hat, hat [mm] $M\times [/mm] M$ vier Elemente, und die Potenzmenge von [mm] $M\times [/mm] M$ hat dann [mm] $2^4$ [/mm] Elemente.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:14 So 24.01.2010 | | Autor: | a_la_fin |
Okay, ich fasse nochmal zusammen: Die Potenzmenge von X = {1,2} hat 16 Elemente, nämlich (1,1), (1,2), (2,1) usw. , wobei die leere Menge da NICHT enthalten ist, da sie kein Element ist. Sie ist aber sehr wohl eine Relation auf der Menge {1,2}.
Das heißt Relationen auf X sind alle Teilmengen von der Potenzmenge mit entweder 1, 2, 3 oder 4 Elementen, wobei die Reihenfolge der Elemente (Paare) in den Teilmengen egal ist (bedeutet: die Relation [mm] R_1:= [/mm] {(1,1), 1,2)} ist die gleiche (?) wie die Relation [mm] R_2:={(1,2), (1,1)}, [/mm] wird nur EIN Mal gezählt, die Reihenfolge der Elemente (=Zahlen) in den Elementen (=Paaren) aber NICHT egal ist (heißt: das Paar (1,2) ist verschieden vom Paar (2,1) und wird doppelt gezählt (beide werden gezählt)). Dazu kommt als Relation noch die leere Menge als einzelne Teilmenge.
Wenn das so ist, muss es ja aber 17 Relationen (16 Paare aus der Potenzmenge + die leere Menge) geben?
Es ist egal, wie viele Elemente die Relation enthält, 1,2, 3 oder 4. Weiterhin ist die Reihen wie gesagt egal und deswegen können keine Paare doppelt vorkommen. Dann gibt es vier 1- und sechs 2- elementige! Eine 4-elementige und fünf 3-elementige (ich habe alle aufgeschrieben und da 4+6+1+ 5 = 16 nehm ich mal an, die stimmen so )*
Dann bleibt aber noch meine Frage wegen den Eigenschaften zu beantworten.
Die leere Menge (bzw.: die Relation R_17:= "leere Menge") kann weder reflexiv noch symmetrisch noch transitiv oder anti-symmetrisch sein.
Von den vier 1-elementigen Relationen (nämlich die schon oft genug aufgezählten Teilmengen von {1,2} [mm] \times [/mm] {1,2}) können auch keine von diesen Eigenschaften haben, da sie ja jeweils nur ein Paar enthalten. Bleiben also noch 13.
Von diesen 13 gibt es sechs 2-elementige von denen ist genau eine symmetrisch, nämlich {(1,2), (2,1)} Außerdem ist 4 elementige symmetrisch. Sowie von den 3elementigen die beiden Relationen {(2,2), (1,2), (2,1)} und {(1,1), (1,2), (2,1)}. Macht insgesamt 4. Es muss doch aber 8 geben!!! ich bin gerade völlig am Verzweifeln!!! :-( (denn wenn die Reihenfolge doch nicht egal wäre, würde es ja noch viel mehr geben! (nämlich zwei 2elementige, 4! = 24 4elementige und 3! = 6, also insgesamt 32!!)
Reflexiv ist doch aber (nach meiner Auffassung der Definition und euren Hinweisen) GAR KEINE???!!!! Denn es müsste ja dann jeweils für ALLE Elemente gelten, dass sie doppelt vorkommen müssten (wobei das aber eh kein „Paar“ wäre!!).
Antisymmetrisch wären dann 13 (17-4).
Bei transitiv komme ich auf genau 8 (allerdings nur mit mühsam einzeln überprüfen...). Und auch das ist doch falsch! (oder??)
* das scheint dann wohl auch Zufall zu sein... :-(
Kann mir bitte jemand weiterhelfen, ich weiß einfach nicht wo ich immer dran scheitere bei den Relationen....
lG
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:17 Mo 25.01.2010 | | Autor: | Helbig |
> Okay, ich fasse nochmal zusammen: Die Potenzmenge von X =
> {1,2} hat 16 Elemente, nämlich (1,1), (1,2), (2,1) usw. ,
Nein! Die Potenzmenge von X interessiert hier gar nicht! Sie hat übrigens nur vier Elemente, da es genau vier Teilmengen von X gibt, nāmlich die leere Menge, die Menge mit dem Element 1, die Menge mit dem Element 2 und die Menge X.
Die Relationen auf X sind aber genau die Teilmengen von [mm] $X\times [/mm] X$. Die Elemente einer Relation sind Paare. Auch hier taucht wieder die leere Menge auf. Da sie keine Elemente hat, sind alle ihre Elemente Paare! Jedenfalls ist dies so in der Logik der Mathematik vereinbart. Die leere Menge ist nicht reflexiv, da $(1, 1)$ kein Element der leeren Menge ist. Sie ist aber symmetrisch, antisymetrisch und transitiv. Die Symmetrie bedeutet ja: " Wenn $(a, b) [mm] \in [/mm] R$ dann ist auch $(b, a) [mm] \in [/mm] R$". Nun ist die Praemisse bei leerem R immer falsch, die ganze Aussage also richtig. Ähnlich sieht man die Antisymmetrie und Transitivitāt der leeren Menge ein. Als nāchstes betrachte die einelementigen Teilmengen von [mm] $X\times [/mm] X$: Dies sind die vier Relationen {(1, 1)}, {(1, 2)}, {(2, 1)}, {(2, 2)}. Keine dieser Relationen ist reflexiv, da (2, 2) in den ersten drei und (1,1) in der letzten nicht enthalten ist. Symmetrisch sind nur die erste und letzte, antisymmetrisch nur die zweite und dritte, transitiv alle vier.
Zum Abschluß noch eine Relation mit drei Elementen, sagen wir $R = [mm] \{(1, 1), (2, 2), (1,2)\}$. [/mm] R ist reflexiv, nicht symmetrisch, aber antisymmetrisch und transitiv.
Du mußt jetzt noch die zweielementigen Teilmengen von [mm] $X\times [/mm] X$ untersuchen. Dies sind $4 [mm] \choose [/mm] 2$, die dreielementigen Teilmengen, dies sind $4 [mm] \choose [/mm] 3$ und die ganze Menge, also $R = [mm] X\times [/mm] X$.
> wobei die leere Menge da NICHT enthalten ist, da sie kein
> Element ist. Sie ist aber sehr wohl eine Relation auf der
> Menge {1,2}.
Genau, und zwar weil die leere Menge eine Teilmenge von $X [mm] \times [/mm] X$ ist.
> Das heißt Relationen auf X sind alle Teilmengen von der
> Potenzmenge mit entweder 1, 2, 3 oder 4 Elementen, wobei
Nein. Alle Teilmengen von [mm] $X\times [/mm] X$.
> die Reihenfolge der Elemente (Paare) in den Teilmengen egal
> ist (bedeutet: die Relation [mm]R_1:=[/mm] {(1,1), 1,2)} ist die
> gleiche (?) wie die Relation [mm]R_2:={(1,2), (1,1)},[/mm] wird nur
Ja! Weil [mm] $\{(1,2), (1, 1)\}$ [/mm] und [mm] $\{(1, 1), (1, 2)\}$ [/mm] dieselben Elemente enthält.
> EIN Mal gezählt, die Reihenfolge der Elemente (=Zahlen) in
> den Elementen (=Paaren) aber NICHT egal ist (heißt: das
> Paar (1,2) ist verschieden vom Paar (2,1) und wird doppelt
> gezählt (beide werden gezählt)). Dazu kommt als Relation
Genau. Bei einem Paar kommt es auf die Reihenfolge an, bei einer Menge nicht.
> noch die leere Menge als einzelne Teilmenge.
> Wenn das so ist, muss es ja aber 17 Relationen (16 Paare
> aus der Potenzmenge + die leere Menge) geben?
Nein, nein. Sondern jede der 16 Teilmengen von [mm] $X\times [/mm] X$ ist eine Relation.
>
> Es ist egal, wie viele Elemente die Relation enthält, 1,2,
> 3 oder 4.
Eine Relation auf X kann 0, 1, 2, 3 oder 4 Paare enthalten.
> deswegen können keine Paare doppelt vorkommen. Dann gibt
> es vier 1- und sechs 2- elementige! Eine 4-elementige und
> fünf 3-elementige (ich habe alle aufgeschrieben und da
> 4+6+1+ 5 = 16 nehm ich mal an, die stimmen so )*
Nein. $4 [mm] \choose [/mm] 0$ nullelementige, $4 [mm] \choose [/mm] 1$ einelementige, $4 [mm] \choose [/mm] 2$ zweielementige,$4 [mm] \choose [/mm] 3$ dreielementige und $4 [mm] \choose [/mm] 4$ vierelementige. So ergibt sich $1 + 4 + 6 + 4 + 1 = 16$.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:56 Mo 25.01.2010 | | Autor: | a_la_fin |
> > Okay, ich fasse nochmal zusammen: Die Potenzmenge von X =
> > {1,2} hat 16 Elemente, nämlich (1,1), (1,2), (2,1) usw. ,
>
> Nein! Die Potenzmenge von X interessiert hier gar nicht!
> Sie hat übrigens nur vier Elemente, da es genau vier
> Teilmengen von X gibt, nāmlich die leere Menge, die Menge
> mit dem Element 1, die Menge mit dem Element 2 und die
> Menge X.
>
Okay, da habe ich was verwechselt. Ich dachte, die Potenzmenge sei X [mm] \times [/mm] X...
> Die Relationen auf X sind aber genau die Teilmengen von
> [mm]X\times X[/mm]. Die Elemente einer Relation sind Paare.
dann hatte ich das schon richtig erfasst.
> Auch hier taucht wieder die leere Menge auf.
>"Da sie keine Elemente hat, sind alle ihre Elemente Paare!"
OKAY. Alles klar. ^^
> Jedenfalls ist
> dies so in der Logik der Mathematik vereinbart. Die leere
> Menge ist nicht reflexiv, da [mm](1, 1)[/mm] kein Element der
> leeren Menge ist.
Die Begründung ist für mich jetz iwie überhaupt nicht logisch, denn nur die 1 ist doch auch kein Element von der leeren Menge!?
> Sie ist aber symmetrisch, antisymetrisch
> und transitiv. Die Symmetrie bedeutet ja: " Wenn [mm](a, b) \in R[/mm]
> dann ist auch [mm](b, a) \in R[/mm]". Nun ist die Praemisse bei
> leerem R immer falsch, die ganze Aussage also richtig.
Das wäre doch aber bei reflexiv dann genauso der Fall...? Dass die Prämisse falsch ist? Und außerdem kann ich die Konklusion "Prämisse immer falsch [mm] \Rightarrow [/mm] Aussage richtig" nicht ganz nachvollziehen...
> Ähnlich sieht man die Antisymmetrie und Transitivitāt der
> leeren Menge ein.
...oder auch nicht ^^. Aber ich schätze das muss man notfalls einfach als gegeben hinnehmen.
> Als nāchstes betrachte die
> einelementigen Teilmengen von [mm]X\times X[/mm]: Dies sind die vier
> Relationen {(1, 1)}, {(1, 2)}, {(2, 1)}, {(2, 2)}.
Ja , das hatte ich ja so.
> Keine dieser Relationen ist reflexiv, da (2, 2) in den ersten
> drei und (1,1) in der letzten nicht enthalten ist.
Moment. Da hatte ich ja wieder etwas falsch gedeutet (bzw. aus der Not heraus "geraten" ehrlich gesagt, da ich eben nicht wusste, wie ich die Definitionen der Eigenschaften hier anwenden kann).
Also, wenn ich das jetzt (endlich) richtig verstanden habe, betrachte ich also, wenn ich die Eigenschaft EINER Relation prüfe (man sagt ja: "die Relation, also z.B. (1,1) ist reflexiv", oder nicht??) alle Relationen, die genauso viele Elemente enthalten bzw. die Menge dieser Relationen, also z.B. bei {(1,1)} die Menge aller 1-elementigen??
Sorry, da stehe ich jetz (immer noch!!!) völlig aufm Schlauch. Ich verstehe den letzten Satz leider nicht. Denn wenn (2,2) nicht in den ersten dreien enthalten ist (logisch, so hatte ich mir das ja auch gedacht!) dann ist doch aber (1,1) auch nur in der ersten (also in {(1,1)} enthalten. Tut mir leid, ich sehe einfach nicht, warum (1,1) und {(1,2)} und {(2,1)} enthalten sein soll, (2,2) aber NICHT.
Oder hab ich da irgendwas ganz falsch gelesen?
> Symmetrisch sind nur die erste und letzte,
jup, nachvollziehbar! ^^
> antisymmetrisch nur die zweite und dritte
dito!
> transitiv alle vier.
ööhm...ja, stimmt, wenn man wie grade (von mir) gesagt für jede n-elementige Relation die Menge aller n-elementigen Relationen [mm] (:=M_n) [/mm] hernimmt, jeweils 2 davon anguckt (wobei man alle Kombinationen durchmacht) und diese mit (x,y) und (x,z) gleichsetzt und dann schaut, ob (x,z) auch in dieser Menge aller n-elementigen Relationen enthalten ist.
Für n=1 haben wir also: (1,1) und (1,2) [mm] \in M_n \Rightarrow [/mm] (1,2) [mm] \in M_n, [/mm] (1,1) und (2,2) [mm] \in M_n \Rightarrow [/mm] (1,2) [mm] \in M_n [/mm] usw. [mm] \Rightarrow [/mm] richtig für alle Kombis.
Folgert man dann jeweils, dass das Succedens transitiv ist? Oder die beiden Antecedens? Oder hat das doch was mit den Anzahl von Kominationen, die klappen, zu tun?? DAS war mein Verständnisproblem!!
>
> Zum Abschluß noch eine Relation mit drei Elementen, sagen
> wir [mm]R = \{(1, 1), (2, 2), (1,2)\}[/mm]. R ist reflexiv, nicht
> symmetrisch, aber antisymmetrisch und transitiv.
>
> Du mußt jetzt noch die zweielementigen Teilmengen von
> [mm]X\times X[/mm] untersuchen. Dies sind [mm]4 \choose 2[/mm], die
> dreielementigen Teilmengen, dies sind [mm]4 \choose 3[/mm] und die
> ganze Menge, also [mm]R = X\times X[/mm].
> > wobei die leere Menge
> da NICHT enthalten ist, da sie kein
> > Element ist. Sie ist aber sehr wohl eine Relation auf der
> > Menge {1,2}.
>
> Genau, und zwar weil die leere Menge eine Teilmenge von [mm]X \times X[/mm]
> ist.
>
> > Das heißt Relationen auf X sind alle Teilmengen von der
> > Potenzmenge mit entweder 1, 2, 3 oder 4 Elementen, wobei
>
> Nein. Alle Teilmengen von [mm]X\times X[/mm].
>
> > die Reihenfolge der Elemente (Paare) in den Teilmengen egal
> > ist (bedeutet: die Relation [mm]R_1:=[/mm] {(1,1), 1,2)} ist die
> > gleiche (?) wie die Relation [mm]R_2:={(1,2), (1,1)},[/mm] wird nur
>
> Ja! Weil [mm]\{(1,2), (1, 1)\}[/mm] und [mm]\{(1, 1), (1, 2)\}[/mm] dieselben
> Elemente enthält.
>
> > EIN Mal gezählt, die Reihenfolge der Elemente (=Zahlen) in
> > den Elementen (=Paaren) aber NICHT egal ist (heißt: das
> > Paar (1,2) ist verschieden vom Paar (2,1) und wird doppelt
> > gezählt (beide werden gezählt)). Dazu kommt als Relation
>
> Genau. Bei einem Paar kommt es auf die Reihenfolge an, bei
> einer Menge nicht.
>
> > noch die leere Menge als einzelne Teilmenge.
> > Wenn das so ist, muss es ja aber 17 Relationen (16
> Paare
> > aus der Potenzmenge + die leere Menge) geben?
>
> Nein, nein. Sondern jede der 16 Teilmengen von [mm]X\times X[/mm]
> ist eine Relation.
>
> >
> > Es ist egal, wie viele Elemente die Relation enthält, 1,2,
> > 3 oder 4.
>
> Eine Relation auf X kann 0, 1, 2, 3 oder 4 Paare
> enthalten.
>
> > deswegen können keine Paare doppelt vorkommen. Dann gibt
> > es vier 1- und sechs 2- elementige! Eine 4-elementige und
> > fünf 3-elementige (ich habe alle aufgeschrieben und da
> > 4+6+1+ 5 = 16 nehm ich mal an, die stimmen so )*
>
> Nein. [mm]4 \choose 0[/mm] nullelementige,
nämlich die leere Menge
> [mm]4 \choose 1[/mm] einelementige
klar
> [mm]4 \choose 2[/mm] zweielementige,
(=6) ja, hatte ich auch so
> [mm]4 \choose 3[/mm] dreielementige
(=4), ja, da hatte ich eine aus Versehen doppelt gezählt...
> und [mm]4 \choose 4[/mm] vierelementige.
trivial, die mit allen
>So ergibt sich [mm]1 + 4 + 6 + 4 + 1 = 16[/mm].
>
>
So, ich muss mich vielmals entschuldigen, dass ich (teilweise, oft auch gerade bei den "einfachen" Sachen) so schwer von Verstand (bzw. viel zu ungeduldig und/oder zu störrisch bin, um etwas nachzulesen, wo mir niemand was dazu erklären könnte, falls ich Fragen habe [mm] \Rightarrow [/mm] gut, dass es MatheRaum gibt! ) und immer so genau nachbohre. Aber ich bin halt so ich will immer ALLES ganz genau verstehen, bis ins letzte Detail, grade in Mathe find ich das wichtig und einfach irgendwelche Formeln auswendig lernen geht (in Mathe) GAR NICHT! Etwas gelernt zu haben ohne es verstanden zu haben macht für mich keinen Sinn.
lG
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:33 Mo 25.01.2010 | | Autor: | Helbig |
> > > Okay, ich fasse nochmal zusammen: Die Potenzmenge von X =
> > > {1,2} hat 16 Elemente, nämlich (1,1), (1,2), (2,1) usw. ,
> >
> > Nein! Die Potenzmenge von X interessiert hier gar nicht!
> > Sie hat übrigens nur vier Elemente, da es genau vier
> > Teilmengen von X gibt, nāmlich die leere Menge, die Menge
> > mit dem Element 1, die Menge mit dem Element 2 und die
> > Menge X.
> >
> Okay, da habe ich was verwechselt. Ich dachte, die
> Potenzmenge sei X [mm]\times[/mm] X...
Vergessen wir mal Potenzmenge. Dieser Begriff macht es hier komplizierter als nötig. Betrachten wir nur die beiden Mengen
$X = [mm] \{1, 2\}$ [/mm] und $X [mm] \times [/mm] X = [mm] \{(1, 1), (1, 2), (2, 1), (2, 2)\}$
[/mm]
Jede Relation auf $X$ ist nun eine Teilmenge von [mm] $X\times [/mm] X$.
>
> > Die Relationen auf X sind aber genau die Teilmengen von
> > [mm]X\times X[/mm]. Die Elemente einer Relation sind Paare.
>
> dann hatte ich das schon richtig erfasst.
>
> > Auch hier taucht wieder die leere Menge auf.
>
> >"Da sie keine Elemente hat, sind alle ihre Elemente
> Paare!"
>
> OKAY. Alles klar. ^^
>
> > Jedenfalls ist
> > dies so in der Logik der Mathematik vereinbart. Die leere
> > Menge ist nicht reflexiv, da [mm](1, 1)[/mm] kein Element der
> > leeren Menge ist.
>
> Die Begründung ist für mich jetz iwie überhaupt nicht
> logisch, denn nur die 1 ist doch auch kein Element von der
> leeren Menge!?
Richtig! Entscheidend ist aber daß $(1, 1)$ nicht in der leeren Relation enthalten ist.
Vielleicht hilft zum Verstāndnis eine andere Schreibweise: Statt $(a, b) [mm] \in [/mm] R$ schreibt man auch $a R b$. Wenn $R$ reflexiv ist, muß $a R a$ für $a = 1$ und für $a = 2$ gelten. Das heißt, es muß $(1, 1) [mm] \in [/mm] R$ und $(2, 2) [mm] \in [/mm] R$ gelten. Dies ist nicht der Fall, wenn $R$ leer ist. Also ist die leere Relation nicht reflexiv! Dagegen ist die Relation [mm] $\le [/mm] = [mm] \{(1,1), (1, 2), (2, 2)\}$ [/mm] reflexiv, da $1 [mm] \le [/mm] 1$ und $2 [mm] \le [/mm] 2$ ist.
>
> > Sie ist aber symmetrisch, antisymetrisch
> > und transitiv. Die Symmetrie bedeutet ja: " Wenn [mm](a, b) \in R[/mm]
> > dann ist auch [mm](b, a) \in R[/mm]". Nun ist die Praemisse bei
> > leerem R immer falsch, die ganze Aussage also richtig.
>
> Das wäre doch aber bei reflexiv dann genauso der Fall...?
Nein! Bei reflexiv heißt die Aussage "$(a, a) [mm] \in [/mm] R$ für alle $a [mm] \in [/mm] X$.
Bei symmetrisch heißt die Aussage "Wenn $(a, b) [mm] \in [/mm] R$ dann $(b, a) [mm] \in [/mm] R$". Die Prämisse ist "$(a, b) [mm] \in [/mm] R". Dies ist für leeres $R$ falsch. Die Wenn - Dann - Aussage ist deshalb richtig. Dies ist einfach Konvention in der mathematischen Argumentationsweise.
> Dass die Prämisse falsch ist? Und außerdem kann ich die
> Konklusion "Prämisse immer falsch [mm]\Rightarrow[/mm] Aussage
> richtig" nicht ganz nachvollziehen...
>
> > Ähnlich sieht man die Antisymmetrie und Transitivitāt der
> > leeren Menge ein.
>
> ...oder auch nicht ^^. Aber ich schätze das muss man
> notfalls einfach als gegeben hinnehmen.
Nein, bitte nicht . Auch bei der Antisymmetrie und Transivitāt hat man eine Prāmisse, die für die leere Relation falsch ist.
>
> > Als nāchstes betrachte die
> > einelementigen Teilmengen von [mm]X\times X[/mm]: Dies sind die vier
> > Relationen {(1, 1)}, {(1, 2)}, {(2, 1)}, {(2, 2)}.
>
> Ja , das hatte ich ja so.
>
> > Keine dieser Relationen ist reflexiv, da (2, 2) in den
> ersten
> > drei und (1,1) in der letzten nicht enthalten ist.
>
> Moment. Da hatte ich ja wieder etwas falsch gedeutet (bzw.
> aus der Not heraus "geraten" ehrlich gesagt, da ich eben
> nicht wusste, wie ich die Definitionen der Eigenschaften
> hier anwenden kann).
> Also, wenn ich das jetzt (endlich) richtig verstanden habe,
> betrachte ich also, wenn ich die Eigenschaft EINER Relation
> prüfe (man sagt ja: "die Relation, also z.B. (1,1) ist
> reflexiv", oder nicht??) alle Relationen, die genauso viele
Falsch! Die Relation ist die Menge [mm] $\{(1, 1)\}$, [/mm] nicht das Paar $(1, 1)$.
Diese Relation ist nicht reflexiv, da sie das Paar $(2, 2)$ nicht enthālt!
> Elemente enthalten bzw. die Menge dieser Relationen, also
> z.B. bei {(1,1)} die Menge aller 1-elementigen??
> Sorry, da stehe ich jetz (immer noch!!!) völlig aufm
> Schlauch. Ich verstehe den letzten Satz leider nicht. Denn
> wenn (2,2) nicht in den ersten dreien enthalten ist
> (logisch, so hatte ich mir das ja auch gedacht!) dann ist
> doch aber (1,1) auch nur in der ersten (also in {(1,1)}
> enthalten. Tut mir leid, ich sehe einfach nicht, warum
> (1,1) und {(1,2)} und {(2,1)} enthalten sein soll, (2,2)
> aber NICHT.
> Oder hab ich da irgendwas ganz falsch gelesen?
Damit R reflexiv ist, muß $1 R 1$ und $2 R 2$ gelten! Das heißt $(1, 1) [mm] \in [/mm] R$ und $(2, 2) [mm] \in [/mm] R$. Dies ist aber bei keiner der vier einelementigen Relationen der Fall.
>
> > Symmetrisch sind nur die erste und letzte,
>
> jup, nachvollziehbar! ^^
>
> > antisymmetrisch nur die zweite und dritte
>
> dito!
>
> > transitiv alle vier.
>
> ööhm...ja, stimmt, wenn man wie grade (von mir) gesagt
> für jede n-elementige Relation die Menge aller
> n-elementigen Relationen [mm](:=M_n)[/mm] hernimmt, jeweils 2 davon
> anguckt (wobei man alle Kombinationen durchmacht) und diese
> mit (x,y) und (x,z) gleichsetzt und dann schaut, ob (x,z)
> auch in dieser Menge aller n-elementigen Relationen
> enthalten ist.
> Für n=1 haben wir also: (1,1) und (1,2) [mm]\in M_n \Rightarrow[/mm]
> (1,2) [mm]\in M_n,[/mm] (1,1) und (2,2) [mm]\in M_n \Rightarrow[/mm] (1,2)
> [mm]\in M_n[/mm] usw. [mm]\Rightarrow[/mm] richtig für alle Kombis.
> Folgert man dann jeweils, dass das Succedens transitiv
> ist? Oder die beiden Antecedens? Oder hat das doch was mit
> den Anzahl von Kominationen, die klappen, zu tun?? DAS war
> mein Verständnisproblem!!
Betrachte bitte jede Relation zunāchst für sich! Und mach Dir klar, daß eine Relation eine Menge von Paaren ist. Und dann überlege, wieviele solcher Relationen reflexiv sind. Das sind genau die, die die Elemente $(1, 1)$ und $(2, 2)$ enthalten.
Die symmetrischen Relationen sind genau die, die entweder die beiden Elemente $(1, 2)$ und $(2, 1)$ enthalten, oder keines dieser Elemente.
Wenn Du alle Relationen aufgeschrieben hast, kannst Du das dann einfach abzāhlen. Oder Du überlegst Dir, daß bei den reflexiven Relationen [mm] $2^2$ [/mm] und bei den symmetrischen Relationen $2* [mm] 2^2$ [/mm] herauskommt.
> Etwas gelernt zu haben
> ohne es verstanden zu haben macht für mich keinen Sinn.
Da sind wir uns einig!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:01 Mi 27.01.2010 | | Autor: | a_la_fin |
Danke! JETZT habe ich den "Knackpunkt" (da, wo es bei mir gehakt hat beim Verständnis) gefunden: Und zwar habe ich bei reflexiv die ganze Zeit "für alle x [mm] \in [/mm] R" (statt [mm] \in [/mm] X) gelesen. So KONNTE das Ganze (v.a. bei der leeren Menge) ja garnicht funktionieren! So aber, da es ja bei reflexiv heißt: "für alle x aus der ursprünglichen (!) Menge X muss das Paar von x, also (x,x) Element der Relation sein" und bei symmetrisch, anti-symm. und transitiv heißt es ja: "für jedes Paar (x,y) Element von R (!)", also der Relation "muss gelten: (y,x) [mm] \in [/mm] R". Ein kleiner aber feiner Unterschied ^^. Lesen muss man können... :-(.
Die Schreibweise mit dem aRb kannte ich nicht, sie macht das Ganze aber tatsächlich verständlicher.
Man muss sich die leere Menge einfach als Paar aus 2 leeren Mengen, bzw. besser gesagt "Jokern" (aber nicht beliebigen) vorstellen. So ist die Bedingung der Reflexivität NICHT erfüllt, da diese beiden leeren Mengen im Paar zwar sowohl gleiche als auch verschiedene "Elemente sind" (das ist mathematisch natürlich NICHT korrekt, das ist mir schon klar! aber um es sich vorzustellen), aber eben nicht beliebige "Joker". So ist die Bedingung für Reflexivität NICHT erfüllt, da diese beiden leeren Mengen nicht einfach jeden beliebigen Wert (aus der ursprünglichen Menge X), also hier 1 oder 2, annehmen können, aber man sie für die Bedingungen von (Anti-)Symmetrie und Transitivität als (x,y) etc. "definieren" (bzw. "substituieren" darf.
Ich betone nochmal (v.a. an alle, die bei mathematischen Begrifflichkeiten / Notationen pingelig sind), dass das mit den beiden leeren Mengen unter "sich vorstellen" läuft! ^^
lG
|
|
|
|
