Как построить такое множество, что его дополнение и оно само неперечислимо?

задан 12 Июн 2:59

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

Один из возможных примеров таков. Рассмотрим формальную арифметику PA (описание см. в учебнике Мендельсона). Известно, что эта теория алгоритмически неразрешима. Занумеруем стандартным образом все замкнутые формулы теории. Каждая из них либо истинна, либо ложна в стандартной интерпретации. В качестве A возьмём множество номеров истинных формул. Его дополнением будет множество номеров ложных формул. Если одно из этих множеств было бы перечислимым, то и другое тоже было бы таковым, так как отрицание истинной формулы ложно. Тогда по известному критерию оказалось бы, что множество номеров истинных формул разрешимо, но это заведомо не так.

Примеры здесь можно построить и другие -- по идее, их много.

ссылка

отвечен 12 Июн 19:53

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,709

задан
12 Июн 2:59

показан
55 раз

обновлен
12 Июн 19:53

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

по почте:

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

по RSS:

Ответы

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

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