Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


Замкнутые полукольца

Замкнутые полукольца


При изучении колец большое внимание было уделено полям. Связано это прежде всего с тем, что в полях разработана техника решения систем линейных уравнений. Оказывается, можно выделить специальный класс идемпотентных полуколец, в которых также удается находить решения систем уравнений, рассматриваемых в качестве аналогов систем линейных алгебраических уравнений.


Определение 3.2. Полукольцо [math]\mathcal{S}=(S,+,\cdot,\bold{0},\bold{1})[/math] называют замкнутым, если:


1) оно идемпотейтно;

2) любая последовательность элементов множества [math]S[/math] имеет точную верхнюю грань относительно естественного порядка [math]\leqslant[/math] этого идемпотентного полукольца;

3) операция умножения полукольца [math]S[/math] сохраняет точные верхние грани последовательностей, т.е. для любого [math]a\in S[/math] и любой последовательности [math]X=\{x_n\}_{n\in\mathbb{N}}[/math] элементов множества [math]S[/math] имеем


[math]a\sup X=\sup aX,\qquad (\sup X)a=\sup(Xa).[/math]

Замечание 3.1. Условие 3 определения 3.2 можно сформулировать иначе и говорить о сохранении точной верхней грани любого не более чем счетного подмножества множества [math]S[/math]. Однако в дальнейшем такие подмножества часто будут строиться как множества элементов некоторых последовательностей.


Кроме того, из элементов не более чем счетного множества всегда можно образовать последовательность, используя некоторую нумерацию этого множества.




Теорема 3.2. Любое конечное идемпотентное полукольцо замкнуто.


Поскольку носитель [math]S[/math] идемпотентного полукольца [math]\mathcal{S}= (S,+,\cdot, \bold{0}, \bold{1})[/math] есть конечное множество, то множество элементов любой последовательности в этом полукольце конечно. Для нахождения точной верхней грани такой последовательности нужно найти точную верхнюю грань множества [math]P=\{p_1, \ldots, p_n\}[/math] ее членов, т.е., согласно теореме 3.1, вычислить некоторую конечную сумму, которая всегда существует. Таким образом, в конечном идемпотентном полукольце любая последовательность имеет точную верхнюю грань.


Условия сохранения точных верхних граней имеют вид


[math]\begin{aligned}a(p_1+\ldots+p_n)&= ap_1+\ldots+ap_n\,,\\[2pt] (p_1+\ldots+p_n)a&= p_1a+\ldots+p_na\,. \end{aligned}[/math]

и выполняются в силу аксиом полукольца. Таким образом, полукольцо [math]\mathcal{S}[/math] замкнуто.



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


В силу этого в замкнутом полукольце естественно точную верхнюю грань последовательности [math]\{x_n\}_{n\in\mathbb{N}}[/math] называть суммой элементов последовательности, полагая, по определению,


[math]\sum\limits_{n=1}^{\infty}= \sup\{x_n\colon\, n\in\mathbb{N}\}.[/math]
(3.2)

Согласно условию 2 определения 3.2, всегда [math]\textstyle{\sum\limits_{n=1}^{\infty}x_n}[/math] есть элемент множества [math]S[/math]. Иногда, если это не приводит к недоразумению, "пределы суммирования" будем опускать и писать просто [math]\textstyle{\sum x_n}[/math]. Также будем использовать обозначение [math]\textstyle{\mathop{\sum\limits_{n\in\mathbb{N}}x_n}\limits^{.}}[/math]. Подчеркивая, что в (3.2) множество элементов [math]x_n[/math] в общем случае бесконечно, будем сумму, стоящую в левой части (3.2), называть бесконечной суммой. Заметим, что в частных случаях бесконечная сумма может свестись к конечной (если множество всех элементов последовательности [math]\{x_n\}[/math] конечно).


Итак, согласно определению 3.2, замкнутое полукольцо является индуктивным упорядоченным множеством, в котором наименьшим элементом служит нуль полукольца, точной верхней гранью произвольной (в частности, неубывающей) последовательности [math]\{x_n\}_{n\in \mathbb{N}}[/math] является бесконечная сумма [math]\textstyle{\sum x_n}[/math], причем операция умножения на произвольный фиксированный элемент а непрерывна в смысле определения 1.5, поскольку, согласно определению 3.2, сохраняет точные верхние грани. Заметим, что это свойство умножения в замкнутом полукольце можно рассматривать как аналог дистрибутивности (седьмой аксиомы полукольца, см. определение 3.1) для бесконечной суммы:


[math]a\sum x_n=\sum ax_n[/math] и [math]\left(\sum x_n\right)a= \sum x_na[/math].

Для бесконечной суммы также справедливы аналоги свойств идемпотентности и коммутативности.


Действительно, для последовательности [math]\{x_n\}_{n\in \mathbb{N}}[/math] такой, что [math]x_n=a[/math] для любого [math]n\in \mathbb{N}[/math], имеем [math]\textstyle{\sum x_n= \sup\{a\}=a}[/math], т.е. бесконечная сумма, все слагаемые которой одинаковы и равны некоторому [math]a[/math], равна [math]a[/math]. В этом состоит свойство идемпотентности бесконечной суммы (или, как иногда говорят, свойство бесконечной идемпотентности).


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


Сложнее обстоит дело с аналогом ассоциативности для бесконечной суммы. Такая ассоциативность означает, что результат не изменяется при произвольной группировке слагаемых бесконечной суммы.


Для некоторой последовательности [math]\{x_n\}_{n\in \mathbb{N}}[/math] элементов замкнутого полукольца и произвольной последовательности [math]\{n_k\}_{k\in \mathbb{N}}[/math] натуральных чисел образуем последовательность [math]\{s_k\}_{k\in \mathbb{N}}[/math], где


[math]\begin{aligned}&s_1= x_1+\ldots+x_{n_1},\\ &s_2= x_{n_1+1}+\ldots+x_{n_1+n_2},\\ &\cdots \cdots \cdots \cdots \cdots \cdots \cdots\\ &s_k= x_{n_{k-1}+1}+\ldots+x_{n_{k-1}+n_k},\\ &\cdots \cdots \cdots \cdots \cdots \cdots \cdots \end{aligned}[/math]

Тогда бесконечная ассоциативность состоит в выполнении для любой последовательности [math]\{x_n\}_{n\in \mathbb{N}}[/math] равенства


[math]\sum\limits_{n\in \mathbb{N}}x_n= \sum\limits_{k\in \mathbb{N}}s_k\,.[/math]
(3.3)

Свойство бесконечной ассоциативности (3.3) удобнее не доказывать непосредственно, а вывести из более общих результатов. Один из них касается характеристики замкнутых полуколец в терминах точных верхних граней счетных подмножеств.




Теорема 3.3. Идемпотентное полукольцо [math]\mathcal{S}= (S,+,\cdot, \bold{0}, \bold{1})[/math] замкнуто тогда и только тогда, когда любое счетное подмножество [math]X\subseteq S[/math] имеет точную верхнюю грань и для любого [math]a\in S[/math] верны равенства


[math]a\cdot\sup X=\sup(a\cdot X),\qquad (\sup X)\cdot a=\sup(X\cdot a).[/math]

Справедливость утверждения теоремы немедленно вытекает из определения точной верхней грани последовательности элементов упорядоченного множества как точной верхней грани множества этих элементов.


Теорема 3.4. Пусть [math]\mathcal{S}= (S,+,\cdot, \bold{0}, \bold{1})[/math] — замкнутое полукольцо, [math]X[/math] — не более чем счетное подмножество множества [math]S[/math], a [math](B_i)_{i\in I}[/math] — не более чем счетное семейство подмножеств множества [math]X[/math], такое, что объединение семейства совпадает с [math]X[/math], то есть [math]\textstyle{\mathop{\bigcup\limits_{i\in I}B_i=X}\limits^{\phantom{A}^{.}}}[/math]. Тогда


[math]\sup X=\sup\{\sup B_i,~ i\in I\}.[/math]
(3.4)

Поскольку множества [math]X[/math] и [math]I[/math] не более чем счетны, то, согласно определению 3.2, все точные верхние грани из (3.4) существуют и принадлежат [math]S[/math]. Обозначим левую часть равенства (3.4) через [math]a[/math], а правую — через [math]b[/math].


