Твердження, еквівалентні аксіомі вибору

У статті розглядаються різні формулювання і доводиться еквівалентність таких тверджень:

Еквівалентність цих тверджень слід розуміти в тому сенсі, що будь-якого з них, разом із системою аксіом Цермело — Френкеля (ZF), достатньо, щоб довести інші.

Лема Цорна і принцип максимуму Гаусдорфа

Формулювання леми Цорна.

${𝒵 ℒ}_{1} .$ Частково впорядкована множина, в якій будь-який ланцюг має верхню грань, містить максимальний елемент.

${𝒵 ℒ}_{2} .$ Якщо будь-який ланцюг у частково впорядкованій множині $M$ має верхню грань, то будь-який елемент із $M$ підпорядкований деякому максимальному.

${𝒵 ℒ}_{3} .$ Нехай сімейство множин $𝔐$ володіє тією властивістю, що об'єднання будь-якого ланцюга множин з $𝔐$ є знову множиною цього сімейства. Тоді $𝔐$ містить максимальну множину.

Формулювання принципу максимуму Гаусдорфа (Шаблон:Lang-en):

${ℋ ℳ}_{1} .$ У будь-якій частково впорядкованій множині існує максимальна лінійно впорядкована підмножина.

${ℋ ℳ}_{2} .$ У частково впорядкованій множині кожен ланцюг міститься в деякому її максимальному ланцюгу.

Еквівалентність цих пропозицій доводитимемо за такою схемою:

{𝒵 ℒ}_{1} \overset{(I)}{\Leftrightarrow} {𝒵 ℒ}_{2} \overset{(I I)}{\Rightarrow} {𝒵 ℒ}_{3} \overset{(I I I)}{\Rightarrow} {ℋ ℳ}_{2} \overset{(I V)}{\Rightarrow} {ℋ ℳ}_{1} \overset{(V)}{\Rightarrow} {𝒵 ℒ}_{1}

I . {𝒵 ℒ}_{1} \Leftrightarrow {𝒵 ℒ}_{2}

Ясно, що ${𝒵 ℒ}_{1}$ випливає із ${𝒵 ℒ}_{2}$ , оскільки в ${𝒵 ℒ}_{2}$ стверджується більше: існує максимальний елемент, більший від заданого $a$ . І навпаки, нехай $M$ — частково впорядкована множина, в якій будь-який ланцюг має верхню грань, і нехай $a \in M$ . Застосуємо ${𝒵 ℒ}_{1}$ до множини $M^{'} = {m \in M ∣ m ⩾ a}$ . Її максимальний елемент $\overline{a}$ також є і максимальним елементом $M$ , і, крім того, задовольняє умові $a ⩽ \overline{a}$ .

I I . {𝒵 ℒ}_{2} \Rightarrow {𝒵 ℒ}_{3}

Сімейство множин $𝔐$ частково впорядковане за теоретико-множинним відношенням включення $\subseteq$ . Будь-який ланцюг множин ${M_{α}}$ має верхню грань — це множина $⋃ M_{α}$ , яка, за припущенням, належить системі $𝔐$ . У силу ${𝒵 ℒ}_{2}$ в сімействі є максимальний елемент, тобто максимальна за включенням множина.

I I I . {𝒵 ℒ}_{3} \Rightarrow {ℋ ℳ}_{2}

Нехай $M$ — частково впорядкована множина, $C_{0}$ — ланцюг у $M$ , $𝔐$ — множина всіх ланцюгів у $M$ , що містять $C_{0}$ , упорядкованих відносно включення. Існування максимального ланцюга, що містить $C_{0}$ , тепер випливає із ${𝒵 ℒ}_{3}$ , стосовно до $𝔐$ , і того факту, що об'єднання всіх множин ланцюга в $𝔐$ («ланцюги ланцюгів»), знову є множиною з $𝔐$ .

I V . {ℋ ℳ}_{2} \Rightarrow {ℋ ℳ}_{1}

Очевидно. ${ℋ ℳ}_{1}$ — окремий випадок ${ℋ ℳ}_{2}$ , коли початковий ланцюг — порожня множина $\emptyset$ .

V . {ℋ ℳ}_{1} \Rightarrow {𝒵 ℒ}_{1}

Нехай $M$ — частково впорядкована множина в умові ${𝒵 ℒ}_{1}$ . Розглянемо максимальний ланцюг $C$ в $M$ , існування якого випливає з ${ℋ ℳ}_{1}$ . За умовою цей ланцюг має верхню грань $\overline{a}$ . Тоді $\overline{a}$ є максимальним елементом $M$ , і крім того, належить ланцюгу. Припустивши протилежне, ми прийдемо до суперечності з умовою максимальності $C$ .

Ці міркування доводять еквівалентність принципу максимуму Гаусдорфа і леми Цорна.

Теорема Цермело

Шаблон:Докладніше Формулювання теореми Цермело (Шаблон:Lang-en)

$𝒲 𝒪 .$ Будь-яку множину можна цілком упорядкувати.

{𝒵 ℒ}_{1} \Rightarrow 𝒲 𝒪

Нехай $M$ — довільна дана множина. Покажемо, що її можна цілком упорядкувати.

Розглянемо сукупність $𝔐$ усіх пар $⟨ A, ⩽_{A} ⟩$ , де $A \subseteq M$ , а $⩽_{A}$ — відношення повного порядку на $A$ . На множині $𝔐$ уведемо природне відношення порядку: $⟨ B, ⩽_{B} ⟩$ слідує за $⟨ A, ⩽_{A} ⟩$ , якщо $⟨ A, ⩽_{A} ⟩$ є початковий відрізок $⟨ B, ⩽_{B} ⟩$ , тобто якщо $A = {a \in B : a < b}$ для деякого $b \in B$ і на множині $A$ відношення $⩽_{B}$ збігається з $⩽_{A}$ .

Далі доведемо два твердження.

I. В $𝔐$ існує максимальний елемент. Це випливає із ${𝒵 ℒ}_{1}$ і того факту, що якщо $ℭ$ — ланцюг у $𝔐$ , то об'єднання всіх елементів $C \in ℭ$ є також елементом $𝔐$ , який є верхньою гранню ланцюга $ℭ$ .

II. Якщо $⟨ A, ⩽_{A} ⟩$ — максимальний елемент, то $A = M$ . Якби $M ∖ A$ була непорожньою, то взявши який-небудь елемент $b \in M ∖ A$ , і поклавши $b > a$ для будь-якого $a \in A$ , ми отримали б цілком упорядковану множину $A \cup {a}$ , початковим відрізком якої є $A$ . Це суперечить припущенню про максимальність $⟨ A, ⩽_{A} ⟩$ .

Таким чином, ми маємо цілком упорядковану множину $⟨ M, ⩽_{M} ⟩$ . Що й потрібно було довести.

𝒲 𝒪 \Rightarrow {ℋ ℳ}_{1}

Нехай $⟨ M, ⪯ ⟩$ частково впорядкована множина. В силу теореми Цермело множину $M$ можна цілком упорядкувати. Нехай $⩽$ — відношення цілкомупорядкування на $M$ .

Визначимо розбиття множини $M$ на дві підмножини $C$ і $\overline{C}$ індукцією за цілком упорядкованою множиною $⟨ M, ⩽ ⟩$ (такий спосіб також називають трансфінітною рекурсією).

Нехай $a \in M$ і всі елементи $b < a$ вже віднесено або до $C$ , або до $\overline{C}$ . Віднести $a$ до $C$ , якщо він порівняємо з усіма елементами $C$ ; в іншому випадку віднесемо його до $\overline{C}$ .

Проводячи таким чином індуктивну побудову за цілком впорядкованою множиною $⟨ M, ⩽ ⟩$ ми отримаємо множини $C$ і $\overline{C}$ . Як видно з побудови $C$ — ланцюг в $⟨ M, ⪯ ⟩$ . Крім того, ясно, що він є максимальним. Таким чином, ми довели принцип максимуму Гаусдорфа.

Аксіома вибору

Шаблон:Докладніше Формулювання аксіоми вибору:

$𝒜 𝒞 .$ Для кожного сімейства непорожніх множин ${S_{α}}, α \in A$ існує функція вибору $f$ , тобто $\forall α f (α) \in S_{α}$

Достатньо довести еквівалентність $𝒜 𝒞$ одному з тверджень $𝒵 ℒ, ℋ ℳ, 𝒲 𝒪$ . Однак нижче наведено декілька доведень.

$𝒜 𝒞 \Rightarrow 𝒲 𝒪$

Див. книгу Гаусдорфа, або Куроша.

$𝒜 𝒞 \Rightarrow ℋ ℳ$

Міркування аналогічне тому, що використовувалося для доведення $𝒜 𝒞 \Rightarrow 𝒲 𝒪$ .

Упорядкуємо кожне ${S_{α}}$ , і потім визначимо функцію вибору як мінімальний елемент множини:

f (α) = \min S_{α}

$𝒵 ℒ \Rightarrow 𝒜 𝒞$

Див. книгу Куроша.

Джерела

Твердження, еквівалентні аксіомі вибору

Зміст

Лема Цорна і принцип максимуму Гаусдорфа

Теорема Цермело

Аксіома вибору

Джерела

Навігаційне меню

Твердження, еквівалентні аксіомі вибору

Лема Цорна і принцип максимуму Гаусдорфа

Теорема Цермело

Аксіома вибору

Джерела

Навігаційне меню

Пошук