Полугруппы преобразований, сохраняющие бинарное отношение

ОРГАНИЗАЦИОННО-ЭКОНОМИЧЕСКИЕ АСПЕКТЫ ИННОВАЦИОННОГО РАЗВИТИЯ

УДК 51-77

Полугруппы преобразований, сохраняющие бинарное отношение1

В. М. Амербаев1,2,

И. Б. Кожухов2, А. М. Ревякин2, В. А. Ярошевич2

1 Институт проблем проектирования в микроэлектронике РАН

2 Национальный исследовательский университет «МИЭТ»

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

Ключевые слова: теория измерений; бинарное отношение; частично упорядоченное множество; квазиупорядоченное множество; регулярная полугруппа; цепь; антицепь; частичное преобразование.

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

Измерение заключается в таком присвоении числовых значений, при котором сохраняются наблюдаемые (бинарные) отношения. Первая, основная проблема теории измерений формулируется как проблема представления: найти условия, налагаемые на наблюдаемую систему отношений, которые были бы необходимы и достаточны для существования гомоморфизма из системы в заданную конкретную числовую систему 0 отношений, причем основной упор делается на задачу отыскания

достаточных условий. Вторая проблема теории измерений — проблема единственности: является ли построенный гомоморфизм единственным?

Бинарным отношением на множестве A называется любое подмножество его декартова квадрата A*A, где A*A — это множество всех пар (a, b) элементов из A. Например, если A — множество, состоящее из чисел 1, 2, 3, то обычное отношение порядка < на этом множестве может быть записано в виде

< = {(1,1), (1,2), (1,3), (2,2), (2,3), (3,3)}.

Бинарное отношение на множестве — это математическая абстракция, описывающая отношения между двумя элементами данного множества. В математике бинарными отношениями, например, являются: отношение равенства;

© Амербаев в. М Кижужв и. щ i Данная статья продолжает серию публикаций в разных изданиях

Ревякин А. М., Яр°шевич в. А. (см. [1; 2; 3; 4]), излагающих результаты изучения полугрупп преобразований, сохраняющих бинарные отношения на множествах.

Экономические и социально-гуманитарные исследования № 4 (8) 2015

17

Организационно-экономические аспекты инновационного развития

отношение делимости — на множестве целых чисел; параллельность и перпендикулярность — на множестве прямых линий и т. д. Общность определения бинарного отношения делает его применимым ко многим вопросам математики и прикладных наук. Отношение предпочтения на множестве характеристик какого-либо объекта, отношение знакомства в какой-либо группе людей — это все бинарные отношения.

Бинарные отношения могут обладать специальными свойствами. Перечислим основные из них.

Определенное на множестве X бинарное отношение а:

— рефлексивно, если для всех a £ X выполняется aaa;

— симметрично, если для всех a, b £ X из aab следует baa;

— антисимметрично, если для всех a, b £ Xиз aab и baa следует a = b;

— транзитивно, если для всех a, b, c £ X из aab и bac следует aac.

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

Пусть X — множество, на котором задана некоторая бинарная операция *. Будем говорить, что операция * ассоциативна, если для любых a, b, c £ Xвыполняется равенство a * (b * c) = (a * b) * c. В этом случае множество X совместно с операцией * будем называть полугруппой и обозначать (X, *) (основные сведения из теории полугрупп см. в [5]).

Элемент a £ X полугруппы (X, *) называется регулярным, если найдется такой элемент b £ X, что a = aba. Полугруппа называется регулярной, если все ее элементы регулярны.

Для произвольного множества X пусть T(X) — полугруппа преобразований a : X ^ X с умножением

х(ав) = (ха)в.

Далее, пусть PT(X) — множество всех частичных отображений, т. е. отображений в : X1 ^ X, где X1 с X. Множество X1 называется областью определения отображения в и обозначается dome. Умножение в полугруппе PT(X) осуществляется по правилу

х(ав) = (ха)в при х £ doma n (dome)a-1.

Наконец, пусть B(X) — полугруппа бинарных отношений на множестве X. Пусть a £ B(X). Для х £ X положим

A. = \y\(x,y) £ a}.

Тогда a можно рассматривать как многозначное отображение х ^ Ах. Очевидно, что T(X) и PT(X) — подполугруппы полугруппы B(X) и T(X) Я PT(X) Я B(X). При |X > 1 имеем: T(X) с PT(X) с B(X). В случае, когда X — конечное множество, элементы этих полугрупп можно записывать как обычные подстановки. Например, если X = {1, 2, 3, 4}, то

a = (3 2 4 i) 6 T(X), e = -V3) epT(X),

11 2 3 4 \

Y = (- {1, 3, 4} 2 {1, 2}J e B(X).

Известно и другое представление элементов полугруппы B(X), а именно — представление в виде матриц из 0 и 1 (булевых матриц). Элемент a £ B(X) в этом случае представляется в виде матрицы

a =|1, если (i, j) £ a, ij l0, если (i, j) g a.

18 Экономические и социально-гуманитарные исследования № 4 (8) 2015

Амербаев В. М., Кожухов И. Б., Ревякин А. М., Ярошевич В. А.

Например, таким образом можно представить приведенный выше элемент у:

отношение эквивалентности на множестве X. Введем определения некоторых полугрупп (см. [12]).

Y =

/0 0 0 0\ 1 0 1 1 0 1 0 0 .

\1 1 0 0/

Пусть X — некоторое множество с заданным на нем бинарным отношением а, и а : X ^ X — отображение (преобразование) множества X. Будем говорить, что а сохраняет отношение а, если при любых х, y £ X

(x,y) £ а => (xa, ya) £ а.

Это равносильно включению аа Q аа.

В полугруппе T(X) полных преобразований множества X рассмотрим подполугруппу Y(X) преобразований, сохраняющих а. Особый интерес представляет исследование условий для пары (^а), когда полугруппа Ta(X) регулярна.

Последнему вопросу посвящено много работ. Например, получены условия регулярности T<(X) для случая, когда а = < — частичный порядок [6; 7; 8]. Найдены условия регулярности полугруппы To(X), если а — квазипорядок [9]. Класс преобразований, сохраняющих а, можно расширить до частичных преобразований PT(X), сохраняющих а (см.: [10]). Для квазипорядка (а значит, и частичного порядка) регулярность полугруппы T<(X) эквивалентна слабой регулярности полугруппы T<(X), которая определяется условием

У а £ T<(X) Зв, Y, б, £ £ T<(X): а = авау или а = бага (см.: [11]).

Наряду с полугруппой T^X) преобразований, сохраняющих одно бинарное отношение, закономерно рассматривать полугруппы преобразований, сохраняющих два бинарных отношения одновременно.

Будем считать, что (X, <) — частично упорядоченное множество, а £ —

OE(X) = T(X) n T<(X),

T£*(X) = {а £ T(X) | Vx, y £ X(x, y) £ £ <=> <=> (ха, ya) £ г},

Oe*(X) = r.(X) n T<(X).

Данные полугруппы исследованы в случае, когда частично упорядоченное множество (X, <) представляет собой конечную цепь (см. [12; 13; 14]).

Обозначим через I, Y и Z произвольные множества, где I, Y, Z^ 0 и Yn Z = 0. Будем называть множеством Айзенштат любое множество из следующей совокупности частично упорядоченных множеств:

(i) антицепь;

(ii) квазиполная цепь (см. [11]);

(iii) L} = {a, с} U {b. | i £ I}, где a < b. < c для всех i £ I;

(iv) Fy z = Yu Z, где y < z для всех y £ Y, z £ Z, а другие пары несравнимы;

(v) GY: z = Yu Z, y0 £ Y, z0 £ Z, где y0 < z, y < z0 для всех y £ Y, z £ Z, а другие пары несравнимы;

(vi) C6 = {1, 2, 3, 4, 5, 6}, где 1 < 4, 1 < 5, 2 < 5, 2 < 6, 3 < 6, 3 < 4, а другие пары несравнимы.

Каждый элемент в предыдущем списке задает один из шести типов множества Айзенштат.

Теорема 1 (Айзенштат — Адамса — Гоулда [6; 7]). Пусть X — частично упорядоченное множество. Полугруппа T<(X) регулярна в том и только том случае, если (X, <) — множество Айзенштат.

Наряду с полными преобразованиями множества X будем рассматривать частичные преобразования PT(X).

Для частичного отображения а £ PT(X) множества X в X, сохраняющего а, включение аа £ аа в общем случае неверно. В связи с этим определить, что означает фраза «а £ PT(X) сохраняет а Q X х X», можно двумя различными неэквивалентными способами.

Экономические и социально-гуманитарные исследования № 4 (8) 2015

19

Организационно-экономические аспекты инновационного развития

Определение 1. а £ PT(X) допустимо для a Q Xx X, если

Vx, y £ doma (x, y) £ a =>

=> (xa, ya) £ a.

Определение 2. a £ PT(X) согласуется с a £ X x X, если aa £ aa.

Пусть PTa(X) = {a £ PT(X)|a допустимо для a с X x X}, а PP0 (X) = ={a £ PT(X)|a согласуется с a £ X x X}. Очевидно, что PTa(X) и РГа (X) — моноиды, являющиеся подмоноидами моноида PT(X). Доказано [9], что

РТа (X) с PTa(X).

Теорема 2. Пусть X — частично упорядоченное множество. Полугруппа PT<(X) регулярна в том и только том случае, если X — антицепь или цепь.

Теорема 3. Пусть X — частично упорядоченное множество, не являющееся цепью. Полугруппа РТ< (X) регулярна в том и только том случае, если выполнено хотя бы одно из условий:

(1) X — антицепь;

(2) X = Gj при некотором I.

Теорема 4. Пусть X — квазиупорядоченное множество. Тогда PT<(X) регулярна в том и только том случае, когда выполняется хотя бы одно из условий:

(1) X — антицепь;

(2) X — цепь;

(3) x < у при всех x, y £ X.

Теорема 5. Пусть X — квазиупорядоченное множество, не являющееся линейно упорядоченным. Полугруппа РР< (X) регулярна в том и только том случае, если выполняется хотя бы одно из условий:

(1) X — антицепь;

(2) X = Gj при некотором I (см. рисунок);

(3) x < y при всех x, y £ X.

Xi

Частично упорядоченное множество

Рассмотрим более общий случай многозначных отображений. Всякое многозначное отображение a можно считать бинарным отношением. Понятие «многозначное отображение» обобщает понятие «частичное отображение», поэтому появляется возможность более широко трактовать сохранение бинарного отношения a при многозначном отображении.

Будем говорить, что бинарное отношение a £ B(X):

1) согласуется с a, если aa Q aa.

2) сохраняет a в широком смысле, если

Vx, y £ X (x, y) £ a =>

=> (3u £ xa 3v £ ya: (u, v) £ a);

3) сохраняет a в узком смысле, если

Vx, y £ X Vu, v £ X(u £ xa &

& v £ ya & (x, y) £ a => (u, v) £ a).

Отметим, что из сохранения a в широком смысле (в общем случае) не следует сохранение a в узком смысле, и наоборот (соответствующие примеры см. в статье [15]).

Множества бинарных отношений, удовлетворяющих каждому из последних трех определений в отдельности, обозначим Ba(X), B'a(X) и B”a(X) соответственно.

Эти три множества являются полугруппами относительно операции умножения бинарных отношений. Далее сформулируем результаты, связанные с регулярностью этих полугрупп, полученные в работе [16].

Теорема 6. Для цепи X, где |X| > 2, полугруппа B (X) не является регулярной.

20

Экономические и социально-гуманитарные исследования № 4 (8) 2015

Амербаев В. М., Кожухов И. Б., Ревякин А. М., Ярошевич В. А.

Теорема 7. Для любого отношения эквивалентности a, заданного на множестве X, где |X ^ 3, полугруппа Ba(X) является нерегулярной.

Теорема 8. Пусть X — множество с заданным бинарным отношением а и |X ^ 3. Тогда полугруппа бинарных отношений Ba(X) нерегулярна.

Теорема 9. Пусть X — множество, где IX ^ 3, а a — отношение эквивалентности, заданное на X. Полугруппа B"a(X) регулярна в том и только том случае, когда a — отношение равенства на множестве X.

Подведем итог: остаются слабо исследованными полугруппы полных преобразований, сохраняющие два бинарных отношения, поскольку рассмотрен только случай цепи. Не изучены полугруппы частичных и многозначных преобразований, сохраняющих два бинарных отношения.

Литература

1. Амербаев В. М., Кожухов И. Б., Ревякин А. М. Представления бинарных отношений в теории измерений и полезности для оценки социального капитала // Вестник Московского городского педагогического университета. Серия: Экономика. 2012. № 4 (16). C. 66—71.

2. Представления бинарных отношений и регулярные полугруппы изотонных преобразований / В. М. Амербаев, И. Б. Кожухов, А. М. Ревякин, В. А. Ярошевич // Комбшаторш конфтурацн та 1х застосуван-ня: Матер1али 13-го М1жвуз1вского науково-практичного семшара (13—14 квттня 2012 р.). Кировоград: ДЛАУ, 2012. С. 14—21.

3. Математические методы принятия решений и модели в управлении и во внешнеэкономической деятельности / И. Н. Абанина, В. М. Амербаев, В. В. Бардушкин и др.; под общ. ред. И. Н. Абаниной, А. М. Ревякина. М.: МГАДА, 2013. 163 с.

4. Ярошевич В. А. О регулярных полугруппах изотонных преобразований частично упорядоченных множеств // Вестник Московского городского педагогического университета. Серия: Экономика. 2012. № 4 (16). С. 130—134.

5. Клиффорд А., Престон Г. Алгебраическая теория полугрупп. Т. 1, 2. М.: Мир, 1972.

6. Айзенштат А. Я. Регулярные полугруппы эндоморфизмов упорядоченных множеств //

Ученые записки Ленинградского гос. пед. ин-та им. А. И. Герцена. 1968. Т. 387. С. 3—11.

7. Adams M. E., Gould M. Posets whose monoids of order-preserving maps are regular // Order. 1989. Vol. 6 (2). P. 195—201.

8. Ким В. И., Кожухов И. Б. Условия регулярности полугрупп изотонных преобразований счетных цепей // Фундаментальная и прикладная математика. 2006. Т. 12. Вып. 8. С. 97—104.

9. Ярошевич В. А. О свойствах полугрупп частичных изотонных преобразований квазиупорядоченных множеств // Вестник МГАДА. Серия: Философские, социальные и естественные науки. 2011. № 3 (9). С. 139—144.

10. Ярошевич В. А. Отображения, согласующиеся с бинарными отношениями // Математический вестник педвузов и университетов ВолгоВятского региона. 2009. № 11. С. 135—142.

11. Ким В. И., Кожухов И. Б., Ярошевич В. А. Слабо регулярные полугруппы изотонных преобразований // Фундаментальная и прикладная математика. 2012. Т. 17. Вып. 4. С. 145—166.

12. Huisheng Pei, Dingyu Zou. Green’s Equivalences on Semigroups of Transformations Preserving Order and an Equivalence Relation // Semigroup Forum. 2005. Vol. 71 (2). P. 241—251.

13. Lei Sun, Hui Sheng Pei. Green’s Relations on Semigroups of Transformations Preserving Two Equivalence Relations // Journal of Mathematical Research & Exposition. 2009. Vol. 29. № 3. P. 415—422.

14. Deng Lun-Zhi, Zeng Ji- Wen, You Tai-Jie.

Green’s relations and regularity for semigroups of transformations that preserve order and a double direction equivalence // Semigroup Forum. 2012. Vol. 84 (1). P. 59—68.

15. Кожухов И. Б., Ярошевич В. А. Полугруппы отображений, сохраняющих бинарное отношение // Фундаментальная и прикладная математика. 2008. Т. 14. Вып. 7. С. 129—136.

16. Творогов А. В., Ярошевич В. А. О регулярности полугруппы многозначных преобразований, сохраняющих заданное бинарное отношение // Алгебра, теория чисел и дискретная геометрия: современные проблемы и приложения: Мат-лы XIII Междунар. конф., посвящ. 85-летию со дня рожд. проф. С. С. Рышкова. Тула: Изд-во ТулГПУ им. Л. Н. Толстого, 2015. С .135—137.

Амербаев Вильжан Мавлютинович (1931— 2014) — доктор технических наук, профессор вычислительной математики, академик НАН Республики Казахстан, главный научный сотрудник Института проблем проектирования в микроэлектронике РАН.

Кожухов Игорь Борисович — доктор физико-математических наук, профессор кафедры высшей математики № 1 (ВМ-1) МИЭТ. E-mail: kozhuhov i b@mail.ru

Экономические и социально-гуманитарные исследования № 4 (8) 2015

21

Организационно-экономические аспекты инновационного развития

Ревякин Александр Михайлович — кандидат физико-математических наук, доцент кафедры высшей математики № 2 (ВМ-2) МИЭТ. E-mail: arevyakin@mail.ru

Ярошевич Владимир Александрович — кандидат физико-математических наук, доцент кафедры ВМ-1 МИЭТ.

E-mail: v-yaroshevich@yandex.ru

22

Экономические и социально-гуманитарные исследования № 4 (8) 2015