FN_Alg19 (Лекции 2009), страница 3

. . ,который как показано, сходится к a + b. Сгруппировав в последнем ряде слагаемые парами, мыпридем к заключению теоремы 19.5.ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12a + b + 0 + 0 + 0 + ...,ÌÃÒÓÌÃÒÓn=1ÌÃÒÓsup Sl (xn ) = Sl (sup xn ).Поскольку в случае идемпотентного полукольца точная верхняя грань последовательности естьсумма ряда членов этой последовательности, приходим к следующей интерпретации непрерывности сложения:∞∞XX(xn + a) =xn + a.ÌÃÒÓÌÃÒÓÌÃÒÓ57Теорема 19.5 может рассматриваться не только с точки зрения бесконечной коммутативности.

Рассмотрим функцию Sl (x) = x + a. Эта функция удовлетворяет условию x1 6 x2 ⇒Sl (x1 ) 6 Sl (x2 ), т.е. эта функция оказывается монотонной. Точно так же монотонна и функция*Sr (x) = a + x. Об этом свойстве говорят как о монотонности сложения по своим аргументам. Оказывается, что сложение является и непрерывной по своим аргументам.Действительно, непрерывность функции Sl (x) означает, чтоn=1n=1Заменив элемент a в правой части рядом с одинаковыми слагаемыми a, придем к утверждению,вытекающему из теоремы 19.5.Итак, утверждение теоремы 19.5 можно рассматривать как обобщение свойства непрерывности сложения по своим аргументам. Отметим, что умножение в общем случае таким свойствомне обладает.ÔÍ-12ÔÍ-12ÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓ19.

ПОЛУКОЛЬЦАÔÍ-12И БУЛЕВЫ АЛГЕБРЫ ÌÃÒÓ∞PУчитывая вид функции ma (x) и свойство sup xn =xn , свойство непрерывности умноженияn=1можно записать в виде∞∞XXaxn = axn .n=1n=1Теорема 19.7. Конечное идемпотентное полукольцо замкнуто.На самом деле функции Sl (x) и Sr (x) совпадают.ÔÍ-12ÌÃÒÓÔÍ-12*ÔÍ-12В таком виде непрерывность умножения можно рассматривать как свойство бесконечной дистрибутивности.Пример 19.3.

Полукольцо SA = 2A , ∪, ∩, ∅, A является замкнутым. В самом деле,операция объединения распространяется не только на счетное, а на любое семейство множеств,причем даже в этом случае пересечение остается дистрибутивным по отношению к сложению.Полукольцо S[a,b] = ([a, b], max, min, a, b) также замкнуто (его можно рассматривать какмодификацию предыдущего полукольца).ÌÃÒÓÔÍ-12sup ma (x) = ma (sup xn ).ÌÃÒÓÌÃÒÓЗамкнутое полукольцо — идемпотентное полукольцо, в котором любой ряд сходится, а умножение непрерывно по своим аргументам относительно естественного порядка полукольца. Непрерывность умножения, например, по второму аргументу означает, что функция ma (x) = axявляется непрерывной относительно естественного порядка полукольца, т.е.

для любой монотонной последовательности {xn }ÔÍ-12ÔÍ-12Замкнутое полукольцо — идемпотентное полукольцо, в котором любой ряд сходится, а умножение непрерывно относительно естественного порядка. Непрерывность умножения как бесконечнаяPдистрибутивность.Пример: конечное идемпотентое полукольцо замкнутое. Теорема:xn ym =PPP n∗xnym . Итерация x = x .=ÌÃÒÓÌÃÒÓ19.3. Замкнутые полукольцаÌÃÒÓn=1ряда могут принимать конечное число значений. Поэтому можно указать такой номер N , чтовсе значения встречаются среди первых N членов ряда.

Но тогдаНетрудно показать, что SN =NPi=1ai есть точная верхняя грань последовательности частичныхi=1сумм {Sn }. Таким образом, любой ряд в конечном идемпотентном полукольце сходится.Заменяя бесконечные суммы (ряды) конечными, легко свести свойство бесконечной дистрибутивности (неппрерывность умножения) к свойству обычной дистрибутивности. In,mn=1J Под суммой в равенстве слева можно понимать двойную суммуxn ym ,n=1 m=1равно как и сумму любой перенумерации двухиндексной последовательности (см. теорему 19.6).Используя свойство бесконечной дистрибутивности, получаем∞∞∞ ∞∞ X∞X X XX Xxnym =xnym=xn ym .Im=1n=1m=1n=1 m=1ÔÍ-12Для любого элемента x в замкнутом полукольце определена сумма∗2ÌÃÒÓnx = 1 + x + x + ... + x + ...

=∞Xxi ,i=0которую называют итерацией элемента x.Теорема: наименьшими решениями уравнений x = ax + b и x = xa + b в замкнутом полукольцеявляются x = a∗ b и x = ba∗ . Системы линейных уравнений. Теорема: если S — идемпотентное(замкнутое) полукольцо, то Mn (S) — идемпотентное (замкнутое) полукольцо. Наименьшее решениесистемы X = AX + B и X = XA + B в случае квадратных матриц. Применение к системам спрямоугольной матрицей B (в частном случае столбцом).

