Welche der folgenden Abbildungen sind surjektiv, welche injektiv?

Question

Aufgabe:

Sei N = {1, 2, 3, ...} die Menge der natürlichen Zahlen. Welche der folgenden Abbildungen sind surjektiv, welche injektiv?:

a) f: N→N, n ↦ ⌊√n⌋

b) f: N×N→N, (n,m) ↦ 2^n-1(2m-1)

c) f: N_≥2 := {2, 3, 4, 5, ...} → N, wobei f(n) die grösste Zahl, welche ein Teiler von n ist, und < n ist.

d) f: N → N_≥3, wobei f(n) = die Anzahl Buchstaben, welche die Zahl n in Deutsch beschreibt (Wortabstand zählt als 0).

Problem / Ansatz:

a) Man kann zeigen, dass die Funktion nicht injektiv ist mit einem Gegenbeispiel n₁=2 und n₂=3 ⇒f(2) = ⌊√2⌋ = 1 und f(3) = ⌊√3⌋ = 1. Jedoch weiss ich nicht ich vorgehen soll um zu zeigen, dass die Funktion surjektiv / nicht surjektiv ist.

b) Ich habe angenommen f(n, m) = f(a, b) wobei (n, m), (a, b) ∈ N×N sind. Dies führt zur Gleichung 2^n-1(2m-1) = 2^a-1(2b-1), aber ich weiss nicht ob dies zielführend ist. Auch hier weiss ich nicht wie ich zeigen kann, dass die Funktion surjektiv oder nicht surjektiv ist.

Bei c) und d) habe ich keine Ansätze.

Answer 1

a) Man kann zeigen, dass die Funktion nicht injektiv ist mit einem Gegenbeispiel n1=2 und n2=3 ⇒f(2) = ⌊√2⌋ = 1 und f(3) = ⌊√3⌋ = 1.  Gut !

Jedoch weiss ich nicht ich vorgehen soll um zu zeigen, dass die Funktion surjektiv / nicht surjektiv ist.

Sei n ∈ℕ. Dann gilt ⌊√(n^2)⌋ = n. Also gibt es mindestens ein m ( nämlich z.B. n^2 ) mit f(m)=n. ==>   f ist surjektiv.

b) Ich habe angenommen f(n, m) = f(a, b) wobei (n, m), (a, b) ∈ N×N sind. Dies führt zur Gleichung 2n-1(2m-1) = 2a-1(2b-1), aber ich weiss nicht ob dies zielführend ist.    2^(n-1)(2m-1) = 2^(a-1)(2b-1)

Doch, ist es:

1. Falls n=a dann ist 2m-1=2b-1 ==>  m=b und somit (a,b)=(n,m)

2. Falls n≠a dann ist einer von beiden der größere Wert. sagen wir a.

Dann kann man durch 2^(n-1) dividieren und hat

             2m-1= 2^(a-n)(2b-1)

Dies kann aber nicht sein, weil links eine ungerade und rechts eine

gerade Zahl steht. Also tritt immer Fall1 ein, f ist also injektiv.

Comments

Vielen Dank für Ihre Antwort! Wie würden Sie bei c) und d) vorgehen, um zu zeigen, dass die Abbildungen surjektiv / nicht surjektiv sind?