Diagonalbeweis

Übersicht

Sonstiges

Smalltalk

	faeX Betreff: Diagonalbeweis	Fr, Okt 26, 2012 16:35 Antworten mit Zitat
Hey Leute, ich sitze gerade an einer Hausaufgabe und komme nicht weiter. Zeigen Sie mittels eines Diagonalbeweises, dass die Menge N hoch N (jeweils das N das die Menge der natürlichen Zahlen representiert, ich kann das hier auf dem Handy nicht einfügen) aller Funktionen von N nach N (wieder natürliche Zahlen) überabzählbar ist. Der Diagonalbeweis ist mir völlig klar. Ich weiß nur nicht wie ich das in Bezug auf die Funktionen machen soll. Ich dachte mir erst eine Teilmenge der Funktionen zu nehmen und die Überabzählbarkeit dafür zu beweisen, z.B. f(x) = x+ n, nur leider ist diese Funktionsschar ganz klar abzählbar. Irgendwelche Ideen? Mfg faeX

faeX

Betreff: Diagonalbeweis

Fr, Okt 26, 2012 16:35
Antworten mit Zitat

Hey Leute, ich sitze gerade an einer Hausaufgabe und komme nicht weiter.

Zeigen Sie mittels eines Diagonalbeweises, dass die Menge N hoch N (jeweils das N das die Menge der natürlichen Zahlen representiert, ich kann das hier auf dem Handy nicht einfügen) aller Funktionen von N nach N (wieder natürliche Zahlen) überabzählbar ist. Der Diagonalbeweis ist mir völlig klar. Ich weiß nur nicht wie ich das in Bezug auf die Funktionen machen soll. Ich dachte mir erst eine Teilmenge der Funktionen zu nehmen und die Überabzählbarkeit dafür zu beweisen, z.B. f(x) = x+ n, nur leider ist diese Funktionsschar ganz klar abzählbar.

Irgendwelche Ideen?
Mfg
faeX

	TimBo	Sa, Okt 27, 2012 1:02 Antworten mit Zitat
Hi, kann sein , dass ich total falsch liege aber ich würde das so machen : {1^1} {1^2} {1^3} .... {2^1} {2^2} {2^3} .... {3^1} {3^2} {3^3} .... .... .... .... und dann kannst du die Werte durchnummerieren, dadurch wären sie abzählbar. Ich meine, wenn N / N schon abzählbar ist (rationale Zahlen) dann sollte doch N^N auch abzählbar sein ?! Hier steht noch was von einem 2-Tupel an natürlichen Zahlen ist auch abzählbar: http://de.wikipedia.org/wiki/Abz%C3%A4hlbarkeit
mfg Tim Borowski // CPU: Ryzen 2700x GPU: Nvidia RTX 2070 OC (Gigabyte) Ram: 16GB DDR4 @ 3000MHz OS: Windows 10 Stolzer Gewinner des BCC 25 & BCC 31 hat einen ersten Preis in der 1. Runde beim BWInf 2010/2011 & 2011/12 mit BlitzBasic erreicht.

TimBo

Sa, Okt 27, 2012 1:02
Antworten mit Zitat

Hi,

kann sein , dass ich total falsch liege aber ich würde das so machen :

{1^1} {1^2} {1^3} ....
{2^1} {2^2} {2^3} ....
{3^1} {3^2} {3^3} ....
....
....
....

und dann kannst du die Werte durchnummerieren, dadurch wären sie abzählbar.

Ich meine, wenn N / N schon abzählbar ist (rationale Zahlen) dann sollte doch N^N auch abzählbar sein ?!

Hier steht noch was von einem 2-Tupel an natürlichen Zahlen ist auch abzählbar: http://de.wikipedia.org/wiki/Abz%C3%A4hlbarkeit

mfg Tim Borowski // CPU: Ryzen 2700x GPU: Nvidia RTX 2070 OC (Gigabyte) Ram: 16GB DDR4 @ 3000MHz OS: Windows 10
Stolzer Gewinner des BCC 25 & BCC 31
hat einen ersten Preis in der 1. Runde beim BWInf 2010/2011 & 2011/12 mit BlitzBasic erreicht.

	BBPro2	Mi, Nov 07, 2012 4:15 Antworten mit Zitat
ich weiß der thread ist bissl alt, aber: die aufgabe hier hat nichts mit tupeln zu tun und auch nicht mit deiner illustration, timbo es geht um die menge aller funktionen von N nach N, also alle funktionen, die der vorschrift f*: \|N -> \|N genügen und diese menge ist überabzählbar beweise gibt es dafür jede menge, diagonalbeweis sagt mir jetzt spontan aber leider nichts. abgesehen davon war das thema vermutlich ohnehin schon überfällig ^^ wenn der autor nichts besseres zu tun hat würde ich mich über eine kurze beweisskizze freuen (mittlerweile kennst du die lösung ja vermutlich?)

BBPro2

Mi, Nov 07, 2012 4:15
Antworten mit Zitat

ich weiß der thread ist bissl alt, aber:

die aufgabe hier hat nichts mit tupeln zu tun und auch nicht mit deiner
illustration, timbo

es geht um die menge aller funktionen von N nach N, also alle funktionen, die
der vorschrift

f*: |N -> |N genügen

und diese menge ist überabzählbar

beweise gibt es dafür jede menge, diagonalbeweis sagt mir jetzt spontan aber leider nichts.
abgesehen davon war das thema vermutlich ohnehin schon überfällig ^^

wenn der autor nichts besseres zu tun hat würde ich mich über eine kurze beweisskizze freuen Smile

(mittlerweile kennst du die lösung ja vermutlich?)