Abzählbarkeit, Diagonalverfahren

Neue Frage »

math.random Auf diesen Beitrag antworten »
Abzählbarkeit, Diagonalverfahren
Hi,

ich habe 2 Aufgaben, bei denen ich mir nicht sicher bin ob die Lösung so hinhaut, ich wäre euch dankbar wenn ihr mal schauen könntet ob es stimmt.

a) Sind die Mengen abzählbar, so auch .

--> Hier dachte ich an das Cantorsche Diagonalverfahren, also alle Elemente a11, a12, a13,....a1n in die erste Zeile schreiben, dann in die darauffolgenden Zeilen die Elemente der anderen Mengen bis an1, an2, ... ann. Und dann mithilfe des Verfahrens zeigen das die Vereinigung dieser Mengen abzählbar ist.


b) Es sei A = {a, b}. Zeigen Sie das die Menge A* aller Zeichenketten, die aus Buchstaben aus A abgebildet werden können,abzählbar ist. Verallgemeinern Sie diese Aussage dahingehend, dass die Menge aller Programme einer Programmiersprache abzählbar ist.

--> Hier dachte ich auch wieder an das oben genannte Cantorsche Verfahren, in der Form
1.Zeile: a b
2. Zeile: aa ab ba bb
...
n.Zeile: a...., b...., .....

Sicher bin ich mir hier aber nicht. Bei der Teilaufgabe mit den Programmen fällt mir leider nix ein.

Schöne Grüße
JochenX Auf diesen Beitrag antworten »

zur ersten: wozu diagonalisieren?
nimm von jeder menge das erste nacheinander, dann von jeder das zweite nacheinander, dann von jeder das dritte.....

duplikate werden dabei einfach gekillt


bei der anderen aufgabe wäre es interessant, wie es weitergeht mit deiner kette

tipp zu den progsprachen: a=0, b=1
math.random Auf diesen Beitrag antworten »

Also, ich habs auch gemerkt, habs dann halt einfach nach dem Cantorschen Abzählschema gemacht, aber ob das einfach als Beweis gilt ?

zu b) naja ich weiß auch nicht recht wie ich das hinschreiben soll das die kette unendlich weitergeht, ich denke mir nur es gibt unendlich viele unendlich lange Zeichenketten like aaaaaaaaa..... aaaabababa..... was weiß ich nich noch. Es gibt aber trotzdem eine Bijektion von den nat.Zahlen auf die einzelnen Elemente der Menge A*, also das A* halt gleichmächtig mit der menge der nat.Zahlen ist. Nur keine Ahnung wie ich das halt aufschreiben soll ^^

bei den Programmen, ja, durch deinen Tipp denke ich mir es gibt eine Menge, z.B. A die aus den Elementen {0, 1} besteht, also den Binärzahlen und die Programme sind dann halt wie im ersten teil von b) nur unendlich lange Zeichenketten dieser Zahlen.

Mal noch ne kleine Aufgabe nebenbei die nicht allzu schwer sein sollte:

wenn f und g 2 Abb sind z.B. f: A--> B und g: A--> B
ist dann der Schnitt bzw. die Vereinigung und die Differenz wieder eine Funktion ?
Ich würde sagen Schnitt und Vereinigung ja, da f und g ja beides Mengen sind die Teilmenge von B sind und wenn man diese beiden Mengen, z.B. X1 und X2, schneidet dann entsteht wieder eine Menge mit Elementen aus B. Das ist dann wieder eine Funktion. Bei der Vereinigung sollte es somit erst recht klar sein. Und wenn man z.B. f ohne g betrachtet, dann würde es ja bedeuten das es eine Menge sein würde die aus Elementen aus B besteht aber ohne Elementen aus B was ja nicht sein kann. Was meint ihr dazu oder ist das nur non-sense was ich geschrieben hab ? Teufel

Schöne Grüße
Mathespezialschüler Auf diesen Beitrag antworten »

Die erste Aufgabe kannst du gar nicht mit dem Cantorschen Diagonalverfahren machen. Du hast doch ein Schema, was nicht beliebig weit nach unten geht. Es sieht so aus:

.

Du gehst also erst die erste Spalte runter, dann die zweite usw., wie Jochen sagte:



Die "überflüssigen" kannst du dann einfach immer auslassen.

Gruß MSS
math.random Auf diesen Beitrag antworten »

Ok, verstanden, habs jetzt so fertig. Die 2. mit den Buchstaben habe ich so ähnlich gemacht, auch mit nem Abzählschema: a->b->aa->ab->ba->... wo dann jedem Element aus IN eins aus A* zugeordnet wird und somit A* abzählbar ist.
chipbit Auf diesen Beitrag antworten »
Frage zu a)
Kann mir bitte nochmal jemand nen bisserl genauer sagen wie das bei a) jetzt gemacht wurde? Verstehe ich nicht wirklich....
 
 
papahuhn Auf diesen Beitrag antworten »
RE: Frage zu a)
Einfach abwechselnd aus jeder Menge ein Element rauspicken und dabei bereits aufgelistete Elemente nicht wiederholt auflisten.
chipbit Auf diesen Beitrag antworten »

aha, okay....und was ist daran dann jetzt genau der Beweis für" Sind die Mengen abzählbar, so auch " ? Muss man da nochwas zuschreiben oder wie? Hab grad irgendwie nen Brett vorm Kopf....
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »