Аксиома выбора

Размещено на http://www.allbest.ru/

Введение

Аксиома выбора (от греч. axioma - принятое положение) - один из важнейших теоретико-множественных принципов, введенный в 1904 Э. Цермело и утверждающий, что «для всякого семейства непустых множеств существует функция выбора, выбирающая из каждого множества этого семейства ровно по одному элементу». Аксиома выбора была введена в силу того факта, что имевшиеся к тому времени «наивные» принципы рассуждений не позволяли ответить на очень многие простые вопросы о множествах (напр., на вопрос о сравнении мощностей двух произвольных множеств). С помощью аксиомы выбора Э. Цермело удалось доказать, что всякое множество может быть вполне упорядочено (как оказалось, это просто одна из эквивалентных форм аксиомы выбора).

Аксиома выбора вызвала серьезные возражения со стороны многих математиков начала 20 в. как самой формулировкой, так и некоторыми своими следствиями (утверждавшими существование множеств с непривычными свойствами, например, неизмеримого множества действительных чисел, или того факта, что множество действительных чисел можно вполне упорядочить).

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

Тем не менее, оказалось (и это было подтверждено дальнейшими исследованиями в метаматематике и дескриптивной теории множеств), что некоторые утверждения, совершенно необходимые для построения математического анализа и теории меры не могут быть получены без аксиомы выбора. Однако для доказательства этих утверждений необходима не полная форма аксиома выбора, а так называемая счетная форма аксиомы выбора, которая постулирует существование функции выбора в случае, если семейство непустых множеств счетно. Оказалось, что именно такой формы аксиомы выбора достаточно, чтобы построить теорию меры и математический анализ в привычном для классического математика виде. Аксиома выбора оказалась как совместной (К. Гедель, 1939), так и независимой (П. Коэн, 1963) от остальных постулатов теории множеств Цермело-Френкеля (а также и от ряда теоретико-множественных принципов, вводимых в дальнейшем для подобного исследования). Отметим также, что аксиома выбора несовместна с некоторыми аксиоматическими системами теории множеств с подлежащей классической логикой (т.е. в таких системах выводимо отрицание А.в.). Таким образом, вопрос о принятии аксиомы выбора в полном виде или в виде некоторых «урезанных» форм зависит от того, какую математическую теорию мы желаем построить, т.е. От исходных философских установок.

Аксиомой выбора называется следующее высказывание теории множеств: «Для каждого семейства непустых непересекающихся множеств существует (по меньшей мере одно) множество d, которое имеет только один общий элемент c c каждым из множеств b данного семейства».

На формальном языке:

1. История и оценки

Аксиома выбора была сформулирована и опубликована Эрнстом Цермело в 1904 году (хотя впервые её отметил Беппо Леви на 2 года раньше). Новая аксиома вызвала бурную полемику и до сих пор принимается в качестве аксиомы не всеми математиками безоговорочно: некоторые математики относятся с недоверием к её недоказуемости. В связи с сомнительным характером недоказуемости этой аксиомы также бытует мнение, что доказательства, полученные с её привлечением, имеют «иную познавательную ценность», чем доказательства, независимые от неё. Появление аксиомы выбора в своё время даже вызвало дискуссию о том, что означает в математике понятие «существование» - в частности, о том, можно ли считать существующим множество, ни один элемент которого не известен.

Неприятие аксиомы выбора некоторыми математиками в качестве аксиомы основано, прежде всего, тем, что в ней лишь утверждается существование множества d, но не дается никакого способа его определения: хотя этот способ интуитивно ясен для конечных множеств (достаточно выбрать по одному элементу от каждого из непересекающихся множеств, чтобы сформировать множество d), нет никакой гарантии, что эта аксиома окажется справедливой в общем случае (в частности, в случае бесконечных множеств). Конечно, можно дать способ построения множества d для любых множеств (в том числе и для бесконечных), но в чём тогда «аксиоматичность» аксиомы выбора? Это мнение, например, Бореля и Лебега. Противоположного мнения придерживались, например, Гильберт, Хаусдорф и Френкель, которые принимали аксиому выбора без всяких оговорок, признавая за ней ту же степень «очевидности», что и за другими аксиомами теории множеств: аксиома объёмности, аксиома существования пустого множества, аксиома пары, аксиома суммы, аксиома степени, аксиома бесконечности.

Более того, среди следствий аксиомы выбора есть много довольно парадоксальных, вызывающих интуитивный протест некоторых исследователей. Например, появляется возможность доказать парадокс Банаха - Тарского, который вряд ли могут счесть «очевидным» все исследователи (см. ткж. Квадратура круга Тарского (англ.)). Подробный анализ многочисленных доказательств, использующих аксиому выбора, провел Вацлав Серпинский. Однако, без сомнения, многие важные математические открытия нельзя было бы сделать без аксиомы выбора[1].

Бертран Рассел так отозвался об аксиоме выбора: «Сначала она кажется очевидной; но чем больше вдумываешься, тем более странными кажутся выводы из этой аксиомы; под конец же вообще перестаешь понимать, что же она означает».

2. Альтернативные формулировки

Аксиома выбора утверждает:

Пусть X - множество непустых множеств. Тогда мы можем выбрать единственный элемент из каждого множества в X.

Функция выбора - функция на множестве множеств X такая, что для каждого множества s в X, f(s) является элементом из s. С использованием понятия функции выбора аксиома утверждает:

Для любого семейства непустых множеств X существует функция выбора f, определённая на X.

Или альтернативно:

Произвольное декартово произведение непустых множеств непусто.

Или наиболее сжато:

Каждое множество непустых множеств имеет функцию выбора.

Отсюда немедленно следует компактная формулировка отрицания аксиомы выбора:

Существует множество непустых множеств, которое не имеет никакой функции выбора.

Вторая версия аксиомы выбора утверждает:

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

Некоторые авторы используют другую версию, которая эффективно утверждает:

Для любого множества A, его булеан за вычетом пустого подмножества  имеет функцию выбора.

Авторы, которые используют эту формулировку, часто также говорят о «функции выбора на A», но оговаривают, что имеют в виду немного другое понятие функции выбора. Её область определения - булеан (минус пустое подмножество), тогда как в других местах этой статьи, область определения функции выбора - «множество множеств».

С этим дополнительным понятием функции выбора, аксиома выбора может быть сжато сформулирована так: каждое множество имеет функцию выбора.

3. Применение

До конца XIX века аксиома выбора использовалась безоговорочно. Например, после определения множества X, содержащего непустое множество, математик мог сказать: «Пусть F(s) будет определено для каждого s из X». В общем, невозможно доказать, что Fсуществует без аксиомы выбора, но это, кажется, оставалось без внимания до Цермело.

Не во всех случаях требуется аксиома выбора. Для конечного набора X аксиома выбора следует из других аксиом теории множеств. В этом случае это то же самое, что говорить, если мы имеем несколько (конечное число) коробок, каждая из которых содержит в себе по одной одинаковой вещи, тогда мы можем выбрать ровно одну вещь из каждой коробки. Ясно, что мы можем сделать это: мы начнём с первой коробки, выберем вещь; отправимся ко второй коробке, выберем вещь; и т. д. Так как есть конечное число коробок, то действуя нашей процедурой выбора, мы придём к концу. Результатом будет функция явного выбора: функция, которая первой коробке сопоставляет первый элемент, который мы выбрали, второй коробке - второй элемент и т.д. (Для получения формального доказательства для всех конечных множеств следует воспользоваться принципом математической индукции).

В случае с бесконечным множеством X иногда также можно обойти аксиому выбора. Например, если элементы X - множества натуральных чисел. Каждый непустой набор натуральных чисел имеет наименьший элемент, таким образом, определяя нашу функцию выбора, мы можем просто сказать, что каждому множеству сопоставляется наименьший элемент набора. Это позволяет нам сделать выбор элемента из каждого множества, поэтому мы можем записать явное выражение, которое говорит нам, какое значение наша функция выбора принимает. Если возможно таким образом определить функцию выбора, в аксиоме выбора нет необходимости.

Сложности появляются в случае, если невозможно осуществить естественный выбор элементов из каждого множества. Если мы не можем сделать явный выбор, то почему уверены, что такой выбор можно совершить в принципе? Например, пусть X - это множество непустых подмножеств действительных чисел. Во-первых, мы могли бы поступить как в случае, если бы X было конечным. Если мы попробуем выбрать элемент из каждого множества, тогда, так как X бесконечно, наша процедура выбора никогда не придёт к концу, и вследствие этого мы никогда не получим функции выбора для всего X. Так что это не срабатывает. Далее, мы можем попробовать определить наименьший элемент из каждого множества. Но некоторые подмножества действительных чисел не содержат наименьший элемент. Например, таким подмножеством является открытый интервал . Если x принадлежит , то x / 2 также принадлежит ему, причем меньше, чем x. Итак, выбор наименьшего элемента тоже не работает.

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

Доказательства, требующие аксиомы выбора, всегда неконструктивны: даже если доказательство создаёт объект, невозможно сказать, что же именно это за объект. Следовательно, хоть аксиома выбора позволяет вполне упорядочить множество действительных чисел, это не даёт нам никакой наглядности и конструктивизма в целом. Сама причина, по которой наш вышеуказанный выбор вполне упорядочения действительных чисел был таким для каждого множества X, мы могли явно выбрать элемент из такого множества. Если мы не можем указать, что мы используем вполне упорядоченность, тогда наш выбор не вполне явный. Это одна из причин, почему некоторые математики не любят аксиому выбора). Например, конструктивистская установка что все существующие доказательства должны быть полностью явными; должно быть возможным построение чего бы то ни было что существует. Они отвергают аксиому выбора потому, что она заявляет существование объекта без описания. С другой стороны, факт - что для доказательства существования используется аксиома выбора - не означает, что мы не сможем совершить построение другим способом.

3.1 Принцип вполне упорядочивания (теорема Цермело)

Очень распространённая и удобная формулировка использует понятие вполне упорядоченного множества. Нам потребуется несколько определений, и мы начнём со строгого определения линейного порядка, выражающего знакомую нам идею на языке теории множеств. Напомним, что упорядоченная пара элементов обозначается  и что декартово произведение множеств состоит из всех возможных упорядоченных пар  где .

Линейным порядком на множестве A называется подмножество декартова произведения , обладающее следующим свойствами:

Полное: .

Антисимметричное: .

Транзитивное: .

Полным порядком на множестве A называется такой линейный порядок, что каждое подмножество  имеет наименьший элемент.

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

Например, множество натуральных чисел может быть вполне упорядоченно обычным отношением «меньше или равно чем». С тем же отношением, множество целых чисел не имеет наименьшего элемента. В этом случае мы можем собрать целые числа в последовательность  и сказать, что младшие члены меньше чем старшие. Очевидно, такое отношение будет полным порядком на целых числах.

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

3.2 Лемма Цорна

аксиома цермело хаусдорф принцип

Если в частично упорядоченном множестве любая цепь (то есть линейно упорядоченное подмножество) имеет верхнюю грань, то всё множество имеет хотя бы один максимальный элемент.

Более формально:

Пусть  - частично упорядоченное множество, то есть, отношение  - рефлексивно, антисимметрично и транзитивно:

Подмножество  называется линейно упорядоченным, если . Элемент называется верхней гранью, если . Допустим, что любое линейно упорядоченное подмножество множества P имеет верхнюю грань. Тогда  - максимальный элемент.

3.3 Принцип максимума Хаусдорфа

В любом упорядоченном множестве существует максимальное линейное упорядоченное подмножество.

Принцип максимума Хаусдорфа был сформулирован и доказан Феликсом Хаусдорфом в 1914 году, и является альтернативной и более ранней формулировкой леммы Куратовского-Цорна. Как и указанная лемма, принцип максимума Хаусдорфа эквивалентен аксиоме выбора.

Примечания

Элементы: Пределы доказуемости - elementy.ru/lib/430319.

Литература

1. Александров П.С. Введение в теорию множеств и общую топологию - djvu.504.com1.ru:8019/WWW/b18b6e7a94ee349b1091af3b317c6630.djvu. - М.: Наука, 1977. - 368 с. - Глава 3, § 4.

2. Кановей В.Г. Аксиома выбора и аксиома детерминированности - djvu.504.com1.ru:8019/WWW/05b81804f60db0aa728da55e7de216f1.djvu. - М.: Наука, 1984. - 64 с. - (Проблемы науки и технического прогресса).

3. Медведев Ф.А. Ранняя история аксиомы выбора - lib.homelinux.org/_djvu/M_Mathematics/MA_Algebra/MAml_Mathematical logic/Medvedev F.A. Rannyaya istoriya aksiomy vybora (Nauka, 1982)(ru)(T)(305s)_MAml_.djvu. - М.: Наука, 1982. - 304 с.

Размещено на Allbest.ru