Die Mathe-Redaktion [Home] - Neues auf einen Blick 30.11.2023 21:04 [Neues] [Forum] [Suche] - Registrieren/Login
 
Matroids Matheplanet Forum Index
Moderiert von mire2 StrgAltEntf
Mathematik » Logik, Mengen & Beweistechnik » Behauptung zu rekursiv aufzählbar
Autor
Universität/Hochschule J Behauptung zu rekursiv aufzählbar
carlox
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 22.02.2007
Mitteilungen: 1623
  Themenstart: 2023-09-25

Hallo allerseits, Ist meine folgende Behauptung richtig? Behauptung: Sei die Menge X rekursiv aufzählbar. Dann gilt: Z=Menge aller endlichen Teilmengen von X ist rekursiv aufzählbar. mfg cx

   Profil
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 2961
  Beitrag No.1, eingetragen 2023-09-25

\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]} \newcommand{\name}[1]{\ulcorner#1\urcorner} \newcommand{\upamp}{\mathbin {⅋}} \newcommand{\monus}{\mathbin {∸}}\) Ja, das ist richtig. Wenn $X$ aufzählbar ist, dann auch $X^*$, die Menge aller endlichen Worte über dem Alphabet $X$. Und die Surjektion $X^* \to \mathcal P_\text{fin}X$ wird etwa von Data.Set.fromList in der Standardbibliothek von Haskell umgesetzt.\(\endgroup\)

   Profil
Zwerg_Allwissend
Senior Letzter Besuch: im letzten Monat
Dabei seit: 02.12.2013
Mitteilungen: 354
  Beitrag No.2, eingetragen 2023-09-27

Etwas konkreter: Es gilt X rekursiv aufzählbar gdw. X semi-entscheidbar. Wenn X semi-entscheidbar ist, so gibt es ein Programm E_X mit Eingabe n ∈ ℕ so daß (*) n ∈ X ⇔ E_X(n) hält mit Ergebnis 1 Definiere Programm E_X* mit Eingabe N ⊂ ℕ und N endlich durch while N ≠ ∅ do n := some(N) if E_X(n) = 1 then N := N \ {n} end_if end_while return(1) Es gilt: (**) N ⊂ X und N endlich ⇔ E_X*(n) hält mit Ergebnis 1 und folglich ist die Menge aller endlichen Teilmengen von X semi-entscheidbar.

   Profil
carlox hat die Antworten auf ihre/seine Frage gesehen.
Das Thema wurde von einem Senior oder Moderator abgehakt.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]