Лемма Цорна: максимальный элемент, аксиома выбора и базис Гамеля

Лемма Цорна - рабочая форма аксиомы выбора, которой пользуются почти все «существование» в алгебре и функциональном анализе. Когда в учебнике пишут «существует базис», «существует максимальный идеал», «продолжим линейный функционал», за этой фразой обычно стоит ровно одна и та же конструкция: берём частично упорядоченное множество подходящих объектов, проверяем, что у каждой цепи есть верхняя грань, и по лемме Цорна получаем максимальный элемент. Имя - за Максом Цорном, опубликовавшим лемму в 1935 году; до него эквивалентный принцип формулировали Хаусдорф и Куратовский, а исходный материал - аксиома выбора Цермело (1904) и его же теорема о вполне упорядоченности.

Формулировка

Лемма Цорна. Пусть $(P, \leq)$ - непустое частично упорядоченное множество, в котором всякая цепь имеет верхнюю грань в $P$. Тогда в $P$ существует максимальный элемент.

Разберём терминологию подряд, потому что половина ошибок - на ней.

Частичный порядок $\leq$ на множестве $P$ - это рефлексивное ($x \leq x$), антисимметричное ($x \leq y$ и $y \leq x \Rightarrow x = y$) и транзитивное ($x \leq y \leq z \Rightarrow x \leq z$) бинарное отношение. «Частичный» означает, что для пары $x, y$ может не выполняться ни $x \leq y$, ни $y \leq x$ - элементы несравнимы.

Цепь $C \subseteq P$ - линейно упорядоченное подмножество: для любых $x, y \in C$ либо $x \leq y$, либо $y \leq x$. Пустое множество тоже считается цепью.

Верхняя грань цепи $C$ - элемент $u \in P$ такой, что $x \leq u$ для всех $x \in C$. Лемма требует, чтобы такой $u$ нашёлся для каждой цепи, включая пустую (тогда верхней гранью служит любой элемент $P$ - это и есть способ сказать «$P$ непусто»).

Максимальный элемент $m \in P$ - такой, что в $P$ нет элементов строго больше: если $m \leq x$, то $x = m$. Это не то же самое, что наибольший: наибольший элемент сравним со всеми, а максимальный - только не имеет ничего строго над собой. В частично упорядоченном множестве может быть несколько максимальных элементов и ни одного наибольшего.

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

Максимальный не значит наибольший

Это ловушка номер один. Возьмём $P = \{a, b, c\}$ с отношениями $a \leq c$ и $b \leq c$ (и тривиальные $x \leq x$). Тогда $c$ - и максимальный, и наибольший: он больше всех.

Изменим пример: $P = \{a, b\}$ без сравнения между ними (только $a \leq a$, $b \leq b$). И $a$, и $b$ - максимальные элементы (над ними ничего нет), но наибольшего элемента не существует, потому что ни один из них не сравним с другим.

В терминах диаграмм Хассе: максимальные элементы - это «вершины» диаграммы, у которых нет рёбер вверх. Наибольший - единственная такая вершина, и она доминирует над всеми остальными.

Лемма Цорна гарантирует именно максимальный, не наибольший. Этого обычно ровно столько, сколько нужно: «дальше нельзя расширить» - типичное содержание теорем существования.

Эквивалентность с аксиомой выбора

Над аксиоматикой Цермело-Френкеля без аксиомы выбора три утверждения попарно эквивалентны:

1. Аксиома выбора (AC). Для любого семейства непустых множеств $\{A_i\}_{i \in I}$ существует функция выбора $f \colon I \to \bigcup_i A_i$ такая, что $f(i) \in A_i$ для всех $i$.
2. Теорема Цермело о вполне упорядоченности (WO). Всякое множество можно вполне упорядочить (то есть задать линейный порядок, в котором каждое непустое подмножество имеет минимум).
3. Лемма Цорна (ZL). Всякое частично упорядоченное множество, в котором каждая цепь имеет верхнюю грань, содержит максимальный элемент.

Кольцевое доказательство $\text{AC} \Rightarrow \text{ZL} \Rightarrow \text{WO} \Rightarrow \text{AC}$ - стандартный материал учебника по теории множеств. Идея $\text{AC} \Rightarrow \text{ZL}$: предположим в $P$ нет максимального элемента; тогда для каждого $x \in P$ множество строго больших элементов непусто, по AC выбираем стрелку $s(x) > x$, строим возрастающую трансфинитную последовательность, упираемся в противоречие с условием на цепи.

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

Конструктивная картинка

Доказывать лемму Цорна формально нудно (трансфинитная индукция), но «мысленный лифт» работает так:

1. Берём любой элемент $x_0 \in P$. Если над ним ничего нет - это максимальный, готово.
2. Иначе выбираем $x_1 > x_0$. Если над $x_1$ ничего нет - готово.
3. Продолжаем: $x_0 < x_1 < x_2 < \dots$ - растущая цепь.
4. У цепи $\{x_n\}$ по условию есть верхняя грань $u_\omega$. Если над $u_\omega$ ничего нет - готово.
5. Иначе берём $x_{\omega+1} > u_\omega$ и продолжаем трансфинитно.

Поскольку $P$ - множество (а не собственный класс), этот процесс не может длиться «бесконечно долго в смысле ординалов» - иначе мы получили бы инъекцию ординалов в $P$, что превышает мощность $P$. Значит, на каком-то шаге процесс остановится, и точка остановки - максимальный элемент.

Аксиома выбора нужна именно для шагов 2 и 5: «выбираем $x_{\alpha+1} >$ текущей верхней грани» - это функция выбора на семействе непустых множеств «всё, что строго больше».

Применение 1: базис Гамеля

Теорема. Всякое векторное пространство $V$ над полем $K$ имеет базис.

Для конечномерных $V$ это известно из линейной алгебры. Для бесконечномерных (например, $\mathbb{R}$ как $\mathbb{Q}$-векторное пространство) утверждение нетривиально - конкретный базис (базис Гамеля) описать формулой нельзя, его существование чисто теоретическое.

Доказательство через лемму Цорна:

• $P = \{S \subseteq V : S \text{ линейно независимо}\}$, отношение - включение $S_1 \subseteq S_2$.
• Цепь $\{S_i\}$ имеет верхнюю грань $\bigcup_i S_i$: объединение линейно независимых вложенных подмножеств линейно независимо (любая конечная подсумма зависимости сидит в одном из $S_i$).
• $P$ непусто: пустое множество линейно независимо.
• По лемме Цорна существует максимальный $B \in P$. Покажем, что $B$ - базис: если $v \notin \mathrm{span}(B)$, то $B \cup \{v\}$ линейно независимо и строго больше - противоречит максимальности. Значит, $\mathrm{span}(B) = V$.

То же доказательство даёт существование базиса в произвольном модуле над полем - и эквивалентно аксиоме выбора (Блаас, 1984). Совсем иначе устроена теорема Гильберта о базисе: она про конечную порождённость идеалов в кольце многочленов над нётеровым кольцом - конструктивный результат, лемма Цорна там не нужна.

Применение 2: максимальный идеал в кольце с единицей

Теорема. Всякое ненулевое коммутативное кольцо $R$ с единицей содержит максимальный идеал.

Доказательство:

• $P = \{I \subset R : I \text{ собственный идеал}\}$, отношение - включение.
• Цепь $\{I_\alpha\}$ имеет верхнюю грань $J = \bigcup_\alpha I_\alpha$: это снова идеал (для любых $x, y \in J$ оба сидят в каком-то $I_\alpha$, значит $x + y \in I_\alpha \subseteq J$; так же для умножения на элементы $R$). Условие собственности: $1 \notin J$, потому что $1 \notin I_\alpha$ ни для какого $\alpha$.
• $P$ непусто: нулевой идеал $\{0\}$ - собственный, раз $R$ ненулевое.
• По лемме Цорна - максимальный собственный идеал.

Это краеугольное утверждение коммутативной алгебры: фактор $R/\mathfrak{m}$ по максимальному идеалу - поле, спектр кольца $\mathrm{Spec}\, R$ имеет максимальные точки, нильрадикал равен пересечению всех простых идеалов и т. д.

Применение 3: теорема Хана-Банаха

Теорема (Хан-Банах). Пусть $X$ - вещественное векторное пространство, $p \colon X \to \mathbb{R}$ - сублинейный функционал ($p(x+y) \leq p(x) + p(y)$, $p(\lambda x) = \lambda p(x)$ при $\lambda \geq 0$), $Y \subseteq X$ - подпространство, $f \colon Y \to \mathbb{R}$ - линейный функционал с $f \leq p$ на $Y$. Тогда $f$ продолжается до линейного $F \colon X \to \mathbb{R}$ с $F \leq p$ на всём $X$.

Доказательство - цорновская конструкция на множестве частичных продолжений:

• $P = \{(Z, g) : Y \subseteq Z \subseteq X, g \colon Z \to \mathbb{R} \text{ линейный}, g|_Y = f, g \leq p\text{ на } Z\}$.
• $(Z_1, g_1) \leq (Z_2, g_2)$, если $Z_1 \subseteq Z_2$ и $g_2|_{Z_1} = g_1$.
• Цепь имеет верхнюю грань - объединение области определения и согласованное склеивание функционалов.
• Максимальный $(Z_*, g_*)$ обязательно имеет $Z_* = X$: иначе берём $x_0 \in X \setminus Z_*$, расширяем на $Z_* + \mathbb{R} x_0$ с подходящей константой (это отдельная лемма - выбор значения $g_*(x_0)$ внутри отрезка, заданного $p$), получаем строго большее продолжение, противоречие.

Хан-Банах - фундамент теории двойственности в функциональном анализе; без него не было бы теоремы об отделимости, рефлексивности банаховых пространств, слабых топологий.

Применение 4: лемма Тейхмюллера-Тьюки

Свойство конечного характера семейства $\mathcal{F}$ подмножеств $X$: $S \in \mathcal{F}$ тогда и только тогда, когда каждое конечное подмножество $S$ лежит в $\mathcal{F}$.

Лемма (Тейхмюллера-Тьюки). Всякое семейство конечного характера содержит максимальный (по включению) элемент.

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

Частые ошибки

• Путают максимальный и наибольший. Лемма Цорна даёт только максимальный - элемент без ничего строго над собой. Наибольший (сравним со всеми) - более сильное условие, в общем случае не гарантируется. В $\{a, b\}$ с несравнимыми $a$ и $b$ оба максимальны, но наибольшего нет.
• Забывают условие «всякая цепь». Условие - на каждую цепь, включая пустую. Часто проверяют на нетривиальных цепях и упускают, что само $P$ должно быть непусто (формально - пустая цепь требует верхней грани, что эквивалентно $P \neq \varnothing$).
• Проверяют верхнюю грань только для счётных цепей. Цепь может быть несчётной (например, континуум вложенных подпространств). Объединение по цепи - общий приём, но надо проверить, что объединение лежит в $P$ (для идеалов - что не выходит за рамки собственных).
• Применяют лемму Цорна к классам, а не к множествам. Лемма работает только для множеств. Для собственных классов (например, «все кольца») нужны другие средства (трансфинитная индукция с осторожностью или другие принципы).
• Считают, что лемма даёт конструктивный максимум. Нет, лемма - чистое существование. Конкретный базис Гамеля прямой формулой выписать нельзя; конкретный максимальный идеал в кольце $C([0,1])$ непрерывных функций - тоже (за пределами идеалов вида $\{f : f(x_0) = 0\}$, в которых тоже не обходится без AC для произвольной точки).

FAQ

Чем лемма Цорна отличается от принципа максимальности Хаусдорфа? Принцип Хаусдорфа: в любом частично упорядоченном множестве существует максимальная цепь (то есть цепь, которую нельзя расширить до большей цепи). Это эквивалентно лемме Цорна над ZF: из Хаусдорфа Цорн получается так - берём максимальную цепь, у неё по условию есть верхняя грань, она и оказывается максимальным элементом. Обратно - стандартная конструкция через лемму Цорна для частично упорядоченного множества цепей.

Можно ли без леммы Цорна доказать существование базиса в $V$? Для конкретных $V$ - иногда да, явной конструкцией (для $\mathbb{R}^n$ - стандартный базис, для пространства многочленов - $\{1, x, x^2, \dots\}$). Для произвольного бесконечномерного $V$ - нет: «всякое векторное пространство имеет базис» эквивалентно аксиоме выбора (Блаас, 1984). Значит, в моделях ZF без AC существуют пространства без базиса, и лемма Цорна тут неизбежна.

Что значит «применить лемму Цорна» на практике? Канонический рецепт: (1) определить $P$ - множество «частичных» объектов нужного типа с порядком включения или продолжения; (2) показать, что $P$ непусто; (3) проверить, что объединение любой цепи в $P$ снова в $P$ (это и даёт верхнюю грань); (4) сослаться на лемму Цорна и получить максимальный элемент $m$; (5) доказать, что максимальность $m$ влечёт нужное свойство (полнота базиса, идеала, продолжения и т. д.). Шаг (3) обычно требует «локальной» аккуратности: проверить, что нужное свойство сохраняется при объединении.

Коротко

Лемма Цорна: в непустом частично упорядоченном множестве $(P, \leq)$, где у каждой цепи есть верхняя грань в $P$, существует максимальный элемент. Эквивалентна аксиоме выбора и теореме Цермело о вполне упорядоченности. Канонические применения - существование базиса Гамеля в произвольном векторном пространстве, максимального идеала в ненулевом кольце с единицей, продолжение в теореме Хана-Банаха, существование максимального семейства в принципе Тейхмюллера-Тьюки. Главная ловушка - путать максимальный (нет ничего строго над) и наибольший (сравним со всеми): лемма даёт первое, не второе.