Beweis Injektivität
-
Ja und = ist keine Gleichung sondern ne Zuweisung
Was soll mir das also sagen?Kann ja sein, dass das in der Verifikation ein Knaller ist, da kenn ich mich nicht aus. Du hast das aber bei nem mathematischen Thema aufgebracht und argumentierst jetzt mit irgendwelchen Programmiersprachen, das gilt nicht.
In der Mathematik hab ich sowas jedenfalls noch nie gesehen, und halte die Notation für unbrauchbar um damit zum Beispiel Algebra zu betreiben; warum habe ich am Beispiel demonstriert. Genauso wie man in der Mathematik die Funktion niemals nie valueAt0 nennen würde, sondern einen einbuchstabigen Bezeichner wählen würde.
-
Bei uns an der Uni wird die Notation auch verwendet. Beispielsweise bei der Bestimmung der Objektsprachen von EBNF-Termen, in etwa so wie hier. Die verwendete Funktion [[.]] hat bei uns die Signatur [[.]]: T(Σ,V) -> ((V -> P(Σ*)) -> P(Σ*)). Warum sollte das unbrauchbar sein?
-
Das ist eine Funktionsdefinition in ML. Sorry, die Sprache war vielleicht etwas ungeschickt gewälht. Aber eigentlich tut das auch nichts zur Sache. Ich wollte nur noch mal klarmachen, dass die Definition von "A -> B" als die Menge aller Funktionen von A nach B durchaus *sehr sehr* verbreitet in der Informatik ist.
In der Mathematik kommt die Notation auch vor, allerdings weiß ich da nicht, wie verbreitet sie tatsächlich ist. "Algebra" habe ich nie gehört, also weiß ich auch nicht, was man dort so definiert. Ich hatte aber schon bei deinem ersten Widerspruch zugestanden, dass die Definition ggf. hauptsächlich in der Informatik Verwendung findet.
-
otze schrieb:
Nein, über B musst du keine Aussage treffen. B ist dir völlig egal. Du musst nur eine Aussage über C treffen.
Na klar, denn wenn ich zeigen soll, dass f injektiv ist, bedeutet dies, dass jedes Element der Bildmenge, die in B liegt, höchstens einmal eine Abbildung eines Elements aus der Definitionsmenge darstellt.
otze schrieb:
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?
Das würde dann bedeuteten, dass die Injektivität nicht gegeben ist. Aber die Injektivität der Abbildung g(f(x)). Da weiß ich aber, dass sie gegeben ist. Ich möchte ja zeigen, dass f injektiv ist..
Ich komme einfach nicht dahinter, wie ich von meinem Wissen A -> C ist bijektiv, eine Aussage auf B machen zu können...
Zur Notation: Hier wird sie auch verwendet: http://de.wikipedia.org/wiki/Komposition_(Mathematik)
-
freakC++ schrieb:
otze schrieb:
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?
Das würde dann bedeuteten, dass die Injektivität nicht gegeben ist. Aber die Injektivität der Abbildung g(f(x)). Da weiß ich aber, dass sie gegeben ist.
Klingt nach nem Widerspruch, nicht wahr? *zaunpfahlschwenk*
-
wenn f nicht injektiv ist, gibt es x1 != x2 mit f(x1) == f(x2). Dann kannst du g wählen wie du willst, es wird [b]immer[/i] g(f(x1)) = g(f(x2)) sein, also kann gof nie bijektiv sein, egal wie g aussieht.
Wenn du einem Rudel Hunden Namen gibst, und nennst zwei Hunde "Hasso".
Und anschließend vertauschst du die Namen nach dem Motto "jeder Hasso heißt jetzt Rex, jeder Bonzo heißt jetzt Waldi" usw. - können dann hinterher alle Hunde verschiedene Namen haben ? na also.
-
Mir isses ehrlich gesagt völlig wurscht, ihr dürft das von mir aus für die tollste notation der welt halten. ich halt's für unbrauchbar und benutze sowas nicht. Wer's nutzen mag soll's tun, wer's hier als tolle standardnotation verkauft und dann kein einziges Beispiel aus der Mathematik liefern kann, sondern sich dann in Programmiersprachen flüchtet, muß damit leben dass ich widerspreche.
-
freakC++ schrieb:
Zur Notation: Hier wird sie auch verwendet: http://de.wikipedia.org/wiki/Komposition_(Mathematik)
Du verwendest sie aber nicht ganz korrekt.
Angenommen es gäbe eine injektive Funktion f: A -> B.
Richtig: f ist injektiv.
Falsch: A -> B ist injektiv. Was soll das sein? Wie schon diskutiert bezeichnen manche damit die Menge aller Funktionen mit Definitionsbereich A und Zielbereich B, aber auch dann ist die Aussage unsinnig. Vor allem gibt es gar keinen Bezug zu f.Ich weiß nicht, ob die Definition üblich ist, aber bei uns wurde eine Funktion definiert als (A, B, f) mit der Relation f als Teilmenge von A x B. Dafür wurde die Schreibweise f: A -> B eingeführt. Bei der Relation f kann man jetzt Aussagen über Injektivität oder Surjektivität treffen (wobei der Zielbereich implizit bekannt ist), die Schreibweise A -> B gibt es aber in dem Zusammenhang gar nicht.
Sätze wie „…Wissen A -> C ist bijektiv, eine Aussage auf B…“ machen also keinen Sinn. Du fragst dich bestimmt statt dessen, wie du mit dem Wissen, dass gof bijektiv ist, eine Aussage zu f machen kannst.
-
Mmh...ok, danke für den Hinweis. Wie kann ich denn am besten lernen, möglichst mathematisch korrekt zu schreiben? wahrscheinlich einfach nur, indem ich möglichst viele Aufgaben rechne, möglichst viele Fehler mache und möglichst oft verbessert werde? Oder, gibts auch einen eleganteren Weg?
Zur Übung habe ich mir folgendes überlegt. g muss ja auch surjektiv sein. Mithilfe von !rr!rr_ Ansatz habe ich mir gedacht:
Wenn g nicht surjektiv wäre, dann gilt: g(B) != C. B ist jedoch gerade die Bildmenge von f(A) und damit wäre auch g(f(A)) nicht surjektiv. Da wir jedoch wissen, dass g \circ f bijektiv ist, wäre das ein Widerspruch, sodass g surjektiv sein muss.
Ist das jetzt ein Beweis?
-
Eine kleine Ungenauigkeit: du nimmst an, dass wenn g surjektiv ist, es auch die geliftete Funktion ist, beweist das aber nicht (oder hattet ihr das in der Vorlesung?). Der Beweis dafür ist nicht schwer, günstiger kommst du aber wahrscheinlich, wenn du gar nicht erst über die gelifteten Funktionen gehst. Nimm am besten wieder einen Widerspruchsbeweis.
@Jester: mag ja sein, dass die Notation nicht sehr geläufig ist, aber warum ist sie deiner Meinung nach unbrauchbar?
-
freakC++ schrieb:
Wenn g nicht surjektiv wäre, dann gilt: g(B) != C. B ist jedoch gerade die Bildmenge von f(A)
Nein, f(A) liegt in B, muss aber nicht ganz B sein.
und damit wäre auch g(f(A)) nicht surjektiv. Da wir jedoch wissen, dass g \circ f bijektiv ist, wäre das ein Widerspruch, sodass g surjektiv sein muss.
Ist das jetzt ein Beweis?
Du hast bewiesen, dass g surjektiv ist. Aber solltest du nicht zeigen, dass f injektiv ist?
-
ipsec schrieb:
Eine kleine Ungenauigkeit: du nimmst an, dass wenn g surjektiv ist, es auch die geliftete Funktion ist, beweist das aber nicht (oder hattet ihr das in der Vorlesung?).
Weil es gar nicht stimmen muss, denn f muss nicht surjektiv sein.
BTW: "Geliftete Funktion" hab ich auch noch nie gehört
-
ipsec schrieb:
@Jester: mag ja sein, dass die Notation nicht sehr geläufig ist, aber warum ist sie deiner Meinung nach unbrauchbar?
1. Jester war die Notation nicht geläufig und da er sich für das Maß aller Dinge hält, schloss er daraus, dass sie anderen Informatikern auch nicht geläufig sein kann.
2. Ob die Notation nützlich ist oder nicht, hängt sehr von dem Einsatzgebiet ab. Ich habe ja als Beispiel schon funktionale Programmierung erwähnt. Dort ist die Notation sehr praktisch. Siehe z.B. http://en.wikipedia.org/wiki/Currying.
3. Wie ich Jester schon per Email mitgeteilt habe (um den Thread nicht weiter zuzuspamen), kommt die Notation wohl ursprünglich aus der Mengenlehre. Siehe: http://en.wikipedia.org/wiki/Function_space
4. Wenn Jester als Informatiker behauptet, dass ihm die Notation noch nie begegnet ist, kann man ruhigen Gewissens davon ausgehen, dass er lügt. Ich gehe davon aus, dass er sich bisher einfach noch nie Gedanken darüber gemacht hat, was eigentlich sowas wie "f: A -> B -> C" darstellen soll. Dies sollte er vielleicht mal nachholen.
-
Michael E. schrieb:
BTW: "Geliftete Funktion" hab ich auch noch nie gehört
Ich kenne unter der auf die Potenzmenge geliftete Abbildung f die Abbildung, welche man erhält, wenn man f auf die Potenzmengen überträgt (mit der intuitiven Definition f(T) := {f(t) | t in T}). Vermutlich gibt es da unterschiedliche Bezeichnungen.
-
Achso, dann ignorier meinen letzten Beitrag. Ich bin davon ausgegangen, dass gof die geliftete Funktion sein soll.
-
life schrieb:
4. Wenn Jester als Informatiker behauptet, dass ihm die Notation noch nie begegnet ist, kann man ruhigen Gewissens davon ausgehen, dass er lügt.
Mag ja sein, dass Du das normal findest, aber ich pflege weder zu lügen, noch dies anderen grundlos zu unterstellen. Für mich ist dann alles klar.
Und natürlich weiß ich was f:A->B->C ist, f ist ein Weg von A über B nach C in einem Graphen. Noch Fragen?