Definiton: Funktion nicht Injektiv

18.09.2012, 13:58

Colorite

Definiton: Funktion nicht Injektiv

Hi

Es hat mich interessiert, wie man es formal fasst, dass eine Funktion nicht injektiv ist. Ich hatte zuerst an das da gedacht:

f(x_1) = f(x_2) !-> x_1 = x_2

wobei ich !-> für "folgt nicht" verwende - ich denke aber, dass dies falsch ist, da dies nicht ausnahmslos stimmen muss.

Müsste man also Quantoren verwenden? I.e.

-(Ax) : f(x_1) = f(x_2) -> x_1 = x_2

wobei "-(Ax)" für " nicht für alle x gilt ..." steht.

Danke

18.09.2012, 14:15

Math1986

Auf diesen Beitrag antworten »

RE: Definiton: Funktion nicht Injektiv
Die erste Variante ist, wie du selbst richtig begründet hast, falsch.

Die zweite Variante ist formal auch falsch: Du schreibst -(Ax), verwendest dann aber x_1 und x_2.

Man kann es am einfachsten über den Existenzquantor schreiben:
$\begin{eqnarray*} \exists x_1,x_2\colon x_1 \neq x_2 \wedge f(x_1) = f(x_2) \end{eqnarray*}$
Das entpricht dem Beweisansatz "Widerlegen durch Gegenbeispiel"

18.09.2012, 14:19

weisbrot

Auf diesen Beitrag antworten »

RE: Definiton: Funktion nicht Injektiv
wenn du keine quantoren verwendest, solltest du sowieso den durchgestrichenen pfeil als "folgt nicht für alle x" auffassen. besser und formaler wirds natürlich mir quantoren, dann sollte es aber so aussehen:
$\begin{eqnarray*} \forall x, y \in X (f(x) = f(y) \to x = y) \underset{\text{negiert}}{\longrightarrow} \exists x, y \in X \neg (f(x) = f(y) \to x = y) \end{eqnarray*}$
$\begin{eqnarray*} \Leftrightarrow \exists x, y \in X (f(x) = f(y) \wedge x \neq y) \end{eqnarray*}$ .
man benutzt da halt, dass $\begin{eqnarray*} \neg (\forall x A(x)) \Leftrightarrow \exists x \neg A(x) \end{eqnarray*}$ . lg

Edit(Helferlein): Zeilenumbruch eingefügt, um Überbreite zu verhindern.

18.09.2012, 21:02

Colorite

Auf diesen Beitrag antworten »

Zuerst mal an Math:

Stimmt, ich müsste über eine andere Variable all-quantifizieren (zB x_i oder so).

Aber was du aufschreibst ist ja genau die gleiche Aussage wie meine.

NOT(Ax)(Px) = Ex NOT(Px) --> und in unserem Fall ist die Negation einer Implikation: NOT(a->b) bekanntlich nichts anderes als (a && NOT b) ...

18.09.2012, 23:42

Colorite

Auf diesen Beitrag antworten »

..ah Weisbrot jetzt erst hab ich mir deinen Beitrag angeschaut und das ist genau was ich meinte. Vielen Dank erstmals.

Warum ich diese Frage überhaupt gestellt habe: Man soll beweisen (oder widerlegen), dass für f: X -> Y, g: Y -> X mit g o f = id_X

gilt, dass f injektiv ist. Ich kenne den direkten Beweis bereits, wollte aber einen indirekten Beweis benutzen (aus dem ein Widerspruch folgt also, wenn wir annehmen, dass f nicht injektiv ist).

Ich bin aber nur dahin gekommen, dass dann für g(f(x)) = g(f(y)) diese Gleichheit gelten kann obwohl x != y, was möglicherweise verhindert, dass g surjektiv ist...formal konnte ich diesen Gedanken aber nicht umsetzen :/

Vielen Dank Jungs, dieses Forum scheint auch cool zu sein!

Lg

19.09.2012, 11:08

Math1986

Auf diesen Beitrag antworten »

Zitat:

Original von Colorite
Aber was du aufschreibst ist ja genau die gleiche Aussage wie meine.

NOT(Ax)(Px) = Ex NOT(Px) --> und in unserem Fall ist die Negation einer Implikation: NOT(a->b) bekanntlich nichts anderes als (a && NOT b) ...

Ja, da haben wir das selbe. Ich hatte auch nur behauptet, dass bei dir der Allquantor falsch verwendet wurde.

19.09.2012, 11:17

Math1986

Auf diesen Beitrag antworten »

Zitat:

Original von Colorite

gilt, dass f injektiv ist. Ich kenne den direkten Beweis bereits, wollte aber einen indirekten Beweis benutzen (aus dem ein Widerspruch folgt also, wenn wir annehmen, dass f nicht injektiv ist).

Das geht vom Ansatz her:
f sei also nicht injektiv, also gilt nach unseren vorherigen Überlegungen
$\begin{eqnarray*} \exists x_1,x_2\colon x_1\neq x_2\wedge f(x_1)=f(x_2)=:y \end{eqnarray*}$
Daher gilt auch
$\begin{eqnarray*} \left(g\circ f\right)\left(x_1\right)=g\left(f\left(x_1\right)\right)=g\left(y\right) \end{eqnarray*}$
$\begin{eqnarray*} \left(g\circ f\right)\left(x_2\right)=g\left(f\left(x_2\right)\right)=g\left(y\right) \end{eqnarray*}$

Sommit ist $\begin{eqnarray*} \left(g\circ f\right) \end{eqnarray*}$ nicht injektiv, also insbesondere nicht die Identität.

Deine Aussage lässt sich sogar verschärfen zu

Zitat:

Für f: X -> Y, g: Y -> X mit g o f injektiv gilt, dass f injektiv ist

Neue Frage »

Antworten »

Definiton: Funktion nicht Injektiv

Verwandte Themen