Saturday, April 09, 2016

Парадоксы теории множеств

Основано на информация википедии, в частности статьи Кризис оснований математики, Парадокс Рассела, Парадокс Кантора, Парадокс Бурали-Форти


Теоретико-множественный подход, получивший широкое развитие в конце XIX века, позволил возвести математику на прочном, и, казалось, надежном фундаменте — канторовой теории множеств. Развитие канторовой теории множеств привело к возможности выразить в терминах этой теории все основные математические понятия. Возможность построения математики на теоретико-множественном фундаменте Гильберт охарактеризовал как «рай для математиков», а уже построенную на этой основе часть математики называл «симфонией бесконечного». Однако восторги сменились шоковым состоянием, когда была обнаружена противоречивость данного подхода.


Ниже есть продолжение.

На рубеже XIX—XX веков были открыты так называемые парадоксы теории множеств. Сущность парадокса заключается в том, что с помощью логически правильных рассуждений удаётся обосновать (доказать средствами данной теории) одновременно некоторое утверждение и его отрицание, то есть противоречие.

С целью избежания некоторых парадоксов было предложено ограничить принцип свёртывания — широко распространённой математической конструкции, позволяющей образовывать множества с помощью тех или иных свойств объектов.

Принцип свёртывания заключается в том, что для любого свойства P считается существующим множество, состоящее из тех и только тех объектов, которые обладают свойством P.

В ограниченном принципе свёртывания, к условию P(x) добавляется условие, согласно которому элементы M берутся из некоторого заданного множества E, существование которого выведено из некоторого («надёжного») списка аксиом.

Однако даже полное избавление от обнаруженных парадоксов не спасает и не страхует теорию множеств от новых парадоксов. Поэтому по-прежнему оставалась актуальной задача «спасения» математики. Фактически перед математиками стояла задача переосмысления логических средств, используемых в математических рассуждениях, надежности этих средств и соответствия их существу математики. Гарантировать невозможность противоречий в математической теории могло лишь доказательство непротиворечивости этой теории.

Приведём в качестве примеров три парадокса.

Парадокс Рассела. Пусть K — множество всех множеств, которые не содержат себя в качестве своего элемента. Содержит ли K само себя в качестве элемента? Если предположить, что содержит, то мы получаем противоречие с "Не содержат себя в качестве своего элемента". Если предположить, что K не содержит себя как элемент, то вновь возникает противоречие, ведь K — множество всех множеств, которые не содержат себя в качестве своего элемента, а значит должно содержать все возможные элементы, включая и себя.

Противоречие в парадоксе Рассела возникает из-за использования в рассуждении внутренне противоречивого понятия множества всех множеств и представления о возможности неограниченного применения законов классической логики при работе с множествами. Для преодоления этого парадокса было предложено несколько путей. Наиболее известный состоит в предъявлении для теории множеств непротиворечивой формализации M, по отношению к которой являлись бы допустимыми все «действительно нужные» (в некотором смысле) способы оперирования с множествами. В рамках такой формализации утверждение о существовании множества всех множеств было бы невыводимым.

Парадокс Кантора — парадокс теории множеств, который демонстрирует, что предположение о существовании множества всех множеств ведёт к противоречиям и, следовательно, противоречивой является теория, в которой построение такого множества возможно.

Предположим, что множество всех множеств V существует. В этом случае справедливо, что всякое множество t является подмножеством V. Но из этого следует, что мощность любого множества t не превосходит мощности V, т.е. $|P (V)|<=|V|$

С другой стороны для V, как и любого множества, существует множество всех подмножеств P(V), и по теореме Кантора $|P (V)| = 2^{|V|} > |V|$, что противоречит предыдущему утверждению. Следовательно, V не может существовать, что вступает в противоречие с «наивной» гипотезой о том, что любое синтаксически корректное логическое условие определяет множество.

Другая формулировка парадокса Кантора: Не существует максимального кардинального числа. В самом деле: пусть оно существует и равно $\mu$. Тогда по теореме Кантора $2^\mu > \mu$, т.е. мы построили кардинальное число больше, чем $\mu$, в противоречии с тем, что это максимум.

