Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Тогда
(s')(s") = e-(s)-(s)(s)* + (s)* = e.
Обратно, пусть (s') — ряд, в котором коэффициент при пустой цепочке равен единице кольца Q. Положим (s) = е — (s'), построим (s)*, как и выше, а затем положим (s") = е + (s)*.
Ряд (s") будет обратным для ряда (s'). Если Q — тело, то обращение возможно для всякого ряда, у которого коэффициент
') В самом деле, А-эквивалентность рядов означает совпадение всех их членов, являющихся цепочками длины <г; если обозначить через tr многочлен, состоящий из всех тех членов рядов Sn^, snr+i> — степени которых <г
(у всех этих рядов такие члены одинаковы), и положить (s) = lim (tn), то (s) =•
п-> оо
•= lim (sn). — Прим. ред.
П-Ї0О Гл. XVI. Алгебраические языки
255
при пустой цепочке отличен от нуля. В этом случае, в частности, всякий многочлен Q(X) из Q [А*], такой, что Q(O)=^O, обратим в Q [[A"*]]. Отсюда следует, что кольцо Q [[А*]] содержит все частные вида
Р(Х)'0Ш и ШУ'Р(Х)' ГДе Q(0) ^0,
образующие подмножество множества так называемых рациональных рядов.
Ряд (s)* называют квазиобратным для ряда (s).
16.1.9. Подстановки в формальных рядах
Пусть имеются алфавиты А" и У и ряд (t) є Q [[У*]]. Когда можно подставить в ряд (t) вместо каждого у^ некоторый ряд (Sj)SQP*]]?
Это возможно, в частности, если (t) — многочлен. Если (t) — ряд, то это возможно при условии, что ряды (Sj) квазирегулярны (убедиться в этом предоставляется читателю в качестве упражнения) .
Пример. Построение ряда (s)* сводится к подстановке ряда (s) в ряд
I- Y+ I- Y2+ ... +1-У"+ ....
16.1.10. п-ки формальных рядов
Пусть п — целое положительное число. Упорядоченные п-ки формальных рядов, принадлежащих Q [[A"*]], образуют пространство, в котором за расстояние между двумя я-ками можно принять сумму расстояний между их компонентами.
Поскольку многочлен — частный случай формального ряда, то факты, установленные при изучении формальных рядов, могут пролить свет на вопросы, относящиеся к композиции многочленов.
Вернемся к ситуации, описанной в п. 16.1.2. Для простоты мы будем говорить о парах рядов или многочленов, что не уменьшает общности рассуждений.
Пусть А и В — переменные, принимающие значения из Й [А"*]; пусть, кроме того, имеется отображение
.4-+0(.V1, .. ., хт, А, В),
В->x(xlt .. ., хт, А, В).
Это отображение индуцирует отображение множества ^[Ar*] в себя: точка М(Р, Q) переходит в точку
M (P', Q') = («г(je,.....xm, P,Q), X(X1.....xm, PtQ)).
Посмотрим, что произойдет при этом с расстоянием. Возьмем точки (/5J, Qx) и (P2, Q2). Расстояние между ними равно d(Pi,P2) + + d(Qi, Q2). Расстояние между их образами равно d[P\, P'^ + + d(Q[, Q'2). 256
Часть III. Алгебраический подход
Однако
d(Pu P2) = val (P2 - P1), d(P[, P2) = val (P2 - P\).
В то же время
Pr2-Prl = т(*„ ..., XmlP2, Q2)-a (xt, ..., Xm, Pv Q1).
В этой разности члены, не содержащие ни Р, ни Q, взаимно уничтожаются. Предположим, что в многочленах сг и т коэффициенты при цепочках е, А и В равны нулю («условие повышения степени»). Тогда нетрудно видеть, что порядок ряда
сг (Х[, . .., xm, P2, Q2) — сг (ху, . .., xm, Py, Q1)
будет больше минимума порядков рядов P2 — Q2 и Pi — Qi на некоторое целое число, зависящее только от сг.
Аналогичное утверждение справедливо для разности Q^ — Qj.
Поэтому расстояние между М[ и M2 получается из расстояния между My и M2 умножением на число К, строго меньшее единицы и зависящее только от сг и т:
d(Mry, Mr2) = U(My, M2), 0<А<1.
Таким образом, рассматриваемое отображение является стягивающим.
Мы воспользуемся этим результатом в п. 16.2.1.
16.1.11. Формальные ряды с коммутативными переменными
Ясно, что можно было бы построить аналогичную теорию, до пустив коммутативность образующих; тогда вместо X* мы рас сматривали бы свободную абелеву полугруппу с единицей над алфавитом X.
Всякому вычислению в Q [[^*]] соответствует вычисление, полученное в предположении коммутативности. Точнее, существует такой гомоморфизм кольца Q [[^*]], при котором всякая цепочка [еХ* отображается в соответствующий элемент свободной абе-левой полугруппы.
Пример. Пусть Q — кольцо целых чисел. Рассмотрим многочлен
f(x, у, а) = а + ху2
и будем итерировать его следующим образом: Y0 = Oe,..., Yn = f(x,Y^ua). Гл. XVI. Алгебраические языки
257
При некоммутативных неизвестных имеем Y0 = Oe, Y1 = а, Y 2 = а + ха2,
Y3 = a + X (a + xa2f = а + ха2 + хаха2 + х2а3 + х2а2ха2,
При коммутативных неизвестных получаем Y0 = Oe, Y1= а, Y2 = а + ха2,
Y3 = а +а2х + 2 а3х2 + а4х3,
§ 16.2. алгебраические ряды
16.2.0. О термине «алгебраический»
Пусть К — поле и К[х] — кольцо коммутативных многочленов над К. Рассмотрим уравнение
а0хп + ... +ап = 0,
не имеющее решения в К.
Обозначим через 0 новый элемент, удовлетворяющий данному уравнению; в этом случае /С[0] называется алгебраическим расширением поля К.
Пример. Рассмотрим поле рациональных чисел К и уравнение Jc2 — 2 = 0; можно ввести символ 0, такой, что 02 — 2 = 0. Отсюда следует, что