Так как [math]a[/math] есть точная верхняя грань множества [math]X[/math], то для любого [math]x\in X[/math] справедливо неравенство [math]x\leqslant a[/math] (где [math]\leqslant[/math] — естественный порядок идемпотентного полукольца [math]S[/math]). В частности, для любого подмножества [math]B_i[/math] и любого его элемента [math]y[/math] получаем [math]y\leqslant a[/math], откуда следует, что элемент [math]a[/math] есть верхняя грань каждого подмножества [math]B_i[/math]. Значит, этот элемент не меньше чем точная верхняя грань каждого из этих подмножеств, т.е. для любого [math]i\in I[/math] имеем [math]a\geqslant\sup B_i[/math]. Последнее означает, что [math]a[/math] есть верхняя грань множества всех точных верхних граней [math]\sup B_i,~i\in I[/math], то есть [math]a\geqslant b[/math].


В то же время, поскольку объединение всех подмножеств [math]B_i[/math] равно [math]X[/math], для любого [math]x\in X[/math] найдется такое [math]i\in I[/math], что [math]x\in B_i[/math]. Поэтому [math]x \leqslant\sup B_i\leqslant b[/math], это означает, что элемент [math]b[/math] является верхней гранью множества [math]X[/math], и тогда [math]b\geqslant a[/math], так как а есть точная верхняя грань [math]X[/math].


Итак, [math]a\geqslant b[/math] и [math]b\geqslant a[/math], откуда [math]a=b[/math], и равенство (3.4) доказано.




Следствие 3.1. Если семейство подмножеств из теоремы 3.4 [math](B_i)_{i\in I}[/math] конечно, т.е. [math]I=\{1,2,\ldots,n\}[/math], то


[math]\sup X=\sum\limits_{i=1}^{n}B_i\,.[/math]

Следствие 3.2. Пусть [math]\{x_n\}_{n\in\mathbb{N}}[/math] — произвольная последовательность элементов замкнутого полукольца и [math](N_i)_{i\in I}[/math] — не более чем счетное семейство подмножеств [math]\mathbb{N}[/math], такое, что [math]\textstyle{\mathop{\bigcup\limits_{i\in I}N_i= \mathbb{N}}\limits^{\phantom{A}^{.}}}[/math]. Тогда


[math]\sum\limits_{n\in\mathbb{N}}x_n= \sum\limits_{i\in I}s_i\,.[/math], где [math]s_i=\sum\limits_{m\in N_i}x_m[/math].

В частности, из следствия 3.2 при условии, что множества [math]N_i,~i\in I[/math], попарно не пересекаются, получаем свойство ассоциативности бесконечной суммы (3.3). Отсюда же при [math]N_1=\{1\},[/math] [math]N_2=\{1;2\}[/math] и т.д., т.е. при определении для любого натурального [math]k[/math] множества [math]N_k[/math] в виде [math]N_k= N_{k-1}\cup \{k\}[/math], получаем равенство


[math]\sum\limits_{n\in\mathbb{N}}x_n= \sum\limits_{n\in\mathbb{N}}(x_1+x_2+\ldots+x_k).[/math]
(3.6)

т.е. точная верхняя грань последовательности [math]\{x_n\}_{n\in\mathbb{N}}[/math] равна точной верхней грани последовательности частичных сумм [math]\{s_k\}_{k\in\mathbb{N}}[/math], где [math]s_k=x_1+\ldots+x_k[/math].


Пусть [math]\{x_n\}_{n\in\mathbb{N}}[/math] и [math]\{y_m\}_{m\in\mathbb{N}}[/math] — произвольные последовательности в замкнутом полукольце [math]\mathcal{S}[/math]. Образуем последовательность, членами которой являются все произведения [math]x_ny_n[/math] при независимом пробегании индексами [math]n[/math] и [math]m[/math] множества натуральных чисел. Эту последовательность будем записывать как [math]\{x_ny_m\}_{n,m\in\mathbb{N}}[/math], а ее точную верхнюю грань обозначим как [math]\textstyle{\mathop{\sum\limits_{n,m\in \mathbb{N}} x_n y_m}\limits^{\phantom{A}^{.}}}[/math].




Теорема 3.5. В любом замкнутом полукольце верно тождество


[math]\sum\limits_{n,m\in \mathbb{N}} x_n y_m= \Bigl(\sum\limits_{n\in \mathbb{N}}x_n \Bigr)\cdot \Bigl(\sum\limits_{m\in \mathbb{N}}y_m\Bigr).[/math]

Ввиду непрерывности умножения в замкнутом полукольце правую часть тождества (3.7) можно переписать в виде


[math]\Bigl(\sum\limits_{n\in \mathbb{N}}x_n \Bigr)\cdot \Bigl(\sum\limits_{m\in \mathbb{N}}y_m\Bigr)= \sum\limits_{m\in \mathbb{N}} \Bigl(\sum\limits_{n\in \mathbb{N}}x_n\Bigr)y_m\,.[/math]

Еще раз используя непрерывность умножения и внося сомножитель [math]y_m[/math] под знак внутренней суммы, получаем


[math]\sum\limits_{m\in \mathbb{N}} \Bigl(\sum\limits_{n\in \mathbb{N}}x_n\Bigr)y_m= \sum\limits_{m\in \mathbb{N}} \Bigl(\sum\limits_{n\in \mathbb{N}}x_n y_m \Bigr).[/math]

В правой части последнего равенства каждое слагаемое внешней суммы (по [math]m[/math]) есть точная верхняя грань подпоследовательности [math]\{x_ny_m\}_{n\in\mathbb{N}}[/math] и фиксированном [math]m[/math]. Поскольку все эти подпоследовательности в совокупности дают всю последовательность [math]\{x_ny_m\}_{n,m\in\mathbb{N}}[/math], то, согласно следствию 3.2, получаем


[math]\sum\limits_{m\in \mathbb{N}} \Bigl(\sum\limits_{n\in \mathbb{N}}x_n y_m \Bigr)= \sum\limits_{n,m\in \mathbb{N}}x_n y_m\,,[/math]
что и доказывает тождество (3.7).



Связь между конечной и бесконечной суммами


Следующая теорема устанавливает связь между конечной и бесконечной суммами.


Пусть [math]\{x_n\}_{n\in\mathbb{N}}[/math] и [math]\{н_n\}_{n\in\mathbb{N}}[/math] — произвольные последовательности в замкнутом полукольце [math]\mathcal{S}[/math]. Образуем последовательность [math]\{x_n+y_n\}_{n\in\mathbb{N}}[/math], называемую суммой исходных последовательностей.


Теорема 3.6. В любом замкнутом полукольце точная верхняя грань суммы двух произвольных последовательностей равна сумме точных верхних граней этих последовательностей, т.е.


[math]\sum(x_n+y_n)= \sum x_n+\sum y_n\,.[/math]

Обозначим через [math]X[/math] множество всех членов последовательности [math]\{x_n\}_{n\in \mathbb{N}}[/math], а через [math]Y[/math] — множество всех членов последовательности [math]\{y_n\}_{n\in \mathbb{N}}[/math]. В силу следствия 3.2


[math]\sup(X\cup Y)= \sup X+\sup Y= \sum x_n+\sum y_n\,.[/math]
Осталось тогда доказать, что
[math]\sum(x_n+y_n)= \sup(X\cup Y).[/math]
(3.9)

Обозначим через [math]a[/math] левую, а через [math]b[/math] правую часть доказываемого равенства (3.9). Для любого натурального [math]n[/math] имеем [math]a \geqslant x_n+y_n[/math]. Согласно теореме 3.1, [math]x_n+y_n\geqslant x_n[/math] и [math]x_n+y_n\geqslant y_n[/math]. Следовательно, для любого [math]n[/math] выполняются неравенства [math]a\geqslant x_n[/math] и [math]a\geqslant y_n[/math], то есть [math]a\geqslant u[/math] для любого [math]u\in X\cup Y[/math]. Таким образом, элемент [math]a[/math] является верхней гранью множества [math]X\cup Y[/math], откуда [math]a \geqslant b[/math].


В то же время элемент [math]b[/math] не меньше любого из элементов множества [math]X\cup Y[/math], и, стало быть, для любого натурального [math]n[/math] имеет место [math]b\geqslant x_n[/math] и [math]b\geqslant y_n[/math], то есть [math]b \geqslant \sup\{x_n,y_n\}= x_n+y_n[/math]. Это значит, что [math]b[/math] есть верхняя грань последовательности [math]\{x_n+y_n\}_{n\in \mathbb{N}}[/math], а потому [math]b\geqslant a[/math].


Итак, [math]a=b[/math], и равенство (3.9) доказано.




Если в (3.8) [math]y_n=a[/math] для всех [math]n[/math], то получаем следствие.


