Эффективная теория множеств. Дискретная оптимизация

1.

В лаборатории 6
«Математические методы и модели в биоинформатике»
присутствуют две математические темы:
1) «Эффективная теория множеств»
(В. Кановей, В. Любецкий)
и
2) «Дискретная оптимизация»
(К. Горбунов, В. Любецкий).
Сегодня расскажем о 1-й теме на примере нашего решения
проблемы А. Тарского, поставленной им и остававшейся открытой с
1948 года до 2022. Сначала – план решения, потом – подробности.

2.

Нами также рассмотрен вопрос, который вряд ли даже
возникал в время Тарского: может ли для любого
наперёд заданного множества U
N в некоторой
структуре L[G] выполняться:
L[G]
n
U
(*) и n
U
(*). ?
Напомним: множество U называется алгоритмически
разрешимым, если существует алгоритм, который на n U
выдаёт 1 и на n U выдаёт 0.
Теорема (Кановей – Любецкий). L[G]
разрешимого множества U, n
U
«для любого
(*) и n
U
(*).