Existe-t-il un lien caché entre l'existence d'ensembles innombrables et l'indécidabilité du problème d'arrêt?

9

Étant donné que les deux preuves utilisent l'argument diagonal, je me demande s'il existe un lien obscur entre l'existence d'ensembles infinis innombrables et l'indécidabilité du problème d'arrêt. Le problème d'arrêt serait-il décidable si tous les ensembles étaient dénombrables?

Lenar Hoyt
la source
10
Oui, l'argument diagonal!
Mahdi Cheraghchi
1
@MCH Ma pensée était qu'il existe peut-être une caractérisation différente en plus de l'argument diagonal qui relie les deux. Cette question est peut-être trop floue pour SE.
Lenar Hoyt
4
Cela peut être un lien partiel: clairement, l'ensemble de toutes les langues sur un alphabet donné est indénombrable. Cependant, l'ensemble de toutes les machines Turing est dénombrable. Cela implique directement l'existence de problèmes indécidables. Cependant, ce raisonnement n'implique rien sur le problème de l'arrêt.
042
9
Il existe certainement des modèles théoriques des ensembles de ZFC où tous les ensembles sont dénombrables (mais pas dans le modèle), mais le problème d'arrêt est toujours indécidable. Voir cette question MathOverflow .
Peter Shor
4
S'il vous plaît, s'il vous plaît, dites indécidabilité à partir de maintenant.
Vijay D

Réponses:

14

Ce n'est pas un lien caché, mais un lien qui a été rendu explicite en utilisant le langage de la théorie des catégories et aussi une question très naturelle à poser et à étudier. Il y a pas mal de matériel sur le sujet.

Vijay D
la source