подмножества бесконечных рекурсивных множеств

Недавний экзаменационный вопрос звучал так:

1. $A$ - бесконечное рекурсивно перечислимое множество. Докажите, что имеет бесконечное рекурсивное подмножество.$A$
2. Пусть бесконечное рекурсивное подмножество . Должен ли иметь подмножество, которое не является рекурсивно перечислимым?$C$$A$$C$

Я ответил 1. уже. Относительно 2. я ответил утвердительно и утверждал следующее.

Предположим, что все подмножества были рекурсивно перечислимыми. Поскольку бесконечен, набор степеней неисчислим, поэтому, по предположению, будет неисчислимо много рекурсивно перечислимых множеств. Но рекурсивно перечислимые множества находятся в однозначном соответствии с распознающими их машинами Тьюринга, а машины Тьюринга перечислимы. Противоречие. Таким образом, должен иметь подмножество, которое не является рекурсивно перечислимым.$C$$C$$C$$C$

Это верно?

Это верно.

Каждое бесконечное множество имеет неразрешимое подмножество, вы можете использовать аргумент мощности: $\aleph_0\leq C \implies \aleph_0 < 2^C$

$C$

$D = \{ i \in C \mid i \notin W_i \}$$W_i$$i$$D \subseteq C$$D$$C$$K = \{ i \mid i\notin W_i\}$$C$$D$