Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

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

На рассылке 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).

Красиво!
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 2 comments