2m+n surjektiv, injektiv?

Question

Aufgabe:Gegeben die Funktion f : ℕ × {2, 3} → ℕ, f(m, n) = 2m + n. Beweisen oder widerlegen Sie:

(i) f ist injektiv

(ii) f ist surjektiv

Problem/Ansatz:

Wie gehe ich hier vor?

injektiv heißt doch, dass jeder x wert aus dem Definitionsbereich höchstens einen Wert y aus dem Wertebereich besitzt.

und surjektiv das selbe mit mindestens.

Ich weiß nicht, wie ich hier anfangen soll.

Comments

"injektiv heißt doch, dass jeder x wert aus dem Definitionsbereich höchstens einen Wert y aus dem Wertebereich besitzt.

und surjektiv das selbe mit mindestens."

Nein!

Injektiv heißt, dass es zu jedem y des Wertebereichs höchstens ein
x im Definitionsbereich gibt, das auf y abgebildet wird.

Surjektiv heißt, dass es zu jedem y des Wertebereichs mindestens
ein x gibt, das auf dieses y abgebildet wird.

Answer 1

Surjektivität: Hier musst du überprüfen, ob jeder Wert aus dem Wertebereich der Funktion (in deinem Fall ob jede natürliche Zahl) angenommen wird. Das ist nicht der Fall, denn es wird nicht auf die 1 abgebildet.

Injektivität: Die Aussage "jedem x-Wert wird höchstens ein y- Wert zugewiesen" ist nicht ganz korrekt. Diese Aussage gilt für alle Funktionen, da für jede Funktion f gilt. Jedem x aus dem Definitionsbereich wird genau ein f(x) aus dem Wertebereich zugeordnet.

Die richtige Definition könnte man wie folgt formulieren: Zwei unterschiedliche Werte aus dem Definitionsbereich: zB x und y

bilden auf unterschiedliche Funktionwert f(x) und f(y) ab.

in Quantorenschreibweise: ∀x,y ∈D : x≠y ⇒ f(y)≠ f(x)

Hier bietet es sich an die Äquivalente Aussage : ∀f(x),f(y) ∈D: f(x) = f(y) ⇒ y=x

Sei also f(x)=2 * m + n  und f(y)= 2* k + l beliebig mit :

2 * m + n = 2* k + l daraus folgt schon direkt l = n , da diese nur die Werte 2 und 3 annehmen können und angenommen es wird einmal 2 und einmal 3 angenommen, so gilt die Gleichheit oben nicht mehr da eine Seite gerade und die andere seite ungerade wird. Also gilt l =n.

⇒ 2*m = 2*k da sieht man sofort, dass m = k gelten muss und somit gilt: (m,n)=x =y = (k,l).

Ich hoffe ich konnte dir weiterhelfen.

LG

Comments

Danke dir. Aber wie beweise ich denn dass die Fkt. nicht surjektiv ist, mit einem Gegenbeispiel?

---

Ist das so richtig?

Nicht surjektiv: 2m + n = y ⇔ 2m = y-n ⇔m =  \( \frac{y-n}{2} \)

Gegenbeispiel: y = 2, n = 2

Für y = 2, n = 2 ist \( \frac{2-2}{2}\) = 0/2 = 0, aber 0 ≠ 2 ∧ 0 ≠ 3.

⇒ Nicht surjektiv.

---

Zur Surjektivität habe ich am anfang der Antwort was geschrieben ;)

---

Ja, das habe ich gelesen. Du sagtest, dass auf die 1 nicht abgebildet wird. Und ich habe doch gezeigt, dass auf die 0 nicht abgebildet wird, oder nicht? Würde das auch gehen?

---

Nein das hast du leider nicht gezeigt. Du nimmst nämlich n= 2 an. Wenn dann müsstest du n beliebig lassen und dann deinen Widerspruchsbeweis führen. Außerdem musst du je nach Vorlesung unterscheiden ob die 0 in den natürlichen Zahlen N liegt oder nicht. (N wurde bei mir zB ohne 0 eingeführt)

---

Ok, danke dir. Aber wie würde ich es denn dann in der Klausur richtig beweisen?

Das was du schriebst, das reicht doch nicht als Antwort in einer Klausur, oder? Und so richtig verstehe ich es auch nicht, ehrlich gesagt.

Ich brauche doch ein Gegenbeispiel.

---

Ja, das Gegenbeispiel ist wie ich es schon in der Antwort geschrieben habe die 1. Da die Funktion auf die natürlichen Zahlen Abbildet die 1 aber nie angenommen wird, deswegen kann die Funktion nicht Surjektiv sein.

Das ist sofort einsichtig und müsste in den meisten Fällen auch nicht weiter begründet werden. Meinetwegen kannst du ja noch f(n,m) = 2n +m ≥ 2 * 0 + 2 = 2 hinschreiben und somit zeigen, dass die Funktion nur Werte größer gleich 2 annehmen kann.

---

Was heißt denn, dass sie Funktion nicht auf 1 abbildet? Dass die 1 nicht als Ergebnis rauskommen kann?

Und wieso hast du f(n,m) n = 0 und m = 2 gewählt? Darf n,m nicht nur entweder 2 oder 3 sein?

---

Ja genau. Egal welche Parameter n und m du einsetzt, das Ergebnis wird nicht die Zahl 1 annehmen. Und ich habe n = 0 und m = 2 gewählt, weil für diese Parameter die Funktion ihr Minimum annimmt. Ich habe den Ausdruck f(n,m) nach unten abgeschätzt.

---

Und wieso darf ich nicht auch m = 0 wählen?

Also n = m = 0?

Oder ist das Minimum = 2, weil {2,3}, und von dieser Menge das Minimum 2 ist?

---

Ich habe die Parameter n und m vertauscht. Wichtig ist aber dass du für die eine Variable nur den Wert 2 oder 3 wählen darfst. Deswegen darf man n = m = 0 nicht wählen. Schau dir die Funktion nochmal an und vergewissere dich, dass du verstanden hast wie diese definiert wurde und wie sie "funktioniert"

---

Ja, aber wenn, wie du sagst, die Variable m oder n entweder den Wert 2 oder 3 annehmen darf, wieso kannst du denn dann einen der beiden = 0 setzen?

---

Schau dir die Definition der Funktion an.

f : ℕ × {2, 3} → ℕ, f(m, n) = 2m + n

Das heißt m nimmt eine natürliche Zahl an und n den Wert 2 oder 3. Da m eine natürliche Zahl ist kann ich auch den Wert 0 annehmen. Was an sich egal ist weil ich sowieso den Ausdruck f(m,n) nach unten abschätze.

f(m, n) = 2m + n ≥ 2*0 +2 = 2   Selbst wenn m nur die Werte 5 und 20 annehmen dürfte wäre die Abschätzung nach unten ja trotzdem richtig.

---

Danke. Woran erkenne ich denn an der Funktion, dass m den Wert 2 oder 3 annehmen arf. Wieso nur m? Wieso nicht auch n? ℕ × {2, 3} heißt doch das Kreuzprodukt aus {2,3}, oder? wird abgebildet auf die natürlichen Zahlen.

Die Funktion besitzt doch 2 variablen m,n. Wieso gilt der Wertebereich {2,3}dann nur für die variable m und nicht für n? Woran erkenne ich das denn?

---

Das ist genau die Definition des Kreuzproduktes.

In ℕ × {2, 3} liegen z.B. (5,2), (7,3) etc. in der ersten Komponente steht eine beliebige nat. Zahl und in der zweiten steht entweder die 2 oder die 3. m nimmt den Wert der ersten Komponente an und n den der zweiten, deswegen gilt n=2 oder n=3 und m darf eine beliebige nat. Zahl annehmen.

---

Danke! Ich wusste nicht die Bedeutung des Kreuzproduktes! Das erklärt einiges!

Liebe Grüße

---

Kann man bei der Injektivität nicht auch anders vorgehen?

Ist doch eine Implikation: Wenn f(x1) = f(x2), dann folgt x1 = x2.

f(x1) = f(x2) => x1 = x2. Aber wenn bei einer Implikation die Prämisse falsch ist, ist die Aussage doch immer wahr. Also wäre es doch nicht schlimm, wenn wir annehmen ,dass z.B. die linke Seite gerade ist und die rechte ungerade. Oder nicht?

---

Ja es gibt für einen beweis tendenziell immer mehr als einen Lösungsweg.

Und ja wenn die Prämisse einer Implikation falsch ist, ist die Implikation richtig.

Es wäre auch nicht schlimm wenn man f(x) ≠ f(y) annimmt. Aber damit alleine funktioniert der Beweis nicht mehr, weil wie du schon richtig erkannt hast, ist das der irrelevante Fall. Interessant wird es ja wenn f(x) = f(y) gilt. Überleg dir mal wieso :)

---

Naja, weil wir dann davon ausgehen können, dass 2m und 2k gleich sein müssen, da n und l einmal gerade und einmal ungerade sind, wenn einmal 2 und einmal 3 angenommen wird. Oder?

---

Ich verstehe deine Antwort leider nicht. Ich hab dir den Beweis nochmal sehr ausführlich aufgeschrieben…

Text erkannt:

\( z z: f(x)=f(y) \Rightarrow x=y \)

---

Injektivität bedeutet, dass unterschiedliche Elemente aus dem Definitionsbereich durch f auf unterschiedliche Funktionswerte abgebildet werden. Also x≠y => f(x)≠f(y)

Die Aussage f(x)=f(y) => x=y ist genau die Kontraposition davon. Also Aussagenlogisch äquivalent dazu. Du willst also zeigen: Wenn die Bild/Funktionswerte von x und y übereinstimmen, so muss x schon mit y übereinstimmen, da die Bildpunkte ja eindeutig sind.

Der Fall dass man f(x) ≠f(y) annimmt ist also nicht relevant, weil das nichts zur Injektivität beiträgt.