Фундаментальная Теорема алгебры

В рамках изложенного выше конструктивного анализа приведем теперь подробное доказательство
фундаментальной теоремы алгебры, по существу следуя Мартину Кнезеру [9].

11

Дело в том, что мы представляем доказательство в свободной от выбора форме; это, конечно, включает
все вспомогательные лемматы. Наше изложение достаточно подробно, поскольку—как уже говорилось во
введении-мы хотим сделать алгоритмическое содержание этого доказательства как
можно более ясным, имея в виду, что оно может впоследствии послужить основой для извлечения программы.

Несколько иное представление доказательства Кнезера было дано в [22].
Однако в[22]: 437 подчеркивается, что это доказательство “по существу покоится на аксиоме
выбора”.

12

Как обычно, вещественные числа порождают комплексные числа, которые в данном контексте
представлены парами модулированных последовательностей Коши рациональных чисел и, таким образом,
также последовательно полны (Теорема 4).

Зафиксируйте степень

n ≥ 1 из рассматриваемых многочленов. Основная часть технической
работы заключается в доказательстве следующей леммы.

Лемма 11. Мы можем найти

q ∈ Q с 0 < q < 1 (в зависимости только от нашего фиксированного n ∈ N)

такие, что для каждого монического многочлена

f (ξ) = ξ

н

+ ля

Н-1

ξ

Н-1

+ · · · + a

1

ξ + a

0

∈ С[ξ ]

степени

Н И С |а

0

| > 0 > мы можем найти z ∈ c удовлетворительным

|Зет| ≤

|ля

0

|

q

1
н

и

|f (z) / ≤ q / a

0

|.

Из доказательства будет ясно, что приблизительный корень

z ∈ C мы строим

зависит от представления коэффициентов в

C; то есть о выборе
пар модулированных последовательностей Коши рациональных чисел, которые их представляют. Это
должно быть ожидаемо; например, нет никакой непрерывной функции

f: C → C такое, что

f (z)

2

= z; для решения неединственности корней необходимы римановы поверхности.

Теорема 12 (фундаментальная Теорема алгебры). Для каждого монического многочлена

g (ξ) = ξ

н

+ b

Н-1

ξ

Н-1

+ · · * + b

1

ξ + b

0

∈ C [ξ ] степени n ≥ 1 мы можем найти
w ∈ C такой, что g(w) = 0.

Доказательство. Выбирай

c > 0 С |b

0

| ≤ c. пусть q (в зависимости от n) задается Леммой 11

(для

g вместо f). Этого явно достаточно, чтобы индуктивно построить последовательность (w

м

)

м∈

Н

комплексных чисел таких, что

|Вт

М+1

− Вт

м

| ≤ (вопрос

М-1

с)

1
н

(7)

11

Еще раз, наша версия этого доказательства вытекает из лекционных заметок второго автора. Это даже
было основой реализации фундаментальной теоремы алгебры в интерактивном пословице Coq [12],
выполненной Барендрегтом, Гейвером, Поллаком, Видейком и Цваненбургом [7].

12

Мы также используем возможность упомянуть в печати небольшую оплошность в доказательстве в [22] - спецификации

от

α на странице 434 содержит цикличность. Это было впервые отмечено Barendregt и Geuvers, и коррекция

вы можете найти его на домашней странице компании Troelstra.

Конструктивные решения непрерывных уравнений

237

и

|g(w

м

)| ≤ вопрос

м

с.

(8)

Любая такая последовательность является модулированной последовательностью Коши в

C, пределом которого является корень из g.

Для начала, установите

в

0

= 0. Для шага индукции предположим, что w

м

уже есть

был найден; затем

ф

м

(ξ) = g (w

м

+ ξ) C C[ξ ] - монический многочлен степениn

с постоянным коэффициентом

g(w

м

). Путем сравнивать |g(w

м

) / с 0

М+1

c, мы либо

иметь

|g(w

м

)| < вопрос

М+1

c или |g(w

м

) / > 0 (Лемма 1). В первом случае мы можем взять

в

М+1

= Вт

м

. В последнем случае, применяя лемму 11 к

ф

м

доходность

z ∈ C такой, что

|Зет| ≤

|g(w

м

)|

q

1
н

≤ (вопрос

М-1

с)

1
н

и

|Ф

м

(z) / ≤ q|g (w

м

)| ≤ вопрос

М+1

с.

(Второе неравенство каждой пары выполняется в соответствии с (8).) Так что в этом случае мы можем
установить

в

М+1

= Вт

м

+ z, для которого g(w

М+1

) = Ф

м

(Зет).

В этом доказательстве теоремы 12 молчаливый вызов последовательной полноты является

довольно несущественное, так как-так же как и

z, поставляемый Леммой 11-каждый w

м

может легко

строиться так, чтобы

в

м

= ля

м

+ ib

м

с рациональной действительной и мнимой частью

один

м

и

б

м

. (Это возможно в силу приблизительного характера каждого результата.) Как тогда

(ля

м

) и (b

м

) оба являются модулированными последовательностями Коши рациональных чисел, они соответственно

представлять вещественные числа

a и b, так что w = a + ib-запрошенное комплексное число

с

g (w) = 0.

На этапе индукции случаи критического различия могут перекрываться, и поэтому
выбор—который может даже зависеть от предыдущего—кажется необходимым
всякий раз, когда оба случая происходят одновременно. Однако Лемма 1 автоматически делает
этот выбор в каждой данной ситуации. Другими словами, счетный выбор, не говоря уже
о зависимом выборе, не участвует в настоящем доказательстве фундаментальной теоремы
алгебры. Кроме того, доказательство фундаментальной теоремы алгебры, приведенной Рутенбергом
в [16], не имеет никакого выбора и предназначено для комплексных чисел, представленных в виде
пары модулированных последовательностей Коши рациональных чисел. Это делается путем первого доказательства
дискретной фундаментальной теоремы алгебры (той, что для алгебраических, а не комплексных
чисел) теоретико-полевыми средствами (расщепление полей, минимальные многочлены и т. д.), а
затем аппроксимация комплексных чисел алгебраическими единицами.

Подобно стратегии, подход Ричмана без выбора [14] к приближенной версии
фундаментальной теоремы алгебры, по-видимому, не зависит от какого-либо конкретного
представления вещественных чисел. Часть цены, которую приходится платить за эту общность, заключается
в том, что человек получает немного меньше: мультимножество алгебраических чисел, максимально приближенное к
воображаемому мультимножеству комплексных корней. Чтобы распространить этот результат на точную версию,
выбирая элементы из этих мультинаборов, требуется только довольно слабый и классически
допустимый фрагмент Счетного выбора [6].

13

13

Грубо говоря, это счетный выбор с дополнительным предположением, что все выборы, но не
более одного—из которых, конечно, никто не знает, когда это происходит-являются выборами (!) из синглетного набора. IT

238

P. Schuster and H. Schwichtenberg

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

Доказательство леммы 11. Прежде чем углубиться в детали, давайте кратко очертим подход
, который окажется успешным в следующем. Во-первых, мы выбираем подходящий один из
мономиалов

один

1

ξ,..., ля

н

ξ

н

= ξ

н

, сказать

один

к

ξ

к

, и далее определиться

z такой, что a

0

и

один

к

зет

к

отличаются отрицательным фактором. Для

|z / = r мы предполагаем только, что этот мономиал является

достаточно маленький, т. е.,

|ля

к

|р

к

≤ |ля

0

| + ε. Тогда мы получим (см. (15))

|f (z) / ≤ / a

0

+ ля

к

зет

к

| +

i=0, k

|ля

я

зет

я

| ≤ |ля

0

| − |ля

к

|р

к

+ 2ε +

i=0, k

|ля

я

|р

я

.

Так что суть в том, чтобы выбрать

k и r таким образом, что мономиалы |a

я

|р

я

(

i = 0, k)

малы сравненные к

|ля

к

|р

к

, но с другой стороны не слишком маленькие по сравнению с

|ля

0

|

(см. (14)).

Шаг 0. Чтобы начать со строительства, установите

q = 1 −

1

4

· 3

2

н

2

−1

и

ε = min

|ля

0

|

2

(n + 1)

·

1

4

· 3

2

н

2

−1

, (вопрос

−1

− 1) / a

0

|.

Эти варианты будут объяснены в шагах 6, 10 и 11 ниже.

Шаг 1. Позволь

m (s): = max {/a

я

|с

я

| i = 1,..., n } для каждого реального s. выберем t ∈ Q,

t > 0, такие что

|m (t) − / a

0

|| ≤ ε.

(9)

Это возможно по приближенной теореме о промежуточном значении (Теорема 10), для
m (0) = 0

0

| и, потому что s

н

≤ m (s), существует s

0

> 0 такие, что |a

0

|

0

);

в этой связи следует отметить, что

m равномерно непрерывна на компактном интервале [0, s

0

].

Шаг 2. Для

i = 1,..., n выберите y

я

∈ Q, y

я

> 0, такие что |y

я

− |ля

я

|t

я

| ≤ ε. С

y

ij

:=

y

я

3

ij

(для

j ∈ Z) получаем

y

ij

− |ля

я

|

т

3

j

я

=

y

я

3

ij

−

|ля

я

|t

я

3

ij

≤

ε

3

ij

.

(10)

Шаг 3. Для каждого

j ∈ Z, выберите k

j

∈ {1,..., n} минимальное такое, что y

ij

≤ год

к

j

j

для

i = 1,..., н. так

|ля

я

|

т

3

j

я

≤ год

ij

+

ε

3

ij

≤ год

к

j

j

+

ε

3

ij

≤ |ля

к

j

|

т

3

j

к

j

+

ε

3

к

j

j

+

ε

3

ij

.

(11)

Шаг 4. У нас есть

к

j

≥ k

j +1

.

(12)

следует также отметить, что многие апелляции к Счетному выбору могут быть сведены к этому более слабому принципу. Мы
ссылаемся на [15] для получения более подробной информации.

Конструктивные решения непрерывных уравнений

239

Действительно, ибо

i ≥ k

j

,

y

к

j

(j +1)

=

1

3

к

j

(j +1)

y

к

j

=

1

3

к

j

y

к

j

j

≥

(∗)

1

3

я

y

ij

=

1

3

i(j +1)

y

я

= год

i(j +1)

;

откуда

к

j +1

≤ k

j

согласно выбору компании:

к

j +1

(“наименее вероятно”).

Шаг 5. Выбирать

j > 0 минимальное такое, что k

j -1

= k

j

= k

j +1

=: k. из-за (12)

У нас есть

n ≥ k

−1

≥ k

0

≥ k

1

≥ · * * ≥ k

j -1

= k

j

= k

j +1

,

где из каждой пары два подряд

≥ (за исключением первого) по крайней мере один должен

быть

>. Следовательно, для 2i-1 ≤ j имеем k

2

i-1

≤ n-i.

Случай 1.

j имеет вид 2i-1. Затем

к

j

≤ n-i = n −

j + 1

2

⇒ 2k

j

≤ 2n − j-1

⇒ j ≤ 2(n-k

j

) − 1.

Случай 2.

j имеет вид 2i. тогда

к

j

= k

j -1

≤ n-i = n −

j
2

⇒ 2k

j

≤ 2n-j

⇒ j ≤ 2(n-k

j

).

Следовательно вообще мы имеем

j ≤ 2 (n − k).

(13)

Шаг 6. Позволь

р:=

т

3

j

∈ Q. мы оцениваем |a

к

|р

к

против

|ля

0

|. Для i = 1,...,.., n, by

(11) и

k = k

j

У нас есть

|ля

к

|р

к

= |ля

к

|(

т

3

j

)

к

≥ |ля

я

|(

т

3

j

)

я

− 2ε ≥

1

3

nj

|ля

я

|t

я

− 2ε, следовательно

|ля

к

|р

к

≥

1

3

nj

m (t) - 2ε

для

m (t) = max {/a

я

|t

я

| i = 1,..., n } как и прежде

≥

1

3

nj

|ля

0

| − 3ε

по выбору:

t в (9).

По (13) мы имеем

nj ≤ 2n (n − k) ≤ 2n

2

- k и поэтому

|ля

к

|р

к

≥

1

3

2

н

2

- к

|ля

0

| − 3ε.

(14)

В частности

|ля

к

| > 0 из-за ε >

|ля

0

|

3

·

1

3

2

n2-1

.

Шаг 7. Мы сначала определимся

z ∈ C с |z / = r такой, что a

0

и

один

к

зет

к

отличаются на a

негативный фактор. Писать

один

0

= |ля

0

|ми

ix

0

и

один

к

= |ля

к

|ми

ix

к

и пусть...

z = / r / e

Ай!

с

y такой

тот

икс

0

+ π = x

к

+ Кентукки.

Мы покажем, что

|ля

0

+ ля

к

зет

к

| ≤ |ля

0

| − |ля

к

зет

к

| + 2ε. Сейчас

