f:M->M UND surjektiv(f) und |Urbild(f(1))| unendlich

[Björn Luck]

Hallo,

man hat mir folgende Aufgabe gestellt:

"Definieren Sie eine Abbildung f: N->N mit folgenden Eigenschaften:

(a) f ist surjektiv, und
(b) die Menge der Urbilder von 1 unter f hat unendlich viele Elemente."

Beim Nachdenken über diese Aufgabe bin ich zu dem Schluss gekommen, dass es
keine Lösung gibt. Ich habe geschrieben:

"Die Aufgabe ist nicht lösbar, da es keine Abbildung mit den geforderten
Eigenschaften gibt.

Beweis:

Zunächst ist bijektiv(f), da nach Voraussetzung surjektiv(f); ausserdem
injektiv(f), wie im Folgenden gezeigt.

Angenommen nicht injektiv(f).
Dann \EXIST x1, x2 (x1 != x2 UND f(x1) = f(x2) )

Daher |Df| > |Wf|. Ist ein Widerspruch, denn nach Aufgabenstellung ist Wf =
Df = N und daher |Df| = |Wf|.

Daher injektiv(f) und somit bijektiv(f).

Da bijektiv(f), hat jedes Element des Wertebereichs genau ein Urbild."

Allerdings bin ich bei den Recherchen zur Aufgabe auf Hilberts Grand Hotel
gestossen, in dem alle unendlich vielen Plätze belegt sind und das trotzdem
noch beliebig viele Gäste aufnehmen kann. Vermasselt das oder etwas anderes
meinen (versuchten) Beweis?

Anm.: N ist hier die Menge der nat. Zahlen. \EXIST ist der Existenzquantor.
!= heißt ungleich. UND ist die logische Konjuktion. Df und Wf sind
Definitions- und Wertebereich. |x| meint die Anzahl der Elemente der Menge
x.

Björn.

[Tjark Weber]

Post by Björn Luck
(a) f ist surjektiv, und
(b) die Menge der Urbilder von 1 unter f hat unendlich viele Elemente."
Beim Nachdenken über diese Aufgabe bin ich zu dem Schluss gekommen, dass
es keine Lösung gibt.

Du irrst.

Post by Björn Luck
"Die Aufgabe ist nicht lösbar, da es keine Abbildung mit den geforderten
Eigenschaften gibt.
Zunächst ist bijektiv(f), da nach Voraussetzung surjektiv(f); ausserdem
injektiv(f), wie im Folgenden gezeigt.
Angenommen nicht injektiv(f).
Dann \EXIST x1, x2 (x1 != x2 UND f(x1) = f(x2) )
Daher |Df| > |Wf|.

"Daher"?

Dein Beweis ist falsch; die Aussage, dass jede surjektive Abbildung
X -> X auch injektiv ist, stimmt nur, wenn X endlich ist.

Post by Björn Luck
Allerdings bin ich bei den Recherchen zur Aufgabe auf Hilberts Grand Hotel
gestossen, in dem alle unendlich vielen Plätze belegt sind und das
trotzdem noch beliebig viele Gäste aufnehmen kann. Vermasselt das oder
etwas anderes meinen (versuchten) Beweis?

Ja.

Tipp 1: Finde eine unendliche Teilmenge M von N, für die auch N\M unendlich
ist.

Tipp 2: Finde nun eine surjektive Abbildung g: M -> N.

Freundliche Grüße,

Tjark

[Hendrik van Hees]

Post by Björn Luck
Hallo,
(a) f ist surjektiv, und
(b) die Menge der Urbilder von 1 unter f hat unendlich viele
Elemente."

Wie wär's mit

f(x)=x/2 für x gerade, 1 sonst.

Die 0 ist natürlich gerade!

[unknown]

