Äquivalenzklassen < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:43 Sa 07.05.2011 | | Autor: | janisE |
| Aufgabe | Seien f : {1,..,m} -> {1,..,n} und g : {1,..,m} -> {1,..,n} Abbildungen.
f,g sind [mm]S_m[/mm] rechtsäquivalent [mm]\Leftrightarrow \exists \; \pi \in S_m : f(\pi(i)) = g(i) \; \forall i \in \{1,\cdots,m\}[/mm].
Bestimmen Sie die Anzahl der Äquivalenzklassen der
a) injektiven
b) surjektiven
c) bijektiven
Abbildungen von {1,..,m} nach {1,..,n} |
Hallo!
Irgendwie verwirrt mich die Aufgabe total, und ich komme nicht weiter.
Theoretisch ist mir klar, was Äquivalenzklassen sind, jedoch ist hier ja keine Definition einer Äquivalenzrelation gegeben. Und rein die Anzahl der injektiven, surjektiven und Bijektiven Abbildungen ist wahrscheinlich nicht gemeint, oder?
Könnt ihr mir bitte helfen die Aufgabe zu verstehen?
Danke im Voraus!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:04 So 08.05.2011 | | Autor: | felixf |
Moin!
> Seien f : {1,..,m} -> {1,..,n} und g : {1,..,m} -> {1,..,n}
> Abbildungen.
>
> f,g sind [mm]S_m[/mm] rechtsäquivalent [mm]\Leftrightarrow \exists \; \pi \in S_m : f(\pi(i)) = g(i) \; \forall i \in \{1,\cdots,m\}[/mm].
>
> Bestimmen Sie die Anzahl der Äquivalenzklassen der
>
> a) injektiven
> b) surjektiven
> c) bijektiven
>
> Abbildungen von {1,..,m} nach {1,..,n}
>
> Hallo!
>
> Irgendwie verwirrt mich die Aufgabe total, und ich komme
> nicht weiter.
>
> Theoretisch ist mir klar, was Äquivalenzklassen sind,
Gut.
> jedoch ist hier ja keine Definition einer
> Äquivalenzrelation gegeben.
Doch:
> f,g sind [mm]S_m[/mm] rechtsäquivalent [mm]\Leftrightarrow \exists \; \pi \in S_m : f(\pi(i)) = g(i) \; \forall i \in \{1,\cdots,m\}[/mm].
Das ist ganz offenbar eine Aequivalenzrelation auf der Menge der Funktionen [mm] $\{ 1, \dots, m \} \to \{ 1, \dots, n \}$.
[/mm]
> Und rein die Anzahl der
> injektiven, surjektiven und Bijektiven Abbildungen ist
> wahrscheinlich nicht gemeint, oder?
Du sollst die Anzahl der Aequivalenzklassen solcher Funktionen zaehlen.
Dazu bietet es sich an, sich fuer jede Aequivalenzklasse eine "Normalform" zu ueberlegen. Wenn z.B. $m = 2$ und $n [mm] \ge [/mm] 2$ ist und du die Funktionen $f$ mit $f(1) = 1$, $f(2) = 2$ und die $g$ mit $g(1) = 2$, $g(2) = 1$ hast, dann sind diese [mm] $S_2$-rechtsaequivalent [/mm] (warum?), allerdings ist $f$ "schoener".
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:14 So 08.05.2011 | | Autor: | janisE |
Erst einmal Danke für die schnelle Antwort!
> > jedoch ist hier ja keine Definition einer
> > Äquivalenzrelation gegeben.
>
> Doch:
>
> > f,g sind [mm]S_m[/mm] rechtsäquivalent [mm]\Leftrightarrow \exists \; \pi \in S_m : f(\pi(i)) = g(i) \; \forall i \in \{1,\cdots,m\}[/mm].
>
> Das ist ganz offenbar eine Aequivalenzrelation auf der
> Menge der Funktionen [mm]\{ 1, \dots, m \} \to \{ 1, \dots, n \}[/mm].
Für eine Äquivalenzrelation benötige ich ja eine einparametrige (d.h. unterscheidbare, klassifizierbare) Relation, die die Ursprungsmenge in disjunkte Teilmengen partitioniert.
Sind dann also alle Funktionen [mm]\{ 1, \dots, m \} \to \{ 1, \dots, n \}[/mm] in einer Äquivalenzklasse, die unter dem selben [mm]\pi[/mm]rechtsäquivalent sind? (Das kann eigentlich auf Grund der vorausgesetzten Transitivität für Äquivalenzrelationen nicht sein, oder?) Dann eher mit m als Parameter, oder?
Was wäre dann mit den nicht rechtsäquivalenten Funktionen?
Auf jeden Fall müsste ich für den Parameter noch zeigen, dass er die Menge der Funktionen in wirklich disjunkte Teilmengen teilt, oder?
> Du sollst die Anzahl der Aequivalenzklassen solcher
> Funktionen zaehlen.
>
> Dazu bietet es sich an, sich fuer jede Aequivalenzklasse
> eine "Normalform" zu ueberlegen. Wenn z.B. [mm]m = 2[/mm] und [mm]n \ge 2[/mm]
> ist und du die Funktionen [mm]f[/mm] mit [mm]f(1) = 1[/mm], [mm]f(2) = 2[/mm] und die
> [mm]g[/mm] mit [mm]g(1) = 2[/mm], [mm]g(2) = 1[/mm] hast, dann sind diese
> [mm]S_2[/mm]-rechtsaequivalent (warum?), allerdings ist [mm]f[/mm]
> "schoener".
f ist [mm]S_2[/mm]-rechtsäquivalent mit [mm]\pi = (1) = id[/mm] und g mit [mm]\pi = (12)[/mm]
was meinst du mit "f sei schöner"?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:07 Mo 09.05.2011 | | Autor: | felixf |
Moin!
> Erst einmal Danke für die schnelle Antwort!
>
> > > jedoch ist hier ja keine Definition einer
> > > Äquivalenzrelation gegeben.
> >
> > Doch:
> >
> > > f,g sind [mm]S_m[/mm] rechtsäquivalent [mm]\Leftrightarrow \exists \; \pi \in S_m : f(\pi(i)) = g(i) \; \forall i \in \{1,\cdots,m\}[/mm].
>
> >
> > Das ist ganz offenbar eine Aequivalenzrelation auf der
> > Menge der Funktionen [mm]\{ 1, \dots, m \} \to \{ 1, \dots, n \}[/mm].
>
> Für eine Äquivalenzrelation benötige ich ja eine
> einparametrige (d.h. unterscheidbare, klassifizierbare)
> Relation, die die Ursprungsmenge in disjunkte Teilmengen
> partitioniert.
Was die Relation $f [mm] \sim [/mm] g [mm] :\Leftrightarrow [/mm] f [mm] \text{ und } [/mm] g [mm] \text{ sind } S_m\text{-rechtsaequivalent} \Leftrightarrow \exists \sigma \in S_m \forall [/mm] i [mm] \in \{ 1, \dots, m \} [/mm] : [mm] f(\sigma(i)) [/mm] = g(i)$ auch tut.
> Sind dann also alle Funktionen [mm]\{ 1, \dots, m \} \to \{ 1, \dots, n \}[/mm]
> in einer Äquivalenzklasse, die unter dem selben
> [mm]\pi[/mm]rechtsäquivalent sind? (Das kann eigentlich auf Grund
> der vorausgesetzten Transitivität für
> Äquivalenzrelationen nicht sein, oder?)
Nein, die Aequivalenzklasse von $f$ ist durch [mm] $\{ f \circ \sigma \mid \sigma \in S_m \}$ [/mm] gegeben.
> Dann eher mit m
> als Parameter, oder?
> Was wäre dann mit den nicht rechtsäquivalenten
> Funktionen?
Die Funktionen $f(1) = 1$, $f(2) = 2$ und $f(1) = 1$, $f(2) = 3$ sind nicht rechtsaequivalent. Ebensowenig $f$ und $h(1) = 1$, $h(2) = 1$. (Hier sind $f, g, h : [mm] \{ 1, 2 \} \to \{ 1, 2, 3 \}$.)
[/mm]
> Auf jeden Fall müsste ich für den Parameter noch zeigen,
Was fuer ein Parameter? Meinst du das [mm] $\pi$? [/mm] Das ist kein Parameter, sondern eine gebundene Variable dank dem Existenzquantor davor.
> dass er die Menge der Funktionen in wirklich disjunkte
> Teilmengen teilt, oder?
>
> > Du sollst die Anzahl der Aequivalenzklassen solcher
> > Funktionen zaehlen.
> >
> > Dazu bietet es sich an, sich fuer jede Aequivalenzklasse
> > eine "Normalform" zu ueberlegen. Wenn z.B. [mm]m = 2[/mm] und [mm]n \ge 2[/mm]
> > ist und du die Funktionen [mm]f[/mm] mit [mm]f(1) = 1[/mm], [mm]f(2) = 2[/mm] und die
> > [mm]g[/mm] mit [mm]g(1) = 2[/mm], [mm]g(2) = 1[/mm] hast, dann sind diese
> > [mm]S_2[/mm]-rechtsaequivalent (warum?), allerdings ist [mm]f[/mm]
> > "schoener".
> f ist [mm]S_2[/mm]-rechtsäquivalent mit [mm]\pi = (1) = id[/mm] und g mit
> [mm]\pi = (12)[/mm]
>
> was meinst du mit "f sei schöner"?
$f$ ist monoton steigend. (Hier sogar streng monoton.)
Du kannst dir ueberlegen, dass es zu jeder Funktion eine aequivalente gibt, die monoton steigend ist. Wieviele aequivalente, monoton steigende Funktionen gibt es zu einer festen Funktion?
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 08:41 Mo 09.05.2011 | | Autor: | janisE |
> > > > jedoch ist hier ja keine Definition einer
> > > > Äquivalenzrelation gegeben.
> > >
> > > Doch:
> > >
> > > > f,g sind [mm]S_m[/mm] rechtsäquivalent [mm]\Leftrightarrow \exists \; \pi \in S_m : f(\pi(i)) = g(i) \; \forall i \in \{1,\cdots,m\}[/mm].
>
> >
> > >
> > > Das ist ganz offenbar eine Aequivalenzrelation auf der
> > > Menge der Funktionen [mm]\{ 1, \dots, m \} \to \{ 1, \dots, n \}[/mm].
>
> >
> > Für eine Äquivalenzrelation benötige ich ja eine
> > einparametrige (d.h. unterscheidbare, klassifizierbare)
> > Relation, die die Ursprungsmenge in disjunkte Teilmengen
> > partitioniert.
>
> Was die Relation [mm]f \sim g :\Leftrightarrow f \text{ und } g \text{ sind } S_m\text{-rechtsaequivalent} \Leftrightarrow \exists \sigma \in S_m \forall i \in \{ 1, \dots, m \} : f(\sigma(i)) = g(i)[/mm]
> auch tut.
>
> > Sind dann also alle Funktionen [mm]\{ 1, \dots, m \} \to \{ 1, \dots, n \}[/mm]
> > in einer Äquivalenzklasse, die unter dem selben
> > [mm]\pi[/mm]rechtsäquivalent sind? (Das kann eigentlich auf Grund
> > der vorausgesetzten Transitivität für
> > Äquivalenzrelationen nicht sein, oder?)
>
> Nein, die Aequivalenzklasse von [mm]f[/mm] ist durch [mm]\{ f \circ \sigma \mid \sigma \in S_m \}[/mm]
> gegeben.
Also, was ich meine ist Folgendes (soweit mein Verständnis): Eine Äquivalenzrelation teilt eine Ursprungsmenge in disjunkte Teilmengen (Äquivalenzklassen). Die zu einem Element x gehörende Äquivalenzklasse A enthält nun alle die Objekte, die nach der Äquivalenzrelation äquivalent zu x sind. Soweit richtig?
Wenn dies so ist, muss es einen Faktor geben, der die Klassen trennt. Von der Aufgabe her würde ich sagen es gibt die Klassen "[mm]S_m[/mm]-rechtsäquivalent" und nicht rechtsäquivalent. Aber das macht ja keinen Sinn, denn dann wäre die Aufgabe beendet ohne richtig begonnen zu haben. Also wo liegt mein Denkfehler?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:35 Mo 09.05.2011 | | Autor: | felixf |
Moin!
> > > Sind dann also alle Funktionen [mm]\{ 1, \dots, m \} \to \{ 1, \dots, n \}[/mm]
> > > in einer Äquivalenzklasse, die unter dem selben
> > > [mm]\pi[/mm]rechtsäquivalent sind? (Das kann eigentlich auf Grund
> > > der vorausgesetzten Transitivität für
> > > Äquivalenzrelationen nicht sein, oder?)
> >
> > Nein, die Aequivalenzklasse von [mm]f[/mm] ist durch [mm]\{ f \circ \sigma \mid \sigma \in S_m \}[/mm]
> > gegeben.
>
> Also, was ich meine ist Folgendes (soweit mein
> Verständnis): Eine Äquivalenzrelation teilt eine
> Ursprungsmenge in disjunkte Teilmengen
> (Äquivalenzklassen). Die zu einem Element x gehörende
> Äquivalenzklasse A enthält nun alle die Objekte, die nach
> der Äquivalenzrelation äquivalent zu x sind. Soweit
> richtig?
Ja.
> Wenn dies so ist, muss es einen Faktor geben, der die
> Klassen trennt. Von der Aufgabe her würde ich sagen es
> gibt die Klassen "[mm]S_m[/mm]-rechtsäquivalent" und nicht
> rechtsäquivalent.
Was meinst du mit "nicht rechtsaequivalent"?
Die Aequivalenzrelation ist hier [mm] "$S_m$-rechtsaequivalent [/mm] sein". Entweder zwei Funktionen sind [mm] $S_m$-rechtsaequivalent, [/mm] oder sie sind nicht [mm] $S_m$-rechtsaequivalent.
[/mm]
> Aber das macht ja keinen Sinn, denn dann
Wieso das?
> wäre die Aufgabe beendet ohne richtig begonnen zu haben.
> Also wo liegt mein Denkfehler?
Ich kann ehrlich gesagt nicht nachvollziehen, was du nicht verstehst / wo du falsch denkst.
LG Felix
|
|
|
|
