sous-ensembles d'ensembles récursifs infinis

11

Une question d'examen récente était la suivante:

  1. est un ensemble infiniment énumérable récursivement. Prouver que A a un sous-ensemble récursif infini.AA
  2. Que soit un sous - ensemble récursif infini de A . C doit-il avoir un sous-ensemble qui n'est pas récursivement énumérable?CAC

J'ai déjà répondu 1.. Concernant 2., j'ai répondu par l'affirmative et j'ai argumenté comme suit.

Supposons que tous les sous-ensembles de soient récursivement énumérables. Puisque C est infini, l'ensemble de puissance de C est indénombrable, donc par hypothèse il y aurait un nombre incalculable d'ensembles récursivement énumérables. Mais les ensembles énumérables récursivement sont en correspondance biunivoque avec les machines de Turing qui les reconnaissent, et les machines de Turing sont énumérables. Contradiction. Donc C doit avoir un sous - ensemble qui ne sont pas récursivement énumérable.CCCC

Est-ce correct?

computability check-my-proof user1435
la source
2
Ce n'est pas tout à fait correct à la fin, car chaque réinitialisation est énumérée par une infinité de machines Turing, pas seulement par une. Vous pouvez cependant contourner ce problème.
Carl Mummert
@Carl: Ah, d'accord, merci - erreur stupide. Mais tout ce dont j'ai besoin, c'est d'une injection dans les MT, pas d'une bijection, non? Et sur la définition de Turing-computable avec laquelle ma classe a travaillé, chaque MT est associée à une et une seule fonction. Donc, différents ensembles -> différentes fonctions de reconnaissance -> différentes MT qui les calculent.
user1435
1
! user1435: vous inversez les choses dans la dernière phrase. Chaque machine Turing calcule une seule fonction, mais chaque fonction calculable est obtenue à partir d'une infinité de machines Turing.
Carl Mummert
Mais si ma fonction f mappe {les fonctions de reconnaissance r} à {TMs} via f (r) = l'un des infiniment de MTs qui la calculent, j'ai une injection, non? Ou je suppose que je pourrais simplement partitionner {TMs} par une relation d'équivalence ~ qui identifie l'infinité de TMs qui calculent la même fonction, puis mapper r à la classe d'équivalence appropriée.
user1435
Carl a raison, ils ne sont pas en correspondance un à un, chaque ensemble de ce correspond à une infinité de MT. Le fait de considérer d'autres ensembles d'objets comme vous le faites dans votre commentaire ne change rien, ce n'est pas l'ensemble des MT.
Kaveh

Réponses:

11

C'est correct.

ℵ0≤C⟹ℵ0<2C

C

D={i∈C∣i∉Wi}WiiD⊆CDCK={i∣i∉Wi}CD

Kaveh
la source
"Chaque ensemble infini a un sous-ensemble indécidable." C'est plus faible que l'affirmation que j'ai essayé de prouver. J'ai essayé de prouver que C doit avoir un sous-ensemble non RE, pas un sous-ensemble non décidable. Ma réclamation est-elle toujours correcte?
user1435
Oui. Le terme "indécidable" est un peu surchargé (Wikipedia a une bonne discussion ). Donc, cette réponse signifie probablement ce que vous essayez de prouver.
David Lewis
@ user1435, oui, le même argument fonctionne pour toutes les classes de langues dénombrables, j'ai mis à jour la question pour qu'elle soit claire.
Kaveh