Следствие 3.3. Для любой последовательности [math]\{x_n\}_{n\in \mathbb{N}}[/math] элементов замкнутого полукольца и любого элемента [math]a[/math] этого полукольца выполняется равенство


[math]a+\sum x_n= \sum(a+x_n).[/math]
(3.10)

Тождество (3.10) можно рассматривать как свойство непрерывности операции сложения в замкнутом полукольце. Это свойство совершенно аналогично свойству непрерывности операции умножения, которое имеет место по определению.


Одним из важнейших понятий в замкнутых полукольцах является понятие итерации (или замыкания) элемента замкнутого полукольца. Итерация [math]x^{\ast}[/math] элемента [math]x[/math] определяется как точная верхняя грань последовательности всех степеней элемента [math]x[/math], то есть


[math]x^{\ast}= \sum\limits_{n=0}^{\infty}x^n,[/math] где, по определению, [math]x^0=1[/math], а [math]x^n=x^{n-1}x,~ n=1,2,\ldots[/math].



Пример 3.5. а. Из теоремы 3.2 сразу получаем, что идемпотентное полукольцо [math]\mathcal{B}[/math] (см. пример 3.2) замкнуто, причем точная верхняя грань любой последовательности элементов этого полукольца равна 1, если хотя бы один ее член равен 1, и равна 0 в противном случае. В частности, итерация любого элемента полукольца [math]\mathcal{B}[/math] равна 1. Для [math]1^{\ast}[/math] это очевидно, а для [math]0^{\ast}[/math] имеем


[math]0^{\ast}= 0^0+0^1+\ldots+0^k+\ldots= 1+0+\ldots+0+\ldots=1.[/math]

б. В идемпотентном полукольце [math]\mathcal{R}^{+}[/math] (см. пример 3.1) любая последовательность есть последовательность неотрицательных действительных чисел. Такая последовательность ограничена снизу и, как известно из курса математического анализа, имеет точную нижнюю грань относительно естественного числового порядка, которая, согласно примеру 3.4, представляет собой точную верхнюю грань относительно естественного порядка идемпотентного полукольца [math]\mathcal{R}^{+}[/math]. Напомним, что этот порядок является двойственным к естественному числовому порядку.


Итак, для любой последовательности [math]x_n[/math] элементов полукольца [math]\mathcal{R}^{+}[/math] точная верхняя грань существует. Непрерывность операции умножения в этом полукольце также можно доказать, опираясь на естественный числовой порядок, для которого она эквивалентна выполнению равенства


[math]a+\inf X=\inf X_{a}\,,[/math]
(3.11)

где [math]a[/math] — неотрицательное действительное число, а [math]X[/math] (соответственно [math]X_a[/math]) — множество элементов последовательности [math]x_n[/math] (соответственно [math]x_n+a[/math]). Равенство (3.11) следует из известных результатов математического анализа.


Таким образом, рассматриваемое идемпотентное полукольцо [math]\mathcal{R}^{+}[/math] является замкнутым.


Итерация [math]x^{\ast}[/math] элемента [math]x[/math] в полукольце [math]\mathcal{R}^{+}[/math] есть точная верхняя грань последовательности степеней элемента [math]x[/math]. Поскольку в этом полукольце операция умножения определена как операция сложения действительных чисел, то [math]x^0=0[/math], так как число 0 есть единица полукольца [math]\mathcal{R}^{+}[/math]. Далее, [math]x^2=x+x=2x,\ldots[/math] [math]x^n=nx[/math]. Очевидно, что для каждого [math]n\geqslant 0[/math] выполняется неравенство [math]x^n\geqslant 0[/math] в смысле естественного числового порядка. Таким образом, число 0 есть наименьший в смысле естественного числового порядка член последовательности [math]\{x_n\}_{n\in \mathbb{N}}[/math] и, следовательно, [math]\inf\{x_n\}_{n\in \mathbb{N}}=0[/math]. Переходя к двойственному порядку — естественному порядку полукольца [math]\mathcal{R}^{+}[/math], получим, что число 0 является точной верхней гранью последовательности [math]\{x_n\}_{n\in \mathbb{N}}[/math], то есть [math]x^n=0[/math]. Таким образом, в полукольце [math]\mathcal{R}^{+}[/math] итерация произвольного элемента также равна единице полукольца, т.е. числу 0.


в. Замкнутость идемпотентного полукольца [math]\mathcal{S}_A[/math] (cm. пример З.З.б) можно обосновать следующим образом. Отношение естественного порядка этого полукольца — это отношение включения (см. пример 3.4). Рассмотрим произвольную последовательность подмножеств [math]B_1,\ldots,B_n,\ldots[/math] множества [math]A[/math]. В данном полукольце бесконечная сумма есть объединение последовательности подмножеств множества [math]A[/math].


Докажем, что объединение [math]\textstyle{\mathop{B=\bigcup\limits_{n\in \mathbb{N}}B_n}\limits^{\phantom{A}^{.}}}[/math] и есть [math]\sup B_n[/math]. Очевидно, что для каждого [math]i[/math] справедливо включение [math]B_i\subseteq B[/math], т.е. объединение есть верхняя грань последовательности [math]\{B_n\}_{n\in\mathbb{N}}[/math]. Покажем, что [math]B[/math] будет точной верхней гранью. Рассмотрим произвольную верхнюю грань [math]C[/math] последовательности [math]B_n[/math]. Тогда [math]B_n\subseteq C[/math] для каждого [math]n\in\mathbb{N}[/math] (см. 1.5) и поэтому


[math]C\cup B= C\cup \Bigl(\bigcup_{n\in \mathbb{N}}B_n\Bigr)= \bigcup_{n\in \mathbb{N}}(C\cup B_n)= C,[/math]

то есть [math]B\subseteq C[/math]. Следовательно, [math]\textstyle{\mathop{B=\bigcup\limits_{n\in \mathbb{N}}B_n= \sup B_n}\limits^{\phantom{A}^{.}}}[/math].


Непрерывность умножения полукольца [math]\mathcal{S}_A[/math], в качестве которого взято пересечение множеств, эквивалентна тождеству


[math]C\cap \Bigl(\bigcup_{n\in \mathbb{N}}B_n\Bigr)= \bigcup_{n\in \mathbb{N}}(C\cup B_n)[/math]

(дистрибутивности пересечения относительно произвольного объединения, см. 1.5). В этом полукольце умножение — это пересечение множеств. Поэтому любая положительная степень множества [math]X[/math] есть само [math]X[/math]. Нулевая же степень [math]X^0[/math] равна единице полукольца, т.е. множеству [math]A[/math]. Поэтому итерация [math]X^{\ast}[/math] равна


[math]X^{\ast}= X^0\cup X\cup \ldots\cup X^n\cup \ldots= X^0\cup X= A\cup X=A,[/math]

то есть также равна единице полукольца.

г. Рассмотрим идемпотентное полукольцо [math]\mathcal{R}_A[/math] (см. пример З.З.в) бинарных отношений на множестве [math]A[/math]. Можно доказать, что точной верхней гранью любой последовательности отношений, как и в полукольце [math]\mathcal{S}_A[/math], служит объединение элементов этой последовательности (см. пример 3.4).


Аналогично доказательству дистрибутивности композиции бинарных отношений на множестве относительно конечного объединения можно доказать, что для любых бинарных отношений [math]\rho[/math] и [math]\sigma_n[/math] на множестве [math]A[/math] справедливы тождества


[math]\rho\circ \bigcup_{n\geqslant1}\sigma_{n}= \big\cup_{n\geqslant1} (\rho\circ \sigma_n),\qquad \Bigl(\bigcup_{n\geqslant1}\sigma_{n}\Bigr)\circ\rho= \bigcup_{n\geqslant1} (\sigma\circ\rho).[/math]

Таким образом, идемпотентное полукольцо [math]\mathcal{R}_A[/math] замкнутое. Итерация бинарного отношения [math]\rho[/math] есть


[math]\rho^{\ast}= \bigcup_{n\geqslant1}\rho^n= \operatorname{id}A\cup \bigcup_{n\geqslant1} \rho^n,[/math]

где [math]\rho^n,~ n\geqslant1[/math], — n-кратная композиция [math]\rho[/math] с самим собой: [math]\mathop{\rho^n= \underbrace{\rho\circ\ldots\circ\rho}_{n~\text{times}}}\limits^{\phantom{A}^{{}^{{}^{.}}}}[/math]. Как видно, в общем случае [math]\rho^{\ast}\ne \operatorname{id}A[/math], т.е. в [math]n[/math] раз этом полукольце итерация элемента, вообще говоря, не равна единице полукольца.




