Упорядоченные множества

33

Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

НИЖНЕКАМСКИЙ МУНИЦИПАЛЬНЫЙ ИНСТИТУТ

Кафедра информатики математики и естественно - научных дисциплин

РЕФЕРАТ

по дисциплине «Абстрактная алгебра»

Тема: Упорядоченные множества

Руководитель Р.М. Мунипов

Студент А.В. Глазунов

Нижнекамск 2007

Введение

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

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

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

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

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

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

Бинарное отношениена множестве А называется антисимметричным если:

(а,в А) а ф в в ф а

Бинарное отношение на множестве А называется рефлексивным если:

(aA) aa

Бинарное отношение на множестве А называется транзитивным если:

(a,в,cA) aв вc > а с

Пример 1.

Отношение делимости (нацело) на множестве натуральных чисел N антисимметрично. В самом деле, если ав, ва, то существуют натуральные q₁,qN, такие, что а=вq₁, в=аq откуда а=аq₁q, то есть q₁q=1. Но,

q₁,qN,следовательно q₁ =q=1, откуда следует, что а = в.

Рефлексивное антисимметричное транзитивное бинарное отношение на множестве А называется отношением порядка (частичного порядка) на множестве А.

Множество А с заданным на нем отношением частичного порядка ? называют частично упорядоченным множеством и обозначают < А; ? >.

В дальнейшем для удобства будем пользоваться сокращением ЧУМ, обозначающим частично упорядоченное множество.

Пример 2.

< N, ? > ? обычное нестрогое неравенство чисел (в школьном смысле). Нужно доказать транзитивность, рефлексивность и антисимметричность этого отношения ?.

a) a ? a ,(2 ? 2) - рефлексивность,

b) если а ? в , в ? с, то a ? c, (3 ? 4, 4 ? 5 > 3 ? 5 ) - транзитивность,

c) если a ? в , в ? a, то a=в , (3 ? 3, 3 ? 3 > 3=3 ) - антисимметричность.

Из этого следует, что < N, ? > - ЧУМ.

Пример 3.

< N, > .

a) Отношение делимости на множестве натуральных чисел N рефлексивно, т.к всякое число кратно самому себе, т.е т.к для любого аN всегда a = a•1 (1N), это , по смыслу отношение , имеем а а . Следовательно, рефлексивно .

б) Если первое число делится нацело на второе(т.е кратное второму), а второе кратно третьему, то первое кратно третьему, значит отношение транзитивно, т.е. если а в, в с, a,в,cN. Значит, существуют такие q,qN, что

a = в q,

в = c q,

a = c (qq).

Обозначим: q = qqN. Имеем

a = cq,

где qN, т.е. а с - по определению . Следовательно, отношение транзитивно.

в) Антисимметричность отношения следует из того, что два натуральных числа, кратных друг другу, равны между собой, т.е. если ав, ва, то существуют такие q₁,qN, что

а=вq₁,

в=аq,

а=аq₁q,

то есть q₁q=1. Но, q₁,qN,следовательно q₁ =q=1, откуда следует, что а = в. Следовательно антисимметрично.

Поэтому есть частичный порядок и , стало быть, < N, > - ЧУМ(частично упорядоченным множеством).

Элементы a,в ЧУМа А называются несравнимыми и записываются

если a ? в и в ? а.

Элементы a,в ЧУМа А называются сравнимыми если a ? в или в ? а.

Частичный порядок ? на A называется линейным, а само ЧУМ линейно - упорядоченным или цепью, если любые два элемента из А сравнимы , т.е. для любых a,в A, либо a ? в, либо в ? a.

Пример 4.

< N, ? >, <R, ? > - являются цепью. Однако <В(М) ; > ,где В(М) - множество всех подмножеств множества М или В(М) называется булеаном на множестве М, не является цепью , т.к. не для любых двух подмножеств множество М одно является подмножеством другого.

Пусть < А, ? > - произвольный ЧУМ.

Элемент mA называется минимальным, если для любого x A из того, что x ? m следует x = m.

Смысл этого понятия в том, что А не содержит элементов строго меньших этого элемента m. Говорят , что х строго меньше m и записывают х < m, если x ? m, но притом x ? m. Аналогично определяется максимальный элемент этого ЧУМ. Ясно, что если m, m- разные минимальные (максимальные) элементы ЧУМ, то m || m.

В теории частично упорядоченных множеств условие a ? в иногда читают так: элемент а содержится в элементе в или элемент в содержит элемент а.

Лемма.

Каждый элемент конечного ЧУМа содержит минимальный элемент и содержится в максимальном элементе этого ЧУМа.

Доказательство:

Пусть а - произвольный элемент конечного ЧУМа S. Если а - минимальный элемент, то в силу рефлексивности, лемма доказана. Если А не минимален, то найдется элемент а такой, что

а< а (1)

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

а< а (2)

Если а минимален, то из (1), (2), благодаря транзитивности, заключаем, что а содержит минимальный элемент а. Если же а не минимален, то

а< а (3)

для некоторого аS. И так далее. Указанный процесс не может быть бесконечным в виду конечности самого множества S.

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

а< а<< а< а< а

За счет транзитивности отсюда следует, что элемент а содержит минимальный элемент а. Аналогично, элемент а содержится в максимальном элементе. Лемма доказана.

Следствие.

Конечное ЧУМ содержит, по меньшей мере, один минимальный элемент.

Сейчас мы введем важное для дальнейшего изложения понятие диаграммы конечного ЧУМа S.

Вначале берем все минимальные элементы m, m,, m в S. Согласно следствию такие найдутся . Затем в частично упорядоченном множестве

S = S \ {m, m,, m},

которые , как и S , является конечным , берем минимальные элементы, , , , и рассматриваем множество

= S\ {, , , }

Элементы “ первого ряда “m, m,, m изображаем точками. Несколько выше отмечаем точками элементы “ второго ряда” , , , и соединяем отрезками точки в том и только том случаи, если m<

Далее отыскиваем минимальные элементы ЧУМа , изображаем их точками “третьего ряда” и соединяем точками “второго ряда” указанным выше способом. Продолжаем процесс до тех пор , пока не будут исчерпаны все элементы данного ЧУМа S. Процесс конечен в силу конечности множества S. Полученную совокупность точек и отрезков называют диаграммой ЧУМа S. При этом a < в тогда и только тогда, когда от “точки” а можно перейти к “точки” в по некоторой “восходящей” ломаной. В силу этого обстоятельства , любое конечное ЧУМ можно отождествить с его диаграммой.

Пример 5.

Здесь задано диаграммой ЧУМ

S = {m, m,, , , },в которой m< , m< , m< m< , m< m< , m< .

Элемент m называется наименьшим элементом ЧУМа, если для любого x A всегда m ? x.

Понятно, что наименьший элемент является минимальным, но обратное не верно: не всякий минимальный элемент является наименьшим. Наименьший элемент (если такой имеется) только один. Аналогично определяется наибольший элемент.

Пример 6.

Это ЧУМ , элементы которого попарно несравнимы. Такие частично упорядоченные множества называются антицепями.

Пример 7.

Эта цепь с наименьшим и наибольшим элементом. Где 0 - наименьший элемент , а 1 - наибольший элемент.

Пусть М - подмножество частичного упорядоченного множества А. Элемент а A называют нижней гранью множества М, если а ? х для любого x М.

Наибольшая из всех нижних граней множества М, если она существует, называется точной нижней гранью множества М и обозначают inf M.

Пусть < А, ? > - произвольный ЧУМ. Элемент сA называется точной нижней гранью элементов a,в A, если с = inf{a,в}.

Замечание 1.

Не во всяком ЧУМ для любых двух элементов существует точная нижняя грань.

Покажем это на примере.

Пример 8.

Для {a;c},{d;e} нет нижней грани,

