Abbildung auf Injektivität beweisen

Question

Zeigen Sie, dass die Abbildung

f : ℕ × (ℕ \ {0}) → ℕ, f(x,y) := (x+y)² + y

injektiv ist.

Mein Ansatz :

f(1,1) = (1+1)² +1 = 2² + 1 = 5

f(1,2) = (1+2)² + 2 = 3² + 2 = 11

f(2,1) = (2+1)² + 1 = 3² + 1 = 10

f(2,2) = (2+2)² + 2 = 4² + 2 = 18

f(2,3) = (2+3)² + 3 = 5² + 3 = 28

f(3,2) = (3+2)² + 2 = 5² + 2 = 27

Es gibt für jeden f(x,y) höchstens ein x,y-Wert, daher ist die Funktion injektiv.

Hoffe, dass der Ansatz stimmt. Falls nicht, würde ich mich auf Lösungsvorschläge freuen.

Comments

Die 0 liegt nicht im Definitionsbereich der zweiten Variablen und die -1 nicht in dem der ersten.
Diese Frage wurde gestern bereits gestellt.

---

Danke voll übersehen, aber der Ansatz mit anderen Zahlenwerten würde stimmen oder?

---

Wenn du tatsächlich zwei verschiedene Zahlenpaare findest, die auf die gleiche Zahl abgebildet werden, dann ist f nicht injektiv.

---

Also oben habe ich meinen Ansatz bearbeitet. Es ist tatsächlich so, dass die Zahlenpaare bei der Funktion nicht auf die gleiche Zahl abgebildet werden. Die Funktion ist auch für x,y ∈ ℕ streng monoton steigend, aus dem kann man auch überlegen, ob die Funktion injektiv ist.

Hoffe, dass ich richtig liege.

---

gelö\(\)scht

---

Also man kann ja anhand der Zahlenwerte begründen, dass die Funktion streng monoton steigend ist und dass es aus diesem Grund die Funktion injektiv sein muss, weil ja für höhere Werte von x,y auch f(x,y) mitwächst. Oder wie würden Sie es begründen ?

---

Die Sache mit der Monotonie reicht nicht als Begründung. Es könnte (im Prinzip) sein, dass eine Erhöhung von x durch ein Verringerung von y kompensiert werden kann.

---

Vielleicht kann man hier ähnlich einem Diagonalverfahren argumentieren.$$\begin{array}{c|cccccc}y&\vdots\\[6px]6&42\\[6px]5&30&41\\[6px]4&20&29&40&\ddots\\[6px]3&12&19&28&39\\[6px]2&6&11&18&27&38\\[6px]1&2&5&10&17&26&37&\cdots\\[3px]\hline\\[-9px]&0&1&2&3&4&5&x\end{array}$$Es gilt f(0,n) < f(n,1) und f(n-m,m+1) < f(n-m-1,m+2) für n ≥ 1 und 0 ≤ m < n.

---

Dies scheint mir ein brauchbarer Ansatz zu sein. Man kann so zeigen, dass man sämtliche (unendlich vielen) Einträge in der Funktionswerte-Tabelle so anordnen kann, dass die Werte eine streng monoton steigende Folge bilden und dass dabei wirklich jedes möglichen Eingangs-Zahlenpaar (x,y)  genau einmal verwendet wird.

Das Ganze aber so zu formulieren, dass daraus ein akzeptabler Beweis (z.B. durch vollständige Induktion) wird, erfordert aber noch einen gewissen Aufwand.

Die besagte streng monoton steigende Folge wäre

<2,5,6,10,11,12,17,18,19,20,26,27,28,29,30, .....>

welche man in die Abschnitte

<2> , <5,6> , <10,11,12> , <17,18,19,20> , <26,27,28,29,30> , .....

aufteilen kann. Dabei sind alle diese einzelnen Abschnitte Folgen aufeinander folgender natürlicher Zahlen. Der k-te Abschnitt beginnt mit der Zahl  k²+1 und endet mit der Zahl k² + k .

---

Ich habe mir nun noch einen Algorithmus für die Umkehrfunktion gebastelt.

Es sei also eine beliebige natürliche Zahl n gegeben. Gesucht ist das Paar (x,y) mit f(x,y) = n  (falls überhaupt so eines existiert).

(1.) Berechne den Wert   k:= ⌊\( \sqrt{n} \) ⌋

(2.) Falls  k² < n ≤ k² + k , dann  ist  y:= n - k²  und  x:= k - y

Sind nicht beide unter (2.) geforderten Ungleichungen erfüllt, so war n keine Zahl, die als Funktionswert von f  in Frage kommt.

Answer 1

hallo

löse die Gleichung  (x+y)2 + y=n nach x auf und zeige dass es zu jedem y maximal ein positives ganze x gibt

Gruß lul

Comments

Könntest du das etwas näher erläutern? Inwiefern ist damit Injektivität gezeigt?

---

Vielleicht sagst du, was injektiv bedeutet , wenn man von N^2 nach N abbildet?

---

Zu zeigen ist wohl, dass es zu jedem n ∈ ℕ höchstens ein Zahlenpaar (x,y) ∈ ℕ × (ℕ \ {0}) mit f(x,y) = n gibt. Was du geschrieben hast, hat damit nichts zu tun.

---

Er muss wahrscheinlich nochmal nachschlagen, was Injektivität bedeutet.

---

löse die Gleichung (x+y)2 + y=n nach x auf und zeige dass es zu jedem y maximal ein positives ganze x gibt

\(x=\sqrt{n-y}-y\). Vielleicht sagst du, wie es weiter geht?

---

Vielleicht könnte man das Beispiel in 2.Fällen unterscheiden :

1.Fall : n = y

y=(x+y)^2+y → 0 = (x+y)^2 / √ → x = -y (Somit ist x für alle natürliche Zahlen definiert)

2.Fall : n = x

x = (x+y)^2 + y → y^2 + (2x+1)*y + (x^2-x) = 0

In Lösungsformel eingesetzt, bekommt man für Diskriminante : (2x+1)^2-4*(x^2-x)

----> Ist für alle natürliche Zahlen definiert.

Die Umkehrbildung im gegebenen Definition und Wertebereich ist möglich → Die Funktion ist im gegebenen Definition und Wertebereich injektiv.

Also anders wüsste ich nicht, wie ich die Gleichung lösen soll.

Answer 2

Hallo,

ich greife mal die Idee mit dem Diagonalverfahren auf (Ich hoffe, ich wiederhole jetzt nichts):

Sei \((x,y) \neq (p,q)\), setzte \(z:=x+y, r:=p+q\).

FALL \(z=r\): Dann ist \(y \neq q\) (sonst auch \(x=p\)) und

$$f(x,y)=z^2+y=r^2+y \neq r^2+q=f(p,q)$$

FALL \(z \neq r\): Dann sei oBdA \(z \geq r+1\) und

$$f(x,y)=z^2+y \geq r^2+2r+1>r^2+2q \geq r^2+q=f(p,q)$$

Also in beiden Fällen \(f(x,y) \neq f(p,q)\).

Comments

Danke. Das ist ein sauberer Beweis für die Injektivität. Ich sehe aber nicht so recht, in welcher Weise das mit dem "Diagonalverfahren" zu tun hat, außer dass die dort verwendeten Schräg- oder Diagonalzeilen durch Gleichungen der Form  x + y = const  beschrieben werden.

---

Die Idee wird insofern verwendet als die Fallinterscheidung ist: Liegen beide Punkte auf derselben Diagonale oder nicht.