Метод Гаусса для линейных систем вполукольцах. Пример: система в U0,1 x1 = 0,5x1 + 0,4x2 + 0,2; x2 = 0,3x1 + 0,9x2 + 0,6.ÔÍ-12В полукольцах нельзя использовать теорию линейных систем в том же виде, как и в поляхи кольцах, поскольку операция сложения не имеет обратной. Однако некоторые виды системлинейных уравнений можно решать.Остановимся на простейших линейных уравнениях x = ax + b и x = xa + b. Несложноувидеть, что эти уравнения, как правило, имеют много решений. Однако можно поставитьвопрос о поиске наименьшего (или минимального) решения такого уравнения.ÌÃÒÓ19.4. Системы линейных уравнений в полукольцахÔÍ-12ÌÃÒÓÌÃÒÓm=1ÔÍ-12Теорема 19.8. Для любых двух последовательностей {xn } и {ym } в замкнутом полукольцевыполняется равенство∞∞X XXxn ym =xnym .n=1ÔÍ-12ÔÍ-12ai .ÌÃÒÓÌÃÒÓi=1NXÌÃÒÓÔÍ-12ai + aN +1 + .

. . + aN +p =∞ X∞XÌÃÒÓÌÃÒÓ58J Основная идея доказательства в том, что любой ряд в конечном полукольце фактически∞Pявляется конечной суммой. Действительно, в любом рядеan в конечном полукольце членыNXÔÍ-12ÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓ19. ПОЛУКОЛЬЦАÔÍ-12И БУЛЕВЫ АЛГЕБРЫ ÌÃÒÓÌÃÒÓЗначит, наименьшее решение xmin уравнения x = ax + b есть сумма этого ряда. Но∞Xn=0na b=∞Xan b = a∗ b.n=0Поэтому xmin = a∗ b. I(19.1)J Несложно увидеть, что для ряда∞PAk частичные суммы будут представлять собой матрицы,k=1(k)составленные из покомпонентных частичных сумм.

Пусть Ak = (aij ). Тогда Sm = A1 + . . . +ÔÍ-12Теорема 19.10. Если K — замкнутое полукольцо, то и Mn (K) — замкнутое полукольцо.ÌÃÒÓможно рассматривать как переход от скалярного уравнения x = ax+b к матричному уравнениюX = AX + B, где A — квадратная матрица порядка n, а X и B — матрицы-столбцы высотыn. Можно более широко трактовать матрицы X и B и рассматривать матричное уравнениеX = AX + B, в котором X и B есть матрицы, состоящие из k столбцов высоты n.Наиболее интересным оказывается случай уравнения X = AX + B, в котором все матрицыквадратные. Такое уравнение можно интерпретировать как скалярное уравнение в полукольцеквадратных матриц порядка n. Действительно, нетрудно показать, что множество Mn (K)квадратных матриц порядка n с элементами из данного полукольца K есть полукольцо.

Приэтом, если K идемпотентное полукольцо, то и Mn (K) — идемпотентное полукольцо.Как устроено отношение порядка в полукольце матриц? Равенство A+B = B, где A = (aij ),B = (bij ), означает, что aij +bij = bij , или aij 6 bij , для любых пар индексов i и j. Таким образом,неравенство A 6 B означает, что aij 6 bij , i, j = 1, n.ÔÍ-12Переход к системе линейных уравнений видаx1 = a11 x1 + a12 x2 + . . . + a1n xn + b1 ,x2 = a21 x1 + a22 x2 + . . .

+ a2n xn + b2 ,. . . . . . . . . . . . . . . . . . . .xn = an1 x1 + an2 x2 + . . . + ann xn + bnÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12Строго это равенство можно доказать методоминдукции. Из полученного n математическойравенства вытекает, что последовательность ϕ (0) есть последовательность частичных суммрядаb + ab + a2 b + . . . + an b + . . .ÌÃÒÓÌÃÒÓJ Рассмотрим уравнение x = ax + b. Для уравнения второго типа x = xa + b все рассужденияаналогичны.В основе доказательства — непрерывность функции ϕ(x) = ax + b в смысле естественногопорячдка полукольца. Эта функция есть композиция двух функций: y = ax и z = y + b.Непрерывность первой есть непрерывность умножения и диктуется определением замкнутогополукольца.

Непрерывность второй — это непрерывность сложения, установленная выше.Поскольку замкнутое полукольцо является индуктивным множеством, уравнение x = ϕ(x),определяемое непрерывной функцией ϕ(x), имеет наименьшее решение, равное точной верхнейграни последовательности ϕn (0), где ϕ1 (x) = ϕ(x), ϕk+1 (x) = ϕ(ϕk (x)), k ∈ N.В нашем случае ϕ(0) = b, ϕ2 (0) = ϕ(b) = ab + b, ϕ3 (0) = ϕ(ab + b) = a2 b + ab + b. Нетрудноуловить закономерность:ϕn (0) = an−1 b + an−2 b + . . . ab + b.ÌÃÒÓÔÍ-12Теорема 19.9.

В любом закнутом полукольце уравнение x = ax + b (x = xa + b) имеетнаименьшее решение xmin , причем xmin = a∗ b (xmin = ba∗ ).ÔÍ-12ÌÃÒÓÌÃÒÓ59ÌÃÒÓÔÍ-12ÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓ19. ПОЛУКОЛЬЦАÔÍ-12И БУЛЕВЫ АЛГЕБРЫ ÌÃÒÓÌÃÒÓ(m)ÌÃÒÓ60(m)Am есть матрица Sm = (sij ), составленная из частичных сумм sij рядов, составленных изэлементов матриц Ak с однаковым положением. Пусть матрица S = (sij ) состоит из сумм рядовsij =∞X(k)aij ,i, j = 1, n.k=1Тогда, во-первых, Sm 6 S, m ∈ N, так как это неравенство выполняется покомпонентно, аво-вторых, для любой матрицы S 0 = (s0ij ), удовлетворяющей условию Sm 6 S 0 , m ∈ N, для(m)каждой пары индексов i и j выполняются соотношения sij 6 s0ij .