к

зет

к

= −Калифорния

0

с

c ∈ R,

c > 0, и по выбору t в (9) также |a

к

зет

к

| ≤ |ля

0

| + ε. Следовательно

c / a

0

| = |ля

к

зет

к

| ≤ |ля

0

| + ε

и

0

< с ≤ 1 +

ε

|ля

0

|

,

240

P. Schuster and H. Schwichtenberg

следовательно

|ля

0

+ ля

к

зет

к

| = |ля

0

| · |1 − c|

= |ля

0

/ max(1-c, c-1)

= |ля

0

/ max(1-c, 1-c + 2(c-1))

≤ |ля

0

/ max 1-c, 1 − c + 2

ε

|ля

0

|

= |ля

0

|(1-c) + 2ε

= |ля

0

| − |ля

к

зет

к

| + 2ε.

Теперь мы получаем

|f (z) / ≤ / a

0

+ ля

к

зет

к

| +

i=0, k

|ля

я

зет

я

|

≤ |ля

0

| − |ля

к

зет

к

| + 2ε +

i=0, k

|ля

я

зет

я

|

= |ля

0

| − |ля

к

|р

к

+ 2ε +

i=0, k

|ля

я

|р

я

.

(15)

Шаг 8. Оценка стоимости

1

≤i

|ля

я

|р

я

. Пусть 1

≤ i

|ля

я

|р

я

= 3

я

|ля

я

|

r
3

я

= 3

я

|ля

я

|

т

3

j +1

я

≤ 3

я

|ля

к

|

т

3

j +1

к

+

ε

3

i(j +1)

+

ε

3

k(j +1)

по (11), ибо

k = k

j +1

≤ 3

я

|ля

к

|

т

3

j

к

1

3

к

+ 2

ε

3

я

=

1

3

К-и

|ля

к

|р

к

+ 2ε,

следовательно (используя

1

3

к−1

+ · · · +

1
3

=

1
2

1

−

1

3

к−1

)

1

≤i

|ля

я

|р

я

≤ |ля

к

|р

к

1
2

1

−

1

3

к−1

+ 2 (k − 1)ε.

(16)

Шаг 9. Оценка стоимости

к

|ля

я

|р

я

. Позволь

к

|ля

я

|р

я

=

1

3

я

|ля

я

|(3r)

я

=

1

3

я

|ля

я

|

т

3

j -1

я

≤

1

3

я

|ля

к

|

т

3

j -1

к

+

ε

3

i(j -1)

+

ε

3

k(j -1)

по (11), ибо

k = k

j -1

Конструктивные решения непрерывных уравнений

241

≤

1

3

я

|ля

к

|

т

3

j

к

· 3

к

+ 2 · 3

к

ε

≤

1

3

и-к

|ля

к

|р

к

+ 2ε,

следовательно (используя

1
3

+ · · · +

1

3

н-к

=

1
2

1

−

1

3

н-к

)

к

|ля

я

|р

я

≤ |ля

к

|р

к

1
2

1

−

1

3

н-к

+ 2 (n − k)ε.

(17)

Шаг 10. Из (15), (16) и (17) получаем

|f (z) / ≤ / a

0

| − |ля

к

|р

к

+ 2ε +

i=0, k

|ля

я

|р

я

≤ 2ne + / a

0

| − |ля

к

|р

к

+ |ля

к

|р

к

1
2

1

−

1

3

к−1

+ |ля

к

|р

к

1
2

1

−

1

3

н-к

≤ 2ne + / a

0

| −

1
2

·

1

3

к−1

|ля

к

|р

к

≤ 2ne + / a

0

| −

1

2

· 3

к−1

1

3

2

н

2

- к

|ля

0

| − 3ε

по (14)

≤ 2 (n + 1)ε + 1 −

1

2

· 3

2

н

2

−1

|ля

0

|

≤ 1 −

1

4

· 3

2

н

2

−1

=вопрос

|ля

0

| для ε ≤

|ля

0

|

2

(n+1)

·

1

4

·3

2

n2-1

Шаг 11. Наблюдать

|z / = r, следовательно

|Зет|

н

= р

н

≤ t

н

≤ m (t) ≤ / a

0

| + ε ≤ q

−1

|ля

0

|

потому что

ε ≤ (q

−1

− 1) / a

0

|. Поэтому мы имеем |z / ≤ (q

−1

|ля

0

|)

1
н

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