Relationen

21.07.2012, 11:44

Lotta 91

Relationen

Meine Frage:
Ich hätte da zwei Fragen, denn am Montag schreibe ich eine Prüfung! Vielleicht kann mir jemand helfen!

1) Sei M eine Menge mit k Elemente (bspw. M={1,2,3}), dann beträgt die Anzahl der zweistelligen Relationen?

2) Sei M eine Menge mit k Elemente (bspw. M={1,2,3}), dann beträgt die Anzahl der Äquvalenzrelationen?

gibt es zu 1 und 2 eine Formel mit der man das lösen kann?

Meine Ideen:
Also was ich weiß, ist das man die Potenzmenge einer Menge mit 2^k berechnen kann! Also bspw. bei M={1,2,3} Potenzmenge 2^3= 8

zu 1 meinte jemand (2^k)^2

aber ich weiß nicht, ob das stimmt?!

21.07.2012, 12:03

DP1996

Auf diesen Beitrag antworten »

Zu 1) Eine Relation ist ja einfach nur eine Teilmenge des kartesischen Produkts zweier Mengen (in deinem Fall von M mit sich selbst), du suchst also die Mächtigkeit der Potenzmenge von MxM.

21.07.2012, 12:11

Lotta 91

Auf diesen Beitrag antworten »

Alsi in meinem Beispiel mit M={1,2,3} wären die zweistelligen Relationen doch

1,1
1,2
1,3
2,2
2,1
2,3
3,3
3,1
3,2

also insgesamt 9

und Potenzmenge wäre 2^3= 8

das wäre die [leere Menge], [1],[2],[3],[12],[13],[23],[123]

21.07.2012, 12:15

DP1996

Auf diesen Beitrag antworten »

Ne, deine Liste enthält lediglich die Elemente von $\begin{eqnarray*} M\times M \end{eqnarray*}$ . Du brauchst aber die Anzahl der Elemente der Potenzmenge, die du aus deiner Liste jetzt aber leicht berechnen kannst.

21.07.2012, 12:34

Lotta 91

Auf diesen Beitrag antworten »

Sei M eine Menge mit k Elemente (bspw. M={1,2,3}), dann beträgt die Anzahl der zweistelligen Relationen?

d.h. ich schau wie viele zweistelligen relationen in meiner potenzmenge sind, in diesem fall [12],[13],[23] und das ist dann die antwort?! verwirrt

21.07.2012, 12:43

DP1996

Auf diesen Beitrag antworten »

Nein. Jede Teilmenge von $\begin{eqnarray*} M\times M \end{eqnarray*}$ , also jedes Element der Potenzmenge von $\begin{eqnarray*} M\times M \end{eqnarray*}$ ist eine Relation.
Und für die Mächtigkeit der Potenzmenge einer Menge gibt es eine Formel (Welche?), die musst du jetzt anwenden.

Bei deinem Beispiel sind also {}, {[1 1]},{[1 2]}, ... {[1 1],[1 2]},... alles Relationen

21.07.2012, 12:48

Lotta 91

Auf diesen Beitrag antworten »

ja die Mächtigkeit der Potenzmenge berechnet man ja mit 2^k.

bei meinem Beispiel wär das jetzt 2^3= 8

muss ich das jetzt nochmal machen mit 2^k also 2^8 ?

oder ist Potenzmenge und Anzahl der zweistelligen Relationen das gleiche? verwirrt

21.07.2012, 12:55

DP1996

Auf diesen Beitrag antworten »

2^3 wäre die Mächtigkeit der Potenzmenge von M

Wieviele Elemente hat denn das kartesische Produkt von M mit sich selbst (du hast sie oben aufgelistet)?

Zitat:

oder ist Potenzmenge und Anzahl der zweistelligen Relationen das gleiche?

Fast; exakter wäre es, zu sagen: Mächtigkeit der Potenzmenge und Anzahl der zweistelligen Relationen - das ist ja genau das, was ich dir klarzumachen versuche.

21.07.2012, 13:12

Lotta 91

Auf diesen Beitrag antworten »

das kartesische produkt hat neun elemente! die potenzmenge 8!

1) Sei M eine Menge mit k Elemente (bspw. M={1,2,3}), dann beträgt die Anzahl der zweistelligen Relationen?

d.h. die antwort ist 2^k verwirrt

21.07.2012, 13:16

DP1996

Auf diesen Beitrag antworten »

Nein

Wenn $\begin{eqnarray*} |M\times M|=|M|^2=9 \end{eqnarray*}$ ist, dann ist doch wohl $\begin{eqnarray*} \mathcal{P}(M\times M)=2^{|M\times M|}=2^9 \end{eqnarray*}$ .

Wie sieht das also für |M|=k aus?

21.07.2012, 13:21

Lotta 91

Auf diesen Beitrag antworten »

ah ok! d.h. ich bilde das kartesiche produkt und mit dieser anzahl, bilde ich sozusagen die potenzmenge?! richtig?

d.h. als lösung müsste ich hinschreiben 2^(MxM), wobei MxM die Anzahl der zweistelligen Relationen in M ist.

21.07.2012, 13:29

DP1996

Auf diesen Beitrag antworten »

Zitat:

2^(MxM), wobei MxM die Anzahl der zweistelligen Relationen in M ist.

Du verwechselst offensichtlich ständig zwei Dinge:
- Die Anzahl der Elemente einer Menge und die Menge selbst, denn sonst hättest du geschrieben: 2^|MxM|

- MxM und P(MxM), denn wie ich nun schon des öfteren erwähne, ist eine Relation R einfach ein Element aus P(MxM), richtigerweise müsstest du geschrieben haben: ..., wobei |MxM| die Anzahl aller geordneten Paare in M ist.

Zitat:

d.h. ich bilde das kartesiche produkt und mit dieser anzahl, bilde ich sozusagen die potenzmenge?! richtig?

Richtig. Warum machst du es dann nicht so?

21.07.2012, 13:37

Lotta 91

Auf diesen Beitrag antworten »

Also 2^|MxM| (ich wusste nicht, dass die Klammern so viel ausmachen mit (MxM) meinte ich die anzahl des kartesischen produkts)

Potenzmenge 2^k
Anzahl der zweistelligen Relationen in einer Menge 2^|MxM|

gibt es für die Menge der Äquivalenzrelationen auch so etwas?

21.07.2012, 13:46

DP1996

Auf diesen Beitrag antworten »

Das mit den Klammern ist nun mal Definitionssache, aber wie du gesehen hast, habe ich dich falsch verstanden, weil du andere Klammern genommen hast... also nimm besser die richtigen.

Dann kannst du zu 1. noch |MxM|=k^2 bezeichnen, wobei eben k=|M| ist, erhälst also dann $\begin{eqnarray*} 2^{k^2} \end{eqnarray*}$

Zu den Äquivalenzrelationen:
Jede Äquivalenzrelation ist eindeutig durch die Äquivalenzklassen bestimmt, die Äquivalenzklassen sind aber nichts anderes als disjunkte Teilmengen von M, die zusammen wieder ganz M ergeben. Wie viele gibt es davon?

Neue Frage »

Antworten »

Relationen

Verwandte Themen