2.5. Простые множества: конструкция Поста

Существуют и другие конструкции перечислимых не­разрешимых множеств. Вот одна из них (предложенная Э. Постом).

Назовём множество иммунным, если оно бесконеч­но, но не содержит бесконечных перечислимых подмно­жеств. Перечислимое множество называют простым, ес­ли его дополнение иммунно. (Очевидно, такое множество не может быть разрешимым.)

Теорема 14. Существует простое множество.

<] Нам нужно, чтобы перечислимое множество 5 име­ло иммунное дополнение. Это означает, что 5 должнопересекаться с любым бесконечным перечислимым мно­жеством. Чтобы гарантировать это, полезно для каждо­го перечислимого множества V добавить какой-то его элемент в 5 (хотя бы для бесконечных V"). При этом на­до позаботиться о том, чтобы вне 5 осталось бесконечно много элементов. Это можно гарантировать, если доба­влять достаточно болыпйе элементы (например, из мно­жества номер г добавлять только один элемент, притом больший 2г).

Объясним конструкцию подробнее. Пусть И7 — уни­версальное перечислимое множество пар, среди сече­ний И7,- которого встречаются все перечислимые множе­ства натуральных чисел. Будем называть И7,- «перечи­слимым множеством номер и (при этом разным номерам может соответствовать одно и то же множество). Рас­смотрим множество пар Т = {(г, х) \ (х £ И7,-) и (х > 2г)}. Это множество перечислимо (как пересечение Ш и раз­решимого множества {{г, ж) | х > 2г}). Перечисляя его, будем отбрасывать пары, у которых первый член уже встречался ранее. Останется некоторое перечислимое подмножество Т' С Т. Рассмотрим теперь перечислимое множество 5 вторых членов пар, входящих в Т".

Это множество пересекается с любым бесконечным перечислимым множеством. В самом деле, если И7,- бес­конечно, то оно содержит и числа, большие 2г, поэтому в Т (а, значит, и в Т") есть пары с первым членом г. Вто­рой член такой пары из Т' будет лежать и в 5, и в И7,-.

С другой стороны, множество 5 имеет бесконечное дополнение, поскольку среди чисел от 0 до 2п — 1 мак­симум п различных чисел могут принадлежать 5 (это числа, попавшие в 5 с одной из первых п вертикалей — все остальные будут уже больше 2п). >

26. Докажите, что бесконечное множество, не содержащее бесконечных разрешимых подмножеств, иммунно.

27. Докажите, что существует перечислимое множество, для которого прямой пересчёт (последовательность элемен­тов в порядке возрастания без повторений) его дополнения не ограничен сверху никакой всюду определённой вычислимой функцией. Докажите, что это множество является простым.