Beweis Überabzählbarkeit

17.10.2014, 08:57

Tuling

Beweis Überabzählbarkeit

Meiner Meinung nach wird aus dem Widerspruch von Beweis 1.3 des Link:

ww w.theory.informatik.uni-kassel.de/veranstaltungen/theoInf-B+FormSpSS2012/vorlesung/Abschnitt1.1.pdf

der falsche Schluss (Überabzählbarkeit) gezogen. Was haltet ihr von diesem Ansatz:

Eine Menge sei indiziert genannt, wenn jedes ihrer Elemente elementindizierbar über den natürlichen Zahlen N ist (d.h. ein Laufindex zur Unterscheidung der Elemente ist zuordnungsbar). Eine abzählbare Menge ist indiziert.
----------------------

Gegeben ist jetzt die Menge F aller Funktionen mit der Eigenschaft:

F sei die Vereinigung von F' mit {f}, und F' die Menge aller Funktionen $\begin{eqnarray*} f_{n} \end{eqnarray*}$ :
N -> N : Anordnung nach Link, realisierbar z. Bsp. mit $\begin{eqnarray*} f_{n}(n) = n \end{eqnarray*}$ .

1. Ein f: $\begin{eqnarray*} f(i) = f_{i}(i) + 1 \end{eqnarray*}$ existiert ganz bestimmt.

2. Behauptung: F ist nicht indiziert. Jedoch sind beide Mengen F' u. {f} abzählbar. Widerspruch.

3. Behauptung: F ist indiziert. Also muß auch f eine natürliche Zahl als Index haben. Folgt F=F', folgt der Widerspruch nach Link.

17.10.2014, 09:23

bijektion

Auf diesen Beitrag antworten »

Zitat:

der falsche Schluss (Überabzählbarkeit) gezogen

Was soll denn heißen der falsche Schluss gezogen? Das die Menge überabzählbar ist, wird doch gezeigt.

Dein Schluss ist falsch, der Widerspruch wird so erzeugt: Wenn $\begin{eqnarray*} F=\left\{ f:\mathbb{N}\to\mathbb{N}\right\} \end{eqnarray*}$ die Menge aller Funktionen $\begin{eqnarray*} \mathbb{N}\to\mathbb{N} \end{eqnarray*}$ ist, dann gibt es eine surjektive Abbildung $\begin{eqnarray*} \mathcal{F}: \mathbb{N}\to F \end{eqnarray*}$ .
Jetzt bauen wir eine Abbildung von $\begin{eqnarray*} \mathbb{N}\to\mathbb{N} \end{eqnarray*}$ , die nicht in $\begin{eqnarray*} F \end{eqnarray*}$ liegt, nämlich $\begin{eqnarray*} g(n):=f_n(n)+1 \end{eqnarray*}$ mit $\begin{eqnarray*} f_n=\mathcal{F}(n) \end{eqnarray*}$ .

Wegen der Surjektivität gibt es $\begin{eqnarray*} j\in\mathbb{N} \end{eqnarray*}$ , mit $\begin{eqnarray*} F(j)=f_j=g \end{eqnarray*}$ , also wäre $\begin{eqnarray*} g(j)=f_j(j) \end{eqnarray*}$ , das kann aber nicht sein, denn nach Definition ist $\begin{eqnarray*} g(j)=f_j(j)+1 \end{eqnarray*}$ .

17.10.2014, 10:12

Tuling

Auf diesen Beitrag antworten »

Ich sage nicht, daß die Menge aller Fkt.: N -> N nicht überabzählbar ist.
Ich behaupte nur das der Beweis aus Link die Überabzählbarkeit nicht beweist.
Ist die konstruierte Menge F abzählbar?

17.10.2014, 10:35

tmo

Auf diesen Beitrag antworten »

Zitat:

Original von Tuling
Ich behaupte nur das der Beweis aus Link die Überabzählbarkeit nicht beweist.

Diese Behauptung ist jedoch nicht haltbar. Der Beweis aus dem PDF ist einwandfrei.

17.10.2014, 12:15

Tuling

Auf diesen Beitrag antworten »

Kannst Du mir noch meine Frage beantworten, tmo?

17.10.2014, 13:27

tmo

Auf diesen Beitrag antworten »

