Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Anzahl der möglichen Relationen

Anzahl der möglichen Relationen

Schüler

Tags: Relation.

Sabine2 aktiv_icon

15:15 Uhr, 18.10.2012

Hallo,
ich soll zunächst die Anzahl der möglichen Relationen auf einer Menge mit 3 Elementen bestimmen.

M^{2} = {a, b, c} x {a, b, c} = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)},

also 9 Elemente.

Eine Relation ist ja definiert als Teilmenge des kartesischen Produktes.

R \subseteq M^{2}

.
Da die Menge

M^{2} 9

Elemente hat, hat sie

2^{9} = 512

verschiedene Teilmengen. Also gibt es

512

mögliche Relationen. Dazu meine erste Frage: Kann man das kartesische Produkt nur bestimmen, wenn die Mengen gleichmächtig sind?

Ich habe hier immernoch Probleme mit den Begrifflichkeiten.. ich dachte zuerst, dass eine Relation immer nur EIN geordnetes Paar

(a, b)

beschreibt und nicht eine Menge an geordneten Paaren, aber offensichtlich ist das anders. Ich habe das nun so verstanden: Eine Relation ist ja immer eine Teilmenge vom kartesischen Produkt zweier Mengen. Sind die Mengen gleich, dann sagt man,

R

ist Relation auf der Menge

z . B

. M.
Es gibt also eine Relation, die kein geordnetes Paar hat, das wäre dann die leere Menge. Wenn ich mir also eine Relation auf einer Menge überlege, die von keinen paar Elementen erfüllt wird, ist

R =

leere Menge. Wenn die Relation nur von einem Paar erfüllt wirf, so ist

R = {(a, b)},

wird sie von zwei Paaren erfüllt, ist sie... usw. Stimmen die überlegungen?

Ich soll jetzt noch herausfinden, wieviele Relationen davon symmetrisch und wieviele reflexiv sind.
Erstmal zum Reflexiven: Ich fang mal an, die aufzuzählen:

{(a, a)}, {(b, b)}, {(c, c)}, {(a, a), (b, b)}, {(a, a), (c, c)}, ...

. All diese Relationen sind doch reflexiv, oder nicht?
Aber wie berechne ich die Anzahl aller?
Keine Idee habe ich zu der Anzahl der symmetrischen Relationen. Und ist die leere Menge eine symmetrische bzw. reflexive Relation?

Danke für die Hilfe! :-)

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

prodomo aktiv_icon

16:33 Uhr, 19.10.2012

Die Begriffe sind hier in der Tat unklar. Geht man von Mengen aus, so ist die Relation auch eine Teilmenge der Produktmenge. Geht man von Abbildungen aus, ist sie eine Abbildung. Sichtbar wird das an der Darstellung

f : x \mapsto x - 2

. Alternativ hieße es

f = {(x, y) | y = x - 2}_{ℝ x ℝ}

. Du wirst

u . U

. an derselben Uni beide Begriffe in parallelen Vorlesungen finden.

Sabine2 aktiv_icon

17:04 Uhr, 19.10.2012

Okay, soviel zu den Begrifflichkeiten. Wie aber gehe ich an die Aufgabe heran?

Edit: Hilfe wird übrigens immernoch benötigt ;-)

vulpi aktiv_icon

22:47 Uhr, 21.10.2012

Hi,
für die Reflexivität müssen alle

(x, x)

der Relation angehören.
Also

{(a, a), (b, b), (c, c)} \subset R

ist Bedingung
Für die 6 restlichen Elemente bist du frei.
Folglich gibt es

2^{6}

Möglichkeiten.

Mach dir für die Frage nach den symmetrischen

R

eine kleine Skizze:

(a, c) - (b, c) - (c, c)

(a, b) - (b, b) - (c, b)

(a, a) - (b, a) - (c, a)

Symmetrisches

R

heisst, dass wenn

(x, y) \in R

auch

(y, x) \in R

gilt.
Das entspricht in der Skizze also jeweils dem an bzw. in der (x,x)-Diagonale
Spiegeln der Elemente.
Also nehm ich mir aus dem Dreieck incl. Diagonale beliebige Elemente raus,
diese kann ich dann entsprechend spiegeln.
Die auf der Diagonalen bleiben dabei einfach die selben Elemente.
Das besagte Dreieck hat 6 Elemente, ergo kann ich

2^{6}

Kombinationen erzeugen, die ich zu symmetrischen

R

zs.-baue.
Auch die leere Menge gehört dazu, weil bei der Symmetrie keine
Enthaltens-Forderung besteht.
Es muß nur die Implikation gelten, also xRy

\Rightarrow

yRx

lg

