Обзорные темы по алгебре
≅Zp⊕Zp⊕ … ⊕Zp . Все элементы аддитивной группы имеют порядок p, поэтому если поле P не совпадает с Zp, то группа
— нециклическая В отличие от аддитивной группы (которая порождается одним элементом лишь в полях Zp), мультипликативная группа конечного поля всегда циклическая, так как все конечные мультипликативные группы любого поля порождаются одним элементом. В поле P мультипликативную группу P* составляют все его ненулевые элементы, т. е. порядок P* мультипликативной группы поля P равен pn – 1. Итак, в поле P найдется такой элемент g, что 288 { P \ {0} = 1, g, g 2 , ..., g p n −2 }. Если циклическая группа гр(g) имеет порядок m, то элемент gk порождает эту группутогда и только тогда, когда k и m взаимно просты. Таким образом, в конечном поле Pпорядка pn содержится в точности ϕ(pn – 1) элементов, каждый из которых порождает группу < P*; ⋅ >. Порождающий элемент g мультипликативной группы P может быть выбран в качестве присоединяемого элемента, т. е. P = ZP (g). Действительно, степени элемента g— это все ненулевые элементы из P, а 0 = g – g. Впрочем, этот же факт можно рассмотреть с иной точки зрения. Каждый элемент конечного расширения поля Zp является корнем многочлена с коэффициентами из Zpи степень этого многочлена не превышает число n. Не будет исключением и порождающий элемент g мультипликативной группы P* поля P. Если k— наименьшая степень многочлена f (x) над Zp , корнем которого является элемент g, то элементы 1, g, g2, … gk – 1 еще линейно независимы над полем Zp , а элементы 1, g, g2, … gk – 1, gk уже линейно зависимы. Поэтому gk = a0 + a1 g + … + ak – 1 gk – 1, (∗) где ao, a1, …, ak – 1 — элементы из Zp . Из минимальности выбора числа k следует, что многочлен f (x) = a0 + a1 x + … + ak– 1 xk– 1 неприводим, поэтому простое алгебраическое расширение ZP (g) поля Zpс помощью g —корня многочлена f (x) — имеет над Zp размерность k. Поле ZP (g) содержится в поле P. С помощью равенства (∗) можно получить все остальные степени элемента g. Так как g — порождающий элемент группы P*, эти остальные степени вместе с 289 уже имеющимися: 1, g, g2, … gk – 1 , дадут все ненулевые элементы поля P. Поэтому ZP (g) = P, а k = n. n p Многочлен x − x не имеет кратных корней, поэтому каждый его неприводимый множитель степени n имеет n различных корней. Каждый порождающий мультипликативной группы поля является корнем одного из таких многочленов-множителей. Число различных порождающих циклической группы порядка pn равноϕ(pn – 1) Кроме того, если один из корней неприводимого многочлена степени n оказался порождающим муль- типликативной группы поля FG(pn), то и все остальные корни этого многочлена тоже будут порождающими. Если k— число неприводимых над Zp многочленов степени n,корни которых оказались порождающими циклической группы
, то1
kn = ϕ(pn – 1).
Следовательно, общее число неприводимых над Zp многочленов степени nне
меньшечисла
(
)
ϕ pn −1
.
n
Это число для некоторых pn действительно равно числу неприводимых
многочленов степени n над полем Zp (например, для рассмотренного ранее поля
из восьми элементов), но, вообще говоря, эта оценка грубовата. Дело в том, что
не каждый корень минимального многочлена обязан быть порождающим
мультипликативной группы поля.
Например,
(
)
(
)
ϕ 212 − 1 ϕ(4095 ) ϕ 32 ⋅ 5 ⋅ 7 ⋅ 13 6 ⋅ 4 ⋅ 6 ⋅ 12
=
=
=
= 144 ,
12
12
12
12
1
Отсюда, в частности, следует, что для любого простого p и любого натурального n число
— целое.
290
(
n
)
ϕ p −1
n
но в действительности число неприводимых над Z2 многочленов степени 12
равно 335. Это значит, что поле FG(212) можно представить как расширение
поля Zp с помощью любого из двенадцати корней 191 многочлена и этот корень
не будет порождающим мультипликативной группы ненулевых элементов
этого поля.
Точное значение числа многочленов степени m и неприводимых над полем
Zp равно
1
m
∑ µ (d )p
d
m
d
,
m
где µ(n) — функция Мебиуса1: µ(1) = 1 и если pi— различные простые числа,
и n = p1α ⋅ p2α ⋅ ... ⋅ pkα , где αi ≥ 1, то
1
2
k
0, если существует i такой, что α i > 1,
µ p1α1 ⋅ p 2α 2 ⋅ ... ⋅ p kα k =
(− 1)k , если все α i = 1 .
(
)
Для строения поля важную роль играет устройство решётки подполей.
ПОДПОЛЯ КОНЕЧНОГО ПОЛЯ. Пусть P— конечное поле порядка pn, и H —
его подполе. Порядок k подполя H является делителем числа pn, поэтому k = pm,
где m ≤ n.
Поле P является расширением подполя H, и значит, P образует векторное
пространство над H конечной размерности s. Каждое такое пространство
изоморфно s-мерному арифметическому пространству строк. Число различных
таких строк (размещений по s элементов из k с повторениями) равно k s ,
т. е.(pm)s = pn.
Август Фердинанд Мебиус (Möbius, 1790–1868) — немецкий математик, получивший в основном
результаты в геометрии; в 1858 г. установил существование односторонних поверхностей (лист Мебиуса). Функция µ(n) введена А. Мебиусом в 1832 г.
1
291
Таким образом, число
элементов
в
подполе
конечногополя
порядка p n равно p m , где m делит n. С другой стороны, для каждого
делителя m числа n в поле P найдется подполе порядка pm.
Действительно, многочлен
f (x ) = x p − x делится на
n
g (x ) = x p − x и,
m
следовательно, поле разложения H многочлена g(x) содержится в поле
разложения многочлена f (x).
Порядок H равен pm, а это значит, что для каждого m— делителя числа n в
поле порядка pnнайдется подполе порядка pm.
Мультипликативная
группа
каждого
подполя
является
подгруппой
мультипликативной группы поля, но в циклической группе порядка t
существует в
точности
одна
подгруппа
порядка q для каждого q— делителя числа t.
Единственная подгруппа дает единственное
подполе.
Для каждого m— делителя числа
n
в
поле
порядка
единственное
pn
подполе
найдется
порядка
p m . Это все означает, что решетка подполей поля GF(pn) элементов изоморфна
решетке делителей числа n.
Например, шести делителям числа 12 соответствуют шесть подполей
поля GF(p12).
Полное
описание
алгебры
включает
исследование
ее
полугруппы
эндоморфизмов и группы автоморфизмов. Эндоморфизмов, отличных от
изоморфизмов, не имеет любое поле, в том числе и конечное.
АВТОМОРФИЗМЫ
КОНЕЧНЫХ
ПОЛЕЙ.
Любой автоморфизм α поля
оставляет на месте нейтральные элементы. Поэтому α(1) = 1, а тогда для
любого натурального n выполняется тождество
292
α(n⋅ 1) = n ⋅ 1.
Следовательно,
любой
автоморфизм
оставляет
простое
подполе
неподвижным. В конечном поле характеристики p простым подполем является
Zp . Элементы из Zp не перемещаются при любом автоморфизме, в частности
группа Aut(Zp) — единичная.
Посмотрим, как устроена группа автоморфизмов конечного поля P из pn
элементов при n > 1.Отображение ϕ: x a
xp
сохраняет операции и, следователь-
но, является (кольцевым)гомоморфизмом. При этом гомоморфизме единица переходит в единицу, т. е. отображение ненулевое. У полей любой ненулевой гомоморфизм является изоморфизмом. Поле P—конечно, следовательно, ϕ—
отображение на(биекция), т. е. автоморфизм. Этот автоморфизм называют автоморфизмом Фробениуса1. Для любого натурального
m < n в поле P не выполняется тождество x p = x , поэтому и сам автоморфизм
m
Фробениуса нетождественный, все n степеней этого автоморфизма(1 ≤ k ≤ n)
( )
p
ϕk (x ) = x p ... = x p
14243
p
k
k
различны. Тождество x p = x означает, что ϕn = ε. Итак, циклическая группа,
n
порожденная автоморфизмом Фробениуса, состоит в точности из n элементов.
Покажем, что других автоморфизмов в группе Aut(P) нет.
Пусть элемент α— корень неприводимого над Zp многочлена f (x) степени n
и α2,α3, ..., αn—
принадлежат
остальные
полю
P,
корни
равному
этого
многочлена.
ZP (α)—
Все
простому
эти
корни
алгебраическому
расширению поля Zp . Поэтому любой автоморфизм, оставляющий поле Zp
неподвижным, однозначно определяется отображением α
a
αi (i = 2, 3, …, n)
Число таких отображений равно n, значит, порядок Aut(P) тоже равен n.
Фердинанд Георг Фробениус (Frobenius, 1849–1917) — немецкий математик, профессор Цюрихского политехникума (1875–1892), Берлинского университета(с 1892 г.). В 1877 г. Ф. Фробениус доказал теорему, из которой следует, что поле комплексных чисел — наибольшая из возможных числовых систем.
1
293
Отсюда следует, что д р у г и х а в т о м о р ф и з м о в , к р о м е с т е п е н е й
автоморфизма Фробениуса, у конечного поля нет.
Группа автоморфизмов конечного поля GF(pn) найдена.
Aut(GF(pn))—э т о
порожденная
циклическая
автоморфизмом
группа
x a xp ,
и
порядка
n,
состоящая
из
n
отображений вида x a x p .
Отметим попутно, что если α— один из корней минимального многочлена,
i
то все корни этого многочлена имеют вид α p , где i = 0, 3, …, n – 1.
Кроме того, из биективности отображения
натурального n уравнение
n
xp = a
n
следует, что для любого
в поле характеристики p имеет в точности
одно решение для любого элемента a.
294
x a xp
23 .УСЛОВИЯ РАЗРЕШИМОСТИ УРАВНЕНИЯ ТРЕТЬЕЙ СТЕПЕНИ В
КВАДРАТНЫХ РАДИКАЛАХ. ПРИМЕРЫ ГЕОМЕТРИЧЕСКИХ
ЗАДАЧ, СВОДЯЩИХСЯ К УРАВНЕНИЯМ, НЕРАЗРЕШИМЫМ В
КВАДРАТНЫХ РАДИКАЛАХ
Основные понятия: расширение поля, подполе, многочлен, корень многочлена, сопряженность, простое алгебраическое расширение, квадратичное расширение, формулы Виета, геометрическая задача на построение.
Основные факты: Корни многочлена третьей степени выражаются в
квадратных радикалах тогда и только тогда, когда один из корней принадлежит полю коэффициентов; все классические задачи древности на
построение циркулем и линейкой неразрешимы.
КВАДРАТИЧНОЕ РАСШИРЕНИЕ ПОЛЯ. Если P – числовое поле, а элемент d
{
}
не является точным квадратом в P. то множество a + b d a, b ∈ P обознача-
( )
ют символом P d и называют простым квадратичным расширением поля P
с помощью элемента
d.
Каждый элемент из простого квадратичного расширения P( d ) имеет
единственное представление в виде a+b d , где a, b∈P.
Элементы a+b d и a-b d из P( d ) являются корнями одного и того же
многочлена c коэффициентами из поля P и неприводимого над P.
Таким образом, a+b d и a-b d - сопряжены над P.
Отображение, переводящее каждый элемент a+b
d
в сопряженный a-b
d
,
является автоморфизмом поля P( d ), оставляющим поле P неподвижным.
Говорят, что корни многочлена
f(x)=a0xn + a1xn-1 + ... + an-1x + an=0
выражаются в квадратных радикалах (или уравнение f(x)=0 разрешимо в квадратных радикалах), если корни этого многочлена выражаются через его ко295
эффициенты a0, a1, ..., an-1, an с помощью операций сложения, умножения, вычитания, деления и извлечения квадратного корня.
Алгебраическое уравнение f(x)=0 разрешимо в квадратных радикалах, если
от его поля коэффициентов P до поля разложения многочлена f(x) можно протянуть цепочку простых квадратичных расширений.
Набор операций {+, -, ⋅, /,
} представляет интерес в связи с геометриче-
скими задачами на построение с помощью циркуля и линейки.
Для того чтобы циркулем и линейкой можно было построить отрезок x,
длина которого является выражением
f(a, b, ..., c) от длин a, b, …, c данных
отрезков, необходимо, и достаточно, чтобы в выражении f(a, b, …, c) использовались только операции сложения, вычитания, умножения, деления и извлечения квадратного корня.
СОПРЯЖЕННЫЕ ЧИСЛА И КВАДРАТИЧНЫЕ РАСШИРЕНИЯ. Комплексные числа сопряжены (а, точнее, сопряжены над полем R), если они являются корнями
одного и того же неприводимого многочлена с действительными коэффициентами. Такое определение сопряженности имеет далеко идущее обобщение.
Пусть P – произвольное поле, а P1 – полевое (или кольцевое расширение
поля P). Два элемента из P1 называют сопряженными над P, если эти элементы
явялются корнями одного и того же неприводимого многочлена с коэффициентами из P.
Если P – числовое поле, а элемент d не является точным квадратом в P. то
множество {a + b d a, b ∈P}, обозначают символом P ( d ) называют простым квадратичным расширением поля P с помощью элемента
Каждый элемент из простого
d.
квадратичного расширения P ( d ) имеет
единственное представление в виде a + b d , где a, b ∈ P.
Элементы a + b d и a - b d из P ( d ) являются корнями одного и того
же многочлена
296
x2 – 2ax + (a2 – b2d)
c коэффициентами из поля P и неприводимого над P.
Таким образом, a + b d и a - b d - сопряжены над P.
Отображение, переводящее каждый элемент a + b d
a–b
d
в сопряженный
, является автоморфизмом поля P ( d ), оставляющим поле P неподвиж-
ным.
УСЛОВИЯ
РАЗРЕШИМОСТИ УРАВНЕНИЯ ТРЕТЬЕЙ СТЕПЕНИ В КВАДРАТНЫХ
РАДИКАЛАХ. Говорят,
что корни многочлена
f(x) = a0xn + a1xn - 1 + ... + an - 1x + an = 0
выражаются в квадратных радикалах (или уравнение f(x) = 0 разрешимо в квадратных радикалах), если корни этого многочлена выражаются через его коэффициенты a0, a1, ..., an-1, an с помощью операций сложения, умножения, вычитания, деления и извлечения квадратного корня.
Алгебраическое уравнение f(x)=0 разрешимо в квадратных радикалах, если
от его поля коэффициентов P до поля разложения многочлена f(x) можно протянуть цепочку простых квадратичных расширений.
Слово цепочка в этом утверждении означает, как обычно, линейно упорядоченное множество. В данном случае – это множество подполей, вложенных
друг в друга. Наименьшим из них является поле P, а наибольшим поле разложения многочлена f(x).
Набор операций (+, -, *, /,
) представляет интерес в связи с геометри-
ческими задачами на построение с помощью циркуля и линейки.
Для того чтобы циркулем и линейкой можно было построить отрезок x,
длина которого является выражением
f(a, b, ..., c) от длин a, b, …, c данных
297
отрезков, необходимо и достаточно, чтобы в выражении f(a, b, …, c) использовались только операции сложения, вычитания, умножения, деления и извлечения квадратного корня.
Пытаясь решить классические задачи древности французский математик
П. Вантцель1 доказал следующую теорему.
Корни многочлена третьей степени выражаются
в квадратных
радикалах через коэффициенты многочлена тогда и только тогда,
когда один из корней принадлежит полю коэффициентов.
Если корень α многочлена
x3 + a1x2 +a2x +a3
(*)
принадлежит полю коэффициентов, то по теореме Безу
x3 + a1x2 + a2x +a3 = (x – α) (x2 + b2x + b3),
а уравнение второй степени разрешимо в квадратных радикалах.
Более интересна обратная ситуация – необходимость условия. Предположим, что ни один из корней не принадлежит полю коэффициентов, но уравнение всё-таки разрешимо в квадратных радикалах.
Это значит, что, по крайней мере, один из корней многочлена (*) выражается через его коэффициенты с помощью полевых операций и извлечения квадратного корня. Но тогда коэффициенты многочлена x2 +b2x + b3, а, следовательно, и его корни тоже имеют аналогичные выражения. Таким образом, для каждого корня исходного многочлена можно протянуть цепочку простых квадратичных расширений от его поля коэффициентов P до поля, содержащего этого
корень.
Пусть x1 – корень многочлена (*), имеющий цепочку наименьшей длины:
298
P = P0 < P1 < … < Pk,
где k > 0 и каждое Pi является простым квадратичным расширением Pk – 1, и
x1∈ Pk.
Пусть Pk = Pk – 1 ( d ), где d – элемент из Pk – 1, а уравнение x2 = d не имеет
решения в Pk-1. Тогда x1 = a + b d , где a, b – элементы из поля Pk – 1. Элемент
x2 = a – b
d
из Pk является вторым корнем многочлена (*). Цепочка корня x2
имеет длину k. По формулам Виета имеем:
x1 + x2 + x3 = a1,
откуда
x3 = a1 – (x1 + x2) = a1 – 2a.
Элементы a1, a принадлежат полю Pk – 1, и, следовательно, x3 ∈ Pk – 1, т. е.
цепочка у корня x3 короче минимальной. Полученное противоречие означает,
что самая короткая цепочка в действительности состоит из одного звена – поля
P, и соответствующий корень принадлежит полю коэффициентов. Утверждение
доказано.
Сделаем одно замечание о приведённом доказательстве. По существу, в
нём речь шла о числе квадратных корней в записи корней многочлена, а рассуждение Вантцеля означает, что символ квадратного корня или вообще не появляется в выражении для корня многочлена или появляется в точности один раз.
ПРИМЕРЫ
ГЕОМЕТРИЧЕСКИХ
ЗАДАЧ,
СВОДЯЩИХСЯ
К
УРАВНЕНИЯМ,
Пьер Лоран Вантцель (Wantzell) (1814–1848) - французский математик, репетитор в Политехнической школе в Париже. Теорему о кубических уравнений Вантцель доказал в 1837 году.
1
299
НЕРАЗРЕШИМЫМ В КВАДРАТНЫХ РАДИКАЛАХ.
Под названием “классические за-
дачи” имеют в виду следующие проблемы:
– построить с помощью циркуля и линейки ребро куба, объем которого в
два раза больше данного (задача об удвоении куба);
– с помощью циркуля и линейки разделить угол на три равные части (задача о трисекции угла);
– построить с помощью циркуля и линейки квадрат, площадь которого
равна площади данного круга (задача о квадратуре круга);
– разделить окружность на n равных частей (задача о построении правильного многоугольника).
В истории человечества немного задач, проверенных временем так, как
проверены «классические задачи».
Решение этих задач на построение в течение многих столетий безуспешно
пытались получить как профессионалы, так и математики-любители.
В восемнадцатом веке число таких любительских «решений», представляемых в Парижскую академию наук превысило пределы разумного, и академия приняла постановление «...Отныне и впредь не рассматривать представляемых решений задач удвоения куба, трисекции угла, квадратуры круга»1.
Постановление академии, впрочем, было поспешным: до окончательного
решения задач об удвоении куба и трисекции угла должно было пройти еще
более полувека, а задаче о квадратуре круга предстояло оставаться нерешенной еще более ста лет.
С помощью своей теоремы П. Вантцель в той же работе 1837 года получил
решение трех из четырех классических задач на построение c с помощью циркуля и линейки.
Удвоение куба. Длину ребра данного куба можно считать единичной, и
задача об удвоении куба сводится к построению отрезка
1
Решения и постановления Парижской академии наук, 1775 г.
300
3
2 . Непосредст-
венной проверкой можно убедиться, что многочлен x3 - 2 не имеет рациональных корней, и поэтому по теореме
Вантцеля з а д а ч а о б у д в о е н и и к у б а с
помощью
циркуля
и
линейки
неразрешима.
Трисекция угла. В задаче о трисекции угла требуется с помощью циркуля и линейки разделить данный угол на три равные части, т. е. построить трисектрису. Для некоторых частных случаев такое построение возможно. Например, чтобы разделить на три части угол в 180°, нужно построить угол в 60°,
а это угол при вершине правильного треугольника.
Чтобы разделить угол в 90°, нужно построить
угол в 30°, а для этого достаточно угол в 60° разделить пополам. Аналогичным образом произойдет
180o
трисекция угла в 45°, 22,5° и вообще угла n (где
2
n - любое натуральное число).
Возможно, что своему возникновению задача
обязана прямой аналогии с делением отрезка на равные части, тем более, что деление отрезка пополам и построение биссектрисы
угла очень похожи. Деление отрезка на три равные части не представляет никаких трудностей - так же легко разделить отрезок и на n
частей. По-
видимому, первоначально задача с делением угла была задачей общего вида –
разделить угол на n частей, но непреодолимые трудности возникли уже при
n = 3.
Будем считать, что нам даны два отрезка – единичный (на рисунке – это
отрезок OA) и отрезок a = AC, равный cos 3α. Задача о трисекции угла сводится к построению отрезка x, равного cos α (на рисунке x = BC).
Тогда
301
cos3 α = 4 cos 3 α − 3 cos α,
и соответсвенно возникает уравнение для x:
a = 4x3 – 3x.
Возможность построения трисектрисы теперь зависит от числа a. Например, при a = 0 (тогда 3α = 90°) корни уравнения можно построить с помощью
циркуля и линейки. Если a=
2
(тогда 3α=45°) построение тоже возможно.
2
1
Возьмем теперь угол, подлежащий трисекции, равным 60°, то есть a = .
2
Уравнение для x примет вид:
4 x3 − 3x −
1
= 0.
2
Это уравнение не имеет рациональных корней, и поэтому по теореме
Вантцеля ни один из корней этого не выражается через коэффициенты с помощью арифметических операций и извлечения квадратного корня. Следовательно, разделить угол в 60° с помощью циркуля и линейки невозможно, з а дача о трисекции угла с помощью циркуля и линейки в общем случае неразрешима.
Задача о квадратуре круга пользовалось исключительной популярностью в течение столетий, начиная с древнейших времен.
По условию задачи дан отрезок a, и требуется построить отрезок x такой,
что квадрат со стороной x имеет площадь, равную площади круга радиуса a.
Иначе говоря, нужно построить корень уравнения x2 = πa2.
302
Отрезок πa - это в точности половина длины окружности. Если бы удалось «распрямить» окружность с помощью циркуля и линейки, то есть построить отрезок 2πa, то разделить его пополам нетрудно.
Таким образом, задача о квадратуре круга – эта задача о спрямлении окружности, то есть построении отрезка, равного 2πa. При a = 1 эта длина составляет 2π.
Построение с помощью циркуля и линейки отрезка, равного π, означало
бы, что число π можно получить из числа 1 с помощью арифметических операций и извлечения квадратного корня.
Индукцией по числу квадратных корней в таком представлении (т. е. по
длине цепочки квадратичных расширений), получаем, что каждое число, которое можно получить из единицы с помощью арифметических операций и извлечения квадратного корня, является корнем многочлена с рациональными
коэффициентами.
Другими словами, ц и р к у л е м и л и н е й к о й п р и д а н н о м е д и н и ч н о м о т р е з к е м о ж н о п о с т р о и т ь л и ш ь а л г е б р а и ч е с к и е ч и с л а (да
и то далеко не все).
В 1882 году Ф. Линдеманн1 доказал, что число π - трансцендентно, и, следовательно, окружность не спрямляема с помощью циркуля и линейки: задача о квадратуре круга неразрешима.
В задаче о построении правильного n-угольника можно считать данным произвольный отрезок r, а искомым отрезок, равный стороне правильного
n-угольника, вписанного в окружность радиуса r.
Фердинанд Карл Луис Линдеманн (Lindemann, 1852–1939) – немецкий математик, профессор Кёнигсбергского (с 1883 г.) и Мюнхенского (с 1893 г.) университетов.
1
303
Пусть n = 7, т. е. рассмотрим сейчас задачу построе360o
ния правильного семиугольника. Пусть x = cos
.
7
Число x является корнем уравнения деления круга
x6 + x5 + x4 + x3 + x2 + x2 + 1 = 0.
Это возвратное уравнение и подстановкой y = x + 1 оно сводится к уравx
нению
x3 + 2x − 8x − 8 = 0.
Это уравнение (а, следовательно, и исходное) не имеет рациональных корней, поэтому, снова, применяя теорему Вантцеля, получаем, что задача о построении правильного с помощью циркуля и линейки семиугольника неразрешима.
Доказательство невозможности построения правильного семиугольника с
помощью циркуля и линейки было получено в 1796 году К. Гауссом1. Тогда же
он обнаружил, что с помощью циркуля и линейки м о ж н о п о с т р о и т ь п р а в и л ь н ы й с е м н а д ц а т и у г о л ь н и к - результат, как сам автор правильно
оценил, не уступающий по значимости классическим результатам древних.
В 1801 г. К. Гаусс полностью решил задачу о построении правильного
n-угольника, доказав, что правильный n-угольник можно построить с помощью циркуля и линейки тогда и только тогда, когда значение функции Эйлера
от n является степенью двойки, ϕ(n) = 2n.
Наивысшим достижением своей жизни Гаусс считал решение задачи о построении правильных
многоугольников особенности о возможности построения правильного 17-угольника. Этого достижение отражено и в памятнике К. Гауссу в Гёттингене; этот памятник располагается на семнадцатигранном цоколе.
1
304
Функция Эйлера от степени двойки снова является степенью двойки. Если
p - простое число, то ϕ(p) = p - 1. Таким образом, если простое число p = 2n + 1,
то ϕ(p) = 2n.
n
П. Ферма1. заметил, что числа Fn= 22 + 1 при n=0, 1, 2, 3, 4 являются простыми, и сделал предположение, что Fn простые для любого n. Пока неизвестно
ни одного простого числа Fn, кроме этих пяти.
Простое число вида 2n + 1 называется простым числом Ферма.
Правильный n-угольник можно построить с помощью циркуля и линейки
тогда и только тогда, когда n имеет вид:
n = 2k ⋅ p1 ⋅ p2 ⋅ ... ⋅ ps,
где ⋅p1⋅p2⋅...⋅ps - различные простые числа Ферма.
Если вдруг окажется, что существует лишь конечное число простых чисел
Ферма, то число правильных n-угольников с нечетным n тоже будет конечным. А если выяснится, например, что простых чисел Ферма всего пять, то таких n-угольников будет в точности 31.
Пьер Ферма (Pierre Fermat) (1601-1665) - французский юрист и математик-любитель. Научные результаты П. Ферма опубликованы его сыном в 1670 году в сборнике «Разные сочинения».
1
305
24. СИСТЕМА ЦЕЛЫХ НЕОТРИЦАТЕЛЬНЫХ ЧИСЕЛ. НЕПОЛНОТА
АРИФМЕТИКИ
Основные понятия: полукольцо, упорядоченность, вполне упорядоченность, условие индуктивности, условие обрыва убывающих цепей, условие
минимальности, метод математической индукции, аксиоматическая
теория, непротиворечивость, категоричность, полнота, независимость
аксиоматики, аксиомы Пеано, рекурсивная функция.
Основные факты: модель аксиом Пеано и тождеств Грассмана является линейно упорядоченным полукольцом; любая аксиоматическая теория,
содержащая арифметику, неполна.
АКСИОМАТИКА
АРИФМЕТИКИ.
Впервые и сразу удачно основные предло-
жения аксиоматической теории целых неотрицательных чисел были предложены в 1889 году Д. Пеано1.
В этой аксиоматике основное, то есть неопределяемое, понятие – это целое
неотрицательное число. Будем обозначать число буквами латинского алфавита,
а все множество целых неотрицательных чисел обозначим символом Z0.
Основных отношений в этой аксиоматике Пеано будет два: двухместное отношение S(x) (которое чуть позже мы сразу объявим функциональным отношением, то есть одноместной функцией, поэтому сразу авансом и выбрана функциональная запись для отношения) и одноместное отношение, состоящее из одного элемента (назовем этот элемент «нулем» и обозначим символом 0).
Элементы x и S(x), связанные отношением следования имеют особые названия. S(x) принято называть «последователем элемента x» , а x - «предшественником элемента S(x)».
Теперь осталось написать основные предложения об основных отношений,
то есть выписать аксиомы.
В первоначальном авторском изложении аксиом Пеано было пять:
306
1) нуль является натуральным числом;
2) каждое натуральное число обладает последователем;
3) нуль не является последователем никакого натурального числа;
4) числа, имеющие одинаковых последователей, равны;
5) множество, содержащее нуль и вместе с каждым числом его последователь, содержит все натуральные числа.
Первая аксиома утверждает, что нуль – это одноместное отношение, а четвертая, - что отношение S является функцией.
Таким образом, объявив заранее, что нуль – одноместное отношение, а S одноместная функция (назовем ее функцией следования), можно ограничиться
всего тремя аксиомами (которые обычно и называют аксиомами Пеано):
1) у нуля нет предшествующего;
2) функция следования разнозначна;
3) множество, содержащее нуль и вместе с каждым элементом x элемент
S(x), содержит все натуральные числа.
Множество всех логических следствий аксиом Пеано принято называть
арифметикой.
ЭЛЕМЕНТАРНОСТЬ
АРИФМЕТИКИ.
Формулы алгебры предикатов, кванторы
которых навешены только на символы переменных, называют элементарными,
а теорию, состоящую из элементарных формул - элементарной теорией. Правила вывода сохраняют элементарность, поэтому теория элементарна, если ее
аксиомы – элементарные формулы.
Навесив квантор на предикат, мы получим пример не элементарной формулы. Например, предложение, начинающееся словами «для каждого свойства
элементов ... » или «для каждого подмножества», не является элементарным.
Обозначим множество целых неотрицательных чисел символом Z0, а нуль
- знаком 0.
Джузеппе Пеано (Peano,1856–1932) - итальянский математик, с 1890 г. профессор Туринского университета.
1
307
Первая аксиома Пеано является элементарной формулой:
(∀x)[x ≠ S(x)].
Вторая аксиома тоже элементарна:
(∀x) (∀y)[S(x) = S(x) → x = y].
Последнюю, третью аксиому принято называть аксиомой индукции. Аксиома индукции означает, что для каждого подмножества M из Z0 если:
1) нуль принадлежит M,
2) из того, что x принадлежит M, следует, что и следующий, то есть S(x),
тоже принадлежит M,
то множество M совпадает с Z0.
Другими словами, третья аксиома утверждает, что любое целое неотрицательное число непременно содержится в последовательности
S(0), S((0)), S(((0))), ... .
Множества описываются с помощью предикатов: M={x P(x)}. Правда, все
подмножества множества натуральных чисел так описать невозможно (множество предикатов лишь счетно, а множество подмножеств множества Z0 несчетно), поэтому если в аксиоме индукции вместо слова «множество» говорить:
«свойство элементов» (то есть «предикат»), то мы получим более слабое, чем
аксиома индукции, утверждение:
(∀P) [[P(0) & (∀x) [P(x) → P(S(x))]] →(∀x)P(x)],
308
означающее, что если нуль обладает свойством P и за каждым элементом, обладающим свойством P, следует элемент тоже со свойством P, то свойством P
обладают все элементы.
Даже ослабленная аксиома индукции не является элементарным предложением: там есть квантор, навешенный на предикат.
Таким образом, аксиома индукция является не элементарной формулой.
Однако множество одноместных предикатов всего лишь счётно, и если
P1(x), P2(x), …, Pi(x), …
– это все одноместные предикаты, то аксиому индукции можно заменить
бесконечной серией элементарных аксиом вида:
[Pi(0) & (∀x) [Pi(x) → Pi (S(x))]] →(∀x) Pi (x).
С таким договором арифметика превращается в элементарную (но бесконечно аксиоматизируемую) теорию.
НЕЗАВИСИМОСТЬ
АКСИОМАТИКИ
ПЕАНО. Самыми важными вопросами об
арифметике будут следующие: является ли арифметика непротиворечивой? категоричной? полной? разрешимой? И, наконец, вопрос, имеющий наименьшую
теоретическую значимость: является ли система аксиом Пеано независимой.
К сожалению, вполне строго можно ответить лишь на этот последний, не
главный вопрос. Ответ утвердительный: да, с и с т е м а а к с и о м П е а н о н е зависима.
Независимость какой-либо аксиомы означает, что для нее не существует
доказательства, опирающегося на оставшиеся аксиомы.
309
Покажем, что первая аксиома не зависит от остальных, т. е. сколько бы не
получали логических следствий из второй и третьей аксиомы, никогда не получится теорема: у нуля нет предшествующего.
Для этого укажем модель, на которой вторая и третья аксиома выполняются, а третья аксиома не выполняется. Тогда на модели верны все логические
следствия из второй и третьей аксиомы и предположение о том, что среди следствий есть и аксиома один сразу приводит к противоречию. Пусть множество
Z1 состоит из двух элементов,
Z1={0, a},
а функция следования S задана правилами:
S(0) = a, S(a) = 0.
Вторая и третья аксиомы здесь выполняются, а первая – нет, значит, первая
аксиома Пеано не выводится из двух оставшихся.
Покажем, что вторая аксиома не выводится логически и первой и третьей.
Теперь возьмем множество Z2 из трех элементов,
Z2 = {0, a, b},
а функцию следования S зададим правилами:
S(0) = a, S(a) = b, S(b) = a.
Функция S здесь не разнозначна, она принимает одно и то же значение в
различных точках: S(0)=S(b). Первая аксиома выполняется: у элемента 0 нет
предшествующего, выполняется и третья аксиома: двигаясь от нуля согласно
310
функции следования, получим все множество модели. Итак, вторая аксиома
Пеано не является следствием двух оставшихся.
Первые две модели были конечными, чтобы убедиться в их существовании,
не нужно никаких вспомогательных теорий.
Теперь нам надо привести модель, на которой выполняются первая и вторая
аксиома. Независимо, будет там выполняться третья аксиома или нет, можно
заранее сказать: эта модель должна быть бесконечной. Действительно, функция S является по второй аксиоме взаимно однозначным отображением множества модели в себя. Первая аксиома означает, что образ множества при этом
отображении является собственным подмножеством множества модели. Следовательно, если выполняются первая и вторая аксиомы, то множество равномощно своему собственному подмножеству.
Таким образом, третья модель строится существенно на теоретикомножественной основе: если аксиоматическая теория множеств непротиворечива, то третья аксиома не зависит от двух первых. Построение системы рациональных чисел будет Q проводится на основе теории натуральных чисел, но
без использования того факта, что третья аксиома не выводится из остальных,
поэтому при построении третьей модели можно воспользоваться системой Q.
Пусть множество модели Z3 состоит из нуля, единицы и рациональных чисел вида
n
,
n +1
где n ∈{1, 2, 3, ... },
Z3={0,
1 2 3
, , , ... , 1}.
2 3 4
Действие функции следования будем считать уже заданной в записи множества Z3:
1
2
3
2
1
S(0)= , S ( ) = , S ( ) =
2
2
3
3
4
311
и так далее. Первая аксиома в этой модели выполняется: у нуля нет предшествующего. Вторая аксиома тоже выполняется: функция следования разнозначна. Третья аксиома не выполняется. В самом деле, пусть множество M=Z3\{1}.
Тогда посылка аксиомы индукции выполнена: 0∈M и
x∈M ⇒ S(x)∈M,
а заключение - нет: M≠Z3.
Итак, третья аксиома Пеано не зависит от остальных.
Третья аксиома, аксиома индукции, играет особую роль в теории целых неотрицательных чисел. Доказательство, использующее аксиому индукции, называют методом математической индукции.
МЕТОД МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ. Предположим, что нам надо доказать теорему, имеющую вид утверждения: некоторыми свойством P обладают
все целые неотрицательные числа: (∀x) P(x). Докажем это, используя аксиому
индукции (а, точнее ее частный случай для предиката P):
[P(0) & (∀x )[P(x ) → P(S (x ))] ] → (∀x )(P(x )) .
Посылка аксиомы состоит из двух утверждений.
Первое: свойством P обладает самый первый элемент нашего множества:
P(0) – истинно.
Второе утверждение посылки аксиомы индукции говорит о том, что если
свойством P обладает элемент натуральное число x, то и число, следующее за
ним, т. е. S(x), тоже должно обладать этим свойством.
Следовательно, если будет установлена посылка аксиомы индукции, с помощью правила отделения
312
будет получено доказываемое утверждение.
Проверку истинности утверждения теоремы для первого элемента принято
называть базой (или базисом, или основанием) индукции.
Второе утверждение посылки аксиомы индукции говорит о том, что если
свойством P обладает элемент натуральное число n, то и следующее за ним, т.
е. S(n), тоже должно обладать таким свойством.
Если мы обозначим элемент S(n) символом n + 1, то это утверждение выглядит следующим образом:
(∀x)[P(n) → P(n + 1)]
(*)
Доказательство утверждения (*) принято называть шагом индукции (или индуктивным переходом), а само утверждение об истинности P(n) называют индуктивным предположением (или индуктивной гипотезой).
Истинность утверждения
(∀x) [P(n) → P(n + 1)]
означает, что всегда, когда истинно высказывание P(n), будет истинно и
P(n + 1), или, другим словами, предикат P(n + 1) является логическим следствием предиката P(n):
P(n) ⇒ P(n+1).
313
Символ ⇒ – «логическое следствие» - это знак отношения между предикатами. В таком виде обычно и записывают шаг индукции, то есть шаг состоит в
движении вдоль символа логического следствия: ⇒.
Напомним, что метод математической индукции и метод полной индукции
– это не одно и тоже. Методом полной индукции называют полный разбор случаев. Если теорема имеет вид высказывания
(∀x∈M)P(x),
а множество M можно представить в виде объединения (не обязательно непересекающихся) подмножеств:
M = M1 ∪ M2 ∪ ... ∪ Mn,
то утверждение теоремы равносильно следующему:
(∀x∈M1)P(x) & (∀x∈M2)P(x) & ... & (∀x∈Mn)P(x).
Такое разбиение предложения на n более мелких утверждений и есть метод
полной индукции
Метод математической индукции использует аксиому индукции и применяется только для счётных множеств.
Счетное множество, для которого происходит доказательство по индукции это не обязательно множество натуральных чисел в привычной для нас интерпретации, то есть множество N = {1, 2, .. , n, n+1,...}. Доказательство по индукции можно провести для любой модели Пеано.
Например, для целых неотрицательных чисел Z0 если:
1) P(0) – истинно;
2) P(n) ⇒ P(n + 1),
314
то свойством P обладают все целые неотрицательные числа,
В качестве модели Пеано можно взять, например, множество неотрицательных четных чисел M = {0, 2, 4, ...}. Тогда доказательство по индукции для множества M опирается на следующее утверждение (интерпретацию аксиомы индукции). Свойством P обладают все неотрицательные четные числа, если:
1) P(0) – истинно;
2) P(n) ⇒ P(n + 2).
Число n + 2 – это четное число, следующее за числом n.
Может случиться, что свойством P обладают натуральные числа, начиная с
числа k. Тогда доказательство этого факта методом математической индукции
будет использовать модель Пеано на множестве {k, k + 1, k + 2, ...}.
Итак, метод математической индукции – это доказательство утверждения о
свойстве элементов модели Пеано, опирающееся на третью аксиому – аксиому
индукции (или на равносильные ей утверждения).
УТВЕРЖДЕНИЯ, РАВНОСИЛЬНЫЕ УСЛОВИЮ ИНДУКТИВНОСТИ. Говорят, что
в линейно упорядоченном множестве