Полная упорядоченность множества целых чисел. Упорядоченные множества. Свойства операции сложения

Будем говорить, что натуральное число а больше , чем натуральное число b (и обозначать а > b ), если существует такое натуральное k, что а = b + k.

Теорема 1 . Единица не больше никакого натурального числа.

Действительно, условие 1 > a влечёт за собой 1 = а + k, что невозможно: для k = 1 получим 1 = а / , что противоречит первой аксиоме натуральных чисел; для k ¹ 1 найдём для него предшествующий и вновь придем к тому же противоречию.

Данное отношение «больше» является антирефлексивным (не верно, что а > a) и транзитивным (а > b /\ b > c => a > c), то есть является отношением строгого порядка . Более того, данное отношение является отношением линейного порядка, то есть для множества натуральных чисел справедлива теорема о трихотомии:

Теорема о трихотомии: Для любых двух натуральных чисел справедливо одно и только одно из следующих трёх утверждений:

Доказательство : Вначале покажем, что никакие два из трёх условий не выполняются одновременно. Допустим, что выполнены условия 1 и 2. Тогда

a = b + k, b = a + n => a = a + (n + k) => a > a,

что противоречит антирефлексивности отношения «больше». Аналогично устанавливается несовместность условий 2 и 3, условий 1 и 3.

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

а = с / = с + 1 = 1 + с = b + c => a > b.

Таким образом, для b = 1 утверждение теоремы справедливо. Сделаем индукционное предположение о том, что теорема справедлива для некоторого х, а именно, что х сравним с числом а, то есть возможны три варианта: либо a > x, либо x > a, либо х = а. Тогда докажем, что и х / также сравним с а. В первом случае a > x, то есть а = х + k. В зависимости от того, будет данное k равно 1 или нет, получим

а) а = х + 1 = х / (теорема справедлива)

б) а = х + с / = х + с + 1 = х + 1 + с = х / + с => a > x / .

Во втором случае x > a, но тогда

х / = (а + m) +1 = a + (m + 1),

то есть x / > a. Аналогично при х = а, х / = х + 1 = а + 1, то есть снова x / > a. Теорема полностью доказана.

Теперь можно ввести понятия <, £, ³.

a < b ó b > a;

a £ b ó a < b \/ a = b

a ³ b ó a > b \/ a = b.

Свойства монотонности:

Для операции сложения:

1) а > b => a + c > b + c;

2) a + c > b + c => а > b;

3) а > b /\ c > d=> a + c > b + d.

<, £, ³.

Для операции умножения:

4) а > b => a×c > b×c;

5) Закон сокращения: ас = bc => a = b

6) ac > bc => а > b;

7) а > b /\ c > d=> ac > bd.

Те же свойства имеют место и для других знаков <, £, ³.

Приведём в качестве примера доказательства свойств 4 и 5. Так как а > b, по определению а = b + k, тогда а×с = (b + k)×c = b×c + k×c, что означает, что a×c > b×c, и свойство 4 доказано. Свойство 5 докажем методом от противного. Пусть ас = bc, но предположим, что а ≠ b, но тогда, по теореме о трихотомии, либо а > b, либо b > a, но это означает, согласно свойству 4, что либо ас > bс, либо bс > aс, что противоречит условию (ас = bc).

Теорема о дискретности. Между двумя соседними натуральными числами нельзя вставить натуральное число:

(" а, х Î N) не верно, что а < x < a /

Доказательство (методом от противного). Пусть а < x < a / . Тогда х = а + k,

a / = x + n = a + k + n => a + 1 = a + k + n => 1 = k + n.

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

Терема Архимеда. Для любых натуральных чисел а и b существует такое натуральное n, что a < bn.

Доказательство проведём индукцией по b. Для b = 1, n = a / . Сделаем индукционное предположение, что для b = k требуемое n существует, то есть a < kn. Но тогда тем более a < k / n = kn + k. Теорема доказана.

Наименьшим элементом множества М будем называть такой элемент с Î М, что для любых элементов m Î M выполнено неравенство: с ≤ m.

Теорема о наименьшем элементе . Любое непустое подмножество множества натуральных чисел имеет наименьший элемент.

Доказательство : Если М – подмножество N, содержащее в себе 1, то 1 как раз и будет искомым наименьшим элементом. Если же 1 не входит в множество М, то рассмотрим вспомогательное множество А, состоящее из всех натуральных чисел меньших, чем все натуральные числа из множества М:

А = {a Î N | (" m Î M) a < m}.

Из этого построения, в частности следует, что множества А и М не имеют общих элементов. Кроме того, А – не пусто, так как 1 Î А. В А есть также элемент b, что b / Ï А. Действительно, если бы такого элемента не было, то по аксиоме индукции можно было бы доказать, что А = N , но тогда М было бы пусто, что не соответствует условию теоремы. Элемент b / = с как раз и будет наименьшим элементом во множестве М. Действительно, с £ m для любого m ÎМ (если бы это было не так, то неравенство с > m выполнялось бы хотя бы при одном натуральном m, но b Î A, поэтому b < m < c = b / , что противоречит теореме о дискретности). Кроме того, с не может быть строго меньше всех элементов множества М, иначе с Î А, что противоречит его выбору. Таким образом, с равен хотя бы одному элементу из М, а значит с Î М, то есть действительно с – наименьший элемент множества М. Теорема доказана.

Заметим, что не всякое подмножество множества натуральных чисел имеет наибольший элемент, но если это подмножество конечно, то в нём имеется и наибольший элемент. Верно и обратное. Если подмножество множества натуральных чисел имеет наибольший элемент, то это подмножество конечно. Можно доказать даже более общее утверждение: непустое подмножество множества натуральных чисел ограничено сверху тогда и только тогда, когда оно конечно (имеет наибольший элемент).

Задания для самостоятельного решения

№ 1.8. Докажите антирефлексивность и транзитивность отношения «больше» на множестве натуральных чисел.

№ 1.9. Докажите свойства монотонности 1, 2, 3, 6, 7 из данного параграфа.

№ 1.10. Докажите неравенства для всех натуральных n

а) 5 n > 7n – 3;

б) 2 n +2 > 2n + 5;

Кабиров Николай Николаевич,студент второго курса факультета физики, математики, информатики Таганрогского института имени А.П.Чеховафилиала) ФГБОУ ВО «Ростовский государственный экономический университетРИНХ)», г.Таганрог[email protected]

Ляхова Наталья Евгеньевна,кандидат физикоматематических наук, заведующий кафедрой математикиТаганрогского института имени А.П.Чехова филиала) ФГБОУ ВО «Ростовский государственный экономический университет РИНХ)», г.Таганрог[email protected]

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

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

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

1. Основные определения

Под бинарным отношением на множестве понимаетсяподмножество декартового произведения. Если, где, то будем писать и говорить, “что находится в отношении с ”.Важным типом бинарных отношений являются отношения частичной упорядоченности, т.е.бинарные отношения, обладающие свойствами рефлексивности, транзитивности и антисимметричности. Множество с заданной в нем частичной упорядоченностью называется частично упорядоченным. Для записи упорядоченности обычно употребляется символ; если и, то, в зависимости от обстоятельств, говорится, что меньше или равно, содержится в, предшествует b.Пусть в множестве задана частичная упорядоченность. Элементы и этого множества будут называться сравнимыми, если или. Далеко не всякие два элемента из обязаны быть сравнимыми –именно по этой причине можно говоритьо ”частичной” упорядоченности. Так получается тривиальная частичнаяупорядоченность множества, если положить, что лишь при то есть различные элементы из будут несравнимыми.Частично упорядоченное множество, в котором любые два элемента сравнимы, называется упорядоченным множеством или линейно упорядоченным множеством или цепью.В различных разделах математики упорядоченные и частично упорядоченные множества встречаются чрезвычайно часто. В качестве примеровупорядоченных множеств можно указать множество натуральных чисел и множество действительных чисел, оба в их естественной упорядоченности. Примерами частично но не линейно) упорядоченных множеств служатследующие множества:–множество

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

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

2. Порядки наN,·, порожденные конечным множеством пар

Легко видеть, что каждую пару натуральных чисел можно представить в виде, где n–натуральное число, а q–положительная дробь. Например,пару можно записать. Пусть

произвольное конечное подмножество декартова квадрата. Тогда согласно вышесказанному можно представить в виде:

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

Одновременно не равных нулю, .Ясно, что определение является обобщением известного понятия антисимметричности.

Определение.Пусть

антисимметричное множество пар. Всякое натуральное число, для которого существует две такие последовательности, где и, где такие что,

Где первое число пары из множества, назовем числом, а числа

числами множества.

Теорема1. Если

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

Доказательство. Для доказательства теоремы необходимо показать, что, вопервых, отношение порядка, а, вовторых,

совпадает с порядком, порожденным множеством.

Докажем первую часть теоремы, т.е. докажем, что

рефлексивно, транзитивно, антисимметрично и стабильно относительно умножения.1) Рефлексивность следует из определения отношения.2) Пусть

и. Из условия имеем,

А из условия имеем,

Таким образом, для можно указать две последовательности

и, такие, что,

Т.е. -число, а -число множества. Следовательно. Случаи, когда или являются очевидными. Транзитивность доказана.3) Пусть и.Из условия следует,что.Из условия следует, что.Выше доказана транзитивность, следовательно,

и при этом.Так как все, эти равенстваможно записать в виде

Из последнего равенства следует, что. Но это возможно лишь при, так как множество антисимметрично. Учитывая, что и, получаем. Следовательно. Антисимметричность доказана.4) Стабильность относительно умножения,очевидно,следует из стабильности отношения равенства, которое используется для определения и чисел множества.Докажем вторую часть теоремы. Обозначим через порядок порожденныймножеством. Необходимо показать, что.Пусть произвольная пара из, тогда, т.к. существует последовательности и, такие что,т.е. число, а

число множества. Следовательно является порядком, содержащим множество, но

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

Пусть, т.е. является числом, а -числом множества. Это значит, что

, . (3)Покажем, что пара.Так как,то.Поэтому, согласно 1) . ()Учитывая,что

Получим.Значит, согласно 2), . ()Из ) и ) будет следовать, что.И так далее,продолжая этот процесс, получим.Или, учитывая 3), т.е. .Таким образом,показали, что.

Теорема доказана.

Теорема2. Для того, чтобы конечное множество пар было порождающим множествомнекоторого порядка необходимо и достаточно, чтобы оно являлось антисимметричным.

Доказательство.Если множество пар является антисимметричным, то по теореме 1оно будет порождающим множеством порядка.Покажемобратное. Пусть множество пар

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

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

принадлежат порядку. Тогда.

Если некоторый порядок содержит пары, то он содержит и пары, .Следовательно, он содержит пару Применяя этот факт к порядку, можно записать.Следовательно,

Получили, что порядок одновременно содержит пары

и.А это противоречит тому, что является отношением порядка.Полученное противоречие доказывает теорему.

3. Порядки, порожденные множеством взаимно простых пар

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

Определение.Множество пар таких,что, где,называется множеством взаимно простых пар.

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

Где является частичным порядком.

Доказательство.Для доказательства теоремы нужно показать рефлексивность, транзитивность, антисимметричность и стабильность указанного бинарного отношения. 1. Условие выполнено, т.к.существуют, такие,что. Рефлексивность доказана.2. Пусть. Из условия следует, что,аиз условия следует, что,тогда

Для определенности будем полагать, что все и все. Тогда можно записать, что.Отсюда

Выражая и, получим,.Подставляя значения

и в исходные равенства, находим, что,.Следовательно,

и транзитивность доказана. В случае, когда некоторые

пользуемся тем, что, и доказательство будет аналогичным.3. Пусть и. Покажем, что. Изусловия следует, что,.Из условия следует, что,.Замкнем эти пары транзитивно, получим, и по доказанному выше.Но так как,.Следовательно,и антисимметричность доказана.4. Стабильность очевидна. Теорема доказана.

Теорема4. Для того, чтобы порядок был порожден множеством взаимно простых пар необходимо и достаточно, чтобы он был порядком, описанным в теореме 3.

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

1. -минимальный

2. Пусть, тогда

Покажем, что эта пара принадлежит. Для этого достаточно показать, что из того что

следует, что

принадлежит, следовательно,.Из этого следует, что.Таким образом, включение выполняется для. Пусть включение выполняется для, т.е. .Тогда.Так как, то.Следовательно, т.е. данное включение выполняется и пары принадлежат.Отсюда,азначит и.Таким образом, доказано, что.

Итак, получено и, следовательно,

и теорема доказана.

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

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

Рассмотрим порядкина полугруппе натуральных чисел по сложению.

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