Выше было показано, что всякое замкнутое полукольцо является индуктивным упорядоченным множеством. Следовательно, согласно теореме 1.7, любое непрерывное отображение [math]f[/math] замкнутого полукольца в себя имеет наименьшую неподвижную точку, т.е. в любом замкнутом полукольце всякое уравнение вида [math]x=f(x)[/math], где [math]f[/math] — непрерывное отображение носителя этого полукольца в себя, имеет наименьшее решение.


Особенно важными для приложений являются линейные уравнения в замкнутом полукольце, имеющие вид


[math]x=a\cdot x+b[/math]
(3.12)
или
[math]x=x\cdot a+b.[/math]
(3.13)

В силу непрерывности операций сложения полукольца (см. тождество (3.10)) и умножения полукольца (см. определение 3.2) правые части уравнений (3.12) и (3.13) есть непрерывные отображения. Поэтому, согласно теореме 1.7 о неподвижной точке, существуют наименьшие решения этих уравнений.




Теорема 3.7. Наименьшими решениями уравнений (3.12) и (3.13) в замкнутых полукольцах являются соответственно


[math]x=a^{\ast}\cdot b[/math]
(3.14)
и, где [math]a^{\ast}[/math] — итерация элемента [math]a[/math],
[math]x=b\cdot a^{\ast},[/math]
(3.15)

Используя формулу (1.8) для вычисления наименьшей неподвижной точки и записывая sup в случае замкнутого полукольца как бесконечную сумму, для уравнения (3.14) получаем


[math]x=\sum\limits_{n=0}^{\infty}f^n(\bold{0}),[/math]
где [math]\bold{0}[/math] — нуль полукольца, а [math]f(x)=ax+b[/math]. Учитывая, что

[math]\begin{aligned}&f^0(\bold{0})=\bold{0},\\ &f^1(\bold{0})=b,\\ &f^2(\bold{0})= ab+ b=(a+\bold{1})b,\\ &\cdots\cdots\cdots\cdots\cdots\\ &f^n(\bold{0})= (a^{n-1}+\ldots+ a^2+ a+ \bold{1})b, \end{aligned}[/math]
получаем
[math]\sum\limits_{n=1}^{\infty}f^n(\bold{0})= \sum\limits_{n=1}^{\infty}(\bold{1}+ a+\ldots+a^{n-1})b\,.[/math]

Используя непрерывность умножения, вынесем [math]b[/math] (вправо) за знак бесконечной суммы и получим


[math]\sum\limits_{n=1}^{\infty}(\bold{1}+ a+\ldots+a^{n-1})b= \Bigl(\sum\limits_{n=1}^{\infty}(\bold{1}+ a+\ldots+a^{n-1})\Bigr)b\,.[/math]

Сумма [math]\bold{1}+ a+\ldots+a^{n-1}[/math] есть частичная сумма последовательности [math]\{a^n\}_{n\geqslant0}[/math]. Используя равенство (3.6), можем написать


[math]\sum\limits_{n=1}^{\infty}(\bold{1}+ a+\ldots+a^{n-1})= \sum\limits_{n=0}^{\infty}a^n= a^{\ast}.[/math] Окончательно получаем [math]\sum\limits_{n=1}^{\infty}f^n(\bold{0})=a^{\ast}b[/math].

Аналогично доказывается равенство (3.15).




Формулы (3.14) и (3.15) дают именно наименьшие решения уравнений (3.12) и (3.13), а не все возможные их решения. Приведем в этой связи простой пример. В полукольце [math]\mathcal{B}[/math] (см. пример 3.2) можно определить только два уравнения: [math]x=x+1[/math] и [math]x=x+0[/math]. Второе уравнение переписывается совсем просто: [math]x=x[/math]; его решением является любой элемент полукольца — как 0, так и 1. Но по формуле (3.14) получим [math]x=1^{\ast}0=0[/math], что, как и доказано выше, есть наименьшее решение уравнения.


Заметим еще, что в полукольце, в котором итерация любого элемента равна единице полукольца, формулы (3.14) и (3.15) дают один и тот же результат: [math]x=b[/math], т.е. в данном случае наименьшее решение совпадает со свободным членом уравнения.


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved