Definition "nicht injektiv"

15.11.2013, 17:19

Duude

Definition "nicht injektiv"

Hallo ihr,
ich beschäftige mich gerade mit der Injektivität von Abbildungen, habe das auch alles verstanden, (eine Abbildung f ist injektiv genau dann, wenn jedes Element aus dem Bildraum, das getroffen wird, genau einmal getroffen wird.) aber eine Frage zur Definition von "nicht injektiv".

Eine Abb. f ist injektiv genau dann wenn:
$\begin{eqnarray*} f(a)=f(a') \Rightarrow a=a' \end{eqnarray*}$

Entsprechend muss doch gelten:
Eine Abb f ist nicht injektiv genau dann wenn:
$\begin{eqnarray*} \neg(f(a)=f(a') \Rightarrow a=a') \end{eqnarray*}$

Das wiederum ist nach der Aussagenlogik (habe ich mit der Wahrheitstabelle nachgeprüft) äquivalent zu:
$\begin{eqnarray*} \neg(a=a') \Rightarrow \neg (f(a)=f(a')) \end{eqnarray*}$
ist äquivalent zu
$\begin{eqnarray*} (a)\neq (a') \Rightarrow f(a) \neq f(a') \end{eqnarray*}$

Das soll also nun heißen, dass die Abbildung nicht injektiv ist, besagt aber doch nur, dass ungleiche Elemente aus a auf ungleiche Elemente aus b abgebildet werden und das wiederum heißt doch gerade injektiv. Da muss doch irgendwo ein Fehler drin sein, oder?

Ich hätte nicht injektiv so definiert:
Es gibt ein $\begin{eqnarray*} b \in B: f(a_1)=b \quad \text{und} \quad f(a_2)=b, a_1 \neq a_2 \end{eqnarray*}$

Jetzt bin ich irgendwie verwirrt (oder sehe meinen Fehler nicht) und würde mich über Hilfe freuen.

15.11.2013, 18:50

Dopap

Auf diesen Beitrag antworten »

RE: Definition "nicht injektiv"

Zitat:

Original von Duude

Eine Abb. f ist injektiv genau dann wenn:
$\begin{eqnarray*} f(a)=f(a') \Rightarrow a=a' \end{eqnarray*}$

Entsprechend muss doch gelten:
Eine Abb f ist nicht injektiv genau dann wenn:
$\begin{eqnarray*} \neg(f(a)=f(a') \Rightarrow a=a') \end{eqnarray*}$

Das ist so nicht richtig. Was da dasteht ist die Aussage, dass die Definiion der Injektivität falsch ist !!! Und daraus kann man Falsches und auch Wahres folgern !

Zitat:

Das wiederum ist nach der Aussagenlogik (habe ich mit der Wahrheitstabelle nachgeprüft) äquivalent zu:
$\begin{eqnarray*} \neg(a=a') \Rightarrow \neg (f(a)=f(a')) \end{eqnarray*}$
ist äquivalent zu
$\begin{eqnarray*} (a)\neq (a') \Rightarrow f(a) \neq f(a') \end{eqnarray*}$

Was du nun erhalten hast, ist die Kontraposition der Definition und ist selbstredend richtig. In dieser Form ist die Definition eingängiger ( für meinen Geschmack )

Zitat:

Das soll also nun heißen, dass die Abbildung nicht injektiv ist, besagt aber doch nur, dass ungleiche Elemente aus a auf ungleiche Elemente aus b abgebildet werden und das wiederum heißt doch gerade injektiv. Da muss doch irgendwo ein Fehler drin sein, oder?

siehe oben!

Zitat:

Ich hätte nicht injektiv so definiert:
Es gibt ein $\begin{eqnarray*} b \in B: f(a_1)=b \quad \text{und} \quad f(a_2)=b, a_1 \neq a_2 \end{eqnarray*}$

Jetzt bin ich irgendwie verwirrt (oder sehe meinen Fehler nicht) und würde mich über Hilfe freuen.

Das sieht doch schon ziemlich gut aus.

15.11.2013, 19:33

Duude

Auf diesen Beitrag antworten »

Hallo Dopap!
Vielen Dank für die schnelle Antwort. smile

Also lag mein Denkfehler daran, dass ich angenommen habe, die Definition der Injektivität sei falsch. Das ist eine falsche Aussage. Und aus einer falschen Aussage kann man (wie in der Aussagenlogik gezeigt) sowohl Wahres als auch Falsches folgern..

Ich kann also auf diese Weise nicht von der Definition von injektiv auf "nicht injektiv" übergehen..

Im Allgemeinen kann ich also aus einer Definition nicht die Definition des "Gegenteils" erhalten, indem ich ein "nicht" davorschreibe und das umforme, weil das immer eine falsche Aussage ist, aus der ich alles folgern kann...

lg Duude

15.11.2013, 19:52

Dopap

Auf diesen Beitrag antworten »

ja, so sehe ich das.

Hier ist das "nicht injektiv" als die Negation des Gefolgerten ( $\begin{eqnarray*} a \neq a' \end{eqnarray*}$ ) zu verstehen.

Der komplette Nachweis müsste aber auch die Quantoren berücksichtigen.

15.11.2013, 20:15

Duude

Auf diesen Beitrag antworten »

Ja, anschaulich ist mir das alles klar...

Aber wenn ich mir den Nachweis mit den Quantoren anschaue, dann zweifle ich an einer Stelle noch. Ich erhalte doch:

f ist injektiv $\begin{eqnarray*} \Leftrightarrow \forall x_1, x_2 \in X\colon\, (f(x_1)= f(x_2) \Rightarrow x_1=x_2) \end{eqnarray*}$

nicht (f ist injektiv)) $\begin{eqnarray*} \Leftrightarrow \neg (\forall x_1, x_2 \in X\colon\, (f(x_1)= f(x_2) \Rightarrow x_1=x_2) \end{eqnarray*}$

nicht (f ist injektiv)) $\begin{eqnarray*} \Leftrightarrow \exists x_1, x_2 \in X\colon\, \neg (f(x_1)= f(x_2) \Rightarrow x_1=x_2) \end{eqnarray*}$

und der Schritt der jetzt kommt, ist mir formal nicht klar . Ich hätte erwartet, dass hinten in der folgenden Zeile stehen müsste: $\begin{eqnarray*} x_1 \neq x_2 \Rightarrow f(x_1) \neq f(x_2) \end{eqnarray*}$ . Das ist doch die Negation der Aussage die hinten steht. Wie komme ich aber dann auf die jetzt folgende Zeile, die nach meinem Verständnis die richtig sein müsste?

nicht (f ist injektiv)) $\begin{eqnarray*} \Leftrightarrow \exists x_1, x_2 \in X\colon\, (f(x_1)= f(x_2) \Rightarrow x_1 \neq x_2) \end{eqnarray*}$

Anschaulich nach Definition der Injektivität ist mir das klar, denn wenn f nicht injektiv ist, gibt es zwei verschiedene $\begin{eqnarray*} x_1 \end{eqnarray*}$ und $\begin{eqnarray*} x_2 \end{eqnarray*}$ für die gilt, dass sie dieselben Funktionswerte haben.

Ich hoffe ich habe jetzt nicht wieder denselben Fehler wie vorhin gemacht, wel ich die Aussage einfach so negiert habe.. Aber mit den Quantoren müsste das doch gehen, oder?

19.11.2013, 19:58

jimmyt

Auf diesen Beitrag antworten »

Es gilt:

$\begin{eqnarray*} \neg (A ~\implies~ B) ~\Longleftrightarrow~ \neg (\neg A ~\lor~ B) ~\stackrel{\text{de Morgan}}{\Longleftrightarrow}~ (A ~\land~ \neg B) \end{eqnarray*}$

Damit müßte deine Frage beantwortet sein. Freude

Und schon bin ich wieder raus. Big Laugh

20.11.2013, 10:37

Nofeykx

Auf diesen Beitrag antworten »

"Das ist doch die Negation der Aussage die hinten steht. Wie komme ich aber dann auf die jetzt folgende Zeile, die nach meinem Verständnis die richtig sein müsste?"

Nein, ganz im Gegenteil. Was du da hast, ist nicht nur nicht die Negation der Aussage, sie ist stattdessen sogar zur Aussage äquivalent.

Wie es richtig geht, hat jimmyt gezeigt.

26.11.2013, 22:08

Duude

Auf diesen Beitrag antworten »

Also die Äquivalenz von dir jimmyt habe ich nachvollzogen. Damit erhalte ich

nicht (f ist injektiv)) $\begin{eqnarray*} \Leftrightarrow \exists x_1, x_2 \in X\colon\, (f(x_1)= f(x_2) ~\land x_1 \neq x_2) \end{eqnarray*}$

