Abzählbarkeit von Mengen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:11 Do 04.10.2007 | | Autor: | Dablack |
| Aufgabe | 1. Sei A endlich und B abzählbar. Zeige, dass die Vereinigung von A und B abzählbar ist.
2. Zeige, dass die Vereinigung zweier abzählbarer Mengen A und B wieder abzählbar ist. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Ich bin mit der Theorie einigermaßen vertraut, aber bei der Anwendung hapert's. Mir ist bewusst, dass die Lösung beider Aufgaben vermutlich sehr ähnlich ist, wenn nicht gleich.
1.
Mein Ansatz:
A = {a(1),...,a(n)} n [mm] \in \IN, [/mm] B = {b(n+1),...,b(n+m)} n,m [mm] \in \IN
[/mm]
A [mm] \cup [/mm] B = {a(1),...,a(n),b(n+1),...,b(n+m)} n,m [mm] \in \IN
[/mm]
=> A [mm] \cup [/mm] B ist abzählbar, da die Nachfolgerabbildung S: [mm] \IN [/mm] -> [mm] \IN: [/mm] n |-> n+m bijektiv ist.
2.
Mein Ansatz:
A = {a(1),...,a(n)} n [mm] \in \IN, [/mm] B = {b(-1),...,a(-m)} m [mm] \in \IN
[/mm]
also existiert eine bijektive Abbildung mit f: [mm] \IN [/mm] -> [mm] \IZ.
[/mm]
2. Anlauf:
A = {a(1),...,a(2n-1)}, B = {b(2),...,b(2m)} n,m $ [mm] \in \IN [/mm] $
C = A $ [mm] \cup [/mm] $ B = {a(1),b(2),a(2n-1),...,b(2m)} n,m $ [mm] \in \IN [/mm] $
$ [mm] f(n)=\begin{cases} -n/2, & \mbox{für } n \mbox{ gerade} \\ (n+1)/2, & \mbox{für } n \mbox{ ungerade} \end{cases} [/mm] $
Nun wird wird von $ [mm] \IN [/mm] $ -> $ [mm] \IZ [/mm] $ abgebildet.
Die A's wandern als negative Indizes ins C und die B's als positive.
Ist das so korrekt? Gibt es noch Verbesserungsvorschläge?
Danke schonmal für Anworten.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:54 Do 04.10.2007 | | Autor: | dormant |
Hi!
> 1.
> Mein Ansatz:
> A = {a(1),...,a(n)} n [mm]\in \IN,[/mm] B = {b(n+1),...,b(n+m)} n,m
> [mm]\in \IN[/mm]
>
> A [mm]\cup[/mm] B = {a(1),...,a(n),b(n+1),...,b(n+m)} n,m [mm]\in \IN[/mm]
>
> => A [mm]\cup[/mm] B ist abzählbar, da die Nachfolgerabbildung S:
> [mm]\IN[/mm] -> [mm]\IN:[/mm] n |-> n+m bijektiv ist.
OK!
> 2.
> Mein Ansatz:
> A = {a(1),...,a(n)} n [mm]\in \IN,[/mm] B = {b(-1),...,a(-m)} m [mm]\in \IN[/mm]
Das geht so nicht: negative ganze Zahlen liegen nicht in [mm] \IN. [/mm] Und deswegen gilt nicht, dass:
> also existiert eine bijektive Abbildung mit f: [mm]\IN[/mm] -> [mm]\IZ.[/mm]
Du sollst dir einfach eine andere Durchnumerierung ausdenken. Z.B. gerade und ungerade Zahlen.
Gruß,
dormant
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:15 Do 04.10.2007 | | Autor: | Dablack |
Ok, danke erstmal^^
Ich versuch's noch einmal:
2.
A = {a(1),...,a(n)}, B = {b(1),...,b(m)} n,m [mm] \in \IN
[/mm]
C = A [mm] \cup [/mm] B = {a(1),b(1),a(n),...,b(m)} n,m [mm] \in \IN
[/mm]
[mm] f(n)=\begin{cases} n/2, & \mbox{für } n \mbox{ gerade} \\ (n+1)/2, & \mbox{für } n \mbox{ ungerade} \end{cases}
[/mm]
Nun wird wird von [mm] \IN [/mm] -> [mm] \IN [/mm] abgebildet.
Ist das so korrekt? Gibt es noch Verbesserungsvorschläge?
mfg
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:28 Do 04.10.2007 | | Autor: | dormant |
> 2.
> A = {a(1),...,a(2n-1)}, B = {b(2),...,b(2m)} n,m [mm]\in \IN[/mm]
>
> C = A [mm]\cup[/mm] B = {a(1),b(2),a(2n-1),...,b(2m)} n,m [mm]\in \IN[/mm]
Das ist i.O.
> [mm]f(n)=\begin{cases} -n/2, & \mbox{für } n \mbox{ gerade} \\ (n+1)/2, & \mbox{für } n \mbox{ ungerade} \end{cases}[/mm]
Das ist nicht Ziel der Sache. Man braucht ne Abbildung [mm] A\cup B\rightarrow\IN. [/mm] Eigentlich hast du die Lösung oben.
Die Funktion sieht ungefähr so aus:
[mm] f(\cdot(i))=2i [/mm] für [mm] \cdot=a [/mm] und [mm] f(\cdot(i))=2i+1 [/mm] für [mm] \cdot=b.
[/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:37 Do 04.10.2007 | | Autor: | Blech |
> 1. Sei A endlich und B abzählbar. Zeige, dass die
> Vereinigung von A und B abzählbar ist.
> 2. Zeige, dass die Vereinigung zweier abzählbarer Mengen A
> und B wieder abzählbar ist.
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
> Ich bin mit der Theorie einigermaßen vertraut, aber bei
> der Anwendung hapert's. Mir ist bewusst, dass die Lösung
> beider Aufgaben vermutlich sehr ähnlich ist, wenn nicht
> gleich.
>
> 1.
> Mein Ansatz:
> A = {a(1),...,a(n)} n [mm]\in \IN,[/mm] B = {b(n+1),...,b(n+m)} n,m
> [mm]\in \IN[/mm]
B soll abzählbar unendlich sein, damit gibt es kein letztes Element [mm] $b_{n+m}$
[/mm]
> 2. Anlauf:
Die Grundidee in Deinem 2. Anlauf stimmt: Löse es ähnlich wie der Beweis, daß die ganzen Zahlen abzählbar sind. Die Ausführung ist nur etwas chaotisch =)
$ A = [mm] \{a_1,a_2,a_3,\dots\},\ [/mm] B = [mm] \{b_1,b_2,b_3,\dots\},\ [/mm] C:= [mm] A\cup [/mm] B$
wie oben; A,B sind abzählbar unendlich, damit haben sie kein letztes Element, deswegen ist [mm] $A=\{a_1,\dots,a_n\}$ [/mm] nicht richtig, denn sie impliziert die Existenz eines solchen n; wenn Du ein "n" irgendwo haben willst, schreib es [mm] $A=\{a_n;\ n\in \IN\}$
[/mm]
Gut, was wollen wir nun machen? Wir brauchen eine surjektive Abbildung von [mm] $\IN$ [/mm] nach C, deswegen:
[mm] $f:\IN \to [/mm] C,\ [mm] f(n):=\begin{cases} a_{n/2},\ & \mbox{für } n \mbox{ gerade} \\ b_{(n+1)/2},\ & \mbox{für } n \mbox{ ungerade} \end{cases}$
[/mm]
Surjektivität ist ziemlich offensichtlich,
Nachdem [mm] $|\IN|\geq|C|\geq max\{|A|,|B|\}=|\IN|$ [/mm] sind sie damit gleich mächtig. (die erste Ungleichung gilt, wg der Surjektivität von f, die 2. weil C die Vereinigung ist, die Gleichung, weil A und B abzählbar)
Du kannst auch eine bijektive Abbildung konstruieren, aber f ist i.a. nicht bijektiv (warum?)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:56 Do 04.10.2007 | | Autor: | Dablack |
Vielen Dank euch beiden. Ich glaub jetzt hab ich's halbwegs verstanden. ;)
"Du kannst auch eine bijektive Abbildung konstruieren, aber f ist i.a. nicht bijektiv (warum?)"
Ich vermute, weil die Mengen A und B gleiche Elemente haben können und manche Elemente somit zweimal getroffen werden. Bijektivität nur, wenn beide Mengen disjunkt sind.
mfg
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:58 Do 04.10.2007 | | Autor: | Blech |
> Vielen Dank euch beiden. Ich glaub jetzt hab ich's halbwegs
> verstanden. ;)
Was vorhin vielleicht etwas kurz kam:
[mm] $A=\{a_1,\dots,a_n\},\ n\in \IN$
[/mm]
[mm] $A'=\{a_n;\ n\in\IN\}$
[/mm]
Der Unterschied zwischen den beiden ist wo [mm] $n\in\IN$ [/mm] steht. Bei A kannst Du Dir ein beliebiges n nehmen, aber welches auch immer Du wählst
[mm] $A=\{a_1,\dots,a_n\}$
[/mm]
ist eine endliche Menge.
Beim zweiten ist das [mm] $n\in\IN$ [/mm] in der Mengendefinition, d.h. für jd. beliebige natürliche Zahl n hast Du ein zugehöriges Element [mm] $a_n$. [/mm] Nachdem [mm] $\IN$ [/mm] unendlich ist, ist es auch A'.
Wollte nur nochmal den Unterschied klarstellen.
>
> "Du kannst auch eine bijektive Abbildung konstruieren, aber
> f ist i.a. nicht bijektiv (warum?)"
> Ich vermute, weil die Mengen A und B gleiche Elemente
> haben können und manche Elemente somit zweimal getroffen
> werden. Bijektivität nur, wenn beide Mengen disjunkt sind.
Richtig =)
Man kann sich natürlich aus A und B zwei disjunkte Mengen konstruieren, und dann mit denen weiterarbeiten, aber im Endeffekt verwendet man die gleichen Eigenschaften. Man benutzt sie nur in anderer Reihenfolge.
|
|
|
|
