Potenzmenge und Abzählbarkeit < Sonstiges < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:19 Sa 29.10.2011 | | Autor: | Summmsel |
| Aufgabe 1 | a) Sei M eine endliche Menge mit genau n [mm] \in [/mm] N Elementen, sei k eine ganze Zahl
mit 0 [mm] \le [/mm] k [mm] \le [/mm] n und sei [mm] \mathcal{P}_k(M) [/mm] die Menge aller Teilmengen A [mm] \subset [/mm] M mit genau k Elementen. Beweisen Sie, dass [mm] \mathcal{P}_k(M) [/mm] genau [mm] \vektor{n \\ k} [/mm] Elemente besitzt |
| Aufgabe 2 | b) Untersuchen Sie, ob die Menge aller Abbildungen f : N [mm] \mapsto [/mm] N mit f(n) [mm] \le [/mm] f(n+1)
für alle n [mm] \in [/mm] N abzählbar oder überabzählbar ist. Wie verhält es sich für die Menge
aller Abbildungen f : N [mm] \mapsto [/mm] N mit f(n) [mm] \ge [/mm] f(n + 1) für alle n [mm] \in [/mm] N? |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo Leute, bei a) habe ich Probleme an die Aufgabe heranzugehen. Ich weiß zwar, dass die Aussage stimmt, doch welche Voraussetzung muss ich benutzen um zu dies zu beweisen?
zu b) Gibt es überhaupt eine solche Abbildung? Denn wie kann f(n) [mm] \ge [/mm] f(n+1) überhaupt erfüllt werden?
Vielleicht hab ich ja auch nur n Brett vorm Kopf (was auch sehr wahrscheinlich ist)
Ich hoffe trotzdem, dass mir jemand helfen kann ;)
|
|
| |
|
Hallo Summmsel, ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
Die Aufgabe ist hier (<- click!) schonmal angefragt worden.
Am Ende meiner sonst recht ranzigen Antwort gibt es aber auch noch zwei Tipps, die Dir vielleicht helfen können.
> Hallo Leute, bei a) habe ich Probleme an die Aufgabe
> heranzugehen. Ich weiß zwar, dass die Aussage stimmt, doch
> welche Voraussetzung muss ich benutzen um zu dies zu
> beweisen?
Siehe den Tipp im oben verlinkten Thread.
> zu b) Gibt es überhaupt eine solche Abbildung? Denn wie
> kann f(n) [mm]\ge[/mm] f(n+1) überhaupt erfüllt werden?
Na, für ein bestimmtes n,n+1 geht das doch einfach, z.B. f(n)=277-n. Da gilt es für alle [mm] 0\le n\le{276}.
[/mm]
> Vielleicht hab ich ja auch nur n Brett vorm Kopf (was auch
> sehr wahrscheinlich ist)
Sieht gar nicht so aus, finde ich. Die Frage ist doch: geht das eigentlich allgemein nicht? Immerhin ist [mm] \IN [/mm] ja abzählbar unendlich groß und nach unten beschränkt. Was sagt das über die Endlichkeit des Wertebereichs von f(n)?
> Ich hoffe trotzdem, dass mir jemand helfen kann ;)
Kommst Du damit schon weiter? Wenn nicht, frag nochmal nach.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:33 Sa 29.10.2011 | | Autor: | Summmsel |
zu b): Also müsste hier dann doch eine Abzählbarkeit und keine Überabzählbarkeit vorliegen, weil f(n) endlich ist, oder? Die Anzahl der Elemente sollte dann doch auch nicht größer sein als die Menge der natürlichen Zahlen, oder?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:42 Sa 29.10.2011 | | Autor: | felixf |
Moin!
> zu b): Also müsste hier dann doch eine Abzählbarkeit und
> keine Überabzählbarkeit vorliegen, weil f(n) endlich ist,
$f(n)$ ist der Funktionswert einer festen Funktion $f$ an einer festen Stelle $n$. Das ist eine natuerliche Zahl und keine Menge.
> oder? Die Anzahl der Elemente sollte dann doch auch nicht
> größer sein als die Menge der natürlichen Zahlen, oder?
Bist du jetzt bei $A := [mm] \{ f : \IN \to \IN \mid \forall n \in \IN : f(n) \le f(n + 1) \}$ [/mm] oder bei $B := [mm] \{ f : \IN \to \IN \mid \forall n \in \IN : f(n) \ge f(n + 1) \}$?
[/mm]
Man kann eine Bijektion von der Menge [mm] $\{ f : \IN \to \IN \}$ [/mm] zur Menge $A$ finden. Was bedeutet das fuer die Maechtigkeit von $A$? (Tipp zur bijektiven Abbildung: ueberleg dir wie man aus einem Tupel $(a, b)$ mit $a, b [mm] \in \IN$ [/mm] beliebig ein Tupel $(a, b)$ mit $a [mm] \le [/mm] b$ macht, und zwar mit einem umkehrbaren Verfahren. Wenn du das raus hast, kannst du es auf Funktionen $f : [mm] \IN \to \IN$ [/mm] verallgemeinern.)
Und die Menge $B$ ist unendlich, jedoch abzaehlbar. Man kann jede solche Funktion $f [mm] \in [/mm] B$ durch endlich viele Paare $(a, b) [mm] \in \N^2$ [/mm] beschreiben. (Tipp: die Funktion $f$ kann hoechstens $f(0)$ verschiedene Werte annehmen.)
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:36 Sa 29.10.2011 | | Autor: | felixf |
Moin!
> Hallo Summmsel,
>
> Die Aufgabe ist hier (<-
> click!) schonmal angefragt worden.
> Am Ende meiner sonst recht ranzigen Antwort gibt es aber
> auch noch zwei Tipps, die Dir vielleicht helfen können.
>
> > Hallo Leute, bei a) habe ich Probleme an die Aufgabe
> > heranzugehen. Ich weiß zwar, dass die Aussage stimmt, doch
> > welche Voraussetzung muss ich benutzen um zu dies zu
> > beweisen?
>
> Siehe den Tipp im oben verlinkten Thread.
>
> > zu b) Gibt es überhaupt eine solche Abbildung? Denn wie
> > kann f(n) [mm]\ge[/mm] f(n+1) überhaupt erfüllt werden?
>
> Na, für ein bestimmtes n,n+1 geht das doch einfach, z.B.
> f(n)=277-n. Da gilt es für alle [mm]0\le n\le{276}.[/mm]
Nimm doch $f(n) = 277 - n$ fuer $n [mm] \le [/mm] 277$, und $f(n) = 0$ fuer $n [mm] \ge [/mm] 277$. Dann erfuellt $f$ dies fuer alle $n [mm] \in \IN$.
[/mm]
(Falls $0 [mm] \not\in \IN$ [/mm] muss man die erste Definition halt fuer $n [mm] \le [/mm] 276$ nehmen und die zweite ersetzen durch $f(n) = 1$ fuer $n [mm] \ge [/mm] 277$.)
LG Felix
|
|
|
|