Ich hätte statt dem Und hinten aber gerne einen Folgepfeil für "es folgt". Und das ist doch nicht dasselbe. Schon alleine eine Wahrheitstabelle sagt mir, dass $\begin{eqnarray*} (A ~\land B) \nLeftrightarrow (A \Rightarrow B) \end{eqnarray*}$

Also habe ich noch nicht das erreicht, was ich zeigen wollte, oder habe ich etwas von euren Erklärungen falsch verstanden?

29.11.2013, 11:27

jimmyt

Auf diesen Beitrag antworten »

Zitat:

Original von Duude
... nicht (f ist injektiv)) $\begin{eqnarray*} \Leftrightarrow \exists x_1, x_2 \in X\colon\, (f(x_1)= f(x_2) ~\land x_1 \neq x_2) \end{eqnarray*}$
...

Das stimmt. Freude

Zitat:

Original von Duude
Ich hätte statt dem Und hinten aber gerne einen Folgepfeil für "es folgt".
...

Das wäre dann aber die falsche Definition für nicht injektiv.
Das würde ja heißen, daß wenn $\begin{eqnarray*} f(x_1) ~=~ f(x_2) \end{eqnarray*}$ gilt, daß dann in jedem Fall $\begin{eqnarray*} x_1 ~\neq~ x_2 \end{eqnarray*}$ sein muß. Und das ist falsch.
Nicht injektiv bedeutet, daß es mindestens ein $\begin{eqnarray*} x_1 \end{eqnarray*}$ und ein $\begin{eqnarray*} x_2 \end{eqnarray*}$ gibt, für die gilt $\begin{eqnarray*} x_1 ~\neq~ x_2 \end{eqnarray*}$ und $\begin{eqnarray*} f(x_1) ~=~ f(x_2) \end{eqnarray*}$ .

