Informatiker Board | Theoretische Informatik | Aufgabe: Überabzählbarkeit (Menge/Obermenge)

Informatiker Board » Themengebiete » Theoretische Informatik » Aufgabe: Überabzählbarkeit (Menge/Obermenge)

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Aufgabe: Überabzählbarkeit (Menge/Obermenge)

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

cyberjohn
Grünschnabel

Dabei seit: 25.11.2012
Beiträge: 9

Aufgabe: Überabzählbarkeit (Menge/Obermenge)

Zitatantwort auf diesen Beitrag erstellen

Meine Frage:
Hallo,

ich habe eine Aufgabe erhalten und muss beweisen, dass "Jede Obermenge einer überabzählbaren Menge überabzählbar ist."

Meine Ideen:
Beispiel: Die Menge der rationalen Zahlen Q ist abzählbar.

Mit freundlichen Grüßen,

cyberjohn

Dieser Beitrag wurde 3 mal editiert, zum letzten Mal von cyberjohn: 25.11.2012 14:18.

25.11.2012 13:50

Nehmen Sie cyberjohn in Ihre Freundesliste auf

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Hallo,

das sieht nach einem Widerspruchsbeweis aus. Angenommen, die Obermenge wäre Abzählbar, welche Konsequenz ergäbe sich daraus?

VG,

Karlito

25.11.2012 22:54

Nehmen Sie Karlito in Ihre Freundesliste auf

cyberjohn
Grünschnabel

Dabei seit: 25.11.2012
Beiträge: 9

Hallo Karlito,

Beim indirekten Beweis (Widerspruchsbeweis) wird eine Aussage (A -> B) dadurch bewie-
sen, dass man zeigt: "Aus B folgt A , also ein Widerspruch zu A".

Beispiel: Beweisen Sie das Schubfachprinzip für neN:
Hat man n+1 Objekte in n Schubfächer verteilt, so gibt es mindestens ein Schubfach,
in dem zwei (oder mehr) Objekte liegen.

Lösung: Der Satz hat die Form "A -> B" mit:
A: n+1 Objekte sind in n Schubfächer verteilt.
B: Es gibt mindestens ein Schubfach mit 2 (oder mehr) Objekten.
Angenommen, es gälte B : Jedes Schubfach enthält höchstens 1 Objekt. Dann wären in al-
len Schubladen zusammen n mal höchstens 1 Objekt, also höchstens n Objekte. Dies ist ein
Widerspruch zu A, dass n+1 Objekte in den Schubfächern liegen. Also gilt nicht B -> nicht A ,ist (A -> B) richtig. .

Wenn die Obermenge abzählbar wäre, dann wären die Mengen ebenso abzählbar.

Ist das richtig?

Mit freundlichen Grüßen,

cyberjohn

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von cyberjohn: 27.11.2012 14:54.

27.11.2012 14:53

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Zitat:

Original von cyberjohn
Wenn die Obermenge abzählbar wäre, dann wären die Mengen ebenso abzählbar.

Ja.

27.11.2012 16:31

cyberjohn
Grünschnabel

Dabei seit: 25.11.2012
Beiträge: 9

Dennoch würde der Widerspruchsbeweis für diese Aufgabe nicht ausreichen... D,h. die Aufgabe ist nicht ganz erfüllt. Wie kann man nun beweisen, dass jede Obermenge einer überabzählbaren Menge überabzählbar ist?

Mein Vorschlag:
Die Menge aller Abbildungen f: X*->X* ist überabzählbar und kann nicht durch einen Algorithmus berechnet werden.

Mit freundlichen Grüßen,

cyberjohn

27.11.2012 18:21

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Hallo,

du hattest doch schon alles.
Sei eine Menge [latex]M[/latex]

überabzählbar und eine Menge [latex]N[/latex]

eine Obermenge von [latex]M[/latex]

. Dann folgt, dass $[latex]M \subseteq N[/latex]$ .

Sei [latex]N[/latex]

abzählbar, dann folgt aus den Eigenschaften von abzählbaren Mengen, dass jede Teilmenge von [latex]N[/latex]

abzählbar ist.
Wenn $[latex]M \subseteq N[/latex]$ , dann ergibt sich ein Widerspruch.

Was fehlt dir da noch?

VG,

Karlito

27.11.2012 19:09

cyberjohn
Grünschnabel

Dabei seit: 25.11.2012
Beiträge: 9

Stimmt Du hast Recht! Ich habe zu kompliziert nachgedacht, die Lösung ist ja viel einfacher...

Jedenfalls möchte ich mich für Deine Unterstützung bedanken! Dadurch konnte ich mein Verständnis verbessern. Daumen hoch

Mit freundlichen Grüßen,

cyberjohn

27.11.2012 19:37

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Aufgabe: Überabzählbarkeit (Menge/Obermenge)