Дескриптивная теория множеств: борелевская иерархия

В 1905 году Анри Лебег задался вопросом: существует ли проекция борелевского множества в R^2 на R, которая не является борелевской? В 1916 году 19-летний Михаил Суслин нашёл пример - и открыл целую вселенную проективных множеств, изучаемую до сих пор.

• Борелевские иерархии используются в верификации программ: Sigma^0_2 свойства (safety) и Pi^0_2 свойства (liveness) - это точные классы в иерархии логики темпоральных спецификаций. TLA+ (Microsoft, Lamport) работает с этими понятиями.

Борелевская иерархия

Эмиль Борель в 1898 году определил борелевские множества как наименьшую сигма-алгебру, содержащую открытые множества. Иерархия классов Sigma^0_alpha, Pi^0_alpha, Delta^0_alpha по трансфинитным ординалам alpha < omega_1 классифицирует сложность: Sigma^0_1 = открытые, Pi^0_1 = замкнутые, Sigma^0_2 = F_sigma, Pi^0_2 = G_delta. Эта иерархия является фундаментом дескриптивной теории множеств и связана с иерархией Клини в вычислимости.

Аналитические множества и проективная иерархия

Аналитические множества Sigma^1_1 - непрерывные образы борелевских. Сусслин (1916) показал, что проекция борелевского подмножества R^2 на R не обязательно борелевская. Это открыло проективную иерархию: Sigma^1_n, Pi^1_n, Delta^1_n. Детерминированность проективных игр (Martin, Steel, Woodin) стала центральным результатом 1980-х.

Ключевые результаты

• Борелевская иерархия: Sigma^0_alpha = счётные объединения Pi^0_<alpha.
• Теорема Сусслина: Delta^1_1 = борелевские множества.
• Sigma^1_1 = аналитические = проекции борелевских. Все измеримы по Лебегу.
• Регулярность свойств Sigma^1_2 и выше зависит от аксиом (PD, большие кардиналы).