Глава 4. Один дискриминант: редукционный атлас и разрешимая сторона

Зеркало диагонали

Глава 15.3 дала отрицательную master-структуру: одна диагональ запрещает решатель там, где граница есть role-limit. У границы две стороны, и у второй — своя master-структура, положительная:

там, где граница разрешима, её рисует один терминирующий критерий — дискриминант.

Если коротко: неразрешимость — одна диагональ, разрешимость — один дискриминант. И это не две темы, а одна граница: разрешимая (Element) грань и неразрешимые (role-limit) грани стоят в том же расширенном капстоуне о четырёх лицах границы (15.3) — число разрешимо, программа / множество / сложность нет. Эта глава раскрывает Element-грань: что её рисует, почему одним критерием и почему выбор на ней свободен от аксиомы выбора.

Дискриминант: рациональное собственное значение

Возьмём $2\times 2$-матрицу с целыми входами, след $\text{trace}$ и определитель $\det$. Её собственные значения — корни характеристического квадрата, и всё решает дискриминант

$$\Delta ={\text{trace}}^2-4\det ,{\lambda }_{1,2}=\frac{\text{trace}\pm \sqrt{\Delta }}{2}.$$

Математически (для целочисленной $2\times 2$-матрицы) собственное значение рационально тогда и только тогда, когда $\sqrt{\Delta }$ рационален, то есть когда $\Delta$ — полный квадрат:

$$\lambda \in Q⟺\sqrt{\Delta }\in Q⟺\Delta =r^2\text{для некоторого целого }r.$$

Машинно выделена ключевая направляющая сторона этого моста: целый корень характеристического многочлена вынуждает квадратный дискриминант ($\Delta =(2x-\text{trace}{)}^2$); контрапозиция — $\Delta$ не квадрат $\Rightarrow$ нет рационального корня $\Rightarrow$ role-limit. А сам вопрос «$\Delta$ — полный квадрат?» разрешим терминирующим вычислением (взять целую часть корня и проверить квадрат): Element-граница нарисована — наличие рационального характеристического корня решается за конечное число шагов.¹

Примеры из самого атласа: $\Delta =9$ — полный квадрат, есть рациональный характеристический корень (Element); $\Delta =8$ (Адамар) и $\Delta =32$ (Пелль) — не квадраты, рационального корня нет ($\sqrt{2}$), и это role-limit. Здесь role-limit означает не невычислимость процесса (как у диагонали), а выход за рациональный Element-слой: $\sqrt{\Delta }$ требует расширения носителя — ровно тот барьер рациональное / иррациональное, что делил Часть IV, теперь как разрешимый тест.

Редукционный атлас: разные движки — один вопрос

Сила положительной стороны в том, что этот один критерий покрывает многое. Несколько на вид несвязанных «движков» — уравнение Пелля, теорема Нивена (рациональные значения косинуса при рациональных углах), квадратичные сурды, чётность, унимодулярные матрицы — все сводятся к тому же вопросу: «дискриминант — полный квадрат?». Это и есть редукционный атлас: разные поверхности, один подлежащий критерий.²

Структурно это зеркало 15.3. Там одна диагональ ($b\ne \text{negb}b$) оказалась корнем многих отрицательных результатов; здесь один дискриминант ($\Delta$ — квадрат?) оказывается корнем многих положительных, разрешимых. У границы финитизации две оси симметрии, и каждая — единственная.

Выбор без аксиомы выбора

На разрешимой стороне даром даётся ещё одно — выбор. Если предикат над конечным списком разрешим, то первый свидетель есть канонический, терминирующий выбор: пробежать список, взять первый подходящий элемент. Аксиома выбора не нужна — выбор вычисляется.³

Это та же линия, что в нашей теории множеств без AC (детерминированный выбор: argmax-по-индексу, первый свидетель): где role-limit-сторона потребовала бы оракула (недостижимый выбор сразу из всех), Element-сторона считает выбор за конечное число шагов — на конечном упорядоченном носителе при разрешимом предикате. Выбор как процесс, не как оракул — P4 в действии.

{ И это не потолок конечного. Тот же приём — разрешимый критерий плюс канонический порядок (наименьший элемент $N$) — поднимается лестницей: со счётного носителя (счётный выбор) на счётную цепочку (зависимый выбор) и на бесконечное дерево с разрешимым ветвлением (лемма Кёнига). На каждой ступени, пока критерий разрешим и носитель упорядочен, выбор остаётся вычислимым, и аксиома выбора не требуется. Синтез один: из пяти уровней лестницы от аксиомы выбора свободны четыре — конечный, счётный, зависимый и Кёнигов, — а её цена падает ровно на пятый, где предикат становится неразрешимым. На ту же границу садится и теорема Рамсея: конечный Рамсей разрешим ($R(3,3)=6$ вычисляется перебором), а бесконечный — role-limit (нужно выбрать цвет, повторяющийся бесконечно). Та же грань Element/role-limit, на которой стоит вся глава.⁴ }

Дискриминант как решающая процедура

Соберём положительную сторону в одно. Диагональ (15.3) запрещает решатель для role-limit-границ; дискриминант даёт решатель для Element-границы. Это и есть точное зеркало:

$$\underset{\text{нет решателя}}{\underbrace{\text{диагональ}}}(\text{15.3})⟺\underset{\text{есть решатель}}{\underbrace{\text{дискриминант}}}(\text{здесь}).$$

И обе стоят в одной теореме о лицах границы: число — Element-нарисовано (дискриминант), программа / множество / сложность — role-limit-нарисованы (диагональ).⁵ Одна граница, две master-структуры: диагональ (отрицательная) $\oplus$ дискриминант (положительная). Это и есть хребет части.

Горизонт: общая степень

Будем точны в масштабе. Дискриминантный критерий проведён в нашей системе конкретно — для квадратичного случая ($2\times 2$, $\Delta ={\text{trace}}^2-4\det$) и для пяти движков атласа, всё машинно и 0-аксиомно. Полностью общая процедура — разрешать рациональность спектра в любой степени ($n\times n$, рациональные корни произвольного характеристического многочлена) — есть естественное продолжение того же критерия (тест рационального корня и факторизация характеристического многочлена; для высших степеней одного дискриминанта уже не достаёт). В нашей системе она пока развита по случаям (квадратичный атлас), а не замкнута в одну процедуру общей степени; это — ближайший горизонт положительной стороны, а не заявленный результат.

Различение честное и того же рода, что в 15.3 (где машинно собраны четыре грани, а верх лестницы — стандартное чтение): здесь машинно собран квадратичный дискриминант и атлас, а общая степень названа как направление.

Разбор E/R/R и что глава подготовила

Правила (L5). Дискриминант $\Delta ={\text{trace}}^2-4\det$ есть правило, рисующее Element-границу: «$\Delta$ — полный квадрат $\Rightarrow$ рациональный спектр $\Rightarrow$ Element». Его терминирующая реализация — тест полного квадрата; редукционный атлас — правило, сводящее многие движки к этому одному.

Роли (L4). «Рациональный спектр / Element» против «иррациональный / role-limit» — две роли спектрального данного; решатель (тест квадрата) — роль-критерий; первый свидетель — роль выбора-как-вычисления (не оракул).

{

Элементы (L1$+$P4). Конкретные матрицы, значения $\Delta$, конечные списки свидетелей. Не элемент текущего подтверждённого слоя: замкнутая процедура общей степени — граница охвата, а не онтологический P4-запрет (процедуры рациональных корней существуют).}

Компонент	Что фиксирует	E/R/R-категория
дискриминант $\Delta ={\text{trace}}^2-4\det$; атлас движков	рисование Element-границы	Правило (L5)
рациональный / иррациональный спектр; решатель-тест; первый свидетель	роли и критерий-выбор	Роль (L4)
матрицы; значения $\Delta$; списки свидетелей	конечно-актуальные носители	Элемент (L1$+$P4)

Диагностика P4. Разрешимая сторона — это в точности финитизируемая сторона: граница сворачивается в терминирующий тест, а это и значит «Element». Дискриминант — положительное лицо границы финитизации, диагональ — отрицательное; вместе они и есть та граница, что делит вычислимое и невычислимое.

Что глава подготовила. Предъявлена вторая master-структура части: разрешимость — один дискриминант ($\Delta$ — полный квадрат), редукционный атлас сводит к нему многие движки, а выбор на этой стороне свободен от аксиомы выбора. Всё доказанное здесь 0-аксиомно и машинно проверено; общая степень названа честно как горизонт. Дальше — глава 15.5: типобезопасность через горючее, где бесконечная цепь редукций финитизируется в конечный прогон — ещё одно лицо той же границы; а финал 15.7 сведёт обе master-структуры воедино: диагональ $\oplus$ дискриминант — одна граница финитизации.

---

---

Часть: Часть XV. Вычисления и граница финитизации · Том: «Математика»

Навигация: ← Глава 3. Одна диагональ: halting, Райс, Кантор, Колмогоров · Глава 5. Типобезопасность как fuel-финитизация →

Footnotes

1. Машинно проверено, 0 аксиом: src/cs/BoundaryDecidability.v — is_square (тест полного квадрата через целочисленный корень), rational_split ($\Delta$ есть квадрат), discriminant_ element_drawn (Element-нарисованность критерия). Мост и дискриминант — src/stdlib/ReductionAtlasSynthesis.v: disc / tr2 / det2, disc_eq ($\Delta ={\text{trace}}^2-4\det =(a-d{)}^2+4bc$), char_poly_ complete_square и направляющая eigenvalue_ forces_ square_disc (рациональный корень $\Rightarrow$ квадратный $\Delta$). Полное iff — стандартное математическое чтение для целочисленного $2\times 2$. ↩

2. Машинно проверено, 0 аксиом: капстоун src/stdlib/ReductionAtlasSynthesis.reduction_ atlas_ synthesis (все движки сведены к disc); пять движков — ReductionAtlasPell.v, ReductionAtlasNiven.v, ReductionAtlasSurd.v, ReductionAtlasParity.v, ReductionAtlasUnimodular.v (дополнительные квадратичные леммы — QuadraticDiscriminant.v). ↩

3. Машинно проверено, 0 аксиом: src/cs/DecidableSelection.v (7 Qed) — first_witness (первый свидетель в списке) с first_witness_sound / complete / first, decidable_list_choice (выбор на разрешимом конечном предикате). ↩

4. Машинно проверено, 0 аксиом: src/cs/CountableSelectionFree.v (6 Qed, countable_selection_free, dec_family_choice); CountableDependentChoiceFree.v (7 Qed, countable_dependent_choice_free, dc_chain_step); DecidableKonig.v (7 Qed, decidable_konig); синтез SelectionWithoutChoiceSynthesis.v (8 Qed, selection_without_choice_synthesis: count_free_4 свободны, count_priced_1 с ценой); граница — RamseyBoundary.v (15 Qed, R33_upper / R33_lower / ramsey_3_3, $R(3,3)=6$). ↩

5. Element-грань и role-limit-грани вместе — src/cs/BoundaryDecidability.one_boundary_three_faces и KolmogorovRoleLimit.one_boundary_four_faces (0 аксиом): discriminant_ element_drawn стоит в одной конъюнкции с halting_ role_limit_drawn и Кантором. ↩