Anzahl Relationen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:43 Do 01.11.2007 | | Autor: | ilfairy |
| Aufgabe | a) Sei A eine Menge mit |A| = n (n[mm]\in\IN[/mm]). Wie viele Relationen auf A gibt es?
b) Wie viele reflexive Relationen gibt es auf A?
c) Sei A = {1,2,3,4}. Wie viele Äquivalenzrelationen mit genau zwei Äquivalenzklassen gibt es auf A? |
Hallo!
Ich bräuchte von euch mal wieder Hilfe bei meinen Aufgaben. Eine Idee habe ich schon, aber weiter komme ich nicht.
a) Ich habe also eine Menge A mit n Elementen.
Eine Relatione ist eine Untermenge von AxA, also müssen [mm]n^2[/mm] Tupel vorhanden sein.
Die Anzahl der Relationen zwischen diesen Tupeln müsste also [mm]n^2[/mm]*[mm]n^2[/mm] also [mm]n^4[/mm] Relationen.
b) Eine reflexive Relation ist, wenn ein Element zu sich selbst in Relation steht, z.B. a~a.
Hier sind das also die Tupel gemeint, wie (1,1),(2,2),(3,3), etc.. Ich glaube deren Anzahl ist dann n.
c) Äquivalenzrelation:
es gilt: reflexiv a~a
symmetrische a~b => b~a
transitiv a~b und b~c folgt a~c
Was eine Äquivalenzklasse ist habe ich nicht so ganz verstanden. Ich glaube die Elemente von A, die gleiche Eigenschaften besitzen bilden eine Klasse, wobei ich nun nicht sagen kann was für Eigenschaften.
Ich hoffe ihr könnt mir hier helfen!
Vielen Dank
Ilfairy
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
> a) Sei A eine Menge mit |A| = n (n[mm]\in\IN[/mm]). Wie viele
> Relationen auf A gibt es?
> b) Wie viele reflexive Relationen gibt es auf A?
> c) Sei A = {1,2,3,4}. Wie viele Äquivalenzrelationen mit
> genau zwei Äquivalenzklassen gibt es auf A?
> a) Ich habe also eine Menge A mit n Elementen.
> Eine Relatione ist eine Untermenge von AxA, also müssen
> [mm]n^2[/mm] Tupel vorhanden sein.
Hallo,
Du hast recht damit, daß eine Relation eine Teilmenge von AxA ist.
AxA hat [mm] n^2 [/mm] Elemente, das stimmt.
> Die Anzahl der Relationen zwischen diesen Tupeln
????
Du sagtest oben, daß eine Relation eine Teilmenge von AxA ist.
Wenn nach der Anzahl der Relationen auf A gefragt ist, ist das also die Frage nach der Anzahl er Teilmengen von AxA.
Gruß v. Angela.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:21 Do 01.11.2007 | | Autor: | toefte |
Hallo ,
da ich grad an der gleichen Aufgabe sitze: Wir hatten zu Aufgabe a) ein Beispiel und laut diesen Beispiel wären die Realtionen :
(1,1),(1,2), .............. (1,n)
(2,2)................(2,n)
.
.
.
(n,n)
Also gibt es n + (n-1)+ .... 1 Relationen. Zählt denn aber zum Beispiel (2,1) nicht als Relation? Und wenn nicht, warum?
lg tööööööööööööööööööfte
|
|
|
| |
|
> Hallo ,
>
> da ich grad an der gleichen Aufgabe sitze: Wir hatten zu
> Aufgabe a) ein Beispiel und laut diesen Beispiel wären die
> Realtionen :
>
> (1,1),(1,2), .............. (1,n)
> (2,2)................(2,n)
> .
> .
> .
> (n,n)
>
> Also gibt es n + (n-1)+ .... 1 Relationen. Zählt denn aber
> zum Beispiel (2,1) nicht als Relation? Und wenn nicht,
> warum?
Hallo,
als Relation zählt es ganz sicher nicht...
Eher doch wohl als mögliches Element einer Relation auf [mm] \{1,...,n\}. [/mm]
Naja, ich weiß schon, was Du meinst, und ich verstehe es genausowenig wie Du.
Vielleicht war die Aufgabenstellung etwas anders? Mit besonderen Anforderungen an die Relation vielleicht?
Deine Paare wären ja genau die, die zu [mm] \le [/mm] passen würden.
Gruß . Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:50 Sa 03.11.2007 | | Autor: | toefte |
>
> Eher doch wohl als mögliches Element einer Relation auf
> [mm]\{1,...,n\}.[/mm]
>
> Naja, ich weiß schon, was Du meinst, und ich verstehe es
> genausowenig wie Du.
>
> Vielleicht war die Aufgabenstellung etwas anders? Mit
> besonderen Anforderungen an die Relation vielleicht?
>
> Deine Paare wären ja genau die, die zu [mm]\le[/mm] passen würden.
>
> Gruß . Angela
Hallo nochmal,
mit Relationen sind einfach Teilmengen gemeint, das hatte ich am Donnerstga nicht verstanden. Ich habs jetzt mal versucht zu beweisen, das es [mm] 2^{n} [/mm] Relationen gibt, und zwar mir vollständiger I. :
Für 0 gilt ist die Aussage richtig, da nur die leere Menge dann eine Teilmenge ist. Weiter gilt:
[mm] 2^{n+1} [/mm] = [mm] 2*2^{n} [/mm]
Also verdoppelt sich die Anzahl der Relationen, wenn man ein Element zur Menge A hinzufügt. Und das scheint auch logisch, da man dieses neue Element jeder Menge genau einmal hinzufügen kann und so [mm] 2^{n} [/mm] neue Mengen erhält. Und zusammen mit den alten Mengen hat man dann [mm] 2*2^{n} [/mm] Mengen. Richtig so?
lg
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:59 Sa 03.11.2007 | | Autor: | koepper |
Guten Abend,
> mit Relationen sind einfach Teilmengen gemeint, das hatte
> ich am Donnerstga nicht verstanden. Ich habs jetzt mal
> versucht zu beweisen, das es [mm]2^{n}[/mm] Relationen gibt, und
> zwar mir vollständiger I. :
>
> Für 0 gilt ist die Aussage richtig, da nur die leere Menge
> dann eine Teilmenge ist. Weiter gilt:
>
> [mm]2^{n+1}[/mm] = [mm]2*2^{n}[/mm]
>
> Also verdoppelt sich die Anzahl der Relationen, wenn man
> ein Element zur Menge A hinzufügt. Und das scheint auch
> logisch, da man dieses neue Element jeder Menge genau
> einmal hinzufügen kann und so [mm]2^{n}[/mm] neue Mengen erhält. Und
> zusammen mit den alten Mengen hat man dann [mm]2*2^{n}[/mm] Mengen.
> Richtig so?
Deine Überlegungen sind absolut korrekt und damit hast du die Beweisidee gut verstanden.
LG
Will
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:38 So 04.11.2007 | | Autor: | toefte |
Supi. Dann auch hier nochmal hier ein dankeschön, Will.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:23 So 04.11.2007 | | Autor: | koepper |
Hallo toefte, bedanken darfst du dich hier bei angela.  LG Will
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:50 Do 01.11.2007 | | Autor: | koepper |
Guten Abend,
eine reflexive Relation auf A enthält alle n Elemente $(a | a)$ für $a [mm] \in [/mm] A$.
Aus den restlichen [mm] $n^2 [/mm] - n$ Elementen darfst du nun alle Teilmengen zählen.
Tipp: Die Menge aller Teilmengen einer Menge A heißt Potenzmenge. Sie enthält [mm] $2^n$ [/mm] Elemente.
Gruß
Will
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:58 Fr 02.11.2007 | | Autor: | ilfairy |
Hallo!
Ich habe es leider noch nicht ganz verstanden..
"eine reflexive Relation auf A enthält alle n Elemente [mm](a | a)[/mm] für [mm]a\in A[/mm]."
Damit meinst du einfach die Tatsache, dass es n Elemente gibt, die sich
auf sich selbst abbilden können?
"Aus den restlichen [mm]n^2 - n[/mm] Elementen darfst du nun alle Teilmengen zählen."
Hier wird die Anzahl dieser Elemente von der Anzahl der Elemente von
AxA abgezogen. Aber warum? Ich kann mir das irgendwie nicht bildlich vorstellen..
"Tipp: Die Menge aller Teilmengen einer Menge A heißt Potenzmenge. Sie enthält [mm]2^n [/mm] Elemente."
Ok.. also im Gesamten gibt es [mm]2^n [/mm] Relationen.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:37 Fr 02.11.2007 | | Autor: | koepper |
Hallo und guten Abend,
> "eine reflexive Relation auf A enthält alle n Elemente [mm](a | a)[/mm]
> für [mm]a\in A[/mm]."
>
> Damit meinst du einfach die Tatsache, dass es n Elemente
> gibt, die sich
> auf sich selbst abbilden können?
![[kopfkratz]](/images/smileys/kopfkratz.gif "[kopfkratz]") Nein, ich meine genau das, was ich geschrieben habe, und zwar wörtlich.
Es ist hier nicht notwendig, irgendein "abbilden" hineinzuinterpretieren.
Ich glaube, damit machst du dir das Verstehen nur selbst schwer.
Eine Relation ist schlicht eine Menge. Nichts weiter.
> "Aus den restlichen [mm]n^2 - n[/mm] Elementen darfst du nun alle
> Teilmengen zählen."
>
> Hier wird die Anzahl dieser Elemente von der Anzahl der
> Elemente von
> AxA abgezogen. Aber warum? Ich kann mir das irgendwie nicht
> bildlich vorstellen..
Da gibt es auch nichts vorzustellen. Die "größte" Relation, die es gibt, enthält alle [mm] $n^2$ [/mm] Elemente von $A [mm] \times [/mm] A.$
Jede Relation ist nun eine Teilmenge von $A [mm] \times [/mm] A$. Soll sie reflexiv sein, dann müssen die n Elemente $(a | a)$ für $a [mm] \in [/mm] A$ schonmal drin sein. Für die restlichen Elemente hast du also noch die Wahl aus wie vielen weiteren?
> "Tipp: Die Menge aller Teilmengen einer Menge A heißt
> Potenzmenge. Sie enthält [mm]2^n[/mm] Elemente."
>
> Ok.. also im Gesamten gibt es [mm]2^n[/mm] Relationen.
Nein. Ich sags nochmal genauer:
Eine Menge M mit n Elementen hat genau [mm] $2^n$ [/mm] verschiedene Teilmengen (einschließlich der leeren Menge und sich selbst).
und jetzt..... Think!
aber bitte nicht zu kompliziert, es ist sehr einfach
Gruß
Will
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:49 Mi 14.11.2007 | | Autor: | Wimme |
Huhu! :)
Ich möchte das auch nochmal nachvollziehen. Also so wie ich das verstanden habe, ist die Anzahl der Relationen einer Menge die Anzahl der Teilmengen ihrer Kreuzmenge?
Also wenn ich zB A mit 3 Elementen habe.
Dann hat A [mm] \times [/mm] A 9 Elemente. Dann gibt es doch [mm] 2^9 [/mm] Teilmengen.
Gibt es nun [mm] 2^9-1 [/mm] Relationen auf A (ich habe die leere Menge abgezogen)?
toefls (sorry, kann mich nicht genau an den Namen erinnern) Beitrag klang so, als wären es nur [mm] 2^3.
[/mm]
Danke!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:04 Di 20.11.2007 | | Autor: | koepper |
Hallo,
> Ich möchte das auch nochmal nachvollziehen. Also so wie ich
> das verstanden habe, ist die Anzahl der Relationen einer
> Menge die Anzahl der Teilmengen ihrer Kreuzmenge?
>
> Also wenn ich zB A mit 3 Elementen habe.
> Dann hat A [mm]\times[/mm] A 9 Elemente. Dann gibt es doch [mm]2^9[/mm]
> Teilmengen.
> Gibt es nun [mm]2^9-1[/mm] Relationen auf A (ich habe die leere
> Menge abgezogen)?
>
> toefls (sorry, kann mich nicht genau an den Namen erinnern)
> Beitrag klang so, als wären es nur [mm]2^3.[/mm]
nein, [mm] $2^9$ [/mm] ist richtig.
Gruß
Will
|
|
|
|