Zitat:

Original von Duude
Und das ist doch nicht dasselbe. Schon alleine eine Wahrheitstabelle sagt mir, dass $\begin{eqnarray*} (A ~\land B) \nLeftrightarrow (A \Rightarrow B) \end{eqnarray*}$
...

Natürlich sind die nicht äquivalent, dafür aber $\begin{eqnarray*} (A ~\land~ \neg B) ~\Longleftrightarrow~ \neg (A ~\implies~ B) \end{eqnarray*}$ .

Zitat:

Original von Duude
...
Also habe ich noch nicht das erreicht, was ich zeigen wollte, oder habe ich etwas von euren Erklärungen falsch verstanden?

Vlt. wurde es jetzt klarer? smile

EDIT: @Leopold :
Danke dir. Ich kann die netten Worte nur zurückgeben.
Sehr schön erklärt. Und dieses mathfrak von Latex sieht man auch nicht alle Tage. smile

29.11.2013, 12:32

Leopold

Auf diesen Beitrag antworten »

jimmyt hat das alles schön erklärt. Mein Beitrag soll die Diskussion zusammenfassen und auf den Punkt bringen.

Bezeichen wir $\begin{eqnarray*} f(a) = f(a') \end{eqnarray*}$ mit $\begin{eqnarray*} \mathfrak{A} = \mathfrak{A}(a,a') \end{eqnarray*}$ und $\begin{eqnarray*} a=a' \end{eqnarray*}$ mit $\begin{eqnarray*} \mathfrak{B} = \mathfrak{B}(a,a') \end{eqnarray*}$ . Dann wird die Injektivität von $\begin{eqnarray*} f \end{eqnarray*}$ beschrieben durch

$\begin{eqnarray*} \forall a \forall a' \left( \mathfrak{A} \Rightarrow \mathfrak{B} \right) \end{eqnarray*}$

Die Nichtinjektivität ist einfach die Negation hiervon, also

$\begin{eqnarray*} \neg \left( \forall a \forall a' \left( \mathfrak{A} \Rightarrow \mathfrak{B} \right) \right) \end{eqnarray*}$

Und beim Umformen gelten allgemeine Regeln. Als da wären (mit $\begin{eqnarray*} \equiv \end{eqnarray*}$ bezeichne ich zur Unterscheidung der Sprachebenen die logische Gleichwertigkeit, die Frakturbuchstaben bezeichnen Aussagen beziehungsweise Aussageformen in den entsprechenden Variablen)

$\begin{eqnarray*} \neg \left( \forall x \mathfrak{X} \right) \equiv \exists x \neg \mathfrak{X} \end{eqnarray*}$

$\begin{eqnarray*} \neg \left( \exists x \mathfrak{X} \right) \equiv \forall x \neg \mathfrak{X} \end{eqnarray*}$

$\begin{eqnarray*} \neg \left( \mathfrak{X} \wedge \mathfrak{Y} \right) \equiv \neg \mathfrak{X} \vee \neg \mathfrak{Y} \end{eqnarray*}$

$\begin{eqnarray*} \neg \left( \mathfrak{X} \vee \mathfrak{Y} \right) \equiv \neg \mathfrak{X} \wedge \neg \mathfrak{Y} \end{eqnarray*}$

$\begin{eqnarray*} \neg \left( \mathfrak{X} \Rightarrow \mathfrak{Y} \right) \equiv \mathfrak{X} \wedge \neg \mathfrak{Y} \end{eqnarray*}$

Und jetzt kann man den obigen Ausdruck Stück für Stück umformen:

$\begin{eqnarray*} \neg \left( \forall a \forall a' \left( \mathfrak{A} \Rightarrow \mathfrak{B} \right) \right) \equiv \exists a \neg \left( \forall a' \left( \mathfrak{A} \Rightarrow \mathfrak{B} \right) \right) \equiv \exists a \exists a' \neg \left( \mathfrak{A} \Rightarrow \mathfrak{B} \right) \equiv \exists a \exists a' \left( \mathfrak{A} \wedge \neg \mathfrak{B} \right) \end{eqnarray*}$

Die Nichtinjektivität wird somit beschrieben durch:

$\begin{eqnarray*} \exists a \exists a' \left( f(a)=f(a') \wedge a \neq a' \right) \end{eqnarray*}$

Neue Frage »

Antworten »

Definition "nicht injektiv"

Verwandte Themen