Relationen auf {a,b} < Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | 1. Bestimme alle Relationen auf der Menge {a,b}
2. Welche dieser Relationen sind reflexiv, symmetrisch, transitiv?
3. Welche Relationen sind Äquivalenzrelationen? |
1. [mm] {x,y}\in [/mm] MxM.
(x,x),(y,y),(x,y),(y,x)..
also gibt es für (x,y) [mm] 2^4 [/mm] Relationen
Stimmt das so? wie kann ich denn daraus die weiteren Aufgaben lösen? was reflexiv, symmetrisch, transitiv ist, das weiß ich ja!
Mathegirl
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:23 Sa 13.11.2010 | | Autor: | fred97 |
Eine Relation ist eine nichtleere Teilmenge von [mm] $\{a,b\} \times \{a,b\} [/mm] $
Wie sieht diese Menge [mm] $\{a,b\} \times \{a,b\} [/mm] $ aus ?
Was sind die nichtleere Teilmengen von [mm] $\{a,b\} \times \{a,b\} [/mm] $ ?
FRED
|
|
|
| |
|
also die Menge (a,b)x(a,b) sieht folgendermaßen aus...
(a,a),(b,b),(a,b),(b,a),..also [mm] 2^4 [/mm] = Relationen, stimmt das so?
reflexiv:
Für alle [mm] x\in M:(x,x)\in [/mm] M [mm] x\le [/mm] x
Für alle [mm] y\in M:(y,y)\in [/mm] M [mm] y\le [/mm] y
symmetrisch:
Für alle [mm] x,y\in [/mm] M: ist [mm] (x,y)\in \IR [/mm] dass folgt [mm] (y,x)\in \IR
[/mm]
x=y folgt y=x
Aber wie muss ich das eigen, das sind ja eigentlich nur die definitionen.
|
|
|
| |
|
Hallo Mathegirl,
> also die Menge (a,b)x(a,b) sieht folgendermaßen aus...
Gefragt ist die Menge [mm]\{a,b\}\times\{a,b\} \ = \ M\times M[/mm]
>
> [mm]\red{\{}(a,a),(b,b),(a,b),(b,a)\red{\}}[/mm] ,.. also [mm]2^4[/mm] = Relationen, stimmt das
> so?
Das ist die Anzahl aller Teilmengen, die leere Menge musst du rausnehmen, bleiben also 15 Relationen auf [mm]M\times M[/mm]
>
>
> reflexiv:
> Für alle [mm]x\in M:(x,x)\in[/mm] M [mm]x\le[/mm] x ??
Was soll das bedeuten?
[mm](x,x)\in M[/mm] ist doch keine sinnvolle Aussage.
Du meinst [mm]R\subseteq M\times M[/mm] heißt reflexiv, falls für alle [mm]x\in M: xRx \ \[/mm] bzw. [mm](x,x)\in R[/mm]
> Für alle [mm]y\in M:(y,y)\in[/mm] M [mm]y\le[/mm] y
Was meinst du mit dem [mm]\le[/mm] ??
Ist das hier irgenwo gegeben? Dann muss ich es übersehen haben ...
>
> symmetrisch:
> Für alle [mm]x,y\in[/mm] M: ist [mm](x,y)\in \IR[/mm] dassnn folgt [mm](y,x)\in \IR[/mm] ![[ok]](/images/smileys/ok.gif "[ok]")
>
> x=y folgt y=x
?? Ist das ein Bsp.?
>
>
> Aber wie muss ich das eigen, das sind ja eigentlich nur die
> definitionen.
Na, du musst heuristisch überlegen!
Bei den reflexiven Relationen müssen die beiden Tupel [mm](a,a)[/mm] und [mm](b,b)[/mm] dabei sein.
Wieviele Relationen kannst du damit bilden?
Bei den symmetrischen Relationen:
Die können aus einem Element (Tupel) bestehen, etwa [mm]R=\{(a,a)\}[/mm]
[mm]R=\{(a,a),(b,b)\}[/mm] tut's auch!
Was noch?
Wie sieht's mit den "gemischten" Tupeln aus?
Was ist, wenn da eines dabei ist?
Dann zähle wieder ab, wieviele du insgesamt bilden kannst ...
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:50 Sa 13.11.2010 | | Autor: | dfx |
Hallo,
die Aufgabe ist im Grunde eine der leichtesten. M ist definiert als eine Menge mit den zwei Elementen a und b. Für die erste Aufgabe nimmt man sich die Defintion von Relation zur Hand. Da haben wir aus der Vorlesung:
$R := M [mm] \times [/mm] M$
Das ist wie ich finde nicht ganz korrekt, aber dennoch gültig, glaube ich. Allerdings wäre besser verständlich und einleuchtender:
$R [mm] \subseteq [/mm] M [mm] \times [/mm] M$
Alle Relationen über der Menge $M$ mit ${a, b}$ wären also alle einzelnen Teilmengen, die sich aus dem Kreuzprodukt der Menge $M$ bilden lassen.
Dazu habe ich bei einem eine sehr schöne Tabelle gesehen, die die gesamte Aufgabe von 1.-3. erfasst. In der ersten Spalte die Teilmengen, in der zweiten bis vierten Spalte jeweils reflexiv, symmetrisch und transitiv, wo er darunter Kreuzchen gemacht hat. Als letzte Spalte eben die Äquivalenzrelation, wenn zutreffend angekreuzt.
Zu deiner Frage: Nein, ich finde die Notation nicht richtig. Du solltest die Relationen, also die Teilmengen auch entsprechend ausdrücken.
[mm] $R_0 [/mm] = [mm] \{?\}$
[/mm]
[mm] $R_{1.1} [/mm] = [mm] \{(?,?)\}$
[/mm]
[mm] $R_{1.2} [/mm] = [mm] \{(?,?)\}$
[/mm]
[mm] $R_{1.3} [/mm] = [mm] \{(?,?)\}$
[/mm]
[mm] $R_{1.4} [/mm] = [mm] \{(?,?)\}$
[/mm]
[mm] $R_{2.1} [/mm] = [mm] \{(?,?),(?,?)\}$
[/mm]
$...$
[mm] $R_{4.1} [/mm] = [mm] \{(?,?),(?,?),(?,?),(?,?)\}
[/mm]
Ich hoffe du verstehst meinen "hint" bei der ersten Teilmenge! Die Fragezeichen sind da, weil ich dir nicht zu arg helfen will. Meiner Ansicht nach, habe ich das schon getan. Vorallem durch die Indizierung, die ich bei den Relationen verwende. Insgesamt hoffe ich auch, dass du es soweit nachvollziehen kannst und wir die Aufgabe weiter theoretisch durchgehen können, denn sie enthält ein markantes Detail, welches dir vermutlich bei deiner folgenden Aufgabe helfen würde.
gruss, dfx
|
|
|
| |
|
[mm] R_0 [/mm] = [mm] \{\emptyset\}[/mm]
[/mm]
[mm] R_{1.1} [/mm] = [mm] \{(a,a)\}
[/mm]
[mm] R_{1.2} [/mm] = [mm] \{(b,b)\}
[/mm]
[mm] R_{1.3} [/mm] = [mm] \{(a,b)\}
[/mm]
[mm] R_{1.4} [/mm] = [mm] \{(b,a)\}
[/mm]
[mm] R_{2.1} [/mm] = [mm] \{(a,a),(b,b)\}
[/mm]
[mm] R_{2.2} [/mm] = [mm] \{(b,b),(a,a)\}
[/mm]
[mm] R_{2.3} [/mm] = [mm] \{(a,b),(a,b)\}
[/mm]
[mm] R_{2.4} [/mm] = [mm] \{(b,a),(b,a)\}
[/mm]
[mm] R_{3.1} [/mm] = [mm] \{(a,a),(a,b),(b,b)\}
[/mm]
[mm] R_{3.2} [/mm] = [mm] \{(a,a),(b,a),(b,b)\}
[/mm]
[mm] R_{3.3} [/mm] = [mm] \{(a,a),(a,b),(b,a)\}
[/mm]
[mm] R_{3.4} [/mm] = [mm] \{(b,b),(a,b),(b,a)\}
[/mm]
[mm] R_{4.1} [/mm] = [mm] \{(a,a),(b,b),(a,b),(b,a)\}
[/mm]
symmetrische Relationen:
[mm] {\emptyset}
[/mm]
(a,a)
(b,b)
(a,b),(b,b)
(a,a),(b,b)
(a,a)(a,b)(b,a)
(b,b)(a,b)(b,a)
(a,a)(b,b)(a,b)(b,a)
transitive Relationen
[mm] {\emptyset}
[/mm]
(a,a)
(b,b)
(a,a)(b,b)
(a,b)(b,a)
(a,a)(a,b)(b,b)
(a,a)(b,a)(b,b)
(a,a)(a,b)(b,a)(b,b)
reflexive Relationen
(a,a)
(b,b)
(a,a)(b,b)
Stimmt das soweit? die schreibweise mal außer acht gelassen...
Mathegirl
|
|
|
| |
|
> [mm]R_0[/mm] = [mm]\{\emptyset\}[/mm] (***)
> [mm]R_{1.1}[/mm] = [mm]\{(a,a)\}[/mm]
> [mm]R_{1.2}[/mm] = [mm]\{(b,b)\}[/mm]
> [mm]R_{1.3}[/mm] = [mm]\{(a,b)\}[/mm]
> [mm]R_{1.4}[/mm] = [mm]\{(b,a)\}[/mm]
> [mm]R_{2.1}[/mm] = [mm]\{(a,a),(b,b)\}[/mm]
> [mm]R_{2.2}[/mm] = [mm]\{(b,b),(a,a)\}[/mm]
> [mm]R_{2.3}[/mm] = [mm]\{(a,b),(a,b)\}[/mm]
> [mm]R_{2.4}[/mm] = [mm]\{(b,a),(b,a)\}[/mm]
> [mm]R_{3.1}[/mm] = [mm]\{(a,a),(a,b),(b,b)\}[/mm]
> [mm]R_{3.2}[/mm] = [mm]\{(a,a),(b,a),(b,b)\}[/mm]
> [mm]R_{3.3}[/mm] = [mm]\{(a,a),(a,b),(b,a)\}[/mm]
> [mm]R_{3.4}[/mm] = [mm]\{(b,b),(a,b),(b,a)\}[/mm]
> [mm]R_{4.1}[/mm] = [mm]\{(a,a),(b,b),(a,b),(b,a)\}[/mm]
Hallo Mathegirl,
mal nur erst zu dieser Liste:
diejenigen Relationen, die aus genau 2 Paaren bestehen,
musst du nochmals betrachten. Insgesamt gibt es davon 6 .
Deine [mm] R_{2.3} [/mm] und [mm] R_{2.4} [/mm] enthalten nur je ein Paar anstatt zwei.
(***) Falls (gemäß Fred) nur die nicht-leeren Teilmengen
als Relationen gelten sollen, würde natürlich [mm] R_0 [/mm] wegfallen.
Deine Schreibweise für die leere Menge ist übrigens falsch.
Du kannst dafür [mm]\{\}[/mm] oder [mm]\emptyset[/mm] schreiben, aber nicht [mm]\{\emptyset\}[/mm] .
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:22 So 14.11.2010 | | Autor: | fred97 |
>
> (***) Falls (gemäß Fred) nur die nicht-leeren Teilmengen
> als Relationen gelten sollen, würde natürlich [mm]R_0[/mm]
> wegfallen.
Hallo Al,
leider ist es nicht einheitlich geregelt, ob die leere Menge (als Teilmenge eines kartesischen Produktes) eine Relation ist oder nicht.
Bei manchen Leuten ist es so, bei anderen nicht.
FRED
> LG Al-Chw.
|
|
|
| |
|
Dann müsste [mm] R_{2.3} [/mm] heißen (a,b),(b,a)
und [mm] R_{2.4} [/mm] (b,a),(a,b)??
und wa sist mit den anderen Relationen? also die symmetrisch, reflexiv, transitiv? ist das so okay?
|
|
|
| |
|
> Dann müsste [mm]R_{2.3}[/mm] heißen (a,b),(b,a)
> und [mm]R_{2.4}[/mm] (b,a),(a,b)?? ![[haee]](/images/smileys/haee.gif "[haee]")
.... dann wäre ja [mm] R_{2.3}=R_{2.4}
[/mm]
Wie schon gesagt, gibt es nicht nur 4, sondern 6
Teilmengen, die aus zwei (verschiedenen !) Elementen
bestehen. Dabei ist hier ein "Element" jeweils eines
der 4 möglichen Paare.
Beispiel: die Menge [mm] \{P,Q,R,S\} [/mm] hat insgesamt [mm] 2^4=16 [/mm]
Teilmengen, darunter 6 mit genau 2 Elementen, nämlich
(ohne Mengenklammern notiert:
PQ PR PS QR QS RS
> und was ist mit den anderen Relationen?
du meinst: mit den anderen Fragen
> also die Fragen betr.
> symmetrisch, reflexiv, transitiv? ist das so okay?
Darauf wollte ich eigentlich erst eingehen, wenn die Liste
komplett ist.
LG Al-Chw.
|
|
|
| |
|
Okay...ich habe ha nun alle Relationen, aber vielleicht kannst du mir sagen, ob die symmetrischen, reflexiven und transitiven soweit stimmen..:
also, erstmal alle relationen:
>
>
> [mm]R_0[/mm] = [mm]\{\emptyset\}[/mm][/mm]
> [mm]R_{1.1}[/mm] = [mm]\{(a,a)\}[/mm]
> [mm]R_{1.2}[/mm] = [mm]\{(b,b)\}[/mm]
> [mm]R_{1.3}[/mm] = [mm]\{(a,b)\}[/mm]
> [mm]R_{1.4}[/mm] = [mm]\{(b,a)\}[/mm]
> [mm]R_{2.1}[/mm] = [mm]\{(a,a),(a,b)\}[/mm]
> [mm]R_{2.2}[/mm] = [mm]\{(a,a),(b,a)\}[/mm]
> [mm]R_{2.3}[/mm] = [mm]\{(a,a),(b,b)\}[/mm]
> [mm]R_{2.4}[/mm] = [mm]\{(a,b),(b,a)\}[/mm]
> [mm]R_{2.5}[/mm] = [mm]\{(a,b),(b,b)\}[/mm]
> [mm]R_{2.6}[/mm] = [mm]\{(b,a),(b,b)\}[/mm]
> [mm]R_{3.1}[/mm] = [mm]\{(a,a),(a,b),(b,b)\}[/mm]
> [mm]R_{3.2}[/mm] = [mm]\{(a,a),(b,a),(b,b)\}[/mm]
> [mm]R_{3.3}[/mm] = [mm]\{(a,a),(a,b),(b,a)\}[/mm]
> [mm]R_{3.4}[/mm] = [mm]\{(b,b),(a,b),(b,a)\}[/mm]
> [mm]R_{4.1}[/mm] = [mm]\{(a,a),(b,b),(a,b),(b,a)\}[/mm]
>
>
> symmetrische Relationen:
> [mm]{\emptyset}[/mm]
> (a,a)
> (b,b)
> (a,b),(b,b)
> (a,a),(b,b)
> (a,a)(a,b)(b,a)
> (b,b)(a,b)(b,a)
> (a,a)(b,b)(a,b)(b,a)
>
> transitive Relationen
> [mm]{\emptyset}[/mm]
> (a,a)
> (b,b)
> (a,a)(b,b)
> (a,b)(b,a)
> (a,a)(a,b)(b,b)
> (a,a)(b,a)(b,b)
> (a,a)(a,b)(b,a)(b,b)
>
> reflexive Relationen
> (a,a)
> (b,b)
> (a,a)(b,b)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:20 Di 16.11.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:36 So 14.11.2010 | | Autor: | dfx |
Mahlzeit,
OK, man merkt, dass ich auf etwas bestimmtes hinauswollte. Du bist genau in die Falle reingetappt. Ich glaube, es ist dir nicht selbst aufgefallen. Es scheint da noch eine Schwäche bei dir in Bezug auf Mengen zu geben. Eine Zwischenfrage wäre jetzt, ist ${a,b,c,d,e,a,f}$ eine Menge? Und dann in der Folge sollte ich wohl erstmal fragen, ob dir daraus etwas bei deinen Angaben auffällt.
Das bloße Vertauschen, was du zum Teil praktiziert hast, bildet keine Relation in dem Sinne, wie es gefordert wäre, weil sich die Relationen dann gleichen würden. Die Relationen sollten aber verschieden voneinander sein. Warum eigentlich?
Damit du jetzt einerseits deine Liste vervollständigen kannst und andererseits nochmal die Liste mit den Relationen in Zuordnung zu den Eigenschaften überarbeiten kannst, gebe ich dir mal die Relationen, die aus zwei Paaren bestehen. Denn ich wollte noch auf das Detail zu sprechen kommen, bevor ich nachher zu einem Übungsgruppentreff zu genau diesem Blatt fahre.
[mm] R_{2.1} [/mm] = [mm] \{(a,a),(a,b)\}
[/mm]
[mm] R_{2.2} [/mm] = [mm] \{(a,a),(b,a)\}
[/mm]
[mm] R_{2.3} [/mm] = [mm] \{(a,a),(b,b)\}
[/mm]
[mm] R_{2.4} [/mm] = [mm] \{(a,b),(b,a)\}
[/mm]
[mm] R_{2.5} [/mm] = [mm] \{(a,b),(b,b)\}
[/mm]
[mm] R_{2.6} [/mm] = [mm] \{(b,a),(b,b)\}
[/mm]
Wie du siehst, gibt es sechs Relationen bei zwei Paaren. Bei drei Paaren sieht es soweit bei dir in Ordnung aus. Also nun zur Auffälligkeit:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
Das kennst du sicher. Na ja, ich hätte es vor meinem Studium nicht gekannt, wenn ich damals zu meiner Schulzeit nicht einen Freund gehabt hätte, der das Gymnasium besuchte und mich darin einweihte. Das ist das Pascalsche Dreieck. Beginnend für $n=0$. Man verbessere mich also, wenn ich jetzt etwas falsches sage. Wieviele Paare enthält unsere umfangreichste Relation? Die hast du im dritten Beitrag von oben als erstes angegeben. Das waren $n=4$. Wenn ich das nun richtig interpretiere, dann ist dieses [mm] $R_{4.1}$ [/mm] , wo die Relation ja in unserer Liste wieder auftritt, das $R$ welches dem Kreuzprodukt $M [mm] \times [/mm] M$ entspricht ( $R := M [mm] \times [/mm] M$ ). Wir haben nun sämtliche $R$s, die Teilmengen von $M [mm] \times [/mm] M$ sind aufgelistet und stellen fest, dass wir
1-mal die leere Meere als Relation,
4-mal die Paare einzeln als Relationen,
6-mal zwei Paare in eindeutiger Relation zueinander,
4-mal drei Paare in eindeutiger Relation zueinander,
1-mal die vier Paare als eindeutige Relation,
haben. In diesem Zusammenhang ist noch der Begriff Tupel interessant, allerdings lag es mir gerade nicht, diesen auch noch zu verwenden.
Nun noch zu deinen Angaben zu den Relationen und wie du sie Eigenschaften zugeordnet hast.
Als ersten Satz: "Die leere Menge ist niemals reflexiv."
Das hast du offensichtlich schon verstanden. Sogar insgesamt, wie man mit [mm] $R_0$ [/mm] wie wir sie genannt haben umzugehen hat.
Zweiter Satz: "Alle Teilmengen in denen $(a,a)$ und $(b,b)$ enthalten sind, sind reflexiv."
In anderen Worten: "Alle Teilmengen in denen die Elemente der Grundmenge ( $M = [mm] \{a,b\}$ [/mm] ) in Relation zu sich selbst stehen, sind reflexiv."
So, und bei der Symmetrie fällt es mir gerade nicht so leicht noch Sätze zu formulieren. Sag ich mal kurz, wenn [mm] $(a,b)\in [/mm] R$ , dann ist auch [mm] $(b,a)\in [/mm] R$. Wo ist das der Fall?
Na ja, ich würde insgesamt die Ausführungen jetzt am Liebsten abkürzen, indem ich dich auf die vorherige Aufgabe verweise für die ich in diesem Forum gestern Abend einen Thread erstellt habe: Aufgabe 2. Besonderst interessant sollte da für dich sein, was passiert, wenn man die Voraussetzung nicht ansetzen kann.
Zuallerletzt eben noch, welche bilden dann eine Äquivalenzrelation. Ich sag dir gleich, so wie du die Relationen angegeben hast, träfe es beim überfliegen nur auf [mm] $\{(a,a),(b,b)\}$ [/mm] zu, und das ist nicht richtig. Insgesamt sind zuviele Fehler drin, glaube ich. Sorry.
gruss, dfx
|
|
|
|
