Aufzählbar und abzählbar: Wo liegt der genaue Unterschied?
Konrad Wenzl
Uni in Karlsruhe. Nun haben wir in der Informatikvorlesung derzeit das Thema
Berechenbarkeit! Und dabei traten und treten immer wieder die Begriffe
"abzählbar" und "aufzählbar" auf!
Leider wird jedoch in unserem Skript keine absolut exakte Definition von
beidem gegeben!
So, daher wäre ich sehr erfreut, wenn jemand von euch mir die genauen
Definitionen geben könnte und vielleicht auch noch eine Erläuterung des
Unterschieds zwischen beiden oben genannten Begriffen!
Thanx Konrad
Tobias
Eine Menge A heisst aufzählbar, wenn ein Algorithmus existiert
(Aufzählungsalgorithmus), der
ohne Eingabe startet, und alle Elemente der Menge in irgendeiner Reihenfolge
(evenutell auch
mit Wiederholungen) ausgibt. Der Begriff der Aufzählbarkeit ist äquivalent
zur Semi-entscheid-
barkeit.
Eine Menge A heisst hingegen abzählbar, wenn eine surjektive Abbildung f :
N -> A (N bezeichnet
die natürlichen Zahlen) existiert, wenn sich also die Elemente von A
durchnummerieren lassen.
Ich hoffe, ich konnte dir ein wenig helfen.
MfG
Tobias
"Konrad Wenzl" <Minas...@gmx.de> schrieb im Newsbeitrag
news:93t6hv$s74$1...@news.rz.uni-karlsruhe.de...
Konrad Wenzl
"Tobias" <t.k...@t.online.de> schrieb im Newsbeitrag
news:93t9h7$mm4$1...@nets3.rz.RWTH-Aachen.DE...
> Hi!!!
>
> Eine Menge A heisst aufzählbar, wenn ein Algorithmus existiert
> (Aufzählungsalgorithmus), der
> ohne Eingabe startet, und alle Elemente der Menge in irgendeiner
Reihenfolge
> (evenutell auch
> mit Wiederholungen) ausgibt. Der Begriff der Aufzählbarkeit ist äquivalent
> zur Semi-entscheid-
> barkeit.
> Eine Menge A heisst hingegen abzählbar, wenn eine surjektive Abbildung f :
> N -> A (N bezeichnet
> die natürlichen Zahlen) existiert, wenn sich also die Elemente von A
> durchnummerieren lassen.
> Ich hoffe, ich konnte dir ein wenig helfen.
>
> MfG
> Tobias
>
>
Def. der Abzählbarkeit:
Ich dachte, die Def. der Abzählbarkeit einer Menge M wäre:
Es gibt eine bijektive Abbildung von M in N oder eine Teilmenge von N????
Hab ich da jetzt was falsch verstanden?
Bijektiv heisst doch eineindeutig, surjektiv nicht? oder ist bei der
Umkehrung der Abbildungsrichtung, denn bei dir geht die Abbildung ja von N
auf M (oder A in deinem Fall), dann surjektiv die entsprechung zu bijektiv??
Sorry wenn ich mich so anstelle, aber so ganz blick ich das halt nicht!!! ??
;-]
MfG Konrad
Patrick Breuer
>
> "Tobias" <t.k...@t.online.de> schrieb im Newsbeitrag
> news:93t9h7$mm4$1...@nets3.rz.RWTH-Aachen.DE...
> > Eine Menge A heisst hingegen abzählbar, wenn eine surjektive Abbildung f :
> > N -> A (N bezeichnet
> > die natürlichen Zahlen) existiert, wenn sich also die Elemente von A
> > durchnummerieren lassen.
> Danke für deine prompte Antwort Tobias, aber ich hab da noch ne Frage zur
> Def. der Abzählbarkeit:
> Ich dachte, die Def. der Abzählbarkeit einer Menge M wäre:
> Es gibt eine bijektive Abbildung von M in N oder eine Teilmenge von N????
> MfG Konrad
Hallo Konrad,
deine Definition ist die richtige, die von Tobias lässt sich daraus
herleiten:
Definition:
Eine Menge M heißt abzählbar, wenn sie entweder endlichist oder wenn
eine Bijektion g von M nach N existiert.
Satz:
Eine Menge M ist genau dann abzählbar, wenn sie Wertebereich einer
totalen surjektiven Funktion f:N->M ist.
Beweis:
Ist M abzählbar, existiert nach Def. eine Bijektion g:N->M; diese ist
total und surjektiv.
Sei umgekehrt M Wertebereich einer totalen und surjektiven Funktion
f:N->M. Falls M endlich ist, ist sie nach Def. abzählbar. Falls M
unendlich ist, kann man eine bijektive Funktion g:N->M induktiv
definieren:
Setze g(0)=f(0).
Ann.: Für ein n aus N liegt g(n) fest, und es ist g(n)=f(t(n)).
Dann definiert man
t(n+1)=min{j aus N| j>t(n), f(j)<>f(i) für jedes i mit 0<=i<=t(n)}
und setzt g(n+1)=f(t(n+1)).
Gruß
Patrick Breuer
Roland Harnau
da fehlt ein "h" ;-)
[...]
> Danke für deine prompte Antwort Tobias, aber ich hab da noch ne Frage zur
> Def. der Abzählbarkeit:
> Ich dachte, die Def. der Abzählbarkeit einer Menge M wäre:
> Es gibt eine bijektive Abbildung von M in N oder eine Teilmenge von N????
> Hab ich da jetzt was falsch verstanden?
> Bijektiv heisst doch eineindeutig, surjektiv nicht? oder ist bei der
> Umkehrung der Abbildungsrichtung, denn bei dir geht die Abbildung ja von N
> auf M (oder A in deinem Fall), dann surjektiv die entsprechung zu bijektiv??
> Sorry wenn ich mich so anstelle, aber so ganz blick ich das halt nicht!!! ??
> ;-]
Beide Defs sind (für M!={}) äquivalent:
Sei M (M!={}) eine Menge.
*Def1* M ist _abzählbar_ gdw. es gibt eine Surjektion f:N->M.
*Def2* M ist _abzählbar_ gdw. es ex. eine Injektion g:M->N. (wobei g,
nachbeschränkt auf die Bildmenge, natürlich bijektiv
(=surjektiv+injektiv) ist)
Wenn man eine Injektion g:M->N besitzt, läßt sich die Surjektion
f: N->M mit f(x)= g^{-1}(x), falls x in g(M), und sonst f(x)=a für ein bel. a
in M definieren.
Umgekehrt läßt sich mit einer Surjektion f:N->M eine
Injektion durch g:M->N, x|-> min f^{-1}({x}) definieren.
Es gilt im übrigens allgemein, dass (für b!={}) die Existenz einer Surjektion
f:a->b äquivalent zur Existenz einer Injektion g:b->a ist, wobei die
Konstruktion der Injektion aus der Surjektion i.A. nicht ohne
Auswahlaxiom auskommt.
roland
Michael Albrecht
Weil wir gerade bei diesem Thema sind und ich den Begriff Aufzählbarkeit als
Mathematikstudent in meiner MaTA-Abschlußprüfung das erste Mal um die Ohren
gehauen bekommen habe, hätte ich mal eine Frage:
Gibt es eine abzählbare Menge, die nicht aufzählbar ist?
Danke im voraus
Michael
Thomas Haunhorst
Michael Albrecht <ma...@michael-albrecht.de> wrote:
>Gibt es eine abzählbare Menge, die nicht aufzählbar ist?
Die gibt es. Denn ist eine Menge W nicht entscheidbar, so ist W oder ihr
Komplement (bzgl. der Menge aller Woerter eines Alphabetes) nicht aufzaehlbar.
Gruss
Thomas.
--
Thomas Haunhorst
Thomas Haunhorst <Thomas.H...@HEH.Uni-Oldenburg.DE> wrote:
>Die gibt es. Denn ist eine Menge W nicht entscheidbar, so ist W oder ihr
>Komplement (bzgl. der Menge aller Woerter eines Alphabetes) nicht aufzaehlbar.
Oder anders gesagt: Waeren alle abzaehlbaren Mengen von Woertern ueber einem
abzaehlbaren Alphabet aufzaehlbar, so waeren alle diese Mengen auch entscheid-
bar.
--