о теории множеств и исключённом третьем
Sep. 11th, 2002 07:02 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaНа рассылке FOM обсуждают доказательства, использующие закон исключённого третьего нетривиальным и неконструктивным образом. Это значит, что, например, в процессе доказательства какого-то утверждения X мы используем следующую конструкцию:
Я недавно приводил пример любимого мной доказательства, построенного таким образом. Правда, там мы знаем, верно Y или нет -- просто это показывается куда менее тривиальными методами, чем само доказательство.
А вот очень красивый, по-моему, пример (с рассылки, courtesy of Joe Shipman), такого же рассуждения, где Y - гипотеза континуума (независимая, как известно из работ Гёделя и Коэна, от других аксиом теории множеств).
Мы работаем с множеством действительных чисел 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).
Красиво!
- если Y верно, то... [цепочка рассуждений приводящая к док-ву X]
- если Y неверно, то... [другая цепочка рассуждений, тоже приводящая к док-ву X]
Я недавно приводил пример любимого мной доказательства, построенного таким образом. Правда, там мы знаем, верно 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).
Красиво!
