schubfachprinzip < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:25 Mi 29.10.2008 | | Autor: | gigi |
| Aufgabe | Zeige:
Für alle n, m [mm] \in \IN [/mm] mit n>m und jede Abbildung f: {1,...,n} [mm] \to [/mm] {1,...,m} gibt es 2 verschiedene [mm] n_1,n_2 \in [/mm] {1,...,n} mit [mm] f(n_1)=f(n_2). [/mm] |
hallo!
ich würde dies gern mit einem beweis durch widerspruch angehen: cih nehme an, f sei injektiv, daraus folgte ja dann, dass für [mm] n_1 \not= n_2 [/mm] gilt [mm] f(n_1) \not= f(n_2). [/mm] dies steht aber im widerspruch zur voraussetzung, dass [mm] f(n_1)=f(n_2).
[/mm]
folgt als, dass f nicht injektiv ist.
und was fehlt mir dann noch, wie kann ich zeigen, dass daraus surjektivität folgt??
danke schonmal
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:30 Mi 29.10.2008 | | Autor: | fred97 |
> Zeige:
> Für alle n, m [mm]\in \IN[/mm] mit n>m und jede Abbildung f:
> {1,...,n} [mm]\to[/mm] {1,...,n} gibt es 2 verschiedene [mm]n_1,n_2 \in[/mm]
> {1,...,n} mit [mm]f(n_1)=f(n_2).[/mm]
> hallo!
>
> ich würde dies gern mit einem beweis durch widerspruch
> angehen: cih nehme an, f sei injektiv, daraus folgte ja
> dann, dass für [mm]n_1 \not= n_2[/mm] gilt [mm]f(n_1) \not= f(n_2).[/mm] dies
> steht aber im widerspruch zur voraussetzung, dass
> [mm]f(n_1)=f(n_2).[/mm]
Das ist doch nicht die Voraussetzung !!!!!
Frage: Def. bereich von f = Zielbereich von f ?????? das kann doch nicht sein . Wo steht n und wo m ?
FRED
> folgt als, dass f nicht injektiv ist.
>
> und was fehlt mir dann noch, wie kann ich zeigen, dass
> daraus surjektivität folgt??
>
> danke schonmal
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:17 Mi 29.10.2008 | | Autor: | gigi |
>
> Das ist doch nicht die Voraussetzung !!!!!
was dann??
>
> Frage: Def. bereich von f = Zielbereich von f ?????? das
> kann doch nicht sein . Wo steht n und wo m ?
sorry, habs oben in der aufgabe korrigiert!
also kann ich den beweis nicht über injektivität--widerspruch führen??!!
>
>
>
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:26 Mi 29.10.2008 | | Autor: | fred97 |
Du sollst zeigen: es gibt [mm] n_1,n_2 \in [/mm] {1, ... , n} mit: [mm] f(n_1) [/mm] = [mm] f(n_2).
[/mm]
Nimm an, die sei nicht der Fall. Dann hat f({1, ... , n }) genau n Elemente.
Wegen f({1, ... , n [mm] })\subseteq [/mm] {1, ... , m} hat f({1, ... , n }) höchstens m Elemente. Somit muß n [mm] \le [/mm] m sein, im Widerspruch zur Vor. n>m.
FRED
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:56 Mi 29.10.2008 | | Autor: | gigi |
> Du sollst zeigen: es gibt [mm]n_1,n_2 \in[/mm] {1, ... , n} mit:
> [mm]f(n_1)[/mm] = [mm]f(n_2).[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
>
> Nimm an, die sei nicht der Fall. Dann hat f({1, ... , n })
> genau n Elemente.
das kann man hier einfach so folgern ohne es noch irgendwie zu beweisen?
> Wegen f({1, ... , n [mm]})\subseteq[/mm] {1, ... , m}
woher weiß man denn das?
hat f({1, ...
> , n }) höchstens m Elemente. Somit muß n [mm]\le[/mm] m sein, im
> Widerspruch zur Vor. n>m.
und das wäre dann der vollständige beweis?
>
> FRED
gigi.
|
|
|
| |
|
> > Du sollst zeigen: es gibt [mm]n_1,n_2 \in[/mm] {1, ... , n} mit:
> > [mm]f(n_1)[/mm] = [mm]f(n_2).[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Eingabefehler: "{" und "}" müssen immer
> paarweise auftreten, es wurde aber ein Teil ohne
> Entsprechung gefunden (siehe rote Markierung)
>
>
> >
> > Nimm an, die sei nicht der Fall. Dann hat f({1, ... , n })
> > genau n Elemente.
>
> das kann man hier einfach so folgern ohne es noch irgendwie
> zu beweisen?
Hallo,
ist es Dir nicht klar?
Wenn nicht zwei Funktionswerte gleich sind, sind alle Funktionswerte verschieden. Deshalb enthält dann das Bild n Elemente.
> > Wegen f({1, ... , n [mm]})\subseteq[/mm] {1, ... , m}
>
> woher weiß man denn das?
Kann das Bild was anderes sein als eine Teilmenge der Zielmenge?
Falls Du Zweifel hast, beweise die Aussage.
> hat f({1, ...
> > , n }) höchstens m Elemente. Somit muß n [mm]\le[/mm] m sein, im
> > Widerspruch zur Vor. n>m.
>
> und das wäre dann der vollständige beweis?
Was läßt Dich zweifeln? Was fehlt Dir?
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:19 Mi 29.10.2008 | | Autor: | gigi |
ich kann es schon nachvollziehen, nur bekomme ich bei beweisen dieser art meist höchstens die halbe punktzahl!
war mein ansatz mit der injektivität so falsch? warum kann ich nicht darüber einen widerspruch erzeugen und die aussage damit beweisen?
danke auf alle fälle!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:20 Mi 29.10.2008 | | Autor: | Marcel |
Hallo,
> ich kann es schon nachvollziehen, nur bekomme ich bei
> beweisen dieser art meist höchstens die halbe punktzahl!
mir ist das durchaus klar. Das liegt schon daran, dass Du die Aufgabenstellung missverstehst.
> Für alle n, m $ [mm] \in \IN [/mm] $ mit n>m und jede Abbildung f: {1,...,n} $ [mm] \to [/mm] $
> {1,...,m} gibt es 2 verschiedene $ [mm] n_1,n_2 \in [/mm] $ {1,...,n} mit
> [mm] $f(n_1)=f(n_2). [/mm] $
Was kann man nun voraussetzen? Naja, man soll etwas für alle Abbildungen [mm] $\black{f}$ [/mm] mit der Eigenschaft... zeigen. Also soll das für jede Abbildung [mm] $\black{f}$ [/mm] mit der Eigenschaft... gelten, m.a.W.:
Ist [mm] $\black{f}$ [/mm] irgendeine Abbildung mit der Eigenschaft...
Also:
Voraussetzung (nennen wir das mal (A)):
(A) Es sei $f: [mm] \{1,...,n\} \to \{1,...,m\}$ [/mm] nun irgendeine Abbildung, so dasss folgendes gilt:
Es seien $n,m [mm] \in \IN$ [/mm] beliebig, aber fest und es gelte $n > m$.
Zu zeigen (nennen wir das mal (B)):
(B) Dann gibt es [mm] $n_1,n_2 \in \{1,...,n\}$ [/mm] mit [mm] $n_1 \not= n_2$ [/mm] und [mm] $f(n_1)=f(n_2)$.
[/mm]
(Mit anderen Worten: Es ist nun zu zeigen, dass dann [mm] $\black{f}$ [/mm] nicht injektiv ist.)
> war mein ansatz mit der injektivität so falsch? warum kann
> ich nicht darüber einen widerspruch erzeugen und die
> aussage damit beweisen?
Genau das macht Fred doch. Strenggenommen: Er macht einen Beweis durch Kontraposition. Zu zeigen ist $(A) [mm] \Rightarrow [/mm] (B)$, das ist äquivalent zur Kontraposition:
[mm] $$\neg(B) \Rightarrow \neg(A)\,.$$
[/mm]
Fred geht nun davon aus, dass (B) nicht gelte.
(Laut Kontraposition wäre dann zu zeigen, dass dann auch (A) nicht gilt.)
Nun gehen wir weiter davon aus, dass (A) aber doch gelte.
(Das ist nun ein, wie man manchmal sagt, Pseudo-Widerspruchsbeweis, weil man eigentlich einen Beweis durch Kontraposition führt, so dass man [mm] $\neg(B) \Rightarrow \neg(A)$ [/mm] beweist und dann sagt, dass (A) und [mm] $\neg(A)$ [/mm] nicht zusammen gelten können.)
Wir gehen nun also davon aus, dass (A) zwar gelte, aber (B) falsch sei und müssen das zu einem Widerspruch führen:
Gelte nun also [mm] $\neg(B)$, [/mm] bzw. (B) gelte nicht. Dann gibt es keine [mm] $n_1,n_2 \in \{1,...,n\}$ [/mm] mit [mm] $n_1 \not=n_2$ [/mm] und [mm] $f(n_1)=f(n_2)$. [/mm] Also für alle [mm] $n_1,n_2 \in \{1,...,n\}$ [/mm] mit [mm] $n_1 \not=n_2$ [/mm] gilt [mm] $f(n_1) \not=f(n_2)$, [/mm] bzw. mit anderen Worten: Dann ist [mm] $\black{f}$ [/mm] injektiv.
Weil [mm] $\black{f}$ [/mm] injektiv ist, folgt, dass [mm] $f(\{1,...,n\})$ [/mm] auch genau $n$ verschiedene Elemente haben muss (strenggenommen kann es sein, dass ihr hier eine Definition des Begriffes Anzahl der Elemente einer endlichen Menge ins Spiel bringen müsstet/solltet).
Weil $f: [mm] \{1,...,n\} \to \{1,...,m\}$ [/mm] war und daher [mm] $f(\{1,...,n\}) \subseteq \{1,...,m\}$, [/mm] bedeutet dies nichts anderes, als das [mm] $\{1,...,m\}$ [/mm] mindestens $n$ paarweise verschiedene Elemente enthalten muss. Dies bedeutet aber gerade $m [mm] \ge [/mm] n$.
In (A) wurde aber insbesondere $n > m$ verlangt. Wir haben nun gezeigt, dass, wenn zwar (A), aber (B) nicht, gilt, dann gilt $m [mm] \ge [/mm] n$. Die Bedingung $n > m$ wird aber in (A) verlangt, also müsste nun einerseits $n > m$ (wegen (A)) gelten, andererseits auch $m [mm] \ge [/mm] n$ (weil (B) nicht gilt bzw. weil [mm] $\neg(B)$ [/mm] gilt).
Also:
(A) und [mm] $\neg(B)$ [/mm] liefern:
[mm] $$\blue{n > m} \blue{\text{ und }} \blue{m \ge n}\,.$$ [/mm]
Das Blaugeschriebene kann aber nicht gelten (nach Transitivität würde es $n > m [mm] \ge [/mm] n$, also insbesondere $n > n$ implizieren, was der Trichotomie widerspricht), also: Widerspruch.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:22 Do 30.10.2008 | | Autor: | gigi |
danke nochmal an alle für die ausführlichen erklärungen!
|
|
|
|
