Fixpunkt einer Involution < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 00:32 Mo 03.11.2008 | | Autor: | pelzig |
Hallo,
Ich suche einen besonders schönen und kurzen Beweis für folgende Aussage:
| Aufgabe | Ist X eine endliche Menge und $|X|$ ungerade, sowie [mm] $f:X\to [/mm] X$ eine ![[]](/images/popup.gif) Involution, so besitzt $f$ einen Fixpunkt |
[Dateianhang nicht öffentlich]
Falls jemand da was schönes kennt würd ich mich freuen davon zu erfahren.
Gruß, Robert
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 02:10 Mo 03.11.2008 | | Autor: | Marcel |
Hallo Robert,
> Hallo,
>
> Ich suche einen besonders schönen und kurzen Beweis für
> folgende Aussage:
>
> Ist X eine endliche Menge und [mm]|X|[/mm] ungerade, sowie [mm]f:X\to X[/mm]
> eine
> Involution,
> so besitzt [mm]f[/mm] einen Fixpunkt
> [Dateianhang nicht öffentlich]
>
> Falls jemand da was schönes kennt würd ich mich freuen
> davon zu erfahren.
>
> Gruß, Robert
ein möglicher (Edit:) Beweisansatz könnte so aussehen:
Wir betrachten die Menge [mm] $\text{NFP}$ [/mm] der Nicht-Fix-Punkte, also [mm] $$\text{NFP}:=\{x \in X:\; x \not=f(x)\}\,.$$
[/mm]
Überlege Dir nun, dass (für alle $x [mm] \in [/mm] X$ gilt:) $x [mm] \in \text{NFP}$ $\gdw$ [/mm] $f(x) [mm] \in \text{NFP}\,.$ [/mm] Und in einem (und damit jedem) der beiden Fälle(n) ist $x [mm] \not=f(x)\,.$
[/mm]
Überlege Dir damit, dass
[mm] $$\text{NFP}=\bigcup_{x \in \text{NFP}} \left(\{x\} \overset{d}{\cup}\{f(x)\}\right)\,.$$
[/mm]
Und damit besteht [mm] $\text{NFP}$ [/mm] aus einer geraden Anzahl von Elementen. [mm] $\black{X}$ [/mm] enthält eine ungerade Anzahl von Elementen, und [mm] $\text{NFP}$ [/mm] enthält eine gerade Anzahl von Elementen. Weil [mm] $\text{NFP}$ [/mm] aber eine Teilmenge von [mm] $\black{X}$ [/mm] ist, enthält [mm] $\text{NFP}$ [/mm] aber insbesondere höchtens genausoviele Elemente wie [mm] $\black{X}$ [/mm] (beachte die Endlichkeit der Menge [mm] $\black{X}$). $\text{NFP}$ [/mm] muss also mindestens ein Element weniger enthalten als [mm] $\black{X}$ [/mm] oder anders ausgedrückt:
[mm] $$\exists x_0 \in [/mm] X$: [mm] $x_0 \notin \text{NFP}\,.$$
[/mm]
Das bedeutet aber, dass [mm] $x_0 \in [/mm] X$ ein Fixpunkt für [mm] $\black{f}$ [/mm] ist.
P.S.:
Falls Du nun ein wenig irritiert bist und Dich fragst, wo man denn da bitteschön überhaupt die Involution benötigt:
Du brauchst sie beim Beweis von $x [mm] \in \text{NFP}$ $\gdw$ [/mm] $f(x) [mm] \in \text{NFP}\,.$
[/mm]
(Und wenn mich nicht alles täuscht, brauchst Du eigentlich da auch nur die Beweisrichtung [mm] '$\Rightarrow$'.)
[/mm]
P.P.S.:
Die Kurzfassung des Beweises wäre:
Beweise, dass [mm] $$\text{NFP}=\bigcup_{x \in X: \; f(x) \not=x} \left(\{x\} \overset{d}{\cup}\{f(x)\}\right)\,,$$
[/mm]
und begründe damit, dass [mm] $|\text{NFP}|$ [/mm] gerade ist.
(Wobei [mm] $\overset{d}{\cup}$ [/mm] "disjunkt vereinigt" bedeutet; beachte dabei: bei [mm] $\bigcup_{x \in X: \; f(x) \not=x} \left(\{x\} \overset{d}{\cup}\{f(x)\}\right)$ [/mm] bezieht sich dass nur auf die inneren Vereinigungen. Es geht mir nur darum, dass [mm] $\text{NFP}=\bigcup_{x \in \text{NFP}} [/mm] A(x)$, wobei jede Menge [mm] $A(x)=\{x,f(x)\}$ [/mm] (für $x [mm] \in \text{NFP}$) [/mm] dann genau zweielementig ist.
Ich sehe gerade übrigens, dass man noch einen Beweisschritt ergänzen muss:
Und zwar muss man an geeigneter Stelle irgendwo schreiben, dass für $x,y [mm] \in \text{NFP}$ [/mm] entweder [mm] $\{x,f(x)\} \cap \{y,f(y)\}= \emptyset$, [/mm] oder [mm] $\{x,f(x)\}=\{y,f(y)\}$ [/mm] gilt. Das braucht man schon bei diesem Beweisaufbau, um folgern zu können, dass [mm] $\text{NFP}$ [/mm] aus einer geraden Anzahl von Elementen besteht.
Wenn man dies nicht hätte, so überlegen wir uns mal folgendes: Seien [mm] $x_1,x_2$ [/mm] beides Nicht-Fix-Punkte. Dann bilden wir [mm] $\{x_1,f(x_1)\}$ [/mm] und [mm] $\{x_2,f(x_2)\}$ [/mm] und vereinigen diese und nehmen diese neu entstandene Teilmenge in [mm] $\text{NFP}$ [/mm] auf. Die Menge [mm] $\{x_1,f(x_1),x_2,f(x_2)\}$ [/mm] könnte dann aber aus [mm] $\black{2}, [/mm] 3$ oder [mm] $\black{4}$ [/mm] Elementen bestehen. Und [mm] $\black{3}$ [/mm] wäre schlecht. Die Ergänzung hilft uns dann aber, zu erkennen, dass [mm] $|\text{NFP}|$ [/mm] auch wirklich gerade ist.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 07:33 Mo 03.11.2008 | | Autor: | pelzig |
Jaja das ist schon ganz nett. Im Grunde hälst du es wie dieses Bildchen, ich hatte das nur bisher noch nicht so kompakt aufgeschrieben. Ich hatte mir schon mal überlegt dazu die Äquivalenzrelation [mm] $x\sim y\gdw x=f(y)\vee [/mm] x=y$ zu betrachten, dir mir X genau in diese Pärchen zerlegt, aber man muss halt dann trotzdem noch zeigen, dass das eine ÄR ist und dass die AK höchstens zweielementig sind, das finde ich ein bisschen frickelig.
Eine andere Idee die mir Grad kommt wäre Induktion über die Anzahl der Elemente. Im Induktionsschritt nimmt man sich ein beliebiges Element [mm] $x_0$ [/mm] raus. Ist [mm] $x_0$ [/mm] kein FP, so bilde [mm] $X_0:=X\setminus \{x_0, f(x_0)\}$, [/mm] zeige dass [mm] $f|_{X_0}$ [/mm] auch involutorisch ist und wende die IV an. Schätze das klappt auch. However... ich geh noch ne Runde schlafen 
Gruß, Robert
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:13 Mo 03.11.2008 | | Autor: | fred97 |
Das klappt bestens !
FRED
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:53 Mo 03.11.2008 | | Autor: | Marcel |
Hallo,
> Jaja das ist schon ganz nett. Im Grunde hälst du es wie
> dieses Bildchen, ich hatte das nur bisher noch nicht so
> kompakt aufgeschrieben. Ich hatte mir schon mal überlegt
> dazu die Äquivalenzrelation [mm]x\sim y\gdw x=f(y)\vee x=y[/mm] zu
> betrachten, dir mir X genau in diese Pärchen zerlegt, aber
> man muss halt dann trotzdem noch zeigen, dass das eine ÄR
> ist und dass die AK höchstens zweielementig sind, das finde
> ich ein bisschen frickelig.
warum findest Du das frickelig? Du hast hier ja alle Äquivalenzklassen gegeben durch [mm] $$[x]=\{y \in X:\;x=y \text{ oder }f(x)=y\}\,\;\;\;\text{(}\forall\x x\in X\text{)}\,.$$ [/mm]
Angenommen, eine dieser Äquivalenzklassen bestünde aus echt mehr als zwei Elementen. Sei also [mm] $x_0 \in [/mm] X$ so, dass [mm] $[x_0]$ [/mm] mindestens drei Elemente hätte. Insbesondere ist [mm] $x_0 \in [x_0]$. [/mm] Ist also [mm] $\{x_0,y,z\} \subseteq [x_0]$ [/mm] und dabei die linke Teilmenge dreielementig, so sind [mm] $x_0,y,z$ [/mm] paarweise verschieden. Dann gilt aber wegen $y,z [mm] \in [x_0]$ [/mm] insbesondere $f(y) [mm] =f(x_0)$ [/mm] und $f(z) [mm] =f(x_0)\,,$ [/mm] also $f(y)=f(z)$ für $y [mm] \not=z\,.$ [/mm] Das widerspräche aber der Injektivität von [mm] $\black{f}\,,$ [/mm] denn [mm] $\black{f}$ [/mm] ist als Involution insbesondere injektiv.
Oder hängst Du irgendwo, wenn Du nachrechnen willst, dass das eine ÄR auf [mm] $\black{X}$ [/mm] ist?
> Eine andere Idee die mir Grad kommt wäre Induktion über die
> Anzahl der Elemente. Im Induktionsschritt nimmt man sich
> ein beliebiges Element [mm]x_0[/mm] raus. Ist [mm]x_0[/mm] kein FP, so bilde
> [mm]X_0:=X\setminus \{x_0, f(x_0)\}[/mm], zeige dass [mm]f|_{X_0}[/mm] auch
> involutorisch ist und wende die IV an. Schätze das klappt
> auch. However... ich geh noch ne Runde schlafen
Wie Fred schon sagte: Das sollte eigentlich alles wunderbar klappen
Gruß,
Marcel
|
|
|
|
