|
Докажите, что существует двусторонняя последовательность...⊂A/−1/⊂A/0/⊂A/1/⊂..., такая что Ai перечислимо при чётных i и неперечислимо при нечётных i. задан 2 Май '20 2:26 
xejoto |
|
Вместо подмножеств N будем рассматривать подмножества счётного множества N x Z, которое равномощно N. Построим там подходящую цепочку, а потом перенесём её в N посредством вычислимой биекции. В качестве A(2k) берём N x {i \in Z | i<=k}. Очевидно, все такие множества перечислимы. При переходе от A(2k) к A(2k+2) мы добавляем одну копию N, а именно, N x {2k+2}. Зафиксируем какое-то одно неперечислимое подмножество X < N, и положим A(2k+1) = A(2k) U (X x {2k+2}). Ясно, что оно будет неперечислимо. отвечен 2 Май '20 3:59 
falcao @falcao Почему множество A(2k+1) = A(2k) U (X x {2k+2} будет неперечислимо?
(2 Май '20 23:30)
xejoto
@xejoto: множество A(2k) разрешимо по очевидной причине. Если бы A(2k+1) было перечислимо, то X оказалось бы перечислимо. В самом деле, печатая элементы A(2k+1), состоящие из пар, мы бы сначала проверили, не принадлежит ли пара множеству A(2k) -- просто посмотрев на его вторую координату. Если нет, то первая координата принадлежит X. Тогда этот элемент печатаем, что даёт перечислимость X. Если бы за этим стояло нечто нетривиальное, я бы объяснил в тексте. А если я этого не сделал, то речь о чём-то "одноходовом".
(3 Май '20 0:12)
falcao
|