О системах образующих диагональных полигонов над полугруппами изотонных и непрерывных преобразований | ПДМ. 2014. № 4(26).

О системах образующих диагональных полигонов над полугруппами изотонных и непрерывных преобразований

Исследуются диагональные полигоны (автоматы) над полугруппами изотонных преобразований частично упорядоченного множества и непрерывных отображений топологического пространства в себя. Найдено необходимое условие цикличности диагонального правого полигона над полугруппой непрерывных отображений компакта в себя. Доказано отсутствие счётного множества образующих диагонального биполигона над полугруппой изотонных отображений множества натуральных чисел в себя. Изучаются связи между понятиями изотонности и непрерывности.

On generating sets of diagonal acts over semigroups of isotone and continuous transformations.pdf Введение Изотонные (то есть сохраняющие порядок) отображения X ^ Y, где X и Y - частично упорядоченные множества, изучались многими авторами. При X = Y получаем множество O(X) изотонных отображений X ^ X, которое является полугруппой относительно композиции х(ав) = (ха)в, где х G X, а, в G O(X). В случае, если рассматриваются частичные отображения а : Xi ^ X, где Xi С X, понятие изотонности может быть определено разными неэквивалентными способами [1]. Другое обобщение понятия изотонного отображения состоит в переходе от частичного порядка к квазипорядку или вообще произвольному бинарному отношению [1]. Вместе с тем можно заметить, что понятие изотонного отображения является частным случаем непрерывного отображения X ^ Y, если X и Y наделить топологиями, естественным образом связанными с заданными на X и Y частичными порядками. Для конечных множеств X и Y это установлено в [2], а в общем случае - в п. 1 настоящей работы. Полугруппа C (X) непрерывных отображений X ^ X (где X - топологическое пространство) также подвергалась интенсивному изучению с алгебраической точки зрения. Этой полугруппе посвящён обстоятельный обзор [3]. Один из центральных вопросов этой теории - в каких случаях топологическое пространство X определяется с точностью до гомеоморфизма своей полугруппой C(X)? М. Торнтон [4] дал абстрактную характеризацию полугрупп, изоморфных полугруппе непрерывных отображений C(X). Он рассмотрел гомоморфизмы этих полугрупп и показал, что любой изоморфизм между полугруппами C(X) и C (Y) индуцируется гомеоморфизмом или дуальным гомеоморфизмом (это понятие определяется для некоторого класса Т0-про-странств) между топологическими Т0-пространствами X и Y. Ранее Л. М. Глускин [5] доказал аналогичное утверждение для частично упорядоченных множеств с нетривиальными порядками. Б. С. Нурутдинов [6] рассматривал аналогичные вопросы опреде-ляемости топологического пространства другими полугруппами отображений, в частности полугруппами замкнутых отображений. Далее рассматриваются полигоны над полугруппами. Хорошо известно, что полигон над полугруппой является алгебраической моделью автомата, где элементы множества X - состояния, а S - входные сигналы (см., например, [7]). В п. 2 и 3 изучаются полугруппы непрерывных/изотонных отображений с точки зрения их диагональных полигонов и биполигонов. Ранее автором было доказано, что для отрезка числовой прямой с обычной топологией диагональный правый полигон над полугруппой C (X) непрерывных отображений X ^ X является циклическим. В п. 2 приводится условие на компакт X, необходимое для цикличности полигона (C(X) х C(X))c(х). В п. 3 рассматривается диагональный биполигон над полугруппой O(N) всех изотонных преобразований N ^ N. Доказано отсутствие счётной системы образующих этого полигона. 1. Изотонность и непрерывность В [2] Р. Стонг исследовал конечные топологические пространства X. Он определил Ux для x Е X как пересечение всех открытых множеств, содержащих x, и отношение ^ на X по правилу x ^ y ■ Ux С Uy .В случае конечного множества X пересечение любой совокупности открытых множеств открыто. Поэтому все Ux открыты. Однако данная конструкция может быть легко перенесена и на бесконечные множества X. Пусть X - произвольное частично упорядоченное множество, не обязательно конечное. Введём на X топологию, приняв множество подмножеств вида Ux = (-га, x] = = {y Е X : y ^ x} за базу открытых множеств (тот факт, что это база топологии, проверятся непосредственно). Назовем эту топологию порядковой топологией. Обычно порядковая топология рассматривалась для линейно упорядоченных множеств, но и в случае частично упорядоченного множества получается топология. Легко видеть, что антисимметричность отношения ^ равносильна тому факту, что X является Т0-пространством. Можно расссматривать квазипорядок вместо порядка, тогда от аксиомы T0 придётся отказаться. Утверждение 1. Пусть X, Y - частично упорядоченные множества и а : X ^ Y - отображение. Наделим X и Y порядковыми топологиями. Тогда а изотонно в том и только в том случае, если оно непрерывно. Доказательство. Необходимость. Пусть а изотонно. Возьмём любой элемент y Е Y. Так как {(-га,y] : y Е Y} - база топологии в Y, то достаточно доказать, что (-га,у]а-1 открыто в X. Пусть x Е (-ra,y]a-1. Тогда xa ^ y. Если x' ^ x, то из изотонности а получаем, что x'a ^ y, а значит, (-ra,x] С (-ra,y]a-1. Таким образом, (-ra,y]a-1 = U (-ra,x], то есть (-га^а-1 открыто. xa^y Достаточность. Пусть а непрерывно и x ^ x' для некоторых x,x' Е X. Пусть V = (-га^'а]. Множество V открыто в Y, а так как а непрерывно, Уа-1 открыто в X. Имеем x' Е Уа-1. Отсюда следует, что существует элемент базы U, такой, что x' Е U и U С Уа-1. Имеем U = (-га, u] для некоторого u Е X. Так как x' Е U, выполняется x' ^ u. Это влечёт x ^ u, а значит, x Е U. Но Ua С V. Следовательно, xa ^ x^. ■ Следствие 1. Пусть X - частично упорядоченное множество, рассматриваемое как топологическое пространство с порядковой топологией. Тогда C(X) = O(X). 2. Диагональные полигоны над полугруппой непрерывных отображений Напомним понятие полигона над полугруппой. Правым полигоном [8] над полугруппой S называется множество X, на котором действует полугруппа S, то есть определено отображение X х S м X, (x,s) м- xs, такое, что выполняется тождество (xs)s' = x(ss') для х Е X, s, s' Е S. Левый полигон Y над полугруппой S определяется двойственным образом, то есть как отображение Y х S м Y, (s,y) м sy, причём s(s'y) = (ss')y для y Е Y, s, s' Е S. Если множество X является левым полигоном над полугруппой S и правым полигоном над полугруппой T, то оно называется биполи-гоном в случае, когда выполняется условие (sx)t = s(xt) при x Е X, s Е S, t Е T. Если S - полугруппа, то множество S х S является правым полигоном над S относительно действия (x,y)s = (xs,ys) при всех x,y,s Е S, левым относительно действия s(x, y) = (sx, sy), а также биполигоном. Назовем их правым, левым диагональными полигонами, а также диагональным биполигоном и будем обозначать (S х S)S, S(S х S), s(S х S)s соответственно. Диагональный (би)полигон называется циклическим, если он порождается одним элементом (то есть одной парой (a, b) Е S х S). Раннее автором изучались свойства диагональных полигонов над полугруппой непрерывных отображений в случае, когда X - отрезок числовой прямой. Доказано, что диагональный правый полигон (C(X) х C(X))c(x) является циклическим [9], а диагональный левый полигон c(x)(c(X) х C(X)) не является счётно порождённым [10]. В случае произвольного компакта можно получить необходимое условие цикличности диагонального полигона. Утверждение 2. Пусть X - компакт и |X | > 1. Если диагональный правый полигон (C(X) хC(X))c(x) циклический, то X содержит непересекающиеся подпространства X1,X2, гомеоморфные пространству X. Доказательство. Предположим, что выполнены условия утверждения. Тогда существует пара (а, в) Е C(X) х C(X), порождающая диагональный правый полигон. Если 1х - тождественное отображение X м X, то (а,в)т = (1x, 1х) при некотором Y Е cx. Отсюда следует, что а, в - инъективные отображения. Пусть X1 = Xa, X2 = = Xe. Очевидно, а : X м X1, в : X м X2 -непрерывные биективные отображения, а так как X - компакт, а - гомеоморфизм между X и X1. Аналогично получаем, что в - гомеоморфизм между X и X2. Осталось доказать, что X1 П X2 = 0. Пусть это не так. Тогда xa = yв при некоторых x, y Е X. Возьмём два различных элемента a, b Е X, и пусть 6^,6^ - константные отображения, то есть x6a = a и x6b = b при всех x Е X. Очевидно, что отображения 6^,6^ непрерывны. Следовательно, (а,в)6 = при некотором 6 Е CX. Имеем: a = x6a = xa6 = yв6 = y6b = b, что противоречит выбору элементов a и b. ■ Следует отметить, что не все компакты являются таковыми. Например, в компакте X = -|о, 1,1,1 , . . . j- (с обычной топологией действительных чисел) нет двух непересекающихся гомеоморфных X подпространств. 3. Диагональные биполигоны над полугруппой изотонных отображений В работе [11] доказано, что диагональный правый полигон (S х S)s, диагональный левый полигон s (S х S) и диагональный биполигон s (S х S)s являются циклическими, если S = T(X), P(X) или B(X), где X - бесконечное множество, T(X) - полугруппа всех отображений X ^ X, P(X) -полугруппа частичных отображений, а B (X) -полугруппа бинарных отношений на множестве X. Аналогичный вопрос возникает для полугруппы O(X) всех изотонных (сохраняющих порядок) отображений a : X ^ X, где X - частично упорядоченное множество. Ранее автором были исследованы диагональные полигоны над полугруппой O(X) и получены условия цикличности и конечной порожденности этих полигонов [9]. Там же доказано, что ни для какой бесконечной цепи X диагональные полигоны над полугруппой O(X) не могут быть циклическими. Основной результат данной работы обобщает упомянутый результат в случае, когда X - множество натуральных чисел N с обычным порядком, а именно доказано, что диагональный биполигон над полугруппой изотонных отображений O(N) не имеет счётной системы образующих. Определение 1. Пусть а, в: N ^ N - изотонные отображения. Назовём пару (а, в) правильной, если выполняются следующие условия: (i) ia = ja, %в = jp при i = j; (ii) ia = j в при любых i, j (т. е. ima П imв = 0); (iii) для любого k существует l, такое, что la = k или 1в = k (т. е. im a U im в = N). Замечание 1. Если пара (a, в) принадлежит порождающему множеству (множеству образующих), но не является правильной, то существует правильная пара (a,в), такая, что (a,/3)y = (a,в) при некотором 7 Е O(N). Поэтому в системе образующих пару (a, в) можно заменить на пару (a,/3). Далее будем считать, что система образующих состоит только из правильных пар. Следующая лемма показывает, что в системе образующих любую пару можно заменить на правильную пару. Лемма 1. Пусть a, в : N ^ N - изотонные отображения, такие, что im a, im в - бесконечные множества. Тогда существуют изотонные отображения 1 и p1 > a, где a - количество нулей 0i, таких, что i ^ m и pos0i < pos 1m. Если в последовательности е имеет место pos0m > pos 1m, то a = 0 и можно положить p1 = 2. Пусть числа p1,p2,... ,pk-1 уже построены, причем pi > i при i = 1, 2,... , k - 1. Рассмотрим bfc. Пусть bk = (е,т). Сначала выбираем, если это возможно, p1 нулей, лежащих от 0m до 1m: 0tl = 0m, 0t2, 0t3, ... , 0t . Автоматически будут выбраны единицы 1ti = 0m, 1t2, 1t3, ... , 1t . Ясно, что существует лишь конечное число способов выбора нулей 0tl = 0m, ... , 0t . Далее выбираем, если это возможно, p2 нулей между 1tl и 1t2: 0t +1, 0t +2, ... , 0tpi. Это также можно сделать лишь конечным количеством способов. Пусть выбраны нули 0t + +p +1, ... , 0t + +p i+p., предшествующие элементу 1t.. Так как p1 + ... + pi > i, то определено ti+1, и если i < k - 1, то можно выбрать следующую последовательность из нулей pi+1 между 1ti и 1t . Последние выбранные нули -это 0tpi+...+pfc_2+i, ..., 0tpi+...+pfc_2+pfc_i, они предшествуют элементу 1tk-1. Так как p1 + .. .+pk-1 > k -1, то tk также определено. Обозначим через c максимальное количество нулей между 1tk_ 1 и 1tk при всевозможных выборах нулей и единиц вышеописанным способом. Ввиду конечности количества способов выбора имеем c = то. Полагаемpk = max{c +1, k +1}. Итак, последовательность p1,p2,p3,... построена. Пусть п = 0P110Р210Р31... (здесь 0p обозначает 00^Л)). Докажем, что послеp довательность п не может быть получена из какой-либо последовательности е(^ Е A с помощью прореживания. Действительно, пусть п получается из е(^ путем прореживания, то есть выделения нулей и единиц с номерами t1,t2,..., где t1 < t2 < ... Тогда существует такое k, что (е(^,t1) = bk. Имеем (pos 1k-1) < (pos0P1+...+Pk) < (pos 1tk). Из условия pk = max{c + 1, k +1} имеем pk ^ c +1. Значит, между 1tk_ 1 и 1tk всего нулей меньше чем pk. Получили противоречие. Следовательно, последовательность п не получится из е(^ прореживанием. Последовательность п соответствует некоторой правильной паре (

Ключевые слова

полигон, диагональный полигон, непрерывные отображения, изотонные отображения, система образующих, act, diagonal act, isotone mapping, generating set, semigroup of continuous mappings

Авторы

ФИООрганизацияДополнительноE-mail
Апраксина Татьяна ВалентиновнаНациональный исследовательский университет «МИЭТ», г. Москвааспиранткаtaya.apraksina@gmail.com
Всего: 1

Ссылки

Ярошевич В. А. О свойствах полугрупп частичных изотонных преобразований квазиупо-рядоченных множеств // Вестник МГАДА. 2011. Вып. 3(9). С. 139-144.
Stong R. E. Finite topological spaces // Trans. Amer. Math. Soc. 1996. No. 123. P. 325-340.
Magill K. D. Jr. A survey of semigroups of continuous selfmaps // Semigroup Forum. 1975/1976. V. 11. P. 189-282.
Thornton M. C. Semigroups of isotone selfmaps on partially ordered sets //J. London Math. Soc. 1976. V. 14. No. 3. P. 545-553.
Глускин Л. М. Полугруппы изотонных преобразований // Успехи матем. наук. 1961. №16:5(101). С. 157-162.
Нурутдинов Б. С. Топологии пространств, описываемые полугруппами отображений // Вестник МГУ. Сер. Математика, Механика. 1973. №4. С. 24-29.
Плоткин Б. И., Гринглаз Л. Я., Гварамия А. А. Элементы алгебраической теории автоматов. М.: Высшая школа, 1994.
Kilp M., Knauer U., and Mikhalev A. V. Monoids, acts and categories. Berlin; New York: de Gruyter, 2000.
Апраксина Т. В. Диагональные полигоны над полугруппами изотонных преобразований // Чебышевский сб. 2011. №12:1. С. 10-16.
Апраксина Т. В. Цикличность и конечнопорожденность диагональных полигонов над полугруппами преобразований // Мат. вестн. педвузов и ун-тов Волго-Вятск. региона. 2012. №14. С. 51-58.
Gallagher P. and Ruskuc N. Generation of diagonal acts of some semigroups of transformations and relations // Bull. Austral. Math. Soc. 2005. V. 72. P. 139-146.
 О системах образующих диагональных полигонов над полугруппами изотонных и непрерывных преобразований | ПДМ. 2014. № 4(26).

О системах образующих диагональных полигонов над полугруппами изотонных и непрерывных преобразований | ПДМ. 2014. № 4(26).