Beweis Injektivität
-
Hallo zusammen,
mal wieder beschäftigt mich ein Beweis. Ich habe f: A -> B und g: B -> C. Außerdem weiß ich, dass g * f bijektiv ist. Mit g * f meine ich "g auf f", also g(f(x)).
Ich soll nun zeigen, dass f injektiv ist.
Durch meine Vorgaben weiß ich, dass A -> C injektiv und surjektiv ist. Ich kann damit Aussagen über A und C machen, doch wenn ich zeigen will, dass f injektiv ist, dann muss ich ja was über B aussagen können.
Könnt ihr mir einen Tipp geben, wie ich an einen Ansatz komme?
Danke
-
Widerspruchsbeweise gehen immer gut. Du nimmst an, f sei nicht injektiv. Daraus schließt du, dass g°f auch nicht injektiv sein kann. Da es aber als bijektiv vorausgesetzt ist, hast du einen Widerspruch, musst also deine Annahme verwerfen.
-
Angenommen f sei nicht injektiv. Dann gäbe es ein x und ein y aus A, für die folgendes gilt: f(x) = f(y) !=> x = y.
Ich muss aber doch eine Aussage über B machen können und weiß nur, dass A -> C injektiv und surjektiv ist. Was bringt mir das?
-
freakC++ schrieb:
Angenommen f sei nicht injektiv. Dann gäbe es ein x und ein y aus A, für die folgendes gilt: f(x) = f(y) !=> x = y.
Das Zeichen !=> kenn ich nicht, was soll das heißen?
f nicht injektiv heißt: Es gibt x,y aus A, so dass f(x)=f(y) und x!=y.
-
Das war auch eher mein Zeichen, was soviel wie "daraus folgt nicht" heißen sollte.
-
Was soll das heißen, A -> C sei injektiv und surjektiv? Ich sehe keine Abbildung.
Zum Beweis: Seien x, y in A, x != y mit f(x) = f(y). Was folgt für g(f(x)) und g(f(y))?
-
Ich dachte, dass das "g auf f" bedeutet. Folgt daraus nicht A -> C??
Danke
-
freakC++ schrieb:
Ich dachte, dass das "g auf f" bedeutet.
Ich seh den Originaltext nicht und kann dir deswegen nicht sagen, ob du es richtig liest.
Folgt daraus nicht A -> C??
Was soll das denn darstellen? Du hast da zwei Mengen mit nem Pfeil dazwischen.
-
freakC++ schrieb:
Angenommen f sei nicht injektiv. Dann gäbe es ein x und ein y aus A, für die folgendes gilt: f(x) = f(y) !=> x = y.
Ich muss aber doch eine Aussage über B machen können
Nein, über B musst du keine Aussage treffen. B ist dir völlig egal. Du musst nur eine Aussage über C treffen. Bei deinem Beweis hast du zu früh abgebrochen, denn was bedeutet es für g(f(x)) wenn f(x)= f(y) aber x != y ist?
-
Michael E. schrieb:
Folgt daraus nicht A -> C??
Was soll das denn darstellen? Du hast da zwei Mengen mit nem Pfeil dazwischen.
A -> C ist die Menge aller Funktionen, die von A nach C abbilden. Es ist somit eine Teilmenge der Menge aller Relationen zwischen A und C. Formal: (f \circ g) \in (A -> C) \subseteq 2^{A \times C}
-
Also das hab ich noch nie gesehen. Hom(A,C) ja, aber A->C?
-
Habe ich in Lineare Algebra 1 jedenfalls so gelernt. Ich meine es auch schon so öfter in Papern gelesen zu haben (zumindest in einem Fall bin ich mir sicher) ;).
Vielleicht ist die Notation eher in der Informatik üblich als in der Mathematik?
-
life schrieb:
Vielleicht ist die Notation eher in der Informatik üblich als in der Mathematik?
Hm, umgekehrt würd ich das ja noch gelten lassen... aber in der informatik hab ich das garantiert noch nie gesehen, und da lese ich wirklich sehr regelmäßig. Sieht ehrlich gesagt auch iChat nach ner sonderlich praktischen Notation aus.
-
Ist halt syntaktischer Zucker für dein Hom(A,B) bzw. eher Abb(A,B). Das wird so z.B. auch in der formalen Spezifikationssprache Z (Informatik) verwendet: http://www.uni-koblenz.de/~beckert/Lehre/Spezifikation/11Z.pdf
Ansonsten ist es unter Mathematikern offenbar auch verbreitet, sonst hätte ich es so nicht in Lineare Algebra I (für Mathematiker) gelernt.
-
life schrieb:
Ist halt syntaktischer Zucker für dein Hom(A,B).
Spätestens beim Funktor i: Hom(.,B) -> Hom(.,C) für B teilmenge C, also i: (.->B) -> (.->C) wird das imo eher syntaktisches Brechmittel denn Zucker.
Aber vielleicht kann man das im Bereich Verifikation wirklich brauchen, da ist der Blickwinkel ja oft auch ein bissel anders. Aber weit verbreitet ist die Notation auf keinen fall.
-
Ich arbeite zwar im Bereich Verifikation, aber mein damaliger Matheprof mit Sicherheit nicht. Deshalb wird es sich schon nicht auf dieses Teilgebiet beschränken.
-
Ich hab die Notation auch bei den Mathematikern noch nie gesehen. Aber selbst wenn FreakC++ das so meint, ergeben seine Sätze immer noch keinen Sinn.
-
freakC++ meint mit A->C die Funktion, die A auf C abbildet, also (g o f), wie belegt durch " weiß ich, dass A -> C injektiv und surjektiv ist". Der ist noch nicht so fit in den Formalitäten, man muss das, was er sagt, erstmal in seinen Kontext projizieren. Das ist nicht der eines Mathematikers, sondern eines Anfängers.
-
Bashar schrieb:
freakC++ meint mit A->C die Funktion, die A auf C abbildet, also (g o f), wie belegt durch " weiß ich, dass A -> C injektiv und surjektiv ist". Der ist noch nicht so fit in den Formalitäten, man muss das, was er sagt, erstmal in seinen Kontext projizieren. Das ist nicht der eines Mathematikers, sondern eines Anfängers.
Ich weiß, ich will ihn nur darauf hinweisen, damit sich seine Ausdrucksweise schnell verbessert.
-
Btw. Jester: Eine Funktion f: A -> B bildet Elemente a \in A nach Elementen f(a) \in B ab. Soweit stimmen wir hoffentlich überein. Welche Signatur hat dann aber eigentlich eine Funktion wie
fun valueAt0 f = f (0)für dich? Konsequenterweise müsste das ja "valueAt0: Hom(int,
-> B" für dich sein. Die meisten funktionalen Sprachen, die ich kenne, würden dazu aber "valueAt0: (int -> -> B" inferieren..