Этот парадокс, открытый Кантором около 1899 года, обнаружил необходимость пересмотра «наивной теории множеств» (парадокс Рассела был открыт несколько позднее, около 1901 года).

Парадокс Бурали-Форти демонстрирует, что предположение о существовании множества всех порядковых чисел ведёт к противоречиям и, следовательно, противоречивой является теория множеств, в которой построение такого множества возможно.

Можно доказать, что если x — произвольное множество порядковых чисел, то множество-сумма $\cup x$ есть порядковое число, большее или равное каждому из элементов x. Предположим теперь, что $\Omega$ — множество всех порядковых чисел. Тогда $\cup \Omega$ — порядковое число, большее или равное любому из чисел в $\Omega$. Но тогда и $\cup \Omega \cup \{\cup \Omega\} = \cup \Omega + 1$ — порядковое число, причём уже строго большее, а значит, и не равное любому из чисел в $\Omega$. Но это противоречит условию, по которому $\Omega$ — множество всех порядковых чисел.

Парадокс был обнаружен Чезаре Бурали-Форти в 1897 году и оказался одним из первых парадоксов, показавших, что наивная теория множеств противоречива, а следовательно, непригодна для нужд математики. Несуществование множества всех порядковых чисел противоречит концепции наивной теории множеств, разрешающей построение множеств с произвольным свойством элементов, то есть термов вида "множество всех x таких, что P".


Тем не менее сущность кризиса не исчерпывалась только парадоксами, а заключалась также и в следующем.

* Во-первых, к концу XIX века среди математиков наметились существенные расхождения во взглядах на основные математические понятия и принципы, а также на логические принципы, используемые в математике.

* Во-вторых, возникли расхождения во взглядах на выбор путей избавления от парадоксов.

* Наконец, и по-видимому это самое главное, существовали принципиальные трудности обоснования непротиворечивости математики, её «спасения», многие из которых не преодолены до сих пор.

В результате различных взглядов на использование логических и теоретико-множественных принципов, а также различных взглядов на пути выхода из кризиса сформировались разные математические школы, яростно противостоявших друг другу.

Лидирующей школой являлась формалистская, самым ярким последователем которой был Давид Гильберт. Свои идеи он собрал в так называемой Гильбертовой программе, в которой предполагалось обосновать математику на небольшом логическом базисе, содержащемся в финитизме.

Основным противником данной школы была школа интуиционистов, отрицавшая возможность использования двойного отрицания и считающая недопустимым принятие принципа абстракции актуальной бесконечности. Возглавлял школу Лёйтзен Брауэр. Он безбоязненно отвергал формализм как бессмыссленную игру с символами. В 1920 году Гильберт добился исключения Брауэра, которого он считал угрозой математике, из группы редакторов Mathematische Annalen, главного математического журнала того времени.

Однако теоремы Гёделя о неполноте, доказанные в 1931 году, показали, что ключевые аспекты программы Гильберта не могут быть достигнуты.

Гёдель показал, как сконструировать для любой достаточно сильной и непротиворечивой рекурсивно аксиоматизируемой системы (такой, которая необходима, чтобы аксиоматизировать элементарную теорию арифметики на множестве натуральных чисел) утверждение, для которого может быть показана его правдивость, но не доказуемое системой. Таким образом, стало ясно, что математические основы не могут быть сведены к чисто формальной системе, как предполагалось в Гильбертовой программе. Тем самым был нанесен сокрушительный удар в сердце Гильбертовой программы, — программы, которая предполагала, что непротиворечивость может быть установлена финитическими средствами.
В то же время, интуиционистская школа не привлекла к себе каких-либо постоянных последователей среди активных математиков из-за проблем в конструктивной математике.

Кризис всё ещё не пройден, но он затух. Большинство математиков или не работают с уровня аксиоматических систем, или, если работают, то не сомневаются в корректности системы ZFC, наиболее популярной аксиоматической системы. В большинстве разделов практической математики математические парадоксы и так не играли никакой роли, а в тех разделах, которые напрямую связаны с основами математики — в частности, математическая логика и теория категорий, — их можно обойти.


No comments:

Post a Comment