Diskussion:Abzählbare Menge

primzahlen

Ist die Menge der Primzahlen abzählbar?

--Himmelsfisch 16:42, 18. Jan 2005 (CET)

Ja, denn die Menge aller Primzahlen ist eine Untermenge der Menge der natürlichen Zahlen.

--Barbarossa | Δ 17:32, 18. Jan 2005 (CET)

herrstellung einer bijektion von N auf N

Aus dem Artikel entfernt (es geht um die Herstellung einer Bijektion von N auf N):

Dafür benötigt man zwar unendlich lange und auch unendlich große Zahlen, aber es ist prinzipiell möglich.

Die Behauptung, man bräuchte unendlich lange impliziert, dass man eine Zahl nach der anderen Zuordnen müsste und dass diese Zuordnung Zeit verbraucht - ersteres wird durch die explizite Angabe einer Funktion umgangen, und zweiteres hat in der reinen Mathematik (in der wir uns hier befinden) keinen Sinn. Die Erwähnung unendlich großer Zahlen ist missverständlich bis falsch (es gibt keine unendlich großen Zahlen, aber die zugeordneten Zahlen werden beliebig groß). --SirJective 22:31, 23. Jan 2005 (CET)

Absatz: Die Menge aller rationalen Zahlen

Ich frage mich, warum eine rationale Zahl q durch DREI natürliche Zahlen in der genannten Form als Bruch dargestellt werden muss. Meines Erachtens genügen doch ZWEI natürliche Zahlen für diese Darstellung, z.B. q := a/b mit a,b aus IN. Wenn es aber bestimmte Gründe für die gewählte Darstellung gibt(etwa um die erforderliche Bijektivität der Abbildung zu gewähren), sollte dies erwähnt und ggf. etwas näher erläutert werden.

Mit nur zwei natürlichen Zahlen wird die Darstellung der negativen Brüche problematisch. Natürlich könnte man es hintricksen, aber dann könnte man sich auch gleich auf eine einzige natürliche Zahl beschränken. Mit drei natürlichen Zahlen dagegen ist die Darstellung einigermaßen einfach. Bijektiv ist die Abbildung jedoch nicht, aber surjektiv reicht schon.--MKI 15:39, 1. Okt 2005 (CEST)

Die anderen Beispiele kommen mit N statt N0 aus. Das würde auch dieses Beispiel vereinfachen, da wir uns unter dem Bruch das "1+" ersparen würden.

Absatz: Ganze Zahlen

Ich denke mal das die zweite Abbildung falsch ist. Diese sollte alle ganzen Zahlen z bijektiv auf die natürlichen Zahlen abbilden. Also sollte sie heißen: z -> -2z, wenn z < 0 und z -> 2z + 1, wenn z >= 0

anstatt wie es momentan propagiert wird:

z -> -2z, wenn z < 0 und z -> 2z - 1, wenn z >= 0

Ich hab das mal ausgebessert, falls ich doch falsch liegen sollte kann man es ja wieder rausnehmen :) --84.57.5.165 20:38, 13. Dez 2005 (CET)

Die Definition von Abzählbarkeit ist garantiert falsch (auch wenn ich kein Mathematiker bin, ist das klar), denn nach dieser Definition wäre z.B. auch die Menge der rationalen Zahlen abzählbar (da sie die gleiche Mächtigkeit wie die Menge der natürlichen Zahlen hat), was jedoch falsch ist. (Es gibt zwischen zwei rationalen Zahlen stets unendlich viele weitere rationale Zahlen. ES widerspräche daher dem Sprachgebrauch von abzählbar, wenn die Menge der rationalen Zahlen als abzählbar gelten sollte.) (nicht signierter Beitrag von PhilOrganum (Diskussion | Beiträge) 13:00, 28. Sep 2006)

Die Definition ist korrekt, und wie auch schon im Artikel steht, ist die Menge der rationalen Zahlen in der Tat abzählbar. Mathematische Begriffe unterscheiden sich manchmal stark von ihrer Alltagsbedeutung, kaum jemand würde beispielsweise so etwas fragiles wie den Cantor-Staub oder den Menger-Schwamm im Alltagssinne als kompakt ansehen.--Gunther 13:19, 28. Sep 2006 (CEST)

@ Gunther: Deine Replik ist zwar nicht besonders informativ, aber du hast anscheinend Recht. Gibt es eigentlich auch eine Bezeichnung für die Eigenschaft von (Zahl-)Mengen, dass es zu keiner Zahl eine nächstgrößere oder -kleinere gibt?

Was du meinst, nennt man „in sich dicht liegen“. (Die Erklärung unter Dicht (Mathematik) ist allerdings leider unverdaulich.) Das Abzählen hat dagegen nichts mit der Anordnung zu tun: Bei der Cantor-Diagonalisierung zählt man „kreuz und quer“ - aber jede Zahl kommt irgendwann mal dran. -- Peter Steinberg 19:56, 30. Sep 2006 (CEST)

Quantoralsymmetrie

Sagt irgendjemand der Begriff Quantoralsymmetrie etwas (Stand im Absatz rationale Zahlen [1])? Habe den starken Verdacht, dass sich da jemand einen Scherz erlaubt hat. --Pwjg 23:34, 15. Aug. 2010 (CEST)

Haha! Ja, offensichtlich Bollocks. Nice find! :) Interessant, dass das mehr als 3 Jahre lang [2] hier drinstand. --Daniel5Ko 01:12, 16. Aug. 2010 (CEST)

Abzählbarkeit reeller Zahlen

Hallo :)

Vorab - nein, ich bin kein Mathematiker, aber wie ich es verstanden habe, ist eine Zahlenmenge dann abzählbar, wenn man einen Algorithmus finden kann, der nach einer festen Vorschrift in einer potentiell unendlichen Zeit alle Elemente dieser Menge finden kann. Was ich dabei nicht verstehe: warum sollte das für die reellen Zahlen nicht gehen. Bzw erkläre ich kurz einen Algorithmus, der mMn alle reellen Zahlen erschaffen können sollte. Dass dabei Zahlen ggf. mehrfach gefunden werden, hat ja bei Cantors rationalen Zahlen auch nicht gestört.

Algorithmus: Die Idee ist, dass wir einfach die natürlichen Zahlen durchzählen und dabei das Komma verschieben. Bei jedem Überlauf, d.h. bei jeder neuen Ziffer, beginnen wir quasi von vorn zu zählen, aber eben mit der entsprechenden Zahl an Nullen vorn. Positive und negative Zahlen zu einem Betrag werden direkt hintereinander gefunden:

0, -0, 1, -1, 2, -2, 3, -3 ... , 9, -9

hier kommt der erste Überlauf

00, -00, 0.0, -0.0, 01, -01, 0.1, -0.1, 02, -02, 0.2, -0.2, 03 .... 0.9, -0.9, 10, -10, 1.0, -1.0, .... 99, -99, 9.9, -9.9

nächster Überlauf

000, -000, .. 001, -001, 00.1, -00.1, 0.01, -0.01 ... .... 999, -999, 99.9, -99.9, 9.99, -9.99

etc. ...

Es wäre also nett, wenn mir jemand erklären könnte, wo mein Denkfehler liegt, bzw. welche Zahl der Algorithmus niemals erreicht. Danke -- V0oD0o1 17:38, 21. Okt. 2010 (CEST)

Damit erreichst du nur diejenigen Dezimalbrüche, die nach endlich vielen Nachkommastellen abbrechen, also eine Teilmenge der rationalen Zahlen. --Pwjg 18:18, 21. Okt. 2010 (CEST)

warum macht es denn einen Unterschied, ob die unendlich vielen Stellen vor oder nach dem Komma stehen? -- V0oD0o1 18:25, 21. Okt. 2010 (CEST)

Vor dem Komma stehen bei jeder reellen Zahl nur endlich viele Stellen. Aber dein Algorithmus kommt z.B. nie bei 1/3=0,333... an, ganz zu schweigen von irrationalen Zahlen wie pi etc. --Pwjg 19:14, 21. Okt. 2010 (CEST)

naja, aber wenn du sagst, dass ich nicht unendlich viele Nachkommastellen erhalten kann, dann impliziert das ja, dass es eine letzte geben muss - die gibt es aber nicht, sondern ich erreiche in einer unendlichen Zeit durchaus unendlich lange Zahlenfolgen, also durchaus auch 1/3 (nicht signierter Beitrag von V0oD0o1 (Diskussion | Beiträge) 20:16, 21. Okt. 2010 (CEST))

Abzählbarkeit bedeutet aber, dass du jede gegebene Zahl in einer endlichen Zeit erreichst. Und die 1/3 erreichst du gar nicht, da dein Algorithmus schon unendlich lange braucht, bis er alle endlichen Dezimalbrüche abgearbeitet hat. --Pwjg 22:32, 21. Okt. 2010 (CEST)

Ah okay danke, der Gedankenschritt hat mir gefehlt. -- V0oD0o1 08:51, 22. Okt. 2010 (CEST)

Algebraische Zahlen

Deren Polynome müssen nicht ganzzahlige, sondern können auch rationale Koeffizienten besitzen (siehe auch Algebraische Zahl). Das ändert zwar nichts an der Gesamtaussage, aber ich bin mir nicht sicher, ob man den Beweis unverändert stehen lassen kann... --91.56.26.191 01:43, 8. Aug. 2011 (CEST)

Es geht um die Nullstellen der Polynome. Jedes Polynom mit rationalen Koeffizienten kann in eins umgerechnet werden, das nur ganzzahlige Koeffizienten hat, aber die gleichen Nullstellen (einfach alle Koeffizienten mit dem kgV der Nenner der ursprünglichen Koeffizienten multiplizieren). Von so einer Form wird hier ausgegangen. --Daniel5Ko 01:03, 11. Aug. 2011 (CEST)

Daran hatte ich gar nicht gedacht... Danke für die Erklärung --91.56.2.58 02:28, 11. Aug. 2011 (CEST)

