Abzählbarkeit aller endlichen Teilmengen von N
Andi
kann mir einer von euch helfen, wie ich zeigen kann,
dass die Menge aller endlichen Teilmengen der natürlichen Zahlen abzählbar ist?
Vielen Dank im Voraus
MfG Andi
Thomas Haunhorst
>Sorry, ich stehe gerade auf dem Schlauch,
>kann mir einer von euch helfen, wie ich zeigen kann,
>dass die Menge aller endlichen Teilmengen der natürlichen Zahlen
>abzählbar ist?
Vielleicht koennte man die Mengen so codieren, dass man ueber Primzahlen
eine injektive Abbildung in N erzeugen kann.
Gruss Thomas
--
Martin Wohlgemuth
Eine surjektive Abbildung nach Q würde auch genügen.
Gruß
Martin
Martin Wohlgemuth
Eine injektive Abbildung nach Q würde auch genügen.
Gruß
Martin
Thomas Haunhorst
Na, wenn das mal stimmt.
Gruss Thomas
--
Martin Wohlgemuth
> Sorry, ich stehe gerade auf dem Schlauch,
> kann mir einer von euch helfen, wie ich zeigen kann,
> dass die Menge aller endlichen Teilmengen der natürlichen Zahlen abzählbar ist?
Sei E(N) die Menge der endlichen Teilmengen von N.
Wenn Du schon bewiesen hast oder weißt, daß Q abzählbar ist, dann
konstruiere eine Abbildung von E(N) in Q. Etwa so
Einem Element von E(N), also einer endl. Teilmenge M = {e1, .... , ek },
ordne die rationale Zahle 0,e1e2....ek zu.
Beispiel: {1,12,66,77,183,5,13,7000,99999} -> 0.112667718351370009999
Das Ergebnis ist in jedem Fall in Q, weil M endlich ist.
Leider ist diese Abbildung nicht injektiv, selbst dann nicht, wenn man
die Elemente von M zuerst aufsteigend sortieren würde.
z.B.
{9,9999,100000} -> 0.999991
{99,999,100000} -> 0.999991
{9,9999,10000} -> 0.999991
Injektiv ist notwendig, denn die Abbildung f : IR->IR mit f(x)=0 ist
nicht injektiv und daher auch kein Beleg dafür, daß IR abzählbar ist.
Wat nu?
Vielleicht so:
Sei M aus E(N). Sortiere die Elemente von M nach Größe aufsteigend.
Sei ei das i-te Elemente von M = {e1, ... ek}
Sei si die Anzahl der Dezimalstellen von ei
Sei m das Maximum der si.
Seien Si die linksbündig mit Nullen auf m Stellen aufgefüllten si
Also wenn s1=1 und m=2 => Si="01"
Außerdem sei noch So ein Ziffernfolge bestehend aus m Nullen.
Also wenn m=2 => So="00"
Definiere die Abbildung f so:
f: {e1,e2,....,ek} -> m.s1s2...skSoe1e2...ek
f({9,9999,100000}) = 1.1460999991
f({99,999,100000}) = 1.2360999991
f({9,9999,10000}) = 1.1450999991
f({99999,100000}) = 1.460999991
f ist injektiv, denn wenn
f(M)=f(M') => die maximale Stellenzahl der Elemente aus M und M' ist gleich (m).
Hinter dem Dezimalpunkt von f(M) und f(M') lies nun jeweils m Stellen, solange bis
m Nullen gelesen werden. Da in f(M) und f(M') diese Stellen übereinstimmen, haben
erstens M und M' gleich viele Elemente und die Stellenzahl der Elemente stimmte je-
weils überein. Nenne die gelesenen Zahlen si.
Lies nun weiter jeweils si Stellen. Jeweils si Stellen ergeben eine Zahl, die in M bzw.
M' zu sein hat. Da f(M)=f(M') sind auch die Elemente der Mengen gleich.
Weil nun eine injektive Abbildung von E(N)->Q existiert, ist |E(N)|<=|Q|
Da man schon weiß, daß |N|=|Q| und einfach zu sehen ist, daß |E(N)|>=|N|
ist man am Ziel.
Gruß
Martin
Klaus Loerke
>Sorry, ich stehe gerade auf dem Schlauch,
>kann mir einer von euch helfen, wie ich zeigen kann,
>dass die Menge aller endlichen Teilmengen der natürlichen Zahlen
abzählbar ist?
Gib eine Aufzählung an: erst alle 0-Elementigen Teilmengen, dann alle
1-Elementigen Teilmengen...
und fertig gemäht ist die Wiese
klaus
Janos Blazi
> Gib eine Aufzählung an: erst alle 0-Elementigen Teilmengen, dann alle
> 1-Elementigen Teilmengen...
Ich fürchte, so einfach ist das nicht. Bei diesem Verfahren werden
Teilmengen mit zwei Elementen niemals gezählt.
J.B.
-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
Check out our new Unlimited Server. No Download or Time Limits!
-----== Over 80,000 Newsgroups - 19 Different Servers! ==-----
Johannes S.
> >kann mir einer von euch helfen, wie ich zeigen kann,
> >dass die Menge aller endlichen Teilmengen der natürlichen Zahlen
> abzählbar ist?
>
>
> Gib eine Aufzählung an: erst alle 0-Elementigen Teilmengen, dann alle
> 1-Elementigen Teilmengen...
>
da die Reihenfolge ja keine Rolle spielt (Bsp. 2-elementige Teilmengen):
{1,1},{1,2},{1,3}...{1,n},{2,1},{2,2}...
^^^^^^ ^^^^^^
mit was für einer Art "Regel" bei der Aufzählung kann man diesen Effekt umgehen?
Gruß
Johannes
Klaus Loerke
Andi schrieb in Nachricht ...
>kann mir einer von euch helfen, wie ich zeigen kann,
>dass die Menge aller endlichen Teilmengen der natürlichen Zahlen
abzählbar ist?
Dazu überlegt man sich zunächst, daß für jedes n die Menge aller
n-elementigen Teilmengen abzählbar ist. (Man kann recht leicht eine
Injektion nach N^n finden; und N^n ist abzählbar)
Die Menge aller endlichen Teilmengen ist die Vereinigung über diese
Mengen. Da die Menge aller endlichen Teilmengen eine abzählbare
Vereinigung über abzählbare Mengen ist, ist sie wieder abzählbar.
klaus
Carsten Fritz
Andi wrote:
>
> Sorry, ich stehe gerade auf dem Schlauch,
> kann mir einer von euch helfen, wie ich zeigen kann,
> dass die Menge aller endlichen Teilmengen der natürlichen Zahlen abzählbar
> ist?
>
Wie waere es hiermit: Der endlichen Menge M \subset |N ordnen wir die
Zahl
\sum_{m \in M} 2^m zu.
Gruesse,
Carsten
Rainer Rosenthal
Carsten Fritz <fr...@ti.informatik.uni-kiel.de> wrote
> >
> > ... wie ich zeigen kann, dass die Menge aller endlichen
> > Teilmengen der natürlichen Zahlen abzählbar ist?
> >
>
> Wie waere es hiermit: Der endlichen Menge M \subset |N ordnen wir die
> Zahl
> \sum_{m \in M} 2^m zu.
>
Hmmm..... ja, passt ganz gut zu der Tatsache, dass die
Kardinalzahl einer Menge M gleich 2^M ist. Der Standard-
Beweis dazu beruht ja gerade auf dieser Zuordnung.
Und da 2 eine Primzahl ist ( die kleinste und die geradeste ),
ist auch der Vorschlag von Thomas Haunhorst berücksichtigt :-)
Gruss,
Rainer
Rainer Rosenthal
Rainer Rosenthal <r.ros...@web.de>
> Kardinalzahl einer Menge M gleich 2^M ist
Was wichtiges vergessen:
Kardinalzahl der Potenzmenge einer Menge M
Rainer
Wolfgang Kirschenhofer
Hallo Andreas !
Ich hoffe,Du hast den Vorschlag von Thomas Haunhorst schon
aufgegriffen.
Dies ist bis jetzt die einzige vorgeschlagene Methode,die ich auch
benützen würde;
ein höchstens "dreizeiliger" Beweis.
Ein Hinweis:Jeder zweielementigen Teilmenge {i,j} mit i<j kannst Du
z.B. die natürliche Zahl 2^i*3^j zuordnen.
Überlege Dir,wie das für beliebige endliche Teilmengen mit Hilfe der
Menge der Primzahlen - der Größe nach geordnet - geht.
Gruß,
Wolfgang K.
Sascha Kurz
>Vielleicht koennte man die Mengen so codieren, dass man ueber Primzahlen
>eine injektive Abbildung in N erzeugen kann.
>
>Gruss Thomas
Sei p_i die i-te Primzahl. M endliche Teilmenge von N. e_i=1 wenn x \in M, und 0
sonst.
f(M):=p_1^e_1 * p_2^e_2* ..... (ist endlich, und injektiv).
Diese Abbildungen wurde vor etlichen Monaten in dieser NG angegeben, um zu
zeigen, dass die Potenzmenge von N abzählbar ist. (was natürlich falsch ist.)
Kann mich leider nicht mehr an den Autor erinnern.
Gruss Sascha
--
__________________________________________________________
News suchen, lesen, schreiben mit http://newsgroups.web.de
Michael Hoppe
> Sei p_i die i-te Primzahl. M endliche Teilmenge von N. e_i=1 wenn x \in M,
Du meinst wohl: i \in M, oder?
Michael
--
-= Michael Hoppe <www.michael-hoppe.de>, <m...@michael-hoppe.de> =------
-= Key fingerprint = 74 FD 0A E3 8B 2A 79 82 25 D0 AD 2B 75 6A AE 63
-= PGP public key (0xE0A5731D) available on request. =---------------
Sascha Kurz
>> Sei p_i die i-te Primzahl. M endliche Teilmenge von N. e_i=1 wenn x \in M,
>Du meinst wohl: i \in M, oder?
>
>Michael
Ja, sorry.