Верещагин, Шень "Вычислимые функции" задача №26

[AlexeyKh]

Покажите, что существует множество, которое можно представить в виде симметрической разности трёх перечислимых множеств, но нельзя представить в виде симметрической разности двух перечислимых множеств. См. задачи 15 и 16. (Указание. В классе множеств, которые можно представить в виде симметрической разности двух перечислимых множеств, есть универсальное.)

Из №15 следует, что симметрическую разность двух перечислимых множеств можно представить в виде $A \setminus B, A \supset B$, где $A,B$ - перечислимы.
Из 16 - что симметрическую разность трех перечислимых множеств можно представить в виде $A \setminus (B \setminus C), A \supset B \supset C$, где $A,B,C$ - перечислимы.

Получается, что исходную задачу можно перефразировать: $\exists A \supset B \supset C(\neg\exists A' \supset B'(A \setminus (B \setminus C) = A' \setminus B'))$, где $A,B,C,A',B'$ - перечислимы.
$B \setminus C$ должно быть неперечислимым (в противном случае $A' = A, B' = B \setminus C$)
$B \setminus C$ будет неперечислимым, если $B = \mathbb{N}$, $C$- номера самопременимых программ. (других примеров не знаю). В таком случае $A = \mathbb{N}$, иначе не выполнится условие $A \supset B$. Но разность трех таких множеств легко представляется в виде разности двух перечислимых множеств: $\mathbb{N} \setminus (\mathbb{N} \setminus C) = C \setminus \varnothing$

И еще - не понимаю зачем в указании говорится про универсальное множество? И симметрической разностью каких множеств оно является? (кроме $U \Delta \varnothing$)

[svv]

AlexeyKh в сообщении #1123602 писал(а):

И симметрической разностью каких множеств оно является? (кроме $U \Delta \varnothing$)

(Прочитал только этот вопрос.) Симметрической разностью любого множества $A$ и его дополнения (до универсального).