Mir leuchtet die Schließung "Da Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb{A}} die rationalen Zahlen enthält, ist Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle \mathbb {A} } abzählbar unendlich." in der gegebenen Formulierung nicht ein. Auch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb{R}} enthält die rationalen Zahlen, ist aber trotzdem nicht abzählbar unendlich. Der vorangehende argumentative Zusammenhang ist, denke ich mal, auch ohne dieses zwischengeschaltete Argument schlüssig. Alternativvorschlag zu dem genannten und dem ihm vorangehenden Satz: "Als abzählbare Vereinigung unendlich vieler endlicher Mengen ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb{A}} daher abzählbar unendlich." Wenn ich etwas übersehe, wäre ich gerne belehrt, was. --Psychironiker 22:39, 19. Aug. 2011 (CEST)

Es wird zuerst gezeigt, dass $\mathbb {A}$ höchstens abzählbar ist. In der Argumentation dafür heißt es, dass es für jede Höhe nur endlich viele Polynome gibt, mit jeweils nur endlich vielen Nullstellen. Nun kann es ja sein, dass es ab einer bestimmten Höhe gar keine Nullstellen mehr gibt, also insgesamt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb A} endlich. Darauf, dass dem nicht so ist, wird erst durch den letzten Satz hingewiesen - und er ist auch gleichzeitig ein Kurzbeweis dafür. --Daniel5Ko 00:31, 20. Aug. 2011 (CEST)

Die Formulierung "Da Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb{A}} andererseits $\mathbb {N}$ enthält, ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb{A}} abzählbar unendlich." genügt der aufgeführten Beweiserfordernis, hätte aber folgende Vorteile:

(1) Die Rolle des Arguments im Zusammenspiel mit den vorhergehenden wird deutlicher (rhetorische Dialektik), eine bei isolierter Lektüre des letzten Satzes irreführende logische Konjektur wird vermieden.

(2) Auch mit geringen mathematischen Vorkenntnissen kann man "darauf kommen", dass mit den Höhen $k>0$ die Nullstelle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x=a_0} des Polynoms Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P(x)= -a_0 + x^1 } , (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_0 = k-1 } ) alle natürlichen Zahlen durchläuft. Einverstanden? --Psychironiker 20:03, 20. Aug. 2011 (CEST)

Ja. --Daniel5Ko 20:43, 20. Aug. 2011 (CEST)

Widerspruch: Endliche Mengen sind nicht abzählbar!

Widerspruch:

(1) Endliche Mengen sind nicht abzählbar unendlich, kurz nicht abzählbar. [ Quelle: http://de.wikipedia.org/wiki/Abzählbarkeit#Ganze_Zahlen "Die Beispiele Primzahlen und ganze Zahlen zeigen, dass sowohl echte Teilmengen als auch Obermengen dieselbe Mächtigkeit besitzen können wie die Grundmenge, im Gegensatz zu endlichen Mengen." ]

(2) "Jede aufzählbare Menge ist auch abzählbar." [ Quelle: http://de.wikipedia.org/wiki/Abzählbarkeit#Eigenschaften ]

(3) "Jede endliche Menge ist rekursiv aufzählbar." [ Quelle: http://de.wikipedia.org/wiki/Rekursive_Aufzählbarkeit#Eigenschaften ]

=> Aus (3) und (2) folgt: Jede endliche Menge ist abzählbar.

Dies ist ein Widerspruch zu (1).

Vermutung: "Jede aufzählbare Menge ist auch abzählbar" ist falsch.

-- DRRDietrich 00:01, 11. Aug. 2011 (CEST)

Ich zitiere aus dem Artikel (genauer: der Einleitung):

Die Verwendung des Begriffes abzählbar ist nicht einheitlich. Er kann je nach Definition sowohl abzählbar unendlich als auch höchstens abzählbar bedeuten.

Vor diesem Satz wird sowohl "abzählbar unendlich" als auch "höchstens abzählbar" definiert. Die beiden sind auf jeden Fall eindeutig.

Der von dir zitierte Ganze-Zahlen-Abschnitt im Artikel sagt explizit "abzählbar unendlich". Dein "kurz nicht abzählbar" stammt von dir.

Wenn Informatiker von "abzählbar" sprechen, meinen sie nomalerweise "höchstens abzählbar". Das ist auch ganz sinnvoll, denn es geht darum, festzustellen, ob etwas, was trivialerweise für endliche Mengen möglich ist, bei bestimmten unendlichen Mengen auch geht.

Einen Widerspruch gibt es also nicht, und deine zuletzt genannte Vermutung ist falsch. Jede aufzählbare Menge ist [höchstens] abzählbar.

Gruß, --Daniel5Ko 00:46, 11. Aug. 2011 (CEST)

"Abzählbar" heißt so viel wie "höchstens abzählbar", wie aus der deutschen Sprache klar hervorgeht.--217.251.75.57 13:30, 10. Feb. 2013 (CET)

Quelle für Uneindeutigkeit von "abzählbar"

Gibt es eine Quelle für die Aussage, dass manche Autoren endliche Mengen nicht als abzählbar ansehen? Anderenfalls würde ich diese streichen. --Jobu0101 (Diskussion) 20:37, 30. Nov. 2021 (CET)