QCM Calculabilité Q6 - LINGI1123, QCM 2 Séance 2 (Réponse Potentiellement Erroné)
Closed this issue · 2 comments
La question :
Un sous-ensemble infini d’un ensemble énumérable est énumérable.
Est normalement FAUX, car le contre exemple :
Complément de K est un sous ensemble de N (énumérable), pourtant ceci n'est pas énumérable.
Mais dans le fichier QCM Calculabilité Q6 - LINGI1123, ceci est marqué comme VRAI.
La justification :
C’est un sous-ensemble donc il ne peut pas avoir plus d’éléments., me fait croire que la question a été mal écrit.
Quel est l'ensemble K ? J'ai l'impression que c'est vrai. Si un ensemble A est un sous-ensemble de B et B est énumérable, alors A est énumérable aussi.
Voici une idée de preuve.
Si A est énumérable, c'est possible d'avoir une énumération a_1, a_2, .... tels que {a_i | i = 1, 2, ... } = A
Comme B est une sous-ensemble de A, pour chaque b in B, il existe i(b) tel que b = a_{i(b)}.
Considère la fonction f(b) = |{j | a_j in b, j <= i}| (où |...| est le nombre d'éléments d'un ensemble). Comme B est infini, la fonction f est une bijection entre B et N. Donc B est énumérable.
En effet, je viens de me rendre compte que j'ai mélangé le concept de récursivement énumérable avec énumérable