avva | о теории множеств и исключённом третьем

На рассылке FOM обсуждают доказательства, использующие закон исключённого третьего нетривиальным и неконструктивным образом. Это значит, что, например, в процессе доказательства какого-то утверждения X мы используем следующую конструкцию:

если Y верно, то... [цепочка рассуждений приводящая к док-ву X]
если Y неверно, то... [другая цепочка рассуждений, тоже приводящая к док-ву X]

При этом мы можем не интересоваться или даже не знать того, верно на самом деле Y или нет (в этом и состоит неконструктивность использования закона исключённого третьего, который гласит: "либо Y, либо не-Y").

Я недавно приводил пример любимого мной доказательства, построенного таким образом. Правда, там мы знаем, верно Y или нет -- просто это показывается куда менее тривиальными методами, чем само доказательство.

А вот очень красивый, по-моему, пример (с рассылки, courtesy of Joe Shipman), такого же рассуждения, где Y - гипотеза континуума (независимая, как известно из работ Гёделя и Коэна, от других аксиом теории множеств).

Мы работаем с множеством действительных чисел R. Построим два множества его подмножеств:

A - множество всех подмножеств R, мощность которых - алеф-1 (т.е. следующее за алеф-0 кардинальное число; если гипотеза континуума верна, то алеф-1 является также мощностью всего множества R; если она неверна, то алеф-1 расположен строго между алеф-0 и мощностью R).
B - множество всех не-борелевских подмножеств R.

Вспомним также, что каждое борелевское множество либо конечно, либо счётно (имеет мощность алеф-0), либо имеет мощность континуума, т.е. равную мощности всего R. Этот результат был впервые доказан Хаусдорффом в 1916-м году (он показал, что каждое несчётное борелевское множество содержит в себе совершенное множество, а что совершенное множество имеет мощность континуума показать легко).

Что теперь происходит? Если CH (Continuum Hypothesis - гипотеза континуума) верна, то между алеф-0 и c (мощностью континуума) ничего нет; c равно алеф-1. Т.к. любое конечное или счётное множество - борелевское, то любое не-борелевское множество обязано иметь мощность континуума, т.е. алеф-1. Поэтому B - подмножество A, причём строгое подмножество (т.к. есть и борелевские множества размером алеф-1).

Если же CH неверна, то любое множество действительных размером алеф-1 не может быть борелевским, т.к. оно несчётно, а все несчётные борелевские множества имеют мощность континуума, которая в этом случае строго больше алеф-1. Поэтому A - подмножество B, причём строгое (можно построить не-борелевское множество мощностью c).

Итак: либо A - строгое подмножество B, либо B - строгое подмножество A, причём мы не знаем, какая из этих двух возможностей верна, и никогда не сможем узнать в рамках стандартной теории множеств (т.к. CH независима от остальных аксиом, поэтому при помощи остальных аксиом невозможно ни доказать, ни опровергнуть CH).

Красиво!