Widerspruchsbeweis - richtig?? < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
Hallo,
ganz allgemein:
Wenn ich eine Aussage der Form:
"Gilt die Voraussetzung X, dann folgt Behauptung Y" mit einem Widerspruchsbeweis beweisen will, gehe ich immer folgendermaßen vor?
Angenommen die Behauptung Y gilt nicht....
Dann schlußfolgere ich irgenwann, dass die Voraussetzung Y nicht gilt.
Also gibt es eine Widerspruch zur Voraussetzung. Also war die Annahme, Y gelte nicht, falsch. Woraus der Beweis folgt.
Richtig so???
Beispiele:
Seien L, M und N Mengen und
f: L [mm] \to [/mm] M
g: M [mm] \to [/mm] N Funktionen.
1.)
Behauptung: Ist g [mm] \circ [/mm] f surjektiv, so ist g surjektiv.
Beweis:
Angenommen g ist nicht surjektiv. Daraus folgt:
Es existiert ein z [mm] \in [/mm] N und ein y [mm] \in [/mm] M : g(y) [mm] \not= [/mm] z.
Daraus würde folgen:
Es existiert ein z [mm] \in [/mm] N und ein x [mm] \in [/mm] L : g(f(x)) [mm] \not= [/mm] z.
Also wäre g [mm] \circ [/mm] f nicht surjektiv.
Dies steht im Widerspruch zur Vorausetzung. Also ist die Annahme falsch. Daraus folgt der Beweis.
2.)
Behauptung:
ist g [mm] \circ [/mm] f injektiv, so ist f injektiv.
Beweis:
Angenommen f ist nicht injektiv. Daraus folgt: Es exisitiert [mm] x_{1}, x_{2} \in [/mm] L : [mm] f(x_{1}) [/mm] = [mm] f(x_{2}) \Rightarrow x_{1} \not= x_{2}.
[/mm]
Daraus würde folgen:
Es existiert [mm] x_{1}, x_{2} \in [/mm] L :g( [mm] f(x_{1})) [/mm] =g( [mm] f(x_{2})) \Rightarrow x_{1} \not= x_{2}.
[/mm]
Also wäre g [mm] \circ [/mm] f nicht injektiv. Dies steht im Widerspruch zur Vorausetzung. Also ist die Annahme falsch. Daraus folgt der Beweis.
Ist das okay so?
Noch eine Frage zur Komposition:
gibt es einen Untschied zwischen
g(f(x)) und (g [mm] \circ [/mm] f)(x) ?
viele Grüße, dancingestrella
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:18 Sa 25.12.2004 | | Autor: | Jerry77 |
> Hallo,
>
> ganz allgemein:
> Wenn ich eine Aussage der Form:
> "Gilt die Voraussetzung X, dann folgt Behauptung Y" mit
> einem Widerspruchsbeweis beweisen will, gehe ich immer
> folgendermaßen vor?
>
> Angenommen die Behauptung Y gilt nicht....
> Dann schlußfolgere ich irgenwann, dass die Voraussetzung Y
> nicht gilt.
soll sicher X gilt nicht heissen ..
> Also gibt es eine Widerspruch zur Voraussetzung. Also war
> die Annahme, Y gelte nicht, falsch. Woraus der Beweis
> folgt.
> Richtig so???
> Beispiele:
> Seien L, M und N Mengen und
> f: L [mm]\to[/mm] M
> g: M [mm]\to[/mm] N Funktionen.
>
> 1.)
> Behauptung: Ist g [mm]\circ[/mm] f surjektiv, so ist g surjektiv.
> Beweis:
> Angenommen g ist nicht surjektiv. Daraus folgt:
> Es existiert ein z [mm]\in[/mm] N und ein y [mm]\in[/mm] M : g(y) [mm]\not=[/mm]
> z.
hier muss es heissen,
es ex. ein z so dass fuer alle y [mm]\in[/mm] M gilt g(y) [mm]\not=[/mm]
z. ( mit anderen Worten: z hat kein kein Urbild in M unter der Abbildung g)
Damit wird dann auch der Rest falsch.
> Daraus würde folgen:
> Es existiert ein z [mm]\in[/mm] N und ein x [mm]\in[/mm] L : g(f(x)) [mm]\not=[/mm]
> z.
Also: es existiern natuerlich zu jedem z sehr viele solche x ( im Allgemeinen)
zum Beweis hilft hier, dass zu jedem z ein urbild x in L unter der Komposition g(f(x)) existiert. das liefert den Widerspruch zu der Annahme, g nicht surjektiv.
> Also wäre g [mm]\circ[/mm] f nicht surjektiv.
> Dies steht im Widerspruch zur Vorausetzung. Also ist die
> Annahme falsch. Daraus folgt der Beweis.
d.h. neu aufschreiben , schau es mir dann wieder an
> 2.)
> Behauptung:
> ist g [mm]\circ[/mm] f injektiv, so ist f injektiv.
> Beweis:
> Angenommen f ist nicht injektiv. Daraus folgt: Es
> exisitiert [mm]x_{1}, x_{2} \in[/mm] L : [mm]f(x_{1})[/mm] = [mm]f(x_{2}) \Rightarrow x_{1} \not= x_{2}.
[/mm]
>
> Daraus würde folgen:
> Es existiert [mm]x_{1}, x_{2} \in[/mm] L :g( [mm]f(x_{1}))[/mm] =g(
> [mm]f(x_{2})) \Rightarrow x_{1} \not= x_{2}.
[/mm]
> Also wäre g
> [mm]\circ[/mm] f nicht injektiv. Dies steht im Widerspruch zur
> Vorausetzung. Also ist die Annahme falsch. Daraus folgt
> der Beweis.
>
> Ist das okay so?
leider das selbe wie oben :/
die Existenz der [mm] x_1, x_2 [/mm] ist o.k. und dann nimmst Du die (selben!) [mm] x_1, x_2 [/mm] aus L und betrachtest die Bilder unter der injektiven Abbildung g [mm]\circ[/mm] f. [mm] g(f(x_1) \not [/mm] = [mm] g(f(x_2)) [/mm] , nun waren aber [mm] f(x_1)=f(x_2), \Rightarrow [/mm] Widerspruch
>
> Noch eine Frage zur Komposition:
> gibt es einen Untschied zwischen
> g(f(x)) und (g [mm]\circ[/mm] f)(x) ?
>
> viele Grüße, dancingestrella
>
auf ein Neues , Gruss Jerry
|
|
|
| |
|
Hallo Jerry!
Also nochmal:
Behauptung:
Ist g [mm] \circ [/mm] f surjektiv, so ist auch g surjektiv.
Beweis:
Angenommen g ist nicht surjektiv. Das heißt
es existiert ein z* [mm] \in [/mm] N für alle y [mm] \in [/mm] M : g(y) [mm] \not= [/mm] z*.
(Nach sehr langem Nachdenken ist das auch "anschaulich" logisch  )
(Kann ich jetzt die Voraussetzung nehmen und zeigen, dass sie nicht gilt?
Wenn ja, dann vielleicht so:)
Aus der Surjektivität von g [mm] \circ [/mm] f folgt:
Für alle z [mm] \in [/mm] N existiert ein x [mm] \in [/mm] L : g(f(x)) = z.
Da aber auch z* [mm] \in [/mm] N gilt:
es existiert ein z* [mm] \in [/mm] N für alle x [mm] \in [/mm] L : g(f(x)) [mm] \not= [/mm] z*.
Also g [mm] \circ [/mm] f nicht surjektiv.
Widerspruch zur Annahme.
Ist das inhaltlich und formal ok?
Behauptung:
Ist g [mm] \circ [/mm] f injektiv, so ist auch f injektiv.
Beweis:
Angenommen f ist nicht injektiv. Das heißt
es existieren [mm] x_{1}, x_{2} \in [/mm] L mit [mm] x_{1} \not= x_{2} [/mm] :
f( [mm] x_{1} [/mm] ) = f( [mm] x_{2} [/mm] ).
Aus der Injektivität von g [mm] \circ [/mm] f folgt:
Für alle x, x* [mm] \in [/mm] L mit x = x* : g(f(x)) = g(f(x*)).
Aber: [mm] x_{1}, x_{2} \in [/mm] L. Also [mm] g(f(x_{1} [/mm] )) = g(f( [mm] x_{2} [/mm] )) und [mm] x_{1} \not= x_{2}.
[/mm]
Also g [mm] \circ [/mm] f nicht injektiv.
Widerspruch zur Annahme.
besser so?
gruß, dancingestrella
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 02:45 So 26.12.2004 | | Autor: | Jerry77 |
.. den 2. Beweis kann man so stehen lassen.
Beim 1. ist noch was zu korrigieren:
> Hallo Jerry!
>
> Also nochmal:
>
> Behauptung:
> Ist g [mm]\circ[/mm] f surjektiv, so ist auch g surjektiv.
>
> Beweis:
> Angenommen g ist nicht surjektiv. Das heißt
> es existiert ein z* [mm]\in[/mm] N für alle y [mm]\in[/mm] M : g(y) [mm]\not=[/mm]
> z*.
> (Nach sehr langem Nachdenken ist das auch "anschaulich"
> logisch )
> (Kann ich jetzt die Voraussetzung nehmen und zeigen, dass
> sie nicht gilt?
> Wenn ja, dann vielleicht so:)
> Aus der Surjektivität von g [mm]\circ[/mm] f folgt:
> Für alle z [mm]\in[/mm] N existiert ein x [mm]\in[/mm] L : g(f(x)) = z.
> Da aber auch z* [mm]\in[/mm] N gilt:
und hier musst Du nochmal nachhaken!
> es existiert ein z* [mm]\in[/mm] N für alle x [mm]\in[/mm] L : g(f(x)) [mm]\not=[/mm]
> z*.
Das ist wieder falschrum :(
ich mach den Beweis mal wie ich denke fertig :
zu z* [mm] [mm] \in[/mm] [mm] L existiert also x* mit z*=g(f(x*))
y*:=f(x*) [mm][mm] \in[/mm] [mm] N ist also ein Urbild von z* unter der Abbildung g
(z*=g(y*) ) Widerspruch ( zu g nicht surjektiv!)
ok.
das wars von mir ! (Nachfragen geht natürlich :))
Jerry
|
|
|
| |
|
Hallo Jerry,
Den ersten Beweis habe ich jetzt auch nachvollzogen, nur an einer Stelle hab ich noch eine Frage, deswegen schreibe ich ihn nochmal auf....
Behauptung:
Ist g [mm] \circ [/mm] f surjektiv, so ist g surjektiv.
Beweis:
Angenommen g ist nicht surjektiv. Das heißt es existiert ein x* [mm] \in [/mm] N für alee y [mm] \in [/mm] M : g(y) [mm] \not= [/mm] z*. Aus der Surjektivität von g [mm] \circ [/mm] f folgt: für alle z [mm] \in [/mm] N exisitiert ein x [mm] \in [/mm] L : g(f(x)) = z. Also existiert ein x* [mm] \in [/mm] L für z* [mm] \in [/mm] N mit g(f(x*)) = z*. Setzt man nun f(x*) := y* [mm] \in [/mm] M dann gilt: g(y*) = z*. Also ist g surjektiv. Widerspruch zur Annahme.
Meine Frage: Wieso draf man "Setzt man f(x*) := y*" ??? Setzt das nicht irgenwas voraus?
Dann ist mir aufgefallen, dass der 2. Beweis nicht okay ist, denn ich führe ja die Injektivität von g [mm] \circ [/mm] f zum Widerspruch und nicht die Injektivität von f.
Deswegen habe ich mich da nochmal rangesetzt und bin so weit gekommen:
Behauptung:
Ist g [mm] \circ [/mm] f injektiv, so ist g injektiv.
Beweis:
Angenommen f ist nicht injektiv. Das heißt es existieren [mm] x_{1}, x_{2} [/mm] in L : f( [mm] x_{1} [/mm] ) = f( [mm] x_{2} [/mm] ) [mm] \Rightarrow x_{1} \not= x_{2}. [/mm] Aus der Injektivität von g [mm] \circ [/mm] f folgt: für alle x, [mm] x´\in [/mm] L : g(f(x)) = g(f(x´)) [mm] \Rightarrow [/mm] x = x´. Also gilt für [mm] x_{1}, x_{2} [/mm] in L unter g [mm] \circ [/mm] f: [mm] g(f(x_{1})) [/mm] = [mm] g(f(x_{2})) \Rightarrow x_{1} [/mm] = [mm] x_{2}.
[/mm]
Da fehlt mir jetzt noch der Übergang zum Widerspruch, dass f injektiv ist.
Kannst du mir da nochmal helfen?
viele Grüße, dancingestrella
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:09 So 26.12.2004 | | Autor: | Jerry77 |
Hallo,
> Meine Frage: Wieso draf man "Setzt man f(x*) := y*" ???
> Setzt das nicht irgenwas voraus?
so ist es natürlich falsch: man setzt y*:= f(x*) , denn das kann ich "ausrechnen"
- da ist mir schlicht der ":" auf die falsche Seite gerutscht - sorry
> Dann ist mir aufgefallen, dass der 2. Beweis nicht okay
> ist, denn ich führe ja die Injektivität von g [mm]\circ[/mm] f zum
> Widerspruch und nicht die Injektivität von f.
> Deswegen habe ich mich da nochmal rangesetzt und bin so
> weit gekommen:
>
> Behauptung:
> Ist g [mm]\circ[/mm] f injektiv, so ist g injektiv.
> Beweis:
> Angenommen f ist nicht injektiv. Das heißt es existieren
> [mm]x_{1}, x_{2}[/mm] in L : f( [mm]x_{1}[/mm] ) = f( [mm]x_{2}[/mm] ) [mm]\Rightarrow x_{1} \not= x_{2}.[/mm]
> Aus der Injektivität von g [mm]\circ[/mm] f folgt: für alle x, [mm]x´\in[/mm]
> L : g(f(x)) = g(f(x´)) [mm]\Rightarrow[/mm] x = x´. Also gilt für
> [mm]x_{1}, x_{2}[/mm] in L unter g [mm]\circ[/mm] f: [mm]g(f(x_{1}))[/mm] =
> [mm]g(f(x_{2})) \Rightarrow x_{1}[/mm] = [mm]x_{2}.
[/mm]
>
ist vielleicht zu offensichtlich, denn es steht ja schon da :
f nicht injektiv, d.h. es ex. [mm] x_1, x_2 [/mm]
[mm] f(x_2)=f(x_1) [/mm] =:y für [mm] x_1 [/mm] != [mm] x_2 [/mm] ,
aber
[mm] g(f(x_1) [/mm] ) != [mm] g(f(x_2) [/mm] ) , weil [mm] x_2!=x_1 [/mm] und g [mm]\circ[/mm] f injektiv
nun einsetzen, was wir wissen:
g(y)!=g(y) ist offensichtlich falsch, d.h. Widerspruch
(und das ist ein Widerspruch zu f nicht injektiv, weil für f injektiv ja [mm] f(x_1) [/mm] und [mm] f(x_2) [/mm] verschieden wären, und damit [mm] g(f(x_1))!=g(f(x_2)) [/mm] nichts im Wege stünde)
Gruss,
Jerry
>
|
|
|
| |
|
Hallo, ich bin's schon wieder!
Mir ist gerade, glaube ich, was klargeworden!
So ganz allgemein:
Bei einem Widerspruchsbeweis fange ich ja immer mit "Angenommen (Aussage) X gilt..." an. Dann folgere und folgere und folgere ich... bis ich ganz müde werde vom Folgern... irgendwann VIELEEICHT komme ich auf einen Widerspruch, irgendeinen, z.B. 1 = 2. Kann ich dann nicht aufhören? Es ist ja eigentlich klar, da die ganzen Folgerungen auf eine falsche Annahme beruhen, dass dann 1 = 2 durch die falsche Aussage hervorgerufen wurde. Also muss die Aussage falsch sein.
Also würde es reichen bei 1 = 2 aufzuhören?
Versteht man das was ich meine eigentlich???
nochwas:
das y:= f(x) ist ganz harmlos oder? Ich weiß, es ist eine Definition...Aber dürfen wir das so einfach ersetzen? Es setzt keine blöde Eigenschaft voraus, oder?
gute nacht!
dancingestrella
|
|
|
| |
|
Hallo!
Ich habe mir mal die vorigen Fragen und Antworten nicht durchgelesen, aber ich hoffe, ich kann dir trotzdem helfen...
> So ganz allgemein:
> Bei einem Widerspruchsbeweis fange ich ja immer mit
> "Angenommen (Aussage) X gilt..." an. Dann folgere und
> folgere und folgere ich... bis ich ganz müde werde vom
> Folgern... irgendwann VIELEEICHT komme ich auf einen
> Widerspruch, irgendeinen, z.B. 1 = 2. Kann ich dann nicht
> aufhören? Es ist ja eigentlich klar, da die ganzen
> Folgerungen auf eine falsche Annahme beruhen, dass dann 1 =
> 2 durch die falsche Aussage hervorgerufen wurde. Also muss
> die Aussage falsch sein.
> Also würde es reichen bei 1 = 2 aufzuhören?
> Versteht man das was ich meine eigentlich???
So ganz verstehe ich glaube ich nicht, was du meinst. Aber im Prinzip würde ich sagen, wenn du bei solch einem Widerspruch ankommst, kannst du aufhören. Was hast du denn sonst noch danach gemacht?
Ich würde einen Widerspruchsbeweis ganz kurz so erklären:
du willst z. B. zeigen: [mm] a\Rightarrow [/mm] b (also a sind die Voraussetzungen und b das, was du zeigen sollst)
Du beginnst mit:
Angenommen, es gilt [mm] \neg [/mm] b (also angenommen, die Behauptung stimmt nicht, denn die Behauptung ist ja: es gilt b)
dann folgerst du...
und erhältst irgendwann, dass [mm] \neg [/mm] a gilt
und das wäre ein Widerspruch, denn a war die Voraussetzung. Also hast du gezeigt, dass, wenn die Behauptung nicht stimmt, die Voraussetzung auch nicht stimmen kann. Und somit muss die Behauptung stimmen.
Ich hoffe, ich habe mich jetzt klar ausgedrückt - war doch schwieriger als ich gedacht hatte...
> nochwas:
> das y:= f(x) ist ganz harmlos oder? Ich weiß, es ist eine
> Definition...Aber dürfen wir das so einfach ersetzen? Es
> setzt keine blöde Eigenschaft voraus, oder?
Das ist mir in der Uni glaube ich noch nie so begegnet. Aus alten Schulzeiten sehe ich es einfach als das Gleiche an. Ob es nun y oder f(x) genannt wird, ist meiner Meinung nach egal, von mir aus kannst du es auch Elefant nennen. 
f(x) bedeutet ja, dass es der Funktionswert von x ist, also das, was die Funktion mit deinem x macht. Und y heißt das wahrscheinlich nur, damit man es in ein Koordinatensystem zeichnen kann, bei der die zweite Achse mit y beschriftet ist. Du kannst es aber auch genauso mit f(x) beschriften.
Das ist vielleicht keine gute Begründung, aber für mich ist das beides einfach das Gleiche...
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
|
