Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Von Menge auf Relationen schließen? oO
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> Von Menge auf Relationen schließen? oO
 
Autor Nachricht
info-neuling
Junior Member
Benutzer-Profile anzeigen
Junior Member


Anmeldungsdatum: 20.10.2006
Beiträge: 56

BeitragVerfasst am: 12 Nov 2006 - 11:18:33    Titel: Von Menge auf Relationen schließen? oO

Hey, ich hab folgende Aufgabe.

Es sei M = {1,2,...,n}

i) Wieviele reflexive Relationen gibt es auf M?
ii) Wieviele symmetrische Relationen gibt es auf M?

Woher soll ich denn sowas wissen? oO Wir haben zwar in der Vorlesung besprochen, was Refexivität ist und was Symmetrie ist, aber wie kann ich denn wissen, wieviele Relationen es geben wird, wenn ich die Menge kenne? ich finde da nochnichtmal einen Ansatz.

Refelexiv bedeutet ja z.B., dass alle Paare (1,1), (2,2)...(n,n) vorkommen. Das müssten ja n^n Paare sein... aber das Hilft ja auch nicht weiter.

Eine anderer Teilaufgabe dieser Nummer, war der beweis, dass die Potenzmenge von M genau 2^n Elemente hat. Vlt muss man das ja irgendwie mit einbeziehen, aber ich find überhaupt keinen Ansatz...
Für Vorschläge wär ich echt dankbar^^
someDay
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 04.09.2005
Beiträge: 3889

BeitragVerfasst am: 12 Nov 2006 - 13:09:16    Titel:

Wie habt ihr denn Relationen definiert? Es gibt offensichtlich nicht unendlich viele Relationen auf einer endlichen Menge..

sD.
info-neuling
Junior Member
Benutzer-Profile anzeigen
Junior Member


Anmeldungsdatum: 20.10.2006
Beiträge: 56

BeitragVerfasst am: 12 Nov 2006 - 13:24:49    Titel:

Eine Relation beschreibt Beziehungen zwischen Mengen.

Refelexive Relationen zur Menge M fallen mir jetzt spontan 4 Stück ein.
1) N x N alles steht mit allem in Relation
2) "="-Relation gleiche Elemente stehen in Relation
3) <= (kleinergleich)-Relation hierzu gehören alle Paare der Form (x,x) und halt noch Paare der Form (x,y), wobei x < y ist.
4) >= (größergleich)-Relation siehe Punkt 3)

Mehr fallen mir jetzt zwar nicht ein, aber es gibt doch bestimmt noch hundert andere möglichen Relationen, die auch refelexiv sind auf der Menge M, oder?
someDay
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 04.09.2005
Beiträge: 3889

BeitragVerfasst am: 12 Nov 2006 - 14:12:14    Titel:

info-neuling hat folgendes geschrieben:
Eine Relation beschreibt Beziehungen zwischen Mengen.


Das ist keine Definition. Schreib mal die korrekte auf, die dein Prof brachte; vergiss deinen Ansatz.

Edit: http://en.wikipedia.org/wiki/Relation_%28mathematics%29#Formal_definitions bitte die erste Durchlesen und dann etwas darueber nachdenken.

sD.
info-neuling
Junior Member
Benutzer-Profile anzeigen
Junior Member


Anmeldungsdatum: 20.10.2006
Beiträge: 56

BeitragVerfasst am: 12 Nov 2006 - 15:13:44    Titel:

Ok, also unser Prof hat das in Algebra so definiert:

Eine Relation auf einer Menge X ist eine Teilmenge R C X x X.
Das heißt in R sind alle diejenigen Paare (x,y) aufgelistet, welche in Relation stehen.
Bsp: Die Relation x<y auf IR (reele Zahlen):

< = {(x,y) € IR x IR: y-x > 0}

Für Reflexivität beispielsweise haben wir aufgechrieben:

Für alle x € X: x ~ x

Hilft dir das weiter, um mir zu helfen?

Ich wollte deine Text lesen, aber der ist ja auf englisch -.- Englisch war mein schlechtestes Fach in der Schule (nur 7 Punkte Sad ) und wenn ich den Sachverhalt nochnichtmal auf deutsch verstehe, dann auch nicht auf englisch^^
Bitte erklär mir das doch mal anhand der Reflesivität, hab ja dann immer noch die Symmetrie... die kann ich ja dann vlt eigendständig machen, wenn ichs erstmal verstanden hab... aber morgen ist schon Abgabe, deshalb müsst ich bald mal weiterkommen Smile
someDay
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 04.09.2005
Beiträge: 3889

BeitragVerfasst am: 12 Nov 2006 - 16:34:29    Titel:

Ohne Englisch wirst du im Studium nicht sehr weit kommen - der Text sagte in etwa das gleiche wie die Definition des Profs.

Zuerst einmal gilt: Zwei Relationen sind logischerweise gleich, wenn R1 = R2, also {(x11,y11), (x12, y12)...} = {(x21, y21), (x22,y22)...}.

Wenn eine Relation reflexiv ist, so muss fuer jedes z € X gelten, das (z,z) € R. Die Werte aller anderen Paare sind irrelevant.

