Глава 4. Вполне-упорядоченность как процесс над разрешимым

Где стоит глава

Глава 3 откатила одну «стену» — детерминированность. Та же техника применима ко второй: к минимально-плохой последовательности, двигателю теоремы Крускала о вложении деревьев.

Напомним классическую конструкцию Нэша–Уильямса. Чтобы доказать, что некоторое квази-упорядочение есть вполне-квази-упорядочение (wqo) — то есть что во всякой бесконечной последовательности найдётся «хорошая пара» $i<j$ с $f(i)⪯f(j)$, — предполагают противное (есть «плохая» последовательность без хороших пар) и строят минимальную плохую последовательность, выбирая на каждом шаге наименьшее плохое продолжение. Этот выбор — зависимый, и за него классике нужна аксиома Зависимого Выбора, тянущаяся по завершённой башне; полная теорема Крускала имеет реальную теоретико-доказательную силу. Снова «стена».

{ Тезис главы — тот же откат: над разрешимым пространством и сама вполне-упорядоченность, и её метод суть аксиомо-свободные процессы.}

Над разрешимым выбор минимально-плохой последовательности — не аксиома, а детерминированный процесс наименьшего-преемника; а сама wqo $N$ — фундированный спуск, уже-процесс.

Что глава фиксирует и что нет

{ Доказано точно и без аксиом: над ℕ плохой последовательности не существует; всякая структура с монотонной ℕ-мерой, отражающей порядок, есть wqo; а выбор минимально-плохой над разрешимым порядком есть детерминированный процесс наименьшего-преемника, без Зависимого Выбора¹.}

{ Не доказано здесь (горизонт): полная теорема Крускала для произвольных деревьев — она требует леммы Хигмана над произвольными wqo-алфавитами и общей минимально-плохой последовательности по структуре дерева, и имеет реальную теоретико-доказательную силу. Закрыта разрешимая, ℕ-измеримая подчасть (включая деревья ограниченной глубины через число потомков); общий случай остаётся горизонтом-подъёмом, градуированным тем, насколько пространство разрешимо. Сам приём наименьшего-преемника стандартен; наш вклад — упаковать «wqo и её метод как процесс над разрешимым» и точно локализовать фронтир.}

Базовый рунг: над $N${N} плохой последовательности нет

Самый чистый случай — $N$ с обычным порядком. Здесь вполне-упорядоченность не нуждается ни в каком выборе и ни в какой башне: она есть фундированность.

Допустим, последовательность $f:N\to N$ «плохая» — ни одной хорошей пары, то есть для всех $i<j$ верно $f(i)>f(j)$. Тогда $f$ строго убывает: $f(0)>f(1)>\cdots$. Но строго убывающий процесс на $N$ обязан завершиться — спуститься ниже нуля он не может. Значит плохой последовательности нет².

«Минимально-плохая последовательность невозможна над $N$» — это не обращение к завершённой башне, а завершающийся спуск: тот самый P4-процесс.

То, что классике видится как тонкая теоретико-множественная теорема, на базовом рунге есть просто отсутствие бесконечного спуска — сторона Элемента границы финитизации.

Замыкание: $N${N}-мера даёт wqo как процесс

От базового рунга поднимаемся выше — но как процесс, не как объект. Достаточно измеримости в $N$: если у структуры есть монотонная мера $h$ со значениями в $N$, отражающая порядок (из $h(a)\le h(b)$ следует $a⪯b$), то она автоматически вполне-упорядочена. Хорошая пара находится тем же спуском $N$: применяем вполне-упорядоченность $N$ к измеренной последовательности $h\circ f$ и переносим пару обратно³.

Это ровно приём, которым в основаниях получается wqo для деревьев ограниченной глубины: их мерой служит число потомков, и спуск $N$ делает остальное. Разрешимая, $N$-измеримая часть «высокой» теоремы достигнута — и достигнута как процесс, а не как завершённый объект.

Метод: минимально-плохой выбор — процесс над разрешимым

Осталось главное — сам метод Нэша–Уильямса, тот самый зависимый выбор, за который классике нужна аксиома. Покажем, что над разрешимым порядком он есть процесс.

Пусть на каждом шаге допустимое продолжение определяется разрешимым условием и хотя бы одно продолжение всегда есть. Тогда определён детерминированный шаг: взять наименьшее допустимое продолжение. Его траектория есть искомая цепь — и она построена без Зависимого Выбора: правило «наименьший допустимый» делает каждый шаг однозначным, цепь каноничной и единственной⁴.

Выбор, за который классике нужна аксиома, над разрешимым порядком не выбор, а правило: «наименьший допустимый преемник». Цепь одна, и она процесс.

Граница честна: урони разрешимость или свидетельствуемость продолжений — и шаг перестаёт быть однозначным, и тогда нужен подлинный Зависимый Выбор (или Закон Исключённого Третьего). Над разрешимым — сторона Элемента; над неразрешимым — предел-роль. Та же граница финитизации, проходящая теперь через метод.

E/R/R-разбор: wqo-подъём как система

Разбор по E/R/R в порождающем порядке Rules $\to$ Roles $\to$ Elements.

Rules (L5). Удерживающее правило — фундированный спуск: на $N$ строго убывающий процесс завершается, поэтому плохой последовательности нет. К нему примыкает правило переноса (монотонная $N$-мера переносит wqo на измеримую структуру) и правило выбора-как-шага (наименьший допустимый преемник над разрешимым порядком — вместо Зависимого Выбора).

Roles (L4). Хорошая пара играет роль свидетеля wqo. Наименьший-преемник — роль, назначаемая правилом, а не свободным выбором. $N$-мера — роль спины рунга, по которой идёт спуск.

Elements (L1 + P4). Носители — члены последовательности $f:N\to (\cdots )$ и значения меры в $N$. Под P4 актуальны конечные участки спуска; хорошая пара — конечно-актуальный свидетель, а не предел готовой башни.

Проверка сформированности. Спуск, перенос и выбор-как-шаг — Rules; свидетель-пара, наименьший-преемник, $N$-мера — Roles; члены и значения — Elements; пересечений нет. Самоприменения нет: правило выбора стоит над цепью, не есть её член.

Что даёт разбор. Он показывает, что «нужна ли для wqo аксиома Выбора» сформулировано слишком грубо. Над разрешимым — нет: и теорема (wqo переносится $N$-мерой), и метод (минимально-плохой выбор) суть процессы. Завершённая башня и Зависимый Выбор были упаковкой; необходимым остаётся лишь то, что лежит над неразрешимым, — честный горизонт.

Две «стены» — детерминированность и wqo — откачены одним приёмом: дно достигнуто как процесс, неконструктивность локализована, высота объявлена горизонтом. В заключительной главе мы свяжем все ступени в одну иерархию и увидим, что сшивает их в единый процессный подъём.

---

---

Часть: Часть XVIII. Процессная иерархия · Том: «Математика»

Навигация: ← Глава 3. Детерминированность вверх по иерархии · Глава 5. Синтез: иерархия есть процесс →

Footnotes

1. Файл WqoProcessDecidable; машинно проверено, 0 аксиом. Опирается на базовую wqo_nat_le (вполне-упорядоченность ℕ) и на аксиомо-свободный зависимый выбор над разрешимым CountableDependentChoiceFree. ↩

2. no_bad_seq_nat: над ℕ плохой последовательности не существует. Прямое следствие wqo_nat_le, доказанной фундированным спуском по $f(0)$. 0 аксиом. ↩

3. wqo_pullback_nat: монотонная ℕ-мера, отражающая порядок, влечёт wqo. Хорошая пара — образ пары, найденной спуском wqo_nat_le. 0 аксиом. ↩

4. minimal_selection_is_process: над разрешимым тотальным отношением траектория наименьшего-преемника есть цепь, и каждый шаг минимален — детерминированно, без Зависимого Выбора. Опирается на CountableDependentChoiceFree. 0 аксиом. ↩