inf{a;в}=d, inf{в;c}=e.

Пример 9.

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

inf{a;в}=d, inf{a;d}=d, inf{a;0}=0, inf{a;c}=0, inf{a;e}=0,

inf{в;c}=e, inf{в;e}=e, inf{в;d}=d,

inf{c;e}=c, inf{c;0}=0, inf{c;d}=0,

inf{d;e}=0, inf{d;0}=0,

inf{e;0}=0.

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

Пример 10.

Приведем пример ЧУМ, которое не является полурешеткой.

Пусть < N, ? > - линейно - упорядоченное множество натуральных чисел и e,eN. На множестве N=N{ e ,e} определим бинарное отношение ? , пологая что x ? y, если x,y N, где x ? y, или если x N, y { e ,e}. Также считаем по определению : e ? e ,e? e.

Диаграмма этого ЧУМ следующая:

Любое натуральное число n ? e и n ? e, но в N нет наибольшего элемента, следовательно, N - ЧУМ, но не полурешетка.

Итак, по самому определению, полурешетка есть модель (как множество с отношением ? ). Как мы сейчас увидим к понятию полурешетки возможен и другой подход, а именно, полурешетку можно определить как некоторую алгебру.

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

Произвольную полугруппу обычно обозначают S (semigroup).

Определение. Элемент eS называется идемпотентом, если

e= e, то есть e · e = e.

Пример 11.

Полугруппа < N; · > ? обладает единственным идемпотентом 1.

Полугруппа < Z; + > ? обладает единственным идемпотентом 0.

Полугруппа < N; + > ? не имеет идемпотента, т.к. 0N.

Для любого непустого множества X, как обычно, через обозначается множество всех подмножеств множества X - булеан множества X. Полугруппа <В;> - такова, что каждый ее элемент идемпотентен.

A В , A = AA.

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

Пример 12.

Пусть X - произвольное множество.

B- множество всех подмножеств множества Х.

B- называется булеаном на множестве Х.

Если Х = {1,2,3} , то

B = {O,{1},{2},{3},{1,2},{2,3},{1,3},{1,2,3}}.

Так как пересечение двух подмножеств множества Х вновь является подмножеством в Х, то имеем группоид < В;> , более того , это полугруппа и даже связка, так как

А В и А= АА =А.

Точно также, имеем связку <; В > .

Коммутативная связка называется полурешеткой.

Пример 13.

Пусть Х = {1,2,3}, построим диаграмму < В ; >.

33

Размещено на http://www.allbest.ru/

Приведем примеры ЧУМ, но не полурешетки.

Пример 14.

ЧУМ с двумя нижними гранями е и d , которые между собой не сравнимы: е||d. Следовательно, inf{a;с} не существует.

Пример 15.

ЧУМ с двумя нижними гранями с и d, которые между собой несравнимы: с||d. Следовательно, inf{a;в} не существует.

Приведем примеры полурешеток.

Пример 16.

Диаграмма:

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

inf{a;в}=в, inf{a;с}=с, inf{a;d}=d,

inf{в;c}=d, inf{в;d}=d,

inf{c;d}=d.

Пример 17.

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

inf{a;в}=в, inf{a;с}=с, inf{в;c}=с.

Теорема 1.

Пусть <S ; ? > - полурешетка. Тогда <S ; > коммутативная связка, где

aв = inf {a,в} (*).

Доказательство:

Нужно доказать, что в <S ; > выполняются следующие тождества:

(1) x y = y x

(2) (x y) z = x ( y z)

(3) x x = x

1) Согласно равенству(*)

x y = inf (x,y) = inf (y,x) = y x

2) Обозначим а = (x y) z, в = x ( y z)

Докажем, что а = в.

Для этого достаточно доказать , что

а ? в (4)

в ? а (5) (в силу антисимметричности)

Обозначим

с = x y , d = y z

По смыслу, а точная нижняя грань между с и z

а ? с , а ? z , c ? x,

следовательно, в силу транзитивности a ? x.

Аналогично, а ? y, т.е. а - общая нижняя грань для y и z. А d - их точная нижняя грань .

Следовательно, a ? d, но в = inf {x,d}.

Из неравенства a ? x , a ? d следует , что а - некоторая общая нижняя грань для х и d, а в - их точная нижняя грань, следовательно,

а ? в (4) доказано.

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

Из (4) и (5) , в виду антисимметричности, заключаем, что а = в.

Этим мы доказали ассоциативность операции ().

3) Имеем x х = inf {x,x} = x.

Равенство выполняется за счет рефлексивности : х ? х.

Т.о. построенная алгебра <S ; > будет коммутативной идемпотентной полугруппой , т.е. коммутативной связкой.

Теорема 2.

Пусть <S ; · > - коммутативная идемпотентная полугруппа, тогда бинарное отношение ? на S, определяемое равенство

? = {(a,в) S?S | a·в = а},

является частичным порядком. При этом ЧУМ <S ; ? > является полурешеткой .

Доказательство:

1) рефлексивность ?.

По условию <S ; · > удовлетворяет трем тождествам:

(1) х= х

(2) х·y = y·x

(3) (x·y)·z = x·(y·z)

Тогда х·х = х= х - в силу (1). Поэтому х ? х.

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	в	с
в	-	в	-
с	в	а	-

а·в= в, но в·а не определено, т.е. в·а = O . Символ “ O “ не принадлежит 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,zS) (x·y)·z O x·(y·z) > (x·y)·z = x·(y·z) (*)

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

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

(х,y,zS) (x·y)·z O y·z > (x·y)·z = x·(y·z)

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

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

(х,y,zS) [(x·y)·z O x·(y·z) O > (x·y)·z = x·(y·z)] (*)

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

Пример 3.

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

*	a	в	с
а	-	-	-
в	с	-	-
с	-	в	с

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

Пусть (x·y)·z O т.к. х а, то либо х = с х = в

1) пусть х = с, тогда у = в у = с

а) пусть у = в, тогда z = a

(с·в)·а O с·(в·а) определено

(с·в)·а = с·(в·а) равенство выполняется

б) пусть у = с, тогда z = в z = с

а') если z = в , тогда

(с·с)·в O с·(с·в) определено

(с·с)·в = с·(с·в) равенство выполняется

б') если z = с, тогда

(с·с)·с O с·(с·с) определено

(с·с)·с = с·(с·с) равенство выполняется

2) пусть х = в, тогда у = а , а z = в z = c

а) если у = а и z = в

(в·а)·в O= в·(а·в) не определено

(в·а)·в в·(а·в) равенство не выполняется

б) пусть у = а и z = с

(в·а)·с O= в·(а·с) не определено

(в·а)·с в·(а·с) равенство не выполняется

Итак, по определению, частичный группоид не является сильно ассоциативным . Но это еще не означает, что (S ; · ) не является слабо ассоциативным. Выясним это.

Пусть (x·y)·z O x·(y·z) O .

При х а, у а, а именно, когда

х = в х = с

у = в у = с

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

Пример 4.

Пусть А = {a, в,с}, можно задать на А следующую таблицу Кэли. Получим некоторый частичный группоид. Проверим будет ли этот группоид средне ассоциативным.

*	a	в	с
а	с	а	-
в
с	а	а	-

Пусть (x·y)·z O т.к. х в, тогда х = а х = с

1) пусть х = а, тогда у = а у = в

а) пусть у = а, тогда z = a, z = в

а') если z = а , тогда

(а·а)·а O а·a определено

(а·а)·а а·(а·a) равенство не выполняется

б') если z = в, тогда

(а·а)·в O а·в определено

(а·а)·в а·(а·в) равенство не выполняется

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

Пусть (x·y)·z O x·(y·z) O, т.к. х в, тогда х = а х = с

1) пусть х = а, тогда у = а у = в