Nehmen wir jetzt deine Menge M = {x € |N, x<= n}. Offensichtlich muss (1,1), (2,2) ... (n,n) € R. Jetzt folgt ein wenig Kombinatorik: Wir stellen uns das ganze als eine sehr lange Liste von 1ern und 0ern vor, also 1100111000 (etc). Die ersten n (da es n solcher Paare gibt) sind 1er, die anderen Elemente n^2 (soviele moegliche Paare gibt es insgesamt) - n (die haben wir schon) = n^2 - n koennen beliebig 1 oder 0 sein. Insgesamt gibt es also 2^(n^2-n) reflexive Relationen, da es 2^k verschiedene Kombinationen gibt, k 1er oder 0er hintereinander zu reihen.

sD.
Physikus
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 15.09.2004
Beiträge: 1754
Wohnort: Bielefeld

BeitragVerfasst am: 12 Nov 2006 - 16:34:45    Titel:

Das ist bei den Mathematikern wohl besser aufgehoben...
info-neuling
Junior Member
Benutzer-Profile anzeigen
Junior Member


Anmeldungsdatum: 20.10.2006
Beiträge: 56

BeitragVerfasst am: 12 Nov 2006 - 20:42:59    Titel:

Ich versteh nicht so ganz, was du da meinst.

Das hab ich verstanden:
"Zuerst einmal gilt: Zwei Relationen sind logischerweise gleich, wenn R1 = R2, also {(x11,y11), (x12, y12)...} = {(x21, y21), (x22,y22)...}.

Wenn eine Relation reflexiv ist, so muss fuer jedes z € X gelten, das (z,z) € R. Die Werte aller anderen Paare sind irrelevant.

Nehmen wir jetzt deine Menge M = {x € |N, x<= n}. Offensichtlich muss (1,1), (2,2) ... (n,n) € R. "

Jetzt versteh ich nicht, was du mit den ganzen Einsen und Nullen meinst. Wofür genau steht bei dir so ne 1 bzw. ne 0?


Das es n gleiche Paare (also Paare der Form (x,x) ) gibt erscheint mir auch logisch. Ebenso verstehe ich, dass es insgesamt n^2 Paare gibt. Also das sind dann alle möglichen Paare, die aus den Elementen der Menge gebildet werden können. Sie haben die Form x,x oder x,y oder y,x. Da die Paare (x,x) sowieso in der Relation sein müssen, damit sie reflexiv ist, können wir sie abziehen und kommen somit auf
n^2 - n. Auch das erscheint mir noch logisch.

Das nächste erscheint mir wieder nicht logisch. Du sagst, dass es 2^k verscheidene Kombinationen gibt, k 1er und 0er hintereinander zu reihen.
Was ist hier wieder die 1 bzw. die 0?
Aber mal abgesehen davon: Gehst du mit 2^k nicht davon aus, dass die Paare innerhalb der Menge geordnet sind? Also dass es einen Unterschied macht, ob das Paar (3,5) vor dem Paar (4,6) kommt oder umgedreht?
Aber ist das nicht eigendlich egal, da es bei einer Menge nur auf die Elemente ankommt, die drin sind und nicht, in welcher Reihenfolge man sie aufschreibt? oO
someDay
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 04.09.2005
Beiträge: 3889

BeitragVerfasst am: 12 Nov 2006 - 22:08:27    Titel:

Zu der Erklaerung der Binaerzahl: Nehmen wir die Menge M = {1,2,3}. Wir koennen jetzt eine injektive Abbildung f erstellen, die jedem Element der Potenzmenge von M eine 3-bit Zahl b zuordnet, b bestimmt das Element eindeutig. Beispielsweise ist f(M) = 111, f({1,2}) = 110. Es gibt genau 2^n solcher Kombinationen, also gibt es auch 2^n Mengen (=> die Potenzmenge hat 2^n Elemente). Die Reihenfolge der einzelnen Elemente ist irrelevant, gerade dadurch das wir eine bestimmte Reihenfolge vorgeben und somit alle anderen ausschliessen, wird dies ja beachtet.

sD.
info-neuling
Junior Member
Benutzer-Profile anzeigen
Junior Member


Anmeldungsdatum: 20.10.2006
Beiträge: 56

BeitragVerfasst am: 13 Nov 2006 - 13:55:42    Titel:

Dankeschön, hab das jetzt glaub verstanden^^

Habs für die Symmentrie auch schon gemacht, wäre das jetzt so richitg:

Eine Relation ist symmentrisch wenn gilt:
alle x,y € X: x~y -> y~x

Die Menge M hat n Elemente. Also n^2 mögliche Kombinationen der einzelnen Elemente zu Paaren.
Die Paare der Form (x,x) kommen n mal vor, folglich kommen die Paare der Form (x,y) n^2-n mal vor.
Wenn (x,y) in der Relation vorkommt, dann muss auch (y,x) vorkommen.
Foglich halbieren sich die Möglichkeiten der Kombinationen:

(n^2-n) : 2 .

Die Paare der Form (x,x) müssen nur einmal verkommen, da sie umgedreht, das selbe bedeuten, ihre Möglichekeiten werden also nicht halbiert, sondern bleiben bei n.
Daraus folgt:

(n^2-n):2 +n = (n^2+n):2

Ein Paar kann nun Element der Relation sein oder nicht, es gibt also 2^k verschiedene Kombinationsmöglichkeiten.
Daraus folgt:

2^[(n^2+n):2]

Ist das so richitg?^^
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> Von Menge auf Relationen schließen? oO
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum