Bijektion < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:24 Di 22.11.2005 | | Autor: | Becks |
Hallo zusammen!
Ich habe ein Problem bei folgender Aufgabenstellung, vielleicht könnt ihr mir ja nen kleinen Tipp geben, wie ich das beweisen kann.
Also sei E = {X | X [mm] \subseteq \IN_{0}, [/mm] X endlich } die Menge aller endlichen Teilmengen von [mm] \IN_{0}. [/mm] Wir definieren f: E [mm] \to \IN_{0} [/mm] durch f( [mm] \emptyset) [/mm] = 0 und f(X) = [mm] \summe_{x \in X} 2^{x} [/mm] für [mm] \emptyset \not= [/mm] X [mm] \in [/mm] E. Zeigen Sie, dass f eine Bijektion von E auf [mm] \IN_{0} [/mm] ist.
Als Hinweis wurde uns die Frage gegeben: Warum ist die Binärdarstellung einer natürlichen Zahl eindeutig?
Bijektiv ist es ja, wenn für jedes X es ein eindeutiges f(X) gibt.
Hmm, aber ich weiß nicht, was ich da machen soll.
MFG Becks
|
|
| |
|
Hallo!!Also Bijektiv ist wenn die Funktion surjektiv und injektiv ist.Also
surjektiv heißt,dass deine ganze Wertemenge getroffen wird und injektiv bedeutet,dass jedem element deiner Definitionsmenge genau ein element der wertemenge zugeordnet wird.
also: [mm] f(x_{1}) \ne f(x_{2}) [/mm] wenn [mm] x_{1} \ne x_{2} [/mm] und
img(D)=W
also. f(X) = [mm] \summe_{x \in X} 2^{x} [/mm]
Diese Funktion stellt im Prinzip die Darsterllung einer Zahl a [mm] \in [/mm] N dar.Es kann jede natürliche Zahl als Binärdarstellung dargestellt werden=> Die Funktion muss völlig surjektiv sein und wenn jede Darstellung eindeutig ist,also dass es für eine Zahl nur eine Darstellung gibt dann ist die Abbildung auch injektiv was wir vermuten:
Versuchen wir es mathematisch zu formulieren:
injektiv: f(X_ {1}) [mm] \ne f(X_{2}) [/mm] wenn X1 [mm] \ne [/mm] X2
X1 := {1,2,3,4,5,...,n1} X2:={1,2,3,4,5,....,n2} wobei n2>n1 können wir annehmen
f(X1)= [mm] \summe_{i=1}^{n1}2^n [/mm] und f(X2)= [mm] \summe_{i=1}^{n2}2^n
[/mm]
X1 [mm] \ne [/mm] X2 da X1 zwar eine Teilmenge von X2 jedoch nicht umgekehrt  !!
=> [mm] 2+2^2+2^3,...,2^{n1}=2+2^2+2^3,...,2^{n2}
[/mm]
Jetzt kürzt sich links alles weg da jerder wert bis n1<n2 auch links steht!!
=> [mm] 0=2^{n1+1}+...+2^{n2} [/mm] Und das ist falsch denn eine endliche summe von [mm] 2^n [/mm] ist immer positiv..
Hast du jetzt eine Idee bekommen???mfg daniel
|
|
|
|