Naja deine Ausführungen sind ziemlich wirr und vor allem recht sinnlos.

F ist ja gerade nicht abzählbar.

20.10.2014, 09:23

Tuling

Auf diesen Beitrag antworten »

@ tmo,

Meine Ausführung ist kurz und präzise und ansonsten habe ich die Gedanken von Link identisch übernommen (natürlich nicht dessen Eingangsbehauptung).

Betrachte zB. die Menge der Natürlichen Zahlen und nehme dann eine Murmel, aber nicht die oberhalb Deiner Schultern, und füge diese der Menge hinzu. Ist die resultierende Menge Deiner Meinung nach dann überabzählbar?

20.10.2014, 09:43

tmo

Auf diesen Beitrag antworten »

Zitat:

Original von Tuling
ansonsten habe ich die Gedanken von Link identisch übernommen

Der Unterschied ist, dass der Autor des Beweises aus dem Link es geschafft hat, seinen Gedanken klar zu formulieren.

Mir ist nicht klar, was du da machen willst. Ich interpretiere das so, dass du damit einen deiner Meinung nach hiebfesteren Beweis formulieren willst. Aber letztendlich machst du doch genau dasselbe wie in dem Link. Die Idee: Du nimmst an, dass F' abzählbar ist, konstruierst ein f, das nicht in F' liegt und erhältst einen Widerspruch.

Du erhältst diesen Widerspruch jetzt allerdings über den Umweg des völlig unnötigen Begriffs "indizierbar" und führst auch noch eine weitere Menge F (natürlich ist die abzählbar, wenn wir angenommen haben, dass F' abzählbar ist. Aber das ist nunmal nicht das Hauptargument!) ein. Und dann fragt man sich halt: Wozu das ganze? Will da etwa jemand das (evtl. nicht vorhandene) Hauptargument hinter Formalismen und Begriffen verstecken? Sowas gibt es öfter als man denkt!

Und zu den Murmeln antworte ich jetzt mal nicht. Ich bin raus aus der Diskussion.

20.10.2014, 09:53

Tuling

Auf diesen Beitrag antworten »

Nach Link liegt ganz klar eine Funktionenfolge vor, deren Folgeglieder (alle) eine abzählbare Menge bilden (genauer, zunächst die Bezeichnungen der Fkt.).

Schau, es ist wie bei "Per Anhalter durch die Galaxis" und 42 ist die Anordnung nach Link.
Die Behauptung zum Widerspruchsverfahren nach Link können wir uns hinterher ausdenken.

So gesehen ist es interesssant zu fragen was der Link-Beweis, wenn überhaupt, aussagt.

(komm', die Murmel war Spaß)

20.10.2014, 13:12

RavenOnJ

Auf diesen Beitrag antworten »

Zitat:

Original von Tuling
Nach Link liegt ganz klar eine Funktionenfolge vor, deren Folgeglieder (alle) eine abzählbare Menge bilden (genauer, zunächst die Bezeichnungen der Fkt.).

Dies ist nur aufgrund einer Annahme, nämlich der, dass die Menge der Funktionen abzählbar ist. Dann könnte man nämlich diese Menge auch hintereinander auflisten. Es wird dann ähnlich dem Cantorschen Diagonalargument gezeigt, dass eine bestimmte wohldefinierte Funktion nicht in der Liste auftauchen kann. Also muss die Annahme der Abzählbarkeit falsche sein.

20.10.2014, 15:40

Tuling

Auf diesen Beitrag antworten »

Raven,

es ist zunächst egal, ob die Folge aus einer Annahme resultiert. Tatsache ist, es wird irgendeine abzählbare Menge (aus Folge) als gegeben vorausgesetzt. Ich zB. interpretiere F' als eine Aussonderung aus einer anderen abzählbaren Menge. Aber egal! Was würde denn der Beweis n. Link Deiner Meinung nach aussagen, wenn wir einfach mal für F' eine abzählbare Menge annähmen?

20.10.2014, 20:45

RavenOnJ

Auf diesen Beitrag antworten »

Es ist keineswegs egal, ob die Folge "aus einer Annahme resultiert". Die Beweismethode nennt sich "Beweis durch Widerspruch". Die Methode funktioniert so:
1.) Grundannahme: Annahme der Alternative, die gegenteilig ist zu dem, was man beweisen will (hier: Annahme der Abzählbarkeit der Funktionenmenge, denn man will beweisen, dass die Menge überabzählbar ist)
2.) daraus logische Deduktion, die zu einer falschen Aussage führt (hier: es müsste eine Funktion geben, die es nicht geben kann $\begin{align*} \exists j: f_j(j) = f_j(j)+1 \end{align*}$ )
3.) Schlussfolgerung: Widerspruch zur Annahme; wegen tertium non datur muss also die Grundannahme falsch sein, die Alternative (hier: Menge überabzählbar) also richtig.

Bevor du hier Leute anmachst, beschäftige dich erst mal mit grundlegenden Beweisprinzipien.

21.10.2014, 09:58

Tuling

Auf diesen Beitrag antworten »

Wäre mein Beweis richtig, wendest Du tertiumnondatur auf die falsche Grundannahme an.

Grundannahme G könnte auch sein: F' sei eine abzählbare Menge von Fkt. und Beh.: f sei eines der Elemente. Punkt (1.) oben zeigt aber schon, daß dies nicht der Fall sein kann, was eines Beweises W1 nicht würdig ist, denn (1.) definiert f eben als Fkt., die sich mind. an einer Stelle von jeder anderen Fkt. aus F' unterscheidet. Was tmo schon bemerkte.

Dann ist es zumindest nicht zielführend, wenn Link zugleich einen zweiten Beweis W2 für "f nicht in F' " bringt, die spezielle Indizierung.

F1) Raven, kann man aus W1 und G schließen, daß F' überabzählbar ist?

W2 trägt demnach eine weitere Annahme, die Überabz. . Es ist jedoch schwer bedenklich, wenn eine über eine alle Elemente übergeordnete Eigenschaft (die Überabz.) befunden wird, bevor überhaupt das vollständige Vorliegen aller Elemente feststeht. Denn F ist auch abzählbar.

Und weil all dies nur in intuitives, philosphisches Gerede abgleitet habe ich das Vorgehen/ Konstrukt/ usw. von Link deklariert u. gesagt: Link hat Recht, womit man ein neues Symbol einführen kann und mit Symbolen kann man rechnen.
Und diese Begriffsdefinition wäre überflüssig, wie tmo bemerkt, wenn sich der Begriff im allgemeinen math. Kontext als äquivalent zu einem anderen oder als wirklich überflüssig erweisen würde. Tut es aber nicht! Der schwere "Widerspruch" kann nun aber zwei weitere Gründe haben:
a) Mein gewählter neuer Begriff ist in sich falsch (unwahrscheinlich, weil ich dessen Offenheit identisch von Link übernommen habe),
b) Meine Beweisführung auf elemenar math. Ebene ist falsch (unw., weil Beweis kurz).
(a) und/ oder (b) =: V

V habt ihr zu zeigen. Sonst macht eine Weiterführung des Threads keinen Sinn mehr. Meine Eingangsansicht habe ich dargelegt. F1 bitte beantworten.
(Zur impliziten Frage von tmo: Meiner Erkenntnis nach ist: wenn V nicht gilt, dann ist die Vereinigung aus einer abzählbaren mit einer einelementigen Menge überabzählbar).

21.10.2014, 10:37

Math1986

Auf diesen Beitrag antworten »

Tuling, wie hier schon von drei Leuten festgestellt wurde ist der Beweis aus der PDF-Datei absolut korrekt. Es wird angenommen dass die Menge F abzählbar ist, und diese falsche Annahme wird durch einen Widerspruch widerlegt. Also ist F nicht abzählbar, und so nach Definition überabzählbar.

Deinen Ausführungen kann ich, so wie teilweise auch meine Vorgänger, nicht so recht folgen. Bei dem Beispiel mit dem Murmeln frage ich mich aber auch wirklich, ob deine Beiträge hier ernst gemeinst sind. Wenn du wirklich davon überzeugt bist dass dieser Beweis falsch ist, dann solltest du das mal mit dem Dozenten besprechen, du scheinst da irgendwo ein Verständnisproblem zu haben.

Neue Frage »

Antworten »

Beweis Überabzählbarkeit

Verwandte Themen