Dangerous Knowledge - Аксиома выбора. Часть V (Russian)

Dailymotion. Видео. Часть I
Dailymotion. Видео. Часть II
Dailymotion. Видео. Часть III
Dailymotion. Видео. Часть IV
Dailymotion. Видео. Часть V

Этот пост я должен был довести до ума давно. Все части:
Dangerous Knowledge
Dangerous Knowledge - Бесконечное множество и интуиция.Часть I
Dangerous Knowledge - Парадокс брадобрея. Часть II
Dangerous Knowledge - Диагональный метод доказательства Кантора. Часть III
Dangerous Knowledge - Континуум-гипотеза. Часть IV
Dangerous Knowledge - Аксиома выбора. Часть V
Dangerous Knowledge - Теория меры. Часть VI
Dangerous Knowledge - Тест Тьюринга. Часть VII


Прикоснуться к бесконечности


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

Как я уже говорил, есть некоторые вещи, которые явно не раскрыты в этой доке. Здесь, я кратко расскажу об аксиоме выбора.

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

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

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


Пример 1. Пусть $X=\{1,2\}, Y=\{3,4\}, Z=\{5,6\}$. $A=X \cup Y \cup Z$. Очевидно, что множества X, Y, Z непустые, также легко видеть что они непересекающиеся. Аксиома выбора утверждает, что существует некоторое множество B, такое что $B \cap X = \{x\}$, $B \cap Y = \{y\}$, $B \cap Z = \{z\}$ и $x \neq y \neq z$ при чём $x \in X$, $y \in Y$, $z \in Z$. К примеру, множество $B=\{2,3,5\}$ удовлетворяет всем требованием.

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

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

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

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



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

То же определение можно сформулировать более сжато:

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

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

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

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

Как было показано выше если X конечно, это функция выбора существует и без аксиомы выбора. Пример 2 показывает, что не всегда эта аксиома требуется и для бесконечных множеств.

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

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

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

Оказывается, что для бесконечных семейств аксиома выбора является утверждением теории множеств, независимым от остальных аксиом этой теории (её статус в определённом смысле "такой же" как и континуум-гипотезы, отличие в том, что континуум-гипотеза независима от системы аксиом Цермело — Френкеля с аксиомой выбора,
а аксиома выбора независима от системы аксиом Цермело — Френкеля).

Определения.

Линейным порядком на множестве A частично упорядоченное множеством A называется отношение $R\subseteq A\times A$, обладающее следующим свойствами:
* Полное: $\forall x,\;y\in A\;((x,\;y)\in R\lor(y,\;x)\in R)$.
* Антисимметричное: $\forall x,\;y\in A\;((x,\;y)\in R\wedge(y,\;x)\in R\to y=x)$.
* Транзитивное: $\forall x,\;y,\;z\in A\;((x,\;y)\in R\wedge(y,\;z)\in R\to(x,\;z)\in R)$.

Линейно упорядоченное множество или цепь ― частично упорядоченное множество (полное, антисимметричное, транзитивное отношение $R\subseteq A\times A$), в котором для любых двух элементов a и b имеет место $a\leqslant b$ или $b\leqslant a$. Верхней гранью называется такой элемент $u\in R$, что $\forall x\in R\;x\leqslant u$.

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

Максимальный элементом множества A является такой элемент $\exists m\in A\;\nexists x\in A\;x>m$.


Теорема Цермело (принцип вполне упорядочивания)
Любое множество может быть вполне упорядочено.

Принцип полного порядка (теорема Цермелло) заключается в том, что любое множество может быть вполне упорядочено, т.е. на любом множестве может быть введёно полное, антисимметричное, транзитивное отношение $R\subseteq A\times A$ в котором каждое подмножество $X\subseteq A$ имеет наименьший элемент.

Доказательства эквивалентности теорема Цермелло аксимоы выбора есть тут..

Пример 3. Множество натуральных чисел может быть вполне упорядоченно
обычным отношением «меньше или равно чем». С тем же отношением множество целых чисел не имеет наименьшего элемента. В этом случае мы можем собрать целые числа в последовательность $(0,\;-1,\;1,\;-2,\;2,\;\ldots,\;-n,\;n,\;\ldots)$ и сказать, что младшие члены меньше, чем старшие. Очевидно, такое отношение будет полным порядком на целых числах.

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

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


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

Лемма Цорна, наряду с теоремой Цермело (принцип вполнеупорядочивания) и принципом максимума Хаусдорфа (который, по сути, является альтернативной формулировкой леммы Цорна), является одним из утверждений, эквивалентных аксиоме выбора.

Во многих задачах лемма Цорна является наиболее удобной из всех формулировок, эквивалентных аксиоме выбора.

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

Пусть $V$ — линейное пространство над полем $\mathfrak{R}$.

Свойство:
Базис есть максимальная (по включению) линейно независимая система векторов.
Замечания:
Вектор 0 не входит ни в одну в систему линейно независимой системе векторов.

Для доказательства существования рассмотрим два случая.

I. Линейное пространство V конечномерное, т.е. любая линейно независимая система состоит из $\leqslant n$ векторов. Применим принцип математической индукции.
Если n=1, то тогда $V=\mathfrak{R}$, а значит в качестве базиса Гомеля достаточно выбрать $B=\{\mathbf{1}\}$, а $1 \neq 0$, 1,0- единичные элемента поля $\mathfrak{R}$.

Допустим, что для всех линейный пространств с линейно независимой системой, состоящей из $\leqslant n$ векторов существует базис Гомеля, т.е. линейно независимая система $\{\mathbf{v_1},\;\ldots,\;\mathbf{v_n}\}$, в которой для всех $1<=i<=n v_i \neq 0$. Докажем, что базис Гомеля существует в линейном пространстве, состоящем из $\leqslant {n+1}$ линейно независимой системой векторов. Если у нас есть $\leqslant {n+1}$ линейно независимая система векторов, то значит у нас, в частности, есть и $\leqslant {n}$ линейно независимых векторов, таких что $\{\mathbf{v_1},\;\ldots,\;\mathbf{v_n}\}$, в которой для всех $1<=i<=n v_i \neq 0$. Это систему можно расширить путем добавления вектора $\mathbf{v_{n+1}} \neq 0$, таким что что система $\{\mathbf{v_1},\;\ldots,\;\mathbf{v_{n+1}}\}$ линейно независима. Тогда согласно принципу математической индукции утверждение доказано.

II. Линейное пространство V бесконечномерно.
Аналогично рассуждениям в пункте I мы можем построить цепь линейно независимых систем $B_1\subseteq B_2\subseteq\ldots$ следующим образом.

$B_1=\{\mathbf{v_1}\}$, состоящей из ненулевого вектора $\mathbf{v_1}\neq\mathbf{0}$. Далее, на каждом шаге мы присоединением вектор $\mathbf{v_{n+1}}$ к $B_n=\{\mathbf{v_1},\;\ldots,\;\mathbf{v_n}\}$, таким образом, что система $B_{n+1}=\{\mathbf{v_1},\;\ldots,\;\mathbf{v_n},\mathbf{v_{n+1}\}$ линейно независима (такой вектор существует, так как V бесконечномерно).

Получили $B_1\subseteq B_2\subseteq\ldots$ — цепь линейно независимых систем. Рассмотрим элемент $\bigcup B_k$. Легко доказать. что это объединение является также линейно независимой системой. Также, легко видеть, что для всех i $B_i$ меньше или равно (по включению), чем $\bigcup B_k$ (по построению объединения), т.е. $\bigcup B_k$ является верхней гранью по отношению к любой цепи частично упорядоченной через отношение включения. Тогда, согласно лемме Цорна, существует максимальный элемент, который и будет базисом Гомеля.

Что и требовалось доказать.

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

Трансфинитная индукция — метод доказательства, обобщающий математическую индукцию на случай несчётного числа значений параметра.

Трансфинитная индукция основана на следующем утверждении:

Пусть $M$ — вполне упорядоченное множество, $P(x)$ при $x\in M$ — некоторое утверждение. Пусть для любого $x\in M$ из того, что $P(y)$ истинно для всех $y<x$ следует, что верно $P(x)$. Тогда утверждение $P(x)$ верно для любого $x$.


Математическая индукция является частным случаем трансфинитной индукции. Действительно, пусть $M$ — множество натуральных чисел. Тогда утверждение трансфинитной индукции превращается в следующее: если для любого натурального $n$ из одновременной истинности утверждений $P(1)$, $P(2)$, $\ldots$, $P(n)$ следует истинность утверждения $P(n+1)$, то истинны все утверждения $P(n)$ для всех $n$. При этом база индукции, то есть $P(1)$, оказывается тривиальным частным случаем при $n=1$.

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

В заметке использованы метериалы Википедии.