Post by Björn Luck
...
(a) f ist surjektiv, und
(b) die Menge der Urbilder von 1 unter f hat unendlich viele Elemente."
Beim Nachdenken über diese Aufgabe bin ich zu dem Schluss gekommen, dass
"Die Aufgabe ist nicht lösbar, da es keine Abbildung mit den geforderten
Eigenschaften gibt.
Zunächst ist bijektiv(f), da nach Voraussetzung surjektiv(f); ausserdem
injektiv(f), wie im Folgenden gezeigt.
Angenommen nicht injektiv(f).
Dann \EXIST x1, x2 (x1 != x2 UND f(x1) = f(x2) )
Daher |Df| > |Wf|. Ist ein Widerspruch, denn nach Aufgabenstellung ist Wf
= Df = N und daher |Df| = |Wf|.

So kannst du nur argumentieren, wenn es sich um endliche Mengen handelt.
Davon ist aber nicht die Rede.

Post by Björn Luck
Daher injektiv(f) und somit bijektiv(f).

nö.

Ist bei f: N->N das N die Menge der natürlichen Zahlen oder irgendeine
Menge?
Ist aber egal. Nehmen wir die natürlichen Zahlen:

Sei f(n) = n/2 , falls n gerade.
f(n) = 1 , falls n ungerade.

Somit sind die Voraussetzungen erfüllt.

Andreas

[Rainer Rosenthal]

"Björn Luck" schrieb

... nach Aufgabenstellung ist Wf = Df = N
und daher |Df| = |Wf|.
Df und Wf sind Definitions- und Wertebereich.
|x| meint die Anzahl der Elemente der Menge x

Hallo Björn,

die Anzahl der natürlichen Zahlen ist weniger
ein mathematisches als ein psychologisches Ding :-))

Gruss,
Rainer Rosenthal
***@web.de

[Horst Kraemer]

Post by Björn Luck
Hallo,
(a) f ist surjektiv, und
(b) die Menge der Urbilder von 1 unter f hat unendlich viele Elemente."
Beim Nachdenken über diese Aufgabe bin ich zu dem Schluss gekommen, dass es
"Die Aufgabe ist nicht lösbar, da es keine Abbildung mit den geforderten
Eigenschaften gibt.
Zunächst ist bijektiv(f), da nach Voraussetzung surjektiv(f); ausserdem
injektiv(f), wie im Folgenden gezeigt.
Angenommen nicht injektiv(f).
Dann \EXIST x1, x2 (x1 != x2 UND f(x1) = f(x2) )
Daher |Df| > |Wf|. Ist ein Widerspruch, denn nach Aufgabenstellung ist Wf =
Df = N und daher |Df| = |Wf|.
Daher injektiv(f) und somit bijektiv(f).
Da bijektiv(f), hat jedes Element des Wertebereichs genau ein Urbild."
Allerdings bin ich bei den Recherchen zur Aufgabe auf Hilberts Grand Hotel
gestossen, in dem alle unendlich vielen Plätze belegt sind und das trotzdem
noch beliebig viele Gäste aufnehmen kann. Vermasselt das oder etwas anderes
meinen (versuchten) Beweis?

Gut erkannt. Nimm eine beliebige bijektive Abbildung b:N->N.

Dann ist die folgendermaßen definierte Abbildung f:N->N

f(0) = 4711
f(n) = b(n-1) fuer n>0

weiterhin surjektiv, aber nicht injektiv, da der Wert 4711 jetzt an
zwei verschiedenen Stellen angenommen wird. Genau *das* ist Hilberts
Hotel.

Folgende 3 Aussagen sind aequivalent

1) M ist unendlich.

2) Es gibt eine surjektive Abbildung f:M->M, die nicht injektiv ist.

3) Es gibt injektive Abbildung g:M->M, die nicht surjektiv ist.


Man kann sogar leicht eine surjektive Abbildung einr Teilmenge M von N
in N konstruieren, in der *jeder* Funktionswert unendlich oft
angenommen wird (Sieb des Eratosthenes).

Definitionsbereich sei die Menge der natuerlichen Zahlen >=2

Setze

f(n) = i

fuer alle n, deren kleinster Primfaktor die Primzahl Nr. i (der
Groesse nach numeriert) ist. Da es fuer jede Primzahl p_i unendlich
viele natuerliche Zahlen gibt, deren kleinster Primfaktor p_i ist.
wird jedes i unendlich oft als Funktinswert angenommen.