а) пусть у = а, тогда z = a, z = в

а') если z = а , тогда

(а·а)·а O= а·(а·a) не определено

(а·а)·а а·(а·a)

б') если z = в, тогда

(а·а)·в O а·(а·в) определено

(а·а)·в = а·(а·в) равенство выполняется

б) пусть у = в, тогда z = a, z = в

а') если z = а , тогда

(а·в)·а O= а·(в·a) не определено

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

б') если z = в, тогда

(а·в)·в O а·(в·в) не определено

(а·в)·в а·(в·в) равенство не выполняется

2) пусть х = с, тогда у = а , у = в

а) пусть у = а, тогда z = a, z = в

а') если z = а , тогда

(с·а)·а O= с·(а·a) не определено

(с·а)·а с·(а·a) равенство не выполняется

б') если z = в, тогда (с·а)·в O с·(а·в) определено

(с·а)·в = с·(а·в) равенство выполняется

Итак , мы видим что частичный группоид является слабо ассоциативным при х = а и z = в или при х = с если у = а и z = в.

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

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

(х,yS) x·y = y·х

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

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

(х,y,zS) (x·yO y·z) > [(x·y)·z O x·(y·z)]

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

(хS) х= х

Приведем пример некатенарного частичного группоида. Пример 5.

^	а	в	с	d
a	a	-	c	d
в	-	в	с	d
с	c	c	c	-
d	d	d	-	d

Имеем с а = с O, а d = d O. Однако, (с а) d = c d O. Следовательно, заданный ЧГ не является катенарным.

Ясно, что понимаем под термином “ общая верхняя грань” элементов а и в некоторого ЧУМ.

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

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

Пример 6.

Чум не является категорийным, т.к. элементы с и d имеют верхнюю грань , но не имеют точную нижнюю грань.

Пример 7.

Частично упорядоченное множество, задаваемое таблицей Кэли:

	а	в	с	d	e	f	g	h	k	s
a	a	в	c	d	h	g	g	h	?	?
в	в	в	d	d	0	g	g	0	?	?
c	c	d	c	d	h	0	0	h	?	?
d	d	d	d	d	0	0	0	0	?	?
e	h	0	h	0	e	0	0	h	?	?
f	g	0	0	0	0	f	g	0	?	?
g	G	g	0	0	0	g	g	0	?	?
h	h	0	h	0	h	0	0	h	?	?
k	?	?	?	?	?	?	?	?	k	s
s	?	?	?	?	?	?	?	?	s	s

33

Размещено на http://www.allbest.ru/

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

Пример 8.

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

имеющее следующую таблицу Кэли:

*	а	в	с	d	f
а	а	с	с	-	-
в	с	в	с	-	-
с	с	с	с	-	-
d	-	-	-	d	f
f	-	-	-	f	f

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

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

Пример 9.



называется диамантом, и определяется полурешеткой, имеющей следующую таблицу Кэли:

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

Пример 10.

Диаграмма:

называется пентагоном, и определяется полурешеткой, имеющей следующую таблицу Кэли:

*	а	в	с	е	0
а	а	0	0	а	0
в	0	в	с	в	0
с	0	с	с	с	0
е	а	в	с	е	0
0	0	0	0	0	0

Пример 11.

Полурешетка, задаваемая таблицей Кэли:

*	а	в	с	е	0
а	а	0	0	а	0
в	0	в	0	в	0
с	0	0	с	с	0
е	а	в	с	е	0
0	0	0	0	0	0

имеет диаграмму:

Теорема 1.

Пусть (S ; ? ) - категорийное ЧУМ, тогда (S ; ) - катенарный идемпотентный коммутативный слабо ассоциативный частичный группоид.

Доказательство:

Для любого аS всегда

аа = inf{a,a} = a поэтому частичный группоид S идемпотентен.

Имеем ав = inf{a,в} = inf{в,a} = ва , а поэтому S коммутативен.

Проверим слабую ассоциативность.

Пусть (ав)с O а(вс) , обозначим

ав = d, вс = e, (ав)с = dс = f, а(вс) = ае = g

Докажем, что f = g.

По определению имеем f ? d ? a f ? a,

f ? d ? в f ? в (1)

f ? c (2)

Т.к. е = inf{в,с}, то из (1), (2) следует, что f ? e. Т.о. f - некоторая общая нижняя грань для а и е, а g - их точная нижняя грань, поэтому

f ? g (3)

Аналогично,

g ? f (4)

Неравенство (3), (4) и антисимметричность отношения ? обеспечивают f = g. Слабая ассоциативность доказана.

Проверим катенарность S.

Пусть ав O вс , обозначим ав = х , вс = y, отсюда х ? в, у ? в, т.е.

в - общая верхняя грань х и у. Т.к. ЧУМ S категорийно, то существует inf{х,у}, т.е. существует в S ху. Обозначим ху = z, покажем ,что

а(вс) = хс = z. Имеем z ? x, z ? y (т.к. z = inf{х,у}), y ? z z ? x, z ? c,

z - нижняя грань для х и с.

Обеспечим точность.

Пусть t ? x , t ? c ( t - какая - либо нижняя грань ), т.к. t ? x , то t ? a, t ? в, по условию t ? с, т. е. t - общая нижняя грань для в и с. Отсюда следует по определению у , t ? y.

Итак, t ? x, t ? у следовательно t ? z (по определению z).

Катенарность доказана.

Теорема 2.

Если (S ; ·) - катенарный идемпотентный коммутативный слабо ассоциативный частичный группоид, то отношение

? = { (а,в) S?S | ав = а} (2)

Является отношением порядка. При этом ЧУМ <S ; ? > - является катенарным.

Доказательство:

Докажем рефлексивность отношения ? . Т.к. частичный группоид S идемпотентен , то a·a = a отсюда , по определению (2) а ? а.

Проверим антисимметричность.

Если а ? в , в ? а ,то а·в = а, в·а = в, левые части равны в виду коммутативности , значит равны и правые, следовательно а = в.

Осталось доказать транзитивность.

Пусть а ? в , в ? с, тогда а·в = а, в·с = в, а·с = (а·в)·с. В силу катенарности имеем (а·в)·с O , а·(в·с) O , отсюда в силу слабой ассоциативности

(а·в)·с = а·(в·с), а поэтому, а·с = а·(в·с) = а·в = а.

Итак, а·с = а, т.е. а ? с.

Т.о. имеем ЧУМ <S ; ? > .

Проверим категоричность ЧУМ.

Пусть z - общая верхняя грань для х и у. Следовательно, х ? z, y ? z , отсюда х·z = x, y·z = y, тогда z·y = y. В силу катенарности (x·y)·z O x·y O.

Обозначим х·у =s, докажем , что s точная нижняя грань .

Имеем s·x = (x·y)·x = x·(x·y) = (x·x)·y = x·y = s (в виду катенарности и слабой ассоциативности), следовательно, s ? x, т.е. s - общая нижняя грань.

Из этих теорем вытекают известные в теории полурешеток два следствия.

Следствие 1.

Если <S ; · > - идемпотентная коммутативная полугруппа, то отношение ? , определенное равенством (2), является частичным порядком. При этом для любых двух элементов в S существует точная нижняя грань.

Следствие 2.

Если <S ; · > - частично упорядоченное множество, в котором любых двух элементов существует точная нижняя грань, то относительно операции

ав = inf{a,в} (3)

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

Список литературы

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

Грейцер. Общая теория решеток.Москва.-284с.

Кожевников О.Б. Частично упорядоченные множества частичных группоидов.Москва,1998. - 680с.

Е.С. Ляпин. Полугруппы. Москва: физмат, 1960.- 354с.

Ляпин Е.С. Алгебра и теория чисел. Москва, 1980.-589с.

Размещено на Allbest.ru