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

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

Определение 3.2. Полукольцо S = (S, +, ⋅, 0, 1) называют замкнутым, если:

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

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

3) операция умножения полукольца S сохраняет точные верхние грани последовательностей, т.е. для любого а ∈ S и любой последовательности X = {хⁿ}_n∈ℕ элементов множества S

a sup X = sup aX, (sup X)a = sup(Xa).

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

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

◀Поскольку носитель S идемпотентного полукольца

S = (S, +, ⋅, 0, 1)

есть конечное множество, то множество элементов любой последовательности в этом полукольце конечно. Для нахождения точной верхней грани такой последовательности нужно найти точную верхнюю грань множества Р= {p₁, ... ,p_n} ее членов, т.е., согласно теореме 3.1, вычислить некоторую конечную сумму, которая всегда существует. Таким образом, в конечном идемпотентном полукольце любая последовательность имеет точную верхнюю грань.

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

a(p₁ + ... +p_n) = ap₁ + ... +ap_n , (p₁ + ... + p_n)a = p₁a + ... +p_na

и выполняются в силу аксиом полукольца.

Таким образом, полукольцо S замкнуто. ▶

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

В силу этого в замкнутом полукольце естественно точную верхнюю грань последовательности {x_n}_n∈ℕ называть суммой элементов последовательности, полагая, по определению,

(3.2)

Согласно условию 2 определения 3.2, всегда есть элемент множества S. Иногда, если это не приводит к недоразумению, „пределы суммирования" будем опускать и писать просто . Также будем использовать обозначение подчеркивая, что в (3.2) множество элементов х_n в общем случае бесконечно, будем сумму, стоящую в левой части (3.2), называть бесконечной суммой. Заметим, что в частных случаях бесконечная сумма может свестись к конечной (если множество всех элементов последовательности {хn} конечно).

Итак, согласно определению 3.2, замкнутое полукольцо является индуктивным упорядоченным множеством, в котором наименьшим элементом служит нуль полукольца, точной в верхней гранью произвольной (в частности, неубывающей) последовательности {хⁿ}_n∈ℕ является бесконечная сумма , причем операция умножения на произвольный фиксированный элемент а непрерывна в смысле определения 1.5, поскольку, согласно определению 3.2, сохраняет точные верхние грани. Заметим, что это свойство умножения в замкнутом полукольце можно рассматривать как аналог дистрибутивности (седьмой аксио- аксиомы полукольца, см. определение 3.1) для бесконечной суммы:

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

Действительно, для последовательности {хⁿ}_n∈ℕ такой, что х_n = а для любого n ∈ ℕ, имеем ∑ х_n = sup{a} = a, т.е. бесконечная сумма, все слагаемые которой одинаковы и равны некоторому а, равна а. В этом состоит свойство идемпотентности бесконечной суммы (или, как иногда говорят, свойство бесконечной идемпотентности).

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

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

Для некоторой последовательности {хⁿ}_n∈ℕ элементов замкнутого полукольца и произвольной последовательности {т_л}_л∈ℕ натуральных чисел образуем последовательность {s_k}_k∈ℕ, где

s₁ = x₁ + ... + x_n1,

s₂ = x_n1+1 + ... + x_n1+n2,

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . .

s_k = x_nk-1+1 + ... + x_nk-1+nk,

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . .

Тогда бесконечная ассоциативность состоит в выполнении для любой последовательности {хⁿ}_n∈ℕ равенства

(3.3)

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

Теорема 3.3. Идемпотентное полукольцо S = (S, + ,⋅ ,0, 1) замкнуто тогда и только тогда, когда любое счетное подмножество X ⊆ S имеет точную верхнюю грань и для любого a ∈ S верны равенства

a ⋅ supX = sup(a ⋅ X), (supX) ⋅ a = sup(X ⋅ a).

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

Теорема 3.4. Пусть S = (S, +, ⋅, 0, 1) — замкнутое полукольцо, X — не более чем счетное подмножество множества S, a (B_i)_i∈I — не более чем счетное семейство подмножеств мно- множества X, такое, что объединение семейства совпадает с X, т.е. Тогда

supX = sup {supВ_i, i ∈ I}.    (3.4)

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

Так как а есть точная верхняя грань множества X, то для любого х ∈ X справедливо неравенство х ≤ а (где ≤ — естественный порядок идемпотентного полукольца S). В частности, для любого подмножества B_i и любого его элемента у получаем у ≤ а, откуда следует, что элемент а есть верхняя грань каждого подмножества В_i. Значит, этот элемент не меньше чем точная верхняя грань каждого из этих подмножеств, т.е. для любого i ∈ I a ≥ sup В_i. Последнее означает, что а есть верхняя грань множества всех точных верхних граней supВ_i ∈ I, т.е. a ≥ b

