Верещагин Н.К., Шень А. - Языки и исчисления (1076783), страница 24
Текст из файла (страница 24)
. , Qk ∈ Z[x, x1 , . . . , xn ] части пространства Rn , соответствующие различным значениям диаграммы, являются полуалгебраическими множествами. Начнём с такого очевидного наблюдения: еслиэто верно для какого-то набора Q1 , . . . , Qk , то это останется верными для любого меньшего набора. В самом деле, диаграмму меньшего семейства многочленов можно получить из диаграммы большего семейства: выкидывая многочлен, надо выбросить соответствующую строку, а также столбцы, которые соответствовали корнямэтого многочлена (если они не были корнями других многочленов).При выбрасывании столбца два окружающих его столбца сливаютсяв один.Поэтому мы имеем право для удобства расширить данный намнабор многочленов и доказывать полуалгебраичность частей длярасширенного набора.
Расширение будет состоять в замыкании относительно некоторых операций, которые мы сейчас опишем.Напомним ещё раз, что мы рассматриваем семейство многочленов из Z[x, x1 , . . . , xn ], которые разложены по степеням x, то естьзаписаны как многочлены от x с коэффициентами в Z[x1 , . . . , xk ].Рассмотрим следующие операции:106Языки первого порядка[гл.
3]• отбрасывание старшего члена (с наибольшей степенью переменной x); эта операция понижает степень (по x);• взятие старшего коэффициента (коэффициента при наибольшей степени переменной x); эта операция понижает степеньмногочлена (по x) до нуля;• дифференцирование по x; эта операция понижает степень многочлена (по x) на единицу;• взятие модифицированного остатка при делении одного многочлена на другой.Говоря о «модифицированном остатке», мы имеем в виду следующее. При делении «уголком» многочлена A на многочлен B с остатком нам неоднократно приходится делить на старший коэффициентмногочлена B. Поэтому в общем случае коэффициенты частного иостатка представляют собой дроби, в знаменателях которых стоятнекоторые степени старшего коэффициента многочлена B.Тем самым при вычислении остатка от деления A на B мы выходим за пределы кольца Z[x, x1 , . .
. , xn ]. Этого не случится, если старший коэффициент многочлена B равен единице. Но в общем случаемы должны принять какие-то меры, если хотим оставаться в указанном кольце. Меры эти состоят в следующем: прежде чем делитьA на B, мы умножаем A на старший коэффициент многочлена Bв достаточно большой степени. Если вспомнить процедуру деленияуголком, легко сообразить, что достаточно взять степень a − b + 1,где a и b — степени многочленов A и B (по переменной x). Например,при a = b требуется всего один шаг деления, и достаточно умножитьA на старший коэффициент многочлена B в первой степени.Итак, операция модифицированного остатка применима к любымдвум многочленам A, B ∈ (Z[x1 , .
. . , xn ])[x] степеней a и b (по x) идаёт третий многочлен этого кольца, который есть остаток от деления Aβ a−b+1 на B (здесь β — старший коэффициент многочлена B).Заметим, что степень этого многочлена меньше степени многочленаB. Мы будем предполагать, что a > b (иначе остаток совпадает сA и деление не даёт ничего нового). Таким образом, результат этойоперации имеет меньшую степень, чем оба операнда.Заметим, что понятие модифицированного остатка имеет смыслдля многочленов с коэффициентами из произвольного кольца (нетолько Z[x1 , . .
. , xn ]).[п. 8]Теорема Тарского – Зайденберга107Лемма 1. Для всякого конечного множества F многочленов из(Z[x1 , . . . , xn ])[x] существует его конечное расширение, замкнутое относительно указанных четырёх операций.Это утверждение верно для любого кольца коэффициентов и почти очевидно следует из того, что степень результата операции меньше степени (любого) операнда. Более формально рассуждать надотак. Рассмотрим выражения, составленные из элементов F с помощью четырёх указанных операций. Глубина такого выраженияне превосходит максимальной степени многочленов из F , поскольку каждая операция уменьшает степень. Поэтому таких выраженийконечное число, и их множество очевидным образом замкнуто относительно указанных операций.
Лемма 1 доказана.Доказанная лемма позволяет без ограничения общности считать,что данное нам конечное множество многочленов замкнуто относительно четырёх указанных выше операций.Лемма 2. Пусть F — некоторое конечное множество многочленовиз (Z[x1 , . . . , xn ])[x], замкнутое относительно перечисленных операций. Пусть F0 — его часть, состоящая только из многочленов степени0 по x (они представляют собой многочлены из Z[x1 , . . . , xn ]).
Тогдадиаграмма множества F при данных x1 , . . . , xn полностью определяется диаграммой множества F0 при тех же x1 , . . . , xn .Заметим, что диаграмма множества F0 имеет всего один столбец,указывающий, какие из многочленов положительны, какие отрицательны и какие равны нулю при данных x1 , . . . , xn . Поэтому различным вариантам диаграммы для множества F0 соответствуют полуалгебраические подмножества в Rn , и из леммы 2 следует, что те жесамые множества составят искомое разбиение для полной системыF . Таким образом, нам осталось лишь доказать лемму 2.Будем добавлять в множество F0 многочлены по одному, в порядке возрастания (неубывания) их степеней, пока не получим всёмножество F .
Достаточно показать, что на каждом шаге диаграммарасширенного множества (с новым многочленом) может быть однозначно восстановлена по диаграмме предыдущего множества. Мысейчас опишем, как это делается.Пусть добавляется многочлен P ∈ (Z[x1 , . . . , xn ])[x], при этоммногочлены всех меньших степеней из F уже есть в диаграмме. В силу замкнутости F старший коэффициент многочлена P содержитсяв F и, имея меньшую (нулевую) степень, уже представлен в диаграмме. (Соответствующая строка состоит из одинаковых знаков,так как он не зависит от x.) Если там стоят нули, то (при данных108Языки первого порядка[гл.
3]x1 , . . . , xn ) старший коэффициент равен нулю, и многочлен P совпадает с многочленом, получающимся при отбрасывании старшегочлена. Этот многочлен тоже есть в F и в диаграмме, так что надолишь продублировать соответствующую строку.Итак, достаточно рассмотреть случай, когда старший коэффициент многочлена P (при данных x1 , . . . , xn ) не равен нулю. Пополнение диаграммы включает в себя два шага: сначала мы должныопределить знаки многочлена P в точках (корнях), уже входящих вдиаграмму.
Затем надо пополнить диаграмму корнями многочленаP (при этом число столбцов в ней увеличится).Как найти знак многочлена P в одной из старых точек? По определению диаграммы в этой точке (обозначим её α) один из старыхмногочленов равен нулю. Пусть Q — такой многочлен. Можно считать, что старший коэффициент Q (как многочлена от x) отличенот нуля при данных x1 , .
. . , xn . Если это не так, заменим Q на многочлен, получающийся отбрасыванием старшего члена. Мы знаем,что множество F замкнуто относительно четырёх операций и чтовсе многочлены из F , имеющие меньшую степень, уже входят в диаграмму. Поэтому вся необходимая информация для отбора подходящего Q у нас есть.Кроме того, по тем же причинам нам известен знак старшегокоэффициента многочлена Q. Применим операцию модифицированного деления с остатком к P и Q:β s P = (частное) · Q + R(здесь β — старший коэффициент многочлена Q). Подставим в эторавенство число α. При этом Q обратится в нуль, так как α являетсякорнем Q по построению.
Многочлен R входит в диаграмму в силунаших предположений, так что его знак в точке α нам известен, каки знак β. Тем самым можно найти знак P (α).Итак, мы определили знак нового многочлена в старых корнях.Покажем, что этого достаточно, чтобы предсказать, на каких участках диаграммы появятся новые корни (многочлена P ). При этом нампригодится (пока что не использованная) операция дифференцирования.Если в двух соседних старых корнях α1 , α2 многочлен P имеетодин и тот же знак (скажем, положителен), то между ними нет нового корня. В самом деле, если бы на интервале (α1 , α2 ) многочленP обращался в нуль, то минимум многочлена P на [α1 , α2 ] достигался бы в некоторой внутренней точке, в которой производная P 0[п.
8]Теорема Тарского – Зайденберга109равнялась бы нулю. Но производная P 0 входит в множество F и представлена в диаграмме, так что тогда α1 и α2 не были бы соседнимикорнями диаграммы.Если в одной из точек α1 и α2 многочлен P обращается в нуль, тона интервале (α1 , α2 ) он корней иметь не может (по теореме Роллятакой корень повлёк бы за собой корень производной).Наконец, если P (α1 ) и P (α2 ) имеют разные знаки, то по теоремео промежуточном значении многочлен P имеет на интервале (α1 , α2 )хотя бы один корень.
При этом по уже понятным нам причинам (теорема Ролля) двух корней он иметь не может. Это позволяет вставитьстолбец для этого корня в диаграмму. При этом соответствующийинтервал диаграммы разобьётся на два, которые будут отличатьсялишь в строке для многочлена P .Осталось провести аналогичное рассуждение для лучей, стоящихс края диаграммы. Поведение многочлена P на бесконечности определяется его старшим коэффициентом (который, напомним, не равеннулю — сейчас мы впервые используем это предположение). Поэтомуесли P стремится, скажем, к +∞ при x → +∞, а значение P в самомправом корне было отрицательным, то на этом луче появляется новый корень (только один по теореме Ролля).
Если же значение P вса́мом правом корне равно нулю или имеет тот же знак, что и старший коэффициент, то мы повторяем рассуждение из предыдущегоабзаца и убеждаемся, что корней P на правом луче нет. Аналогичноопределяется и поведение P слева от са́мого левого корня.На этом доказательство леммы 2, а с ней и теоремы Тарского – Зайденбрега, завершается. 67. Докажите, что множество троек hp, q, ri, при которых многочленx3 + px2 + qx + r имеет ровно два положительных корня, является полуалгебраическим.Подобного рода задачи рассматривались в алгебре ещё в прошлом веке (число перемен знака, правило Штурма и др.).68. Докажите, что предикат x = α, где α — некоторое действительноечисло, выразим тогда и только тогда, когда α является алгебраическим(мы отмечали это на с.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