Sabine2 aktiv_icon

18:48 Uhr, 22.10.2012

Erst einmal dankeschön!
Zur Reflexivität:
Jede Ralation muss die von dir angegebene Bedingung erfüllen. Zusätzlich kann sie aber noch andere Elemente enthalten. Wenn

z . B

. xRx ist, ist ja nicht zwangsweise ausgeschlossen, dass xRy gelten darf. Oder etwa doch?
Naja und dann hat eine 6 elementige Teilmenge

2^{6}

Elemente. Jeder dieser Teilmengen muss ich dann mit der Menge der Bedingung vereinigen. Es gibt also

2^{6}

reflexive Ralationen.
Ich denke, ich habe es verstanden! Außer die eine Frage, die ich eben gestellt habe.

Ist die leere Menge auch reflexiv, und wenn ja, ist sie in den

2^{6}

enthalten? Nein, oder? Ich hätte im Prinzip eine Vereinigung der leeren Menge mit der Bedingung, das würde aber die Bedingung ergeben und nicht die leere Menge.

Die Symmetrie kann ich leider garnicht nachvollziehen. Darf eine symmetrische Ralation auch so aussehen:

{(a, b), (b, a), (c, d)}

(c, d)

wär dann ja nicht symmetrisch. Bei der Reflexivität sind ja auch Elemente in der Ralation, die nicht reflexiv sind.

Sabine2 aktiv_icon

19:55 Uhr, 23.10.2012

Die Frage steht noch im Raum, nur mal so nebenbei, damit das Thema nicht geschlossen wird ;-)

vulpi aktiv_icon

20:23 Uhr, 25.10.2012

Hallo nochmal.
Dass

{}

nicht reflexiv ist, hast du ja selber mit Grund beantwortet.

Symmetrie:
WENN xRy DANN auch yRa

Stell dir das Kreuzprodukt MXM doch als quadratische Punkte-Fläche vor.
Da ziehst du dann die

y = x

Diagonale durch.

In einer der Dreieck-Hälften incl. Diagonale wählst du jetzt eine Element

(x_{1}, y_{1})

aus.
Damit

R

symmetrisch ist muß auch

(y_{1}, x_{1}) \in R

enthalten sein.
Und dieses liegt gespiegelt auf der ANDEREN Dreicks-Hälfte.
Also brauch ich nur die Lämpchen EINER Hälfte an bzw. ausknipsen, um alle
Kombis für symm. Relationen zu zählen.
Dss sind wie gesagt

2^{6}

(a, a)

(b, b)

(c, c)

(a, b)

(a, c)

(b, c)

ist Element oder nicht.

Sabine2 aktiv_icon

21:03 Uhr, 25.10.2012

Mit

2^{6}

berechne ich ja alle Teilmengen der oberen Dreieckshälfte incl. Diagonale. Das würde aber heißen, dass die Unteren Elemente doch alle auch drinnen sind. Aber ich dachte nicht jedes Element von unten muss in

R

enthalten sein...

Ich stelle mir das so vor: Mit jedem "Lämpchen" das ich oben anschalte, geht auch automatisch das "inverse" Lämpchen unten an, weil es symmetrisch sein soll. Kann man das hieran irgendwie verständlicher machen?

vulpi aktiv_icon

18:36 Uhr, 26.10.2012

Hi !
" Aber ich dachte nicht jedes Element von unten muss in

R

enthalten sein... "

Ist es ja auch nicht, es sind ja TEIL

! -

Mengen

Nur WENN das Element enthalten ist DANN auch sein Pendant.

Paar Beispiele

{(a, a)}

{(a, b), (b, a)}

{(b, b), (a, c), (c, a)}

Das sind jeweils symmetrische Relationen, und auch

{}

{(a, b), (b, b), (b, c), (b, a)}

ist dagegen nicht symmetrisch,
weil das Pendant zu

(b, c)

fehlt.

Und wenn sich die 2. Hälfte aus der 1. sowieso ergibt,
brauch ich auch nur die erste variieren, um die Möglichkeiten zu zählen.

Sabine2 aktiv_icon

11:37 Uhr, 28.10.2012

Okay, mir ist das jetzt klar.
Ich betrachte die Elemente oberhalb und auf der Diagonalen und bilde alle möglichen Teilmengen aus diesen. Deswegen 2^(Zahl). Zu diesen Teilmengen muss ich dann aber abschließend noch die inversen Elemente der geordneten Paare hinzufügen, damit die Relation symmetrisch wird. Das ändert ja aber nichts an der Anzahl der Mengen.

Vielen Dank! :-)

1041240

1037797

	Status: nicht eingeloggt	Noch nicht registriert?