и расположим их в порядке возрастания. Такое множество обозначим, т.е. ,

Теорема5. Для того, чтобы порядок был порожден множеством пар необходимо и достаточно, чтобы он был бинарным отношением

Доказательство. Докажем, что бинарное отношение является отношением порядка. Для этого нужно показать четыре свойства.1.Рефлексивнсть следует из определения.2.Докажем транзитивность. Пусть и.Из условия следует,что

Из условия следует,что,

Из этих равенствполучаем

Т.е. и транзитивность доказана.3.Антисимметричность. Пусть

и. Тогда имеют место равенства, (1) . (2)Подставим 1) в 2) и получим.А это значит, что.Но

и, следовательно,. Тогда, т.е. .Таким образом,

антисимметрично.4. Стабильность очевидна.

Следовательно,

Отношение порядка. Осталось показать, что является для порождающим множеством.

Обозначим

порядок, порожденный множеством пар. Докажем, что совпадает с.1. Произвольная пара из множества принадлежит. В то же время, согласно определению

можно записать,

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

Нужно показать, что.Учитывая записанные равенства, проделаем следующие рассуждения.

Из того, что,следует, что.Тогда,пары принадлежат. Отсюда.Изтого, что, следуетчто, то есть.Проделывая рассуждения аналогичные предыдущим, получим.Продолжая этот процесс, мы придем к следующему результату:, т.е. , а значит, .

Получаем, что, следовательно,.

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

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

Доказательство. 1. Если множество имеет один из указанных видов, то по теореме 5онопорождает порядок.

2.Пусть порождает порядок. Покажем, что оно является

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

Следовательно

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

И,аэто противоречит тому, что порядок. Следовательно в не может бытьодновременно пар и, т.е. является множеством или двойственным ему.

Теорема доказана.

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

стабильный порядокна.Изусловия следуют равенства,

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

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

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

Рассмотрим, например,порядокна, порожденный парой. Это будет обычный порядок. Заметим, что кроме него и двойственному ему порядка

Других линейных порядков на

нет. Минимальным порождающим множествомпорядка в

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

имеет бесконечное порождающее множество. Нетрудно заметить, что все порядки на, порожденные конечным множеством пар, имеют на

бесконечные порождающие множества.

5. Порядки, порожденные бесконечным множеством пар

Теорема7.Бесконечное множество пар

порождает порядок

на некоторой алгебре

тогда и только тогда, когда любое его конечное подмножество

порождает некоторый порядок

на этой алгебре. При этом определяется следующим образом:

тогда и только тогда, когда существует конечное, такое что.

Доказательство. Пусть порождает порядок. Выберем произвольное конечное подмножество

множества. Тогда минимальный подпорядок

Покажем обратное. Пустьпроизвольноеконечное подмножество

множества

порождает порядок. Рассмотрим отношение, такое что.1. , т.к. . Следовательно рефлексивно.2. Пусть

и.Тогда,такое что

и, такое что.Рассмотрим. Тогда можно записать, что

и. Получаем. Из этого следует. Таким образом, транзитивно.3. Пусть и. Тогда, такое что и, такое что.Но существует, что, и получаем. Следовательно антисимметрично.4.Пусть тогда, такое что. Следовательно, откуда.Т.е. стабильно.

Итак, удовлетворяет свойствам рефлексивности, транзитивности, антисимметричности и стабильности. Значит,

отношение порядка.Докажем, что есть порядок, порожденный бесконечным множеством. Обозначим

порядок, порожденный. Нужно показать, что.1. Произвольная пара содержится в, т.к. , что, Следовательно, . Но минимальный порядок, содержащий, следовательно.

2. Пусть–произвольная пара из, следовательно,что, т.е.

пара содержится в минимальном порядке, порожденном, но, откуда,и,следовательно,. Значит, .

Получили два включенияи, следовательно, т.е. множество является для порождающим.

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

Теорема доказана.

Из доказанной теоремы вытекают следствия.

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

порождало порядок

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

тогда и только тогда, когда существует конечное множество такое что,где

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

Определение. Бесконечное множество пар натуральных чисел называется–множеством, если любое его конечное подмножество является–множеством.

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

порождало порядок

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

М.: Наука, 1970, 393 c.2.Ляпин,Е.С. Упорядоченности в полугруппе преобразований/Е.С. Ляпин //Труды четвертого Всесоюзного математического съезда.Ленинград: Наука.1964.Т.2.С.1314.3.Кривенко, В.М.Соотношения предшествования, определяющие стабильные порядки на мультипликативной полугруппе натуральных чисел/В.М.Кривенко, Н.Е. Ляхова //XIXВсесоюзная алгебраическая конференция: Тезисы сообщений. –Институт прикладных проблем механики и математики АН УССР –Львов, 1987, Ч.1.С.148.

Упражнения

1.. Используя определение умножения, найдите значения выражений:
а) 3 3; 6) 3 4; в) 4 3.

2. Запишите свойство дистрибутивности умножения слева относительно сложения и докажите его. Какие преобразования выражений возможны на его основе? Почему возникла необходимость в рассмотрении дистрибутивности умножения слева и справа относительно сложения?

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

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

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

а) 5 (10 + 4); 6)125 15 6; в) (8 379) 125?

6. Известно, что 37 3 = 111. Используя это равенство, вычислите:

а) 37 18; 6) 185 12.

Все выполненные преобразования обоснуйте.

7. Определите значение выражения, не выполняя письменных вычислений. Ответ обоснуйте:

а) 8962 8 + 8962 2; б) 63402 3 + 63402 97; в) 849 +849 9.

8.. Какие свойства умножения будут использовать учащиеся началь­ных классов, выполняя следующие задания:

Можно ли, не вычисляя, сказать, значения каких выражений будут одинаковыми:

а) 3 7 + 3 5; 6) 7 (5 + 3): в) (7 + 5) 3?

Верны ли равенства:

а) 18 5 2 = 18 (5 2); в) 5 6 + 5 7 = (6 + 7) 5;

б) (3 10) 17 = 3 10 17; г) 8 (7 + 9) = 8 7 + 9 8?
Можно ли, не выполняя вычислений, сравнить значения выражений:

а) 70 32 + 9 32 ...79 30 + 79 2; 6) 87 70 + 87 8 ... 80 78 + 7 78?

Лекция 33. Вычитание и деление целых неотрицательных чисел

1. Упорядоченность множества натуральных чисел.

2. Определение вычитания целых неотрицательных чисел

3. Деление целых неотрицательных чисел. Невозможность деления на нуль. Деление с остатком.

Как известно, множество натуральных чисел можно упорядочить при помощи отношения «меньше». Но правила построения аксиома­тической теории требуют, чтобы это отношение было не только опре­делено, но и сделано это на основе уже определенных в данной теории понятий. Сделать это можно, определив отношение «меньше» через сложение.

Определение. Число а меньше числа b (а < b) тогда и только тогда, когда существует такое натуральное число с, что а + с = b.

При этих условиях говорят также, что число b больше а и пишут b > а.

Теорема 12. Для любых натуральных чисел а и b имеет место одно и только одно из трех отношений: а = b, а > b , а < b.

Доказательство этой теоремы мы опускаем . Из этой теоремы вы­текает, что если

а ¹ b, то либо а < b, либо а > b, т.е. отношение «меньше» обладает свойством связанности.

Теорема 13. Если а < b и b < с. то а < с.

Доказательство. Эта теорема выражает свойство транзитив­ности отношения «меньше».

Так как а < b и b < с. то, по определению отношения «меньше», найдутся такие натуральные числа к и /, что b = а + к и с = b + I. Но тогда с = (а + к) + / и на основания свойства ассоциативности сло­жения получаем: с = а + (к + /). Поскольку к + I - натуральное число, то, согласно определению «меньше», а < с.

Теорема 14 . Если а < b, то неверно, что b < а. Доказательство. Эта теорема выражает свойство антисиммет­ричности отношения «меньше».

Докажем сначала, что ни для одного натурального числа а не вы-!>! ■ )ея отношение а < а. Предположим противное, т.е. что а < а имеет место. Тогда, по определению отношения «меньше», найдется такое натуральное число с, что а + с = а, а это противоречит теореме 6.

Докажем теперь, что если а < b , то неверно, что b < а. Предположим противное, т.е. что если а < b , то b < а выполняется. Но из этих равенств по теореме 12 имеем а < а, что невозможно.

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

Из определения «меньше» и его свойств можно вывести известные свойства множества натуральных чисел.

Теорема 15. Из всех натуральных чисел единица является наименьшим числом, т.е. I < а для любого натурального числа а¹1.

Доказательство. Пусть а - любое натуральное число. Тогда возможны два случая: а = 1 и а ¹ 1. Если а = 1, то существует натуральное число b, за которым следует а: а = b " = b + I = 1 + b , т.е., по определению отношения «меньше», 1 < а. Следовательно, любое натураль­ное равно 1 либо больше 1. Или, единица является наименьшим натуральным числом.

Отношение «меньше» связано со сложением и умножением чисел свойствами монотонности.

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

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

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

Кафедра информатики математики и естественно -

научных дисциплин

Группа 561

РЕФЕРАТ

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

Уровень образования специалист

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

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

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

Нижнекамск 2007

ВВЕДЕНИЕ………………………………………………………………..3

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

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

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

ЗАКЛЮЧЕНИЕ…………………………………………………………..35

СПИСОК ЛИТЕРАТУРЫ……………………………………………….36

Введение

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

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

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

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

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

(а,в А ) а ? в в ? а

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

( a A ) a a

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

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

Пример 1.

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

q 1 ,q N ,следовательно q 1 = 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 (1 N ), это, по смыслу отношение, имеем а а . Следовательно, рефлексивно.

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

a = в q ,

в = c q ,

a = c (q q ).

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

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

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

а=в q 1 ,

в=а q ,

а=а q 1 q ,

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

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

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

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

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

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

Пример 4 .

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

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

Элемент m A называется мини-мальным , если для любого 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 ,e N . На множестве 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).

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

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

Пример 11 .

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

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

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

Для любого непустого множества X, как обычно, через обознача-ется множество всех подмножеств множества X - булеан множества X.

Полугруппа <В;> - такова, что каждый ее элемент идемпотен-тен.

A В, A = A A .

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

Пример 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}, построим диаграмму < В ; >.

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

Пример 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 ; ? > является полурешет-кой.

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

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

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

(1) х = х

(2) х·y = y·x

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

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

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

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

(4) х·у = х

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

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. Вполне упорядоченные множества

Теорию упорядоченных множеств создал Г. Кантор . Шатуновский . Хаусдорфу (1914).

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

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

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

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

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

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

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

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

Пример 1.

	a

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

Пример 2.

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

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

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

а в = inf{a ,в }.

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

				d
a
				d
	c
			-

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

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

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

(х ,y,z S ) (x ·y )·z O x ·(y ·z ) > (x ·y )·z = x ·(y ·z ) (*)

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

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

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

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

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

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

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

Пример 3.

Дано А = {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 , в,с }, можно задать на А следующую таблицу Кэли. Получим некоторый частичный группоид. Проверим будет ли этот группоид средне ассоциативным.

Пусть (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 ; · ) называется коммутативным , если

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

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

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

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

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

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

(х S ) х = х

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

Пример 5.

				d
a
				d
	c
			-

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

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

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

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

Пример 6.

Пример 7.

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

Пример 8.

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

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

				-
				-
				-

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

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

Пример 9.

Диаграмма:

называется диамантом

				d
a
			d
	c

Пример 10.

Диаграмма:

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

Пример 11.

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

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

Теорема 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с.

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

Отношение порядка есть не что иное, как правило, устанавливающее порядок «следования» элементов множества.

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

либо а ≤ b (а не превосходит b ),

либо b ≤ а (b не превосходит а ),

обладающих следующими свойствами:

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

любой элемент не превосходит самого себя;

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

если а не превосходит b , а b не превосходит а , то элементы а и b совпадают;

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

если а не превосходит b , a b не превосходит с , то а не превосходит с .

Пустое множество условились считать упорядоченным. В сформулированном выше определении упорядоченного множества, элементами которого могут быть объекты любой природы, знак ≤ читается «не превосходит». Привычное чтение и смысл этот знак (как знак «меньше или равно») приобретает в случае, когда элементы множества А - числа.

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

Одно и то же множество можно упорядочить различными способами, получая тем самым различные упорядоченные множества.

Пример

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

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

Пример

Записи (1; 2; 3) и (2; 1; 3) представляют различные конечные упорядоченные множества, которые можно получить из одного и того же множества {1; 2; 3}, упорядочивая его двумя различными способами.

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