Teilmengen einer Menge < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:30 Fr 12.06.2009 | | Autor: | Audience |
| Aufgabe | | Sei M = {1, ... , n} und seien [mm] A_{1},...,A_{n} \subseteq [/mm] M paarweise verschiedene Teilmengen. Zeigen Sie, dass ein Element x [mm] \in [/mm] M so existiert, dass die Mengen [mm] A_{1} [/mm] \ {x},..., [mm] A_{n} [/mm] \ {x} paarweise verschieden sind. |
Hallo,
mein Lösungsansatz war folgender: Man könnte die gesamte Operation auch als Abbildung von [mm] \mathcal{P}^{M} [/mm] nach [mm] \mathcal{P}^{M \backslash {x}} [/mm] sehen, und dann die Mächtigkeit der Möglichkeiten zählen.
Also die Anzahl, n Teilmengen mit beliebiger Mächtigkeit ohne "Zurücklegen" aus [mm] \mathcal{P}^{M} [/mm] und ohne Beachtung der Reihenfolge zu wählen, beträgt: [mm] \bruch{(2^{n})^{\underline{n}}}{n!}
[/mm]
Diese Mengen werden dann abgebildet auf Teilmengen von einer Menge M' mit |M'| = |M| - 1. Da aber in jeder Teilmenge nun das herausgenommene Element x hätte sein können, hat man wieder [mm] 2^{n-1}*2 [/mm] = [mm] 2^{n} [/mm] mögliche Teilmengen, aus den man auswählen kann und somit wieder [mm] \bruch{(2^{n})^{\underline{n}}}{n!} [/mm] Möglichkeiten.
Da die Mengen gleich mächtig sind, existiert eine bijektive Funktion, die der Operation des Entfernens entspricht.
Ist mein Versuch so sinnvoll und korrekt? Habe ich in eine völlig falsche Richtung gedacht, geht es einfacher?
Danke für eure Meinungen.
Gruß,
Thomas
|
|
| |
|
Hallo Audience,
die Idee sieht erstmal gut aus, klappt aber doch nicht. Die Mächtigkeit der beiden Potenzmengen ist keineswegs gleich! Die Potenzmenge der verkleinerten Menge ist nur halb so groß - eine bijektive Zuordnung daher nicht möglich.
Dies gilt allerdings nur für endliche Mengen, aber so ist M ja angegeben. Die Aufgabe setzt übrigens die Bedingung voraus, dass kein [mm] A_i=\emptyset [/mm] ist.
Mir scheint vollständige Induktion der beste Weg. Oder Du zeigst, dass die Lösbarkeit für n eine Lösung für n-1 impliziert. Wahrscheinlich ist es dabei leichter zu zeigen, dass kein Gegenbeispiel zu konstruieren ist (also ein Widerspruchsbeweis aus der Gegenannahme).
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:36 Fr 12.06.2009 | | Autor: | Audience |
> Hallo Audience,
>
> die Idee sieht erstmal gut aus, klappt aber doch nicht. Die
> Mächtigkeit der beiden Potenzmengen ist keineswegs gleich!
> Die Potenzmenge der verkleinerten Menge ist nur halb so
> groß - eine bijektive Zuordnung daher nicht möglich.
>
Naja, deswegen hatte ich ja die Idee, eine Art "Trace"-Symbol zu verwenden, das anstatt der fehlenden Zahl eingesetzt wird, z.B. "_" den Unterstrich.
Dann hätten wir z.B. für M = {1, 2, 3}
Und [mm] A_{1} [/mm] = {1, 2, 3}, [mm] A_{2} [/mm] = {1}, [mm] A_{3} [/mm] = {2}
dann die Mengen ohne x = 3
A'_{1} = {1, 2, _}, A'_{2} = {1}, A'_{3} = {2}
als Zuordnung usw.
> Dies gilt allerdings nur für endliche Mengen, aber so ist M
> ja angegeben. Die Aufgabe setzt übrigens die Bedingung
> voraus, dass kein [mm]A_i=\emptyset[/mm] ist.
>
> Mir scheint vollständige Induktion der beste Weg. Oder Du
> zeigst, dass die Lösbarkeit für n eine Lösung für n-1
> impliziert. Wahrscheinlich ist es dabei leichter zu zeigen,
> dass kein Gegenbeispiel zu konstruieren ist (also ein
> Widerspruchsbeweis aus der Gegenannahme).
>
> Grüße
> reverend
Hm, okay, werde ich heute Nachmittag mal versuchen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:57 Fr 12.06.2009 | | Autor: | reverend |
Hallo Audience,
Dein Beispiel ist doch ein echtes Gegenbeispiel; nicht nur für x=3 bleiben die reduzierten Mengen paarweise verschieden, sondern auch für 1 und 2. Das genügt ja, um zu zeigen, dass die Annahme nicht zu beweisen ist: sie ist nämlich falsch.
edit: Quark. Ich sollte aufhören, zwei oder drei Dinge gleichzeitig zu machen. Früher schien das zu funktionieren, heute aber sicher nicht. Dein Beispiel ist kein Gegenbeispiel, weil die Behauptung ja für jedes Element von M stimmt. Vielleicht sollte ich ein Attest über temporäre Erblindung vorlegen. Aber woher nehmen?
Mein ursprünglicher Tipp funktioniert aber. Für [mm] M=\{1,2\} [/mm] ist die Behauptung leicht zu zeigen (notfalls per Tabelle), nur der Induktionsschritt von n auf n+1 braucht etwas Hirnschmalz bzw. eine zündende Idee.
Also immer noch: viel Erfolg!
reverend
PS1: Falls Du Dich schon gewundert hast, zu Recht.
PS2: Warum hat eigentlich noch niemand widersprochen? Böses, böses Forum. 
PS3: Ich bereite dann mal weiter meine Ganztagsveranstaltung für morgen vor. Zeit habe ich am Wochenende eigentlich nur noch am Sonntag Nachmittag. Ich schaue aber sicher zwischendurch mal nach, was die Lösung so macht.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:29 Sa 13.06.2009 | | Autor: | Audience |
Hallo,
also hier mein Induktionsversuch.
Induktionsanfang: Für n = 1 ist [mm] A_{1} [/mm] = {} oder {1}. In beiden Fällen kann x = 1 entfernt werden und die enstehehende Menge ist natürlich verschieden zu den anderen (nicht vorhandenen) Mengen.
Induktionsschritt: Sei M={1,..,n} mit den Mengen [mm] A_{i} [/mm] und x gegeben. Erlaube nun die Konstruktion von Mengen [mm] A_{i}', [/mm] die aus [mm] A_{i} [/mm] mit 1 <= i <= n jeweils hervorgehen, in dem man das Element n + 1 hinzufügt oder nicht. Die Menge [mm] A_{n+1}' [/mm] sei wieder eine beliebige Teilmenge von M'={1,...,n+1}
Jetzt unterscheide 2 Fälle:
1. [mm] A_{n+1}' \cap [/mm] M [mm] \not= A_{i} [/mm] (für alle i aus M):
Wähle x'=n+1, da sich alle Mengen ja schon ohne dieses neue Element unterscheiden.
2. Komplementärer Fall, d.h. durch das Streichen von n+1 würden zwei gleiche Mengen enstehen. Dann x'=x, da sich die übrigen Mengen lt. IA sowieso schon durch Streichen dieses Elements unterscheiden und [mm] A_{n+1}' [/mm] sich mindestens auch um {n+1} von allen Elementen [mm] A_{i}' [/mm] (1 <= i <= n) unterscheidet, werden alle enstehenden Mengen ebenfalls paarweise verschieden sein.
Soweit meine Ideen.
Gruß Thomas.
|
|
|
| |
|
Genau richtig argumentiert.
Der Trick besteht darin, immer Mengen darauf zu untersuchen, ob sie n+1 enthalten oder nicht.
Die leere Menge darf übrigends auch dabei sein.
|
|
|
|
