Докажите, что существует двусторонняя последовательность...⊂A/−1/⊂A/0/⊂A/1/⊂..., такая что Ai перечислимо при чётных i и неперечислимо при нечётных i.

задан 2 Май 2:26

10|600 символов нужно символов осталось
0

Вместо подмножеств 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 Май 3:59

@falcao Почему множество A(2k+1) = A(2k) U (X x {2k+2} будет неперечислимо?

(2 Май 23:30) xejoto

@xejoto: множество A(2k) разрешимо по очевидной причине. Если бы A(2k+1) было перечислимо, то X оказалось бы перечислимо. В самом деле, печатая элементы A(2k+1), состоящие из пар, мы бы сначала проверили, не принадлежит ли пара множеству A(2k) -- просто посмотрев на его вторую координату. Если нет, то первая координата принадлежит X. Тогда этот элемент печатаем, что даёт перечислимость X.

Если бы за этим стояло нечто нетривиальное, я бы объяснил в тексте. А если я этого не сделал, то речь о чём-то "одноходовом".

(3 Май 0:12) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,469
×886
×621

задан
2 Май 2:26

показан
112 раз

обновлен
3 Май 0:12

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru