Beweis Schubfachprinzip < Abbildungen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | a)Beweise das Schubfachprinzip:
Seien [mm] m,n\in \IN, [/mm] m>n, A eine Menge mit m Elementen und B eine Menge mit n Elementen. Ist f: [mm] A\to [/mm] B eine Abbildung [mm] \Rightarrow [/mm] f ist nicht injektiv.
b)Beweisen Sie mit Hilfe des Schubfachfachprinzips:
Sei [mm] n\in \IN [/mm] eine ungerade Zahl, A={1,...,n} und [mm] \pi:A\to [/mm] A eine Permutation. Dann ist
a:= [mm] (\pi (1)-1)(\pi (2)-2)...(\pi [/mm] (n)-n) eine gerade Zahl.
(Hinweis: versuchen sie einen Widerspruchsbeweis zu führen. Nehmen sie an, a wäre ungerade. Betrachten sie dann das Produkt einer geraden und einer ungeraden Zahl und schließen sie daraus, dss alle Terme in dem obigen Produkt gerade/ungerade sein müssen.) |
Also erstmal zu a)
Nur mal zum bildlichen Verständnis: Menge A={1,2,3,4,5,6,...,}
B={2,4,6,8,10,..,} . Eine Menge wird nun also auf die andere Abgebildet.
injektiv heißt injektiv, wenn zu jedem a aus A höchstens ein b aus B existiert mit f(a)=b.
Aber wie führe ich da nun einen widerspruchsbeweis durch?
|
|
| |
|
> a)Beweise das Schubfachprinzip:
> Seien [mm]m,n\in \IN,[/mm] m>n, A eine Menge mit m Elementen und B
> eine Menge mit n Elementen. Ist f: [mm]A\to[/mm] B eine Abbildung
> [mm]\Rightarrow[/mm] f ist nicht injektiv.
>
> b)Beweisen Sie mit Hilfe des Schubfachfachprinzips:
> Sei [mm]n\in \IN[/mm] eine ungerade Zahl, A={1,...,n} und [mm]\pi:A\to[/mm]
> A eine Permutation. Dann ist
> a:= [mm](\pi (1)-1)(\pi (2)-2)...(\pi[/mm] (n)-n) eine gerade Zahl.
>
> (Hinweis: versuchen sie einen Widerspruchsbeweis zu
> führen. Nehmen sie an, a wäre ungerade. Betrachten sie
> dann das Produkt einer geraden und einer ungeraden Zahl und
> schließen sie daraus, dss alle Terme in dem obigen Produkt
> gerade/ungerade sein müssen.)
> Also erstmal zu a)
>
> Nur mal zum bildlichen Verständnis: Menge
> A={1,2,3,4,5,6,...,}
> B={2,4,6,8,10,..,} .
Hallo,
nein, Du mißachtest eine wesentliche Voraussetzung: die Mengen A und B sind beide endlich, und ihre Mächtigkeiten sollen verschieden sein.
Deine Mengen sind nicht endlich und von gleicher Mächtigkeit...
> injektiv heißt injektiv, wenn zu jedem a aus A höchstens
> ein b aus B existiert mit f(a)=b.
Ja.
> Aber wie führe ich da nun einen widerspruchsbeweis durch?
Mach Dir erstmal ein passendes konkretes Beispiel und mach Dir daran klar, warum f nicht injektiv sein kann.
Dazu kannst Du versuchen, ine injektive Funktion zu konstruieren.
Zum Widerspruchsbeweis:
nimm an, daß f injektiv ist. Schätze die Mächtigkeit von B nach unten ab.
Gruß v. Angela
|
|
|
| |
|
okay, dann versuche ich das mal anders...
A= (1,3,5,7,9,)
B= (2,4,5,8)
Für eine endliche Menge A ist die Mächtigkeit | A | einfach die Anzahl der Elemente von A, also in meinem Fall 5.
st nun f: [mm] A\to [/mm] B eine injektive Funktion zwischen endlichen Mengen, dann muss B mindestens genauso viele Elemente wie A haben, es gilt also [mm] |B|\ge [/mm] |A|
das heißt dann also Ist f: [mm] A\to [/mm] B eine Funktion zwischen endlichen Mengen und gilt | B | < | A | , dann ist f nicht injektiv. Es gibt also (mindestens) zwei verschiedene Elemente x und y von A mit f(x) = f(y).
Das ist eine einzige Idee, aber ich denke, das ist zu ungenau für diese Aufgabe und reicht als Beweis nicht aus oder? Brauche wirklich Hilfe weil ich es nicht hinbekomme....
Grüße
Mathegirl
|
|
|
| |
|
> okay, dann versuche ich das mal anders...
> A= (1,3,5,7,9,)
> B= (2,4,5,8)
>
>
> Für eine endliche Menge A ist die Mächtigkeit | A |
> einfach die Anzahl der Elemente von A, also in meinem Fall
> 5.
>
> st nun f: [mm]A\to[/mm] B eine injektive Funktion zwischen
> endlichen Mengen, dann muss B mindestens genauso viele
> Elemente wie A haben, es gilt also [mm]|B|\ge[/mm] |A|
>
> das heißt dann also Ist f: [mm]A\to[/mm] B eine Funktion zwischen
> endlichen Mengen und gilt | B | < | A | , dann ist f nicht
> injektiv. Es gibt also (mindestens) zwei verschiedene
> Elemente x und y von A mit f(x) = f(y).
>
> Das ist eine einzige Idee, aber ich denke, das ist zu
> ungenau für diese Aufgabe und reicht als Beweis nicht aus
> oder? Brauche wirklich Hilfe weil ich es nicht
> hinbekomme....
Hallo,
der Gedanke ist goldrichtig.
Also mal langsam.
Sei |A|=m, also [mm] A=\{a_1, ..., a_m\} [/mm] mit paarweise verschiedenen [mm] a_i [/mm] und |B|=n, m>n.
Es ist f(A)= [mm] \{ .... \} \subseteq [/mm] B,
also |f(A)| [mm] \le [/mm] n.
Was bedeutet das für die Elemente in f(A), die Du oben aufgezählt hast?
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 09:56 Do 05.11.2009 | | Autor: | Mathegirl |
Hallo Angela,
ich habe leider nicht verstanden, was du mit der Frage gemeint hast...
f(A) muss doch größer sein als n...??
Grüße
Mathegirl
|
|
|
| |
|
> ich habe leider nicht verstanden, was du mit der Frage
> gemeint hast...
Hallo,
ja, dafür hättest Du auch mal f(A) explizit aufschreiben müssen.
Ich hat's doch so schön als Lückentext vorbereitet.
Gruß v. Angela
|
|
|
| |
|
Kann mir jemand einen Hinweis dazu geben, wie man die Aufgabe b lösen könnte?? ich verstehe das nicht. Aufgabe a) ging ja noch aber ich versteh (trotz ewigem Lesen und Begriffsklären!!!!!!!!!!) die Aufgabe einfach nicht.
für Hilfe wäre ich sehr dankbar!!
Mathegirl
|
|
|
| |
|
> Kann mir jemand einen Hinweis dazu geben, wie man die
> Aufgabe b lösen könnte?? ich verstehe das nicht. Aufgabe
> a) ging ja noch aber ich versteh (trotz ewigem Lesen und
> Begriffsklären!!!!!!!!!!) die Aufgabe einfach nicht.
>
> für Hilfe wäre ich sehr dankbar!!
Hallo,
was genau verstehst Du nicht?
Die Aufgabenstellung?
Stimmt die Aussage denn für n=5?
Konntest Du das testen? Wenn ja: wie?
Wenn nein: woran scheitert es?
Gruß v. Angela
|
|
|
|