В то же время, поскольку объединение всех подмножеств В_i равно X, для любого х ∈ Х найдется такое i ∈ I, что x ∈ В_i. Поэтому х ≤ sup В_i ≤ b, это означает, что элемент b является верхней гранью множества X, и тогда b ≥ а, так как а есть точная верхняя грань X.

Итак, а ≥ b ≥ а, откуда а = b, и равенство (3.4) доказано. ▶

Следствие 3.1. Если семейство подмножеств из теоремы 3.4(B_i)_i∈I конечно, т.е. I = {1,2,..., n}, то

Следствие 3.2. Пусть {x_n}_n∈ℕ— произвольная последовательность элементов замкнутого полукольца и (N_i)_i∈I - не более чем счетное семейство подмножеств ℕ, такое, что Тогда

В частности, из следствия 3.2 при условии, что множества N_i, i ∈ I, попарно не пересекаются, получаем свойство ассоциативности бесконечной суммы (3.3). Отсюда же при N₁ = {1}, N₂ = {1,2} и т.д., т.е. при определении для любого натурального k множества N_k в виде N_k = N_k-1 U {k}, получаем равенство

т.е. точная верхняя грань последовательности {x_n}_n∈ℕ равна точной верхней грани последовательности частичных сумм {s_k}_k∈ℕ, где s_k = x₁ + ... + x_k

Пусть {x_n}_n∈ℕ и {y_m}_m∈ℕ — произвольные последовательности в замкнутом полукольце S. Образуем последователь- последовательность, членами которой являются все произведения x_ny_m при независимом пробегании индексами n и m множества натуральных чисел*. * Такую последовательность называют произведением Коши исходных последовательностей [IX]. Эту последовательность будем записывать как {x_ny_m}_n,m∈ℕ , а ее точную верхнюю грань обозначим как

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

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

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

В правой части последнего равенства каждое слагаемое внешней суммы (по m) есть точная верхняя грань подпоследовательности {x_ny_m}_n,m∈ℕ при фиксированном m. Поскольку все эти подпоследовательности в совокупности дают всю последовательность {x_ny_m}_n,m∈ℕ, то, согласно следствию 3.2, получаем

что и доказывает тождество (3.7). ▶

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

Пусть {x_n}_n∈ℕ и {y_n}_n∈ℕ — произвольные последовательности в замкнутом полукольце S. Образуем последовательность {x_n + y_n}_n∈ℕ называемую суммой исходных последовательностей.

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

∑ (x_n + y_n) = ∑ x_n + ∑ y_n.    (3.8)

◀Обозначим через X множество всех членов последовательности {x_n}_n∈ℕ; а через У — множество всех членов последовательности {y_n}_n∈ℕ. В силу следствия 3.2

sup(X U Y) = supX + sup Y = ∑ x_n + ∑ y_n.

Осталось тогда доказать, что

∑ (x_n + y_n) = sup (X U Y).    (3.9)

Обозначим через а левую, а через b правую часть доказываемого равенства (3.9). Для любого натурального n имеем a ≥ x_n + y_n. Согласно теореме 3.1, х_n + у_n ≥ х_n и х_n + у_n ≥ у_n. Следовательно, для любого n выполняются неравенства a ≥ x_n и a ≥ y_n, т.е. а ≥ u для любого u ∈ X U Y. Таким образом, элемент а является верхней гранью множества X U Y, откуда а ≥ b.

В то же время элемент b не меньше любого из элементов множества Х U У, и, стало быть, для любого натурального n имеет место b ≥ х_n и b ≥ y_n, т.е. b ≥ sup {х_n, y_n} = x_n + y_n. Это значит, что b есть верхняя грань последовательности {х_n + y_n}_n∈ℕ, а потому b ≥ а.

Итак, а = b, и равенство (3.9) доказано. ▶

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

Следствие 3.3. Для любой последовательности {хⁿ}_n∈ℕ элементов замкнутого полукольца и любого элемента а этого полукольца выполняется равенство

a + ∑ x_n = ∑(a +x_n) .    (3.10)

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

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

где, по определению, х⁰ = 1, а хⁿ = x^n-1, n = 1,2,...

Пример 3.5. а. Из теоремы 3.2 сразу получаем, что идемпотентное полукольцо В (см. пример 3.2) замкнуто, причем точная верхняя грань любой последовательности элементов этого полукольца равна 1, если хотя бы один ее член равен 1, и равна 0 в противном случае. В частности, итерация любого элемента полукольца В равна 1. Для 1* это очевидно, а для 0* имеем

0* = 0⁰ + 0¹ + ... + 0^k + ... = 1 + 0 + ... + 0 + ... = 1

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

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

a + inf X = inf X_a,    (3.11)

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

Таким образом, рассматриваемое идемпотентное полукольцо R⁺ является замкнутым.

Итерация х* элемента х в полукольце R⁺ есть точная верхняя грань последовательности степеней элемента х. Поскольку в этом полукольце операция умножения определена как операция сложения действительных чисел, то х⁰ = 0, так как число 0 есть единица полукольца R⁺. Далее, х² = х + х = 2х, ..., хⁿ = nх. Очевидно, что для каждого n ≥ 0 выполняется неравенство xⁿ ≥ 0 смысле естественного числового порядка. Таким образом, число 0 есть наименьший в смысле естественного числового порядка член последовательности {хⁿ}_n∈ℕ и, следовательно, inf{х_n}_n∈ℕ = 0. Переходя к двойственному порядку — естественному порядку полукольца R⁺, получим, что число 0 является точной верхней гранью последовательности {хⁿ}_n∈ℕ, т.е. х* = 0. Таким образом, в полукольце R⁺ итерация произвольного элемента также равна единице полукольца, т.е. числу 0.

в. Замкнутость идемпотентного полукольца S_A (cm. пример З.З.б) можно обосновать следующим образом. Отношение естественного порядка этого полукольца — это отношение включения (см. пример 3.4). Рассмотрим произвольную последовательность подмножеств B₁, ..., B_n, ... множества А. В данном полукольце бесконечная сумма есть объединение последовательности подмножеств множества А.

Докажем, что объединение и есть supB_n. видно, что для каждого i справедливо включение В_i ⊆ В, т.е. объединение есть верхняя грань последовательности {x_n}_n∈ℕ Покажем, что В будет точной верхней гранью. Рассмотрим произвольную верхнюю грань С последовательности В_n. Тогда B_n ⊆ C для каждого n ∈ ℕ (см. 1.5) и поэтому

т.е. В ⊆ С. Следовательно, .

Непрерывность умножения полукольца S_A, в качестве которого взято пересечение множеств, эквивалентна тождеству

(дистрибутивности пересечения относительно произвольного объединения, см. 1.5). В этом полукольце умножение — это пересечение множеств. Поэтому любая положительная степень множества X есть само X. Нулевая же степень Х⁰ равна единице полукольца, т.е. множеству А. Поэтому итерация X* равна

X* = Х⁰∪ X ∪ ... ∪ Хⁿ ∪ ... = Х⁰ ∪ X = A ∪ X = A,

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

г. Рассмотрим идемпотентное полукольцо R_A (см. пример З.З.в) бинарных отношений на множестве А. Можно доказать, что точной верхней гранью любой последовательности отношений, как и в полукольце S_A, служит объединение элементов этой последовательности (см. пример 3.4).

Аналогично доказательству дистрибутивности композиции бинарных отношений на множестве относительно конечного объединения (см. 1.4) можно доказать, что для любых ных отношений ρ и σ_n на множестве А справедливы тождества

Таким образом, идемпотентное полукольцо R_A замкнутое.

Итерация бинарного отношения ρ есть

где ρⁿ, n ≥ 1, — n-кратная композиция р с самим собой: . Как видно, в общем случае ρ* ≠ id_A, т.е. в этом полукольце итерация элемента, вообще говоря, не равна единице полукольца. #

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

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

x = ax + b   (3.12)

или

x = xa + b   (3.13)

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

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

х = а*b (3.14)   (3.13)

и

х = ba, (3.15)   (3.13)

где а* — итерация элемента а.

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

где 0 — нуль полукольца, a f(x) = ax + b.

Учитывая, что

f⁰ (0) = 0

f¹ (0) = b

f² (0) = ab + b = (a + 1) b,

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

fⁿ (0) = (a^n-1 + ... + a² + a + 1) b,

получаем

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

Сумма 1 + a + ... + a^n-1 есть частичная сумма последовательности {аⁿ}_n≥0. Используя равенство (3.6), можем написать

Окончательно получаем

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

Формулы (3.14) и (3.15) дают именно наименьшие решения уравнений (3.12) и (3.13), а не все возможные их решения. Приведем в этой связи простой пример. В полукольце В (см. пример 3.2) можно определить только два уравнения: х = х +1 и х = х + 0. Второе уравнение переписывается совсем просто: х = х; его решением является любой элемент полукольца — как 0, так и 1. Но по формуле (3.14) получим х = 1*0 = 0, что, как и доказано выше, есть наименьшее решение уравнения.

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