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

есть немало математиков, считающих, что аксиоматический метод порочен сам по себе. эта точка зрения была выдвинута математиком Брауэром (Luitzen Egbertus Jan Brouwer), знаменитым топологом, в 1908 г., в статье, озаглавленной "De onbetrouwbaarheid der logische principes" - "О сомнительности основ логики". Брауэр считал, что классическая (аристотелева) логика не может быть применима к бесконечным множествам и все математические исследования, которые основаны на таких применениях, неправильны. особенно Брауэру не нравился принцип исключенного третьего, на котором основаны популярные доказательства "от противного". на протяжении 1920-х гг. Брауэр был редактором журнала "Mathematische Annalen", и он принципиально возвращал авторам все статьи, где использовались доказательства от противного. Брауэр называл свою философию "интуиционизмом"

в середине XX века математики, близкие к А.А.Маркову и А.Н.Колмогорову, развили свою версию философии интуиционизма под названием "конструктивизм"; как и интуиционисты, конструктивные математики отрицают классическую математику, точнее - все неявные доказательства существования. с точки зрения конструктивиста, любой математический объект должен быть задан явно. например, действительное число в конструктивной математике - это алгоритм его вычисления с любой точностью плюс оценка скорости сходимости этого алгоритма. исследования по теории рекурсивных функций, вдохновленные конструктивизмом, оказались очень полезны в теории алгоритмов и в лингвистике

CH (континуум-гипотеза)

множество A называется счетным, если оно равномощно ℤ. в этом случае |A| = ℵ₀

Тh Кантора: множество ℝ вещественных чисел - несчетно

множество A называется континуальным, если оно равномощно ℝ

континуум-гипотеза (CH) утверждает, что мощность континуума есть 2^ℵ₀ = ℵ₁

Тh: объединение конечного числа множеств мощности континуума имеет мощность континуума

Тh: произведение счетного числа множеств мощности континуума имеет мощность континуума

мощность множества всех подмножеств множества натуральных чисел ℕ обозначается через 2^ℵ₀

мощность множества всех подмножеств множества вещественных чисел ℝ обозначается через 2^2ℵ₀

в 1878 году Георг Кантор высказал следующую гипотезу: не существует мощности промежуточной между ℵ₀ и ℵ₁. иными словами, утверждается, что если ℵ₀ ≤ |X| ≤ ℵ₁ для некоторого множества X, то либо |X| = ℵ₀, либо |X| = ℵ₁. эта гипотеза и называется "гипотезой континуума" и обозначается CH

первым крупным прорывом в этом направлении был результат Курта Геделя 1940 года. он доказал, что если аксиоматика теории множеств непротиворечива, то она остается непротиворечивой и после добавления аксиомы выбора AC и гипотезы континуума CH

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

Кантор формулировал континуум-гипотезу в форме c = 2^ℵ₀ = ℵ₁. можно предположить, что всегда 2^ℵₙ = ℵₙ₊₁. это предположение известно под названием "обобщенной континуум-гипотезы" GCH

обобщенная континуум-гипотеза и аксиома выбора не являются независимыми. в 1947 году Вацлав Серпиньский доказал, что обобщенная гипотеза континуума влечет аксиому выбора

в 1964 году Р.Соловэй показал, что обобщенная континуум-гипотеза не вытекает из аксиомы выбора и континуум-гипотезы

AC, AR, CH

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

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

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

большинство математиков согласны с тем, что нет никаких априорных оснований занимать какую-либо позицию в вопросе о справедливости гипотезы континуума

Universes

Анри Пуанкаре поясняет сущность теории типов следующей иллюстрацией:

возьмем пример Эпименида
лжецом 1-го порядка будет тот, который лжет всегда, за исключением случая, когда он говорит : “я лжец 1-го порядка”
лжецом 2-го порядка будет тот, который лжет всегда, даже и тогда, когда говорит “я лжец 1-го порядка”, но который не лжет, говоря “я лжец 2-го порядка”, и т.д.
т.о., когда Эпименид скажет нам “я лжец”, мы можем его спросить, “какого порядка?” и только после того, как он ответит на этот вопрос, его утверждение будет иметь смысл

это то, что называют Универсумом

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

Def: множество U называется Универсумом, если оно удовлетворяет следующим условиям:

• U1:   ω ∈ U ,     где ω из ZF5
• U2:   A ∈ U ⇒ A ⊆ U
• U3:   A ∈ U ⇒ 2^A ∈ U
• U4:   A ∈ U ⇒ ∪A ∈ U
• U5:   ∀ f : A → U : A ∈ U ⇒ (f A) ∈ U

все обычные теоретико-множественные конструкции с элементами U могут быть реализованы уже внутри U

даже самый крошечный Универсум - чудовищно велик. в частности, он содержит в качестве элементов множество вещественных чисел ℝ и все его подмножества, множество всех подмножеств 2^ℝ и все его подмножества, множество 2^2ℝ и все его подмножества и т.д.

назовем множество A "малым", если A ∈ U, "большим", если A ⊆ U, но A ≠ U, и "экстраординарным", если A = U. теперь мы можем рассматривать малые множества как модели, а большие множества как классы, при этом сам U выступает в качестве класса всех множеств

один ученый однажды читал публичную лекцию по астрономии. он расказал как Земля вращается вокруг Солнца и как Солнце, в свою очередь, вращается вокруг центра нашей Галактики. в конце лекции крошечная старушка из задних рядов поднялась и сказала:
"Все, что вы нам тут расказывали - ерунда. Наша Земля на самом деле - плоская и поддерживается на панцире большой черепахи"
ученый улыбнулся и спросил:
"А на чем же держится черепаха?"
"Вы очень умны, молодой человек, очень умны" - ответила старушка - "но черепаха держится на другой черепахе - и так далее!"

Универсумы настолько велики, что существование хотя бы одного Универсума не может вытекать из аксиом Цермело-Френкеля и должно гарантироваться специальной аксиомой

Аксиома Гротендика

G: для каждого множества A существует такой Универсум U, что A ∈ U

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

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

G': (Слабая аксиома Гротендика): существует хотя бы один Универсум

Аксиома Выбора (axiom of choice, AC)

AC: для всякого семейства непустых множеств существует функция, которая каждому множеству семейства сопоставляет один из элементов этого множества

для конечных семейств множеств утверждение аксиомы выбора может быть доказано

существует множество эквивалентных формулировок аксиомы выбора:

• прямое произведение непустых множеств - не пусто
• каждая сюръективная функция f: A → B имеет правую обратную функцию f⁻: B → A, т.е. f ∙ f⁻ = id_B
• каждое множество может быть вполне упорядочено
• частично упорядоченное множество, в котором любая цепь имеет верхнюю грань, содержит максимальный элемент
• в любом частично упорядоченном множестве существует максимальное линейно-упорядоченное подмножество

прочтем формулировку: "в любом семействе F непустых множеств А в каждом A∈F можно выбрать по одному элементу". раз множества непустые, значит, хотя бы один-то элемент в каждом имеется - получается, что утверждение тривиально? но аксиома не об этом. она говорит о том, что "элемент можно выбрать". но ведь если он существует - значит, его можно и выбрать? тогда скажите - как. ну ... просто показать на него пальцем. хорошо. однако семейство - бесконечно, а значит и выбранные элементы должны составить бесконечное множество. но бесконечное множество нельзя задать непосредственным указанием на его элементы (как мы было вознамерились) - его можно задать только обобщенно. должна быть какая-то функция f(A), каждому множеству семейства ставящая в соответствие "выбранный элемент". аксиома утверждает, что такая функция выбора всегда существует. должно существовать некое свойство, которому удовлетворяет ровно один элемент в каждом из множеств А - но тогда утверждение совсем не очевидно. тем более что аксиома не отвечает ведь на вопрос, откуда взять такую функцию выбора - аксиома неконструктивна, как и все эквивалентные ей утверждения. аксиома устанавливает существование, не отвечая на вопрос: "где взять" или "как сделать"

каждому множеству семейства функция выбора сопоставляет не просто какой-то элемент из всех множеств гуртом, а элемент одного, именно данного множества. имеется понятие прямого (или декартова) произведения множеств. если даны множества А,В,С,…, то прямое произведение A⨯B⨯C⨯... - множество наборов элементов, по одному из каждого. например, прямое произведение трех осей декартовых координат (трех множеств чисел) - множество точек трехмерного пространства, где каждая точка характеризуется упорядоченной тройкой чисел, по одному от каждой из осей. функция выбора в сущности и выдает такой набор элементов: каждому входящему множеству соответствует один элемент из него же, а всем множествам семейства – упорядоченный набор. если теперь исключить выбранные элементы, то из оставшихся опять можно выбрать по одному элементу из каждого - и продолжать сколько угодно раз. возможность такого продолжения устанавливается эквивалентной формулировкой аксиомы выбора: "декартово произведение непустых множеств - непусто"

В 1948 году настал торжественный день. обычно кандидат в граждане и его поручители опрашивались отдельно, но для Эйнштейна сделали исключение, тем более что судья раньше приводил к присяге и его. Бледный от волнения Гёдель уселся между своими поручителями, и судья задал ему первый вопрос
- Откуда вы родом?
- Из Австрии
- А какое там государственное устройство?
- У нас была республика, но из-за несовершенной конституции там оказалось возможным установить диктатуру
- Какая трагедия! К счастью, здесь это невозможно
- Еще как возможно! Я могу это доказать!

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

а это он доказал? мне казалось, что Коэн

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

>>> доказательства непротиворечивости AC и CH
его, вообще-то, до сих пор нет

вас геделевское не устраивает? ну можно это пообсуждать

>>> так Гёдель доказывал несколько не то, что вы ему приписали

ну а что он доказал? именно, что если ZF-AC имееет модель (т.е. непротиворечива) то и ZF+AC имеет модель в той же системе. ну давайте не будем дальше углубляться в мелочи. по крайней мере если они несущественные, и я и вы их заведомо знаете

>>> именно, Гёдель доказал следующее - "если противоречива ZF+AC, то противоречива и ZF". импликация. вы же ему выше приписали доказательство безусловного тезиса о непротиворечивости ZF+AC. если таковое было уже у Гёделя - чем потом Есенин-Вольпин и Кузичев занимались?

ну я что - должен везде говорить "относительно непротиворечиво" - и указывать базу?

>>> принимая во внимание, что тут мы имеем дело с одним из стандартных мифов (по которым и проходит водораздел между грамотными людьми и начитавшимися научпопа обывателями) - разумеется должны!

вы думаете - от этого понятнее будет? тем более что в том же Шенфилде еще на полном серьезе обсуждается возможность нетривиальных категоричных систем. если там профи путались еще недавно - ну вот этими деталями-то зачем дилетантов грузить?

>>> это - как раз не детали! потому что при их опускании возникает совершенно превратное представление о вопросе

Аксиома Детерминированности (axiom of determinateness, AD)

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

в рамках системы аксиом ZFC (Цермело–Френкеля с аксиомой выбора AC) формулируются и доказываются все "содержательные" математические результаты (а следовательно, и результаты естественных наук, выразимые на языке математики). т.о., нет такой аксиомы, которая могла бы помочь в решении вопросов Лузина и при этом не изменила обычную "содержательную" математику, а являлась бы ее естественной частью. при этом неразрешимость вопросов Лузина не связана с тем, сколь большие множества разрешается использовать - она возникает на уровне уже одних только вещественных чисел

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

в классических разделах математики (матанализ) замена AC на AD ничего не меняет, но в теории множеств и топологии следствия из AD существенно отличаются от следствий AC

аксиома детерминированности совместима с ZF, однако с аксиомой выбора она не совместима - доказано, что с помощью аксиомы выбора можно построить недетерминированное множество, что прямо противоречит аксиоме детерминированности

с помощью аксиомы выбора можно доказать, что существуют множества вещественных чисел, неизмеримые по Лебегу; из аксиомы детерминированности следует, что таких множеств не существует: любое бесконечное несчётное множество вещественных чисел континуально

по-разному решается проблема континуума - аксиоматика ZF допускает любой из двух вариантов решения этой проблемы, но из аксиомы детерминированности выводится однозначное решение: любое бесконечное несчётное множество вещественных чисел - континуально

вполне упорядочить аксиома детерминированности разрешает лишь только конечные и счётные множества

AD :

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