Funktion f (k,m) = (k - m) mod n auf Injektivität untersuchen.

Question

!

Ich habe eine Funktionen die ich auf Injektivität untersuchen will. Bei einfacheren Funktionen ist mir die Vorgehensweise mehr oder weniger klar. Bei der gegebenen Funktion aber nicht so ganz)

f (k,m) = (k - m) mod n

Wie gehe ich diese Funktion an?

EDIT: Nachträge aus dem Kommmentar:

In meinem Fall gilt-> f: K × M  k∈K, m∈M 

K = M = {0,..., n - 1}, n ∈ ℕ

Comments

Injektivität ist eine Eigenschaft die stark davon abhängt zwischen welchen Mengen die Funktion f abbildet. Diese solltest du noch angeben.

---

Hallo Yakyu!

In meinem Fall gilt-> f: K × M  k∈K, m∈M

---

schön, was sollen K und M sein? Einfach nur Teilmengen der natürlichen Zahlen?

---

Ich merke ich bin ziemlich ungenau bei den angaben, tut mir leid.

K = M = {0,..., n - 1}, n ∈ ℕ

Answer 1

Hi,

kein Problem, nachdem das geklärt ist kannst du dir zuerst überlegen, warum das ganze erst für $n \geq 2$ interessant wird.

Dann kannst du dir überlegen, dass du immer mindestens 2 Elemente $(a,b) , (c,d) \in K \times M$ findest mit $(a,b) \neq (c,d)$ aber

$$a-b\mod n = c-d \mod n$$

und was das für die Injektivität der Funktion bedeutet.

Gruß

Comments

Also, ich verzweifle langsam.Mit n ≥ 2 ist klar. 0 geht nicht, bei n = 1 ist modulo immer 0.Bei Injektivität ist ƒ₁ = ƒ₂ bei x₁ = x₂.Das würde heißen, meine Funktion ist nicht injektiv,weil wenn z.B n = 2, würde ich bei 2,4,6,... die gleichen Ergebnisse bekommen.Das heißt dann aber, dass falls ich modulo rechne, meine Funktionen niemals injektiv sein können. Es sei denn, ich stelle bestimmte Bedingungen auf. Ist das Richtig?Und wie kann ich das mathematisch richtig auffassen?

---

Hi ich hab das Gefühl, dass du  nah dran bist aber noch nicht hundert prozentig die Funktion begriffen hast, deswegen hier mal eine kleine Verständnisfrage:

Wenn wird den Fall $n = 5$ betrachten, schreib mal ein paar Beispiele für $(a,b) \in K \times M$ auf, so dass

$$f(a,b) = 2\mod 5$$

Verwende nun das was ich in meiner Antwort geschrieben habe (nämlich das die Funktion nicht injektiv ist, so wie du schon richtig erkannt hast) und beschreibe explizit die 2 Elemente (a,b) und (c,d) um zu zeigen, dass die Funktion für alle $n \geq 2$ nicht injektiv ist.

Kleiner Tipp: Entweder in Abhängigkeit von n, oder konkrete Elemente die in allen Mengen für $n\geq 2$ auftreten.

---

Bin mir nicht sicher dich richtig verstanden zu haben, aber hier meine Lösung.(a,b) = (7,5) = x₁;  (c,d) =  (9,7) = x₂;ƒ₁(a,b) = ƒ₂ (c,d) aber x₁ ≠ x₂
Was mache ich nun damit?

---

Deine Beispiele funktionieren im Fall n = 5 nicht wirklich, da die Mengen K und M doch nur von 0 bis 4 gehen. Dein Beispiel würde aber für n = 10 funktionieren. Mit diesem Beispiel hättest du gezeigt, dass die Funktion im Fall n = 10 nicht injektiv ist (ist dir das klar?)

Jetzt versuch es allgemein für $n\geq 2$.

---

Ups, stimmt, mit n = 5 geht's natürlich nicht.

Allgemeine Beschreibungen ist meine Schwachstelle.

Also für n ≥ 2 muss ich mir die die (k-m) genauer ansehen.

(k - m) = - n + 1,..., n - 1

Wenn ich modulo n anwende, liegen auch diese Ergebnisse zwischen -n + 1 und n - 1. Ich habe 2*n-Paare die zum gleichen Ergebnis führen. Hmmm... wie schreibe ich das mathematisch richtig auf?

---

Ok vielleicht noch ein Tipp:

Betrachte die Elemente f(k,k) :) Wieviele gibt es und worauf werden sie abgebildet wenn $n \geq 2$?

---

Diesen Tipp kann ich leider nicht nutzen, ich verstehe ihn nicht. Wenn ich k einsetze, werden die Elemente auf K abgebildet, oder werden sie dann eher auf ℕ abgebildet? 
Es gibt bei n ≥ 2 n-2 viele k-Elemente, da die 0 und die 1 weg fallen. Ich verstehe nicht was es mir sagt.Danke an den Admin für die Ergänzung meiner Frage.

---

K = M = {0, .., n-1},  f: K² -> K

f((k,k)) = (k-k) mod n = 0

Beispiele für (k,k): (0,0), (1,1), (2,2),....(n-1,n-1)

n ≥ 2 => Es gibt mindestens 2 Elemente die auf 0 abgebildet werden => f ist nicht injektiv

---

Oh man, selbst wenn ich die Lösung sehe kann ich's nicht so ganz nachvollziehen.

1) Warum die Schreibweise f: K² -> K

2) Für mein Fall mit k-m kann ich dann sagen, k-m für alle k = m wird auf 0 abgebildet, richtig? Wie sage ich dann, dass auch bei allen gleichen Differenzen (z.B. m-k = 2) auch auf das gleiche Element abgebildet wird?

Danke nochmals für deine Antworten, obwohl ich noch nicht alles verstanden habe, bin ich viel weiter gekommen.

---

1)weil K=M, KxM = KxK =K²

du müsstest doch ℝ² usw. kennen, dann müsstest du doch wissen was ein Kreuzprodukt ist von Mengen.

2)"Für mein Fall mit k-m kann ich dann sagen, k-m für alle k = m wird auf 0 abgebildet, richtig? "

Ja und das reicht schon vollkommen aus um die Injektivität zu widerlegen! Mehr brauchst du hier gar nicht zu machen.

Für den Fall k-m = 2 einfach einsetzen!

k-m =2 bedeutet doch nichts anderes als m = k-2

also ist f((k,m)) = f(k,k-2)) = k-(k-2) mod n = 2 mod n

---

Traurig, dass ich selber nicht drauf komme. Stehe gerade total auf dem Schlauch.

Du hast in deiner Lösung geschrieben: "n ≥ 2 => Es gibt mindestens 2 Elemente die auf 0 abgebildet werden => f ist nicht injektiv". Warum 2 Elemente, wenn du zeigst, dass es n-1 Elemente gibt, die auf 0 abbilden (0,0)...(n-1,n-1)

Um die Sache besser zu verstehen: die Funktion  (km) mod n wäre dann auch nicht injektiv, weil ich wieder zwei Elemente habe, die mir auf das gleich Element abbilden. Z.b.  (2,1) und (1,2) ?

Das ist dann eig. egal was ich in meiner Klammer habe, ob (k - m) oder (k+m), oder (km) oder (k + m)². Ich bin wegen Modulo Rechnung immer nicht injektiv?

---

Ok mein Freund :) -> es sind nicht n-1 sondern n Elemente! 0 bis n-1 sind n Zahlen.Wenn n ≥2 und man gezeigt hat, dass mindestens n Elemente hat die auf 0 abgebildet werden, dann bedeutet dies doch auch das mindestens 2 Elemente auf Null abgebildet werden!
(km)mod n ist sogar "noch schlimmer" da ja jede Zahl mit Null mutlipliziert wieder 0 ergibt!
Und zum Rest -> wenn wir dieselben Mengen wie vorher betrachten kann man die Injektivität der anderen Beispiele ebenfalls widerlegen. Es sollte dir auffallen das es sich bei manchen dieser Anwendungen auch um kommutative Verknüpfungen handelt, die können sowieso nicht injektiv sein auf dem Ring ℤmodn.

---

"Es sollte dir auffallen das es sich bei manchen dieser Anwendungen auch um kommutative Verknüpfungen handelt, die können sowieso nicht injektiv sein auf dem Ring ℤmodn."

WOW

Ich danke dir nochmal!