Упорядоченные множества (стр. 5 из 8)

2) антисимметричность ≤ .

Пусть х ≤ у и у ≤ х, тогда по определению ,

(4) х·у = х

(5) у·х = у

отсюда, благодаря коммутативности, имеем х = у.

3) транзитивность ≤.

Пусть х≤ у и у ≤ z тогда , по определению,

(6) х·у = х

(7) у·z = у

Имеем x·z = (x·y)·z

x·(y·z) х·у

х

Итак, x·z = x, то есть х ≤ z.

Таким образом, имеем ЧУМ <S ; ≤ >. Остается показать, что для любых (а, в)

S существует inf{а,в}.

Берем произвольные а,в

S и докажем, что элемент с = а·в является inf{а,в}, т.е с = inf{а,в}.

В самом деле ,

с·а = (а·в)·а

а·(а·в) (а·а)·в

а·в = с,

т.о. с ≤ а.

Аналогично, с·в = (а·в)·в

а·(в·в)

а·в = с,

т.е. с ≤ в.

Итак, с – общая нижняя грань {а,в}.

Докажем ее точность.

Пусть d – некоторая общая нижняя грань для а и в:

(8) d ≤ a

(9) d ≤ в

Тогда

(10) d·a = d

(11) d·в = d

Поэтому

d·c = d·(а·в)

(d·а)·в

d·в

d,

d·c = d, следовательно, d ≤ c.

Вывод: с = inf{a,в}.

Доказанные теоремы 1 и 2 позволяют смотреть на полурешетки с двух точек зрения: как на ЧУМ, и как на алгебре (идемпотентные коммутативные полугруппы).

2. Вполне упорядоченные множества

Теорию упорядоченных множеств создал Г. Кантор. В 1883 он ввёл понятие вполне упорядоченного множества и порядкового числа, а в 1895 – понятие упорядоченного множества и порядкового типа. В 1906–07 С. О. Шатуновский сформулировал определения направленного множества (у Шатуновского – расположенный комплекс) и предела по направленному множеству (амер. математиками Э. Г. Муром и Г. Л. Смитом эти же понятия были рассмотрены независимо от Шатуновского, но значительно позднее – в 1922). Общее понятие частично упорядоченного множества принадлежит Ф. Хаусдорфу (1914).

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

Упорядоченные множества, имеющие одинаковый порядковый тип, обладают и одинаковой мощностью, так что можно говорить о мощности данного порядкового типа. С др. стороны, конечные упорядоченные множества одинаковой мощности имеют один и тот же порядковый тип, так что каждой конечной мощности соответствует определённый конечный порядковый тип. Положение меняется при переходе к бесконечным множествам. Два бесконечных упорядоченных множества могут иметь одну и ту же мощность, но разные порядковые типы.

3. Частичные группоиды и их свойства

Как известно, бинарная алгебраическая операция на множестве S – это отображение из декартового квадрата S×S. В этом случае говорят , что задано действие на S. Мы его в этом параграфе будем называть полным действием.

Всякое отображение из подмножества S×S в S называется частичным действием на S. Иными словами, частичное действие на S – это некоторая функция из S×S → S.

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

S произведение а·в либо не определено, либо определено однозначно. Попросту говоря, здесь не любые элементы перемножены.

Множество S с заданным в нем частичным умножением называется частичным группоидом и обозначается (S ; · ) в отличие от полного группоида < S ; · >.

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

Пример 1.

•	a	в	с
а	a	в	с
в	─	в	─
с	в	а	─

а·в= в, но в·а не определено, т.е. в·а = Ø . Символ “ Ø “ не принадлежит S , т.е. не является элементом из S.

Пример 2.

Рассмотрим ЧУМ (S ; ≤ ).

S = {a,в,c,d}, где а ≤ а, в ≤ в, с ≤ с, d ≤ d, с ≤ а, с ≤ в, d ≤ а, d ≤ в.

В произвольном ЧУМе (S ; ≤ ) условимся обозначать:

а

в = inf{a,в}.

Тогда указанное в примере ЧУМ относительно этого частичного действия

, является частичным группоидом (S ; ), таблицей Кэли которого является следующая

^	а	в	с	d
a	a	─	c	d
в	─	в	с	d
с	c	c	c	─
d	d	d	─	d

В этом параграфе мы рассмотрим три вида ассоциативности: сильная ассоциативность, средняя ассоциативность, слабая ассоциативность.

Определение 1.

Частичный группоид (S ; · ) называется слабо ассоциативным, если

(

х,y,z

S) (x·y)·z

Ø x·(y·z) → (x·y)·z = x·(y·z) (*)

Определение 2.

Частичный группоид (S ; · ) называется средне ассоциативным, если

(

х,y,z

S) (x·y)·z

Ø y·z → (x·y)·z = x·(y·z)

Определение 3.

Частичный группоид (S ; · ) называется сильно ассоциативным, если

(

х,y,z

S) [(x·y)·z

Ø x·(y·z) Ø → (x·y)·z = x·(y·z)] (*)

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

Пример 3.

Дано А = {a,в,с}. Зададим на А частичное действие умножение “ частичной таблицей Кэли”.

•	a	в	с
а	─	─	─
в	с	─	─
с	─	в	с

Получим некоторый частичный группоид. Проверим будет ли группоид сильно ассоциативным.