Aufzählbark., Entscheidbarkeit < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:42 Sa 16.05.2009 | | Autor: | chris87 |
| Aufgabe | a)
Seinen A, B [mm] \subseteq \IN. [/mm]
Zu zeigen ist: Wenn A [mm] \le [/mm] B und B aufzählbar ist, dass ist auch A aufzählbar
b)
Sei A [mm] \subset \IN [/mm] eine aufzählbare Menge mit A [mm] \not= \emptyset. [/mm]
Zeigen Sie formal: A ist genau dasnn entscheidbar, wenn A [mm] \le \overline{A} [/mm] |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hey Leute,
ich habe mal wieder ein Problem....bei oben stehender Aufgabe geht es ja um die reduzierbarkeit, genauer gesagt um die Aufzählbarkeit von Mengen. Ich habe gelernt, dass wenn es eine surjektive, berechenbare Funktion gibt. Oder wenn es eine Funktion gibt, die alle Elemente einer menge M berechnen kann.
Das ist soweit kla....mir ist boß nich klar wie ich die oben stehende aufgaben beweisen bzw wiederlegen kann.
|
|
| |
|
Hallöchen !
"Eine Menge von Zahlen $M = [mm] a_1,a_2,a_3,...$ [/mm] ist dann aufzählbar, wenn es eine Funktion $f(x)$ gibt, die alle Elemente von M berechnen kann [mm] (f(i)=a_i)"
[/mm]
(Zitat)
a)
Sei also $B$ aufzählbar und [mm] $A\le [/mm] B$. Dann gibt es also eine Funktion $f$, die alle Elemente von $B$ berechnen kann.
Da ja [mm] $A\le [/mm] B$ gilt, muss also...........
b)
Wann ist denn eine Menge entscheidbar?
Gruß
Gib maln bissl eigenmoti
|
|
|
|
