Ример 4. Отношение «меньше» (<) на множестве натуральных чисел, очевидно, обладает свойством транзитивности, но не является ни рефлексивным, ни симметричным.

Заметим, что свойства симметричности и антисимметричности не являются взаимоисключающими. Легко проверить, что для любого множества А отношение I_А является и симметричным, и антисимметричным. Приведем пример отношения, которое не является ни симметричным, ни антисимметричным. Пусть s отношение, которое определено на множестве Р всех людей следующим образом: хsу Û х – брат у. Для семьи, в которой два братьа p и q и сестра r, имеем: ps r, но не rs p, т.е. отношение s не является симметричным. Это отношение также не является антисимметричным, так как ps q и qs p, хотя, p и q различны.

Эти свойства довольно просто описать при графическом задании отношения:

а) отношение рефлексивно тогда и только тогда, когда для каждой точки существует стрелка, которая начинается и заканчивается в этой точке (петля);

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

в) отношение транзитивно тогда и только тогда, когда для каждой пары точек х и у, связанных последовательностью стрелок, идущих от х к а₁, от а₁к а₂, ..., от а_n-1 к а_n, от а_n к у, существует также стрелка от х к у;

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

Если С_s = (с_ij)_{n´ n} – матрица бинарного отношения s на множестве А, то отношение s:

а) рефлексивно Û с_ii = 1 для всех i;

б) симметрично Û с_ij = 1 Þ с_ji = 1;

в) транзитивно Û с_ij = 1 и с_jk = 1Þ с_ik = 1;

г) антисимметрично Û с_ij = с_ji = 1Þ i = j.

В частности, для отношения s из примера 3 по матрице С_s, легко заключить что оно обладает только свойством транзитивности.

2.5. Отношение эквивалентности

Определение 8. Бинарное отношение q на множеств А называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

Если q – отношение эквивалентности на множестве А, то классом эквивалентности, порожденным элементом а, называется подмножество множества А, состоящее из тех элементов b Î А, для которых aq b .

Класс эквивалентности, порожденный элементом а, обозначается через [a] или С_а. По определению имеем: [a] = {b| b Î A и aq b}.

Пример 5. Отношение равенства на множестве целых чисел, очевидно, есть отношение эквивалентности. При этом каждый класс эквивалентности состоит из одного элемента, т.е. для любого целого числа х [x] = {x}.

Пример 6. Отношение подобия на множестве всех треугольников является отношением эквивалентности. Каждый класс эквивалентности представляет собой множество подобных между собой треугольников.

Пример 7. Покажем, что отношение сравнения по модулю натурального числа n на множестве целых чисел Z: х º y(mod n) тогда и только тогда, когда х – у делится на n, есть отношение эквивалентности. Это отношение рефлексивно на Z, так как для любого х Î Z х – x = 0, и, следовательно, делится на n. Если х – у делится на n, то и у – х делится на n, это означает симметричность отношения. Это отношение транзитивно, так как если х – у делится на n, то для некоторого целого r имеем х –у=rn, а если у – z делится на n, то для некоторого целого q имеем у – z = qn. Складывая эти два равенства, получаем: x – z = (r + q)n, т.е. x – z делится на n, так как (r + q) – целое число.

Данное отношение порождает следующие классы эквивалентности: вместе с любым целым числом а в этом же классе эквивалентности содержатся все числа вида а + kn, где k – целое число. Очевидно, что числа 0, 1, 2, ... , n – 1 порождают различные классы эквивалентности: [0], [1], [2], ... , [n – 1]. Они называются классами вычетов по модулю n. Поскольку любое целое число а можно представить в виде а = qn + r, где 0 £ r < n, то все остальные классы эквивалентности совпадают с указанными выше.

Пример 8. Отношением эквивалентности на множестве всех студентов университета, очевидно, является отношение принадлежности одной учебной группе. Классом эквивалентности в этом случае является множество студентов одной группы.

Для любого отношения эквивалентности q на множестве А справедливы следующие утверждения:

· Если а Î А, то а Î [a] (т.е. каждый элемент множества А принадлежит порожденному им классу эквивалентности).

· Если а, b Î А и a q b, то [а] = [b] (т.е. класс эквивалентности порождается любым своим элементом).

Справедливость первого утверждения следует из свойства рефлексивности отношения q : а q а и, следовательно, а Î [a] .Докажем второе утверждение. Пусть с Î [b]. Тогда b q c и в силу транзитивности отношения q, а q с, т.е. с Î [a]. Отсюда [b] Í [a] . Аналогично в силу симметричности q можно показать, что [а] Í [b], а значит, [а] = [b].

Из приведенных выше утверждений следует, что любое отношение эквивалентности q на множестве А позволяет представить это множество в виде объединения попарно непересекающихся подмножеств – классов эквивалентности. Действительно, каждый элемент а из А лежит в порожденном им классе [a]. При этом любые два класса эквивалентности либо не пересекаются, либо совпадают. Предположим, что два различных класса эквивалентности пересекаются, т.е. существует такой элемент с,что c Î [a]Ç[b].Это означает, что а q с, и b q с, следовательно [a] = [c], [b] = [c]. Откуда, [a] = [b]. Такое представление множества А имеет специальное название.

Определение 9. Разбиением множества А называется совокупность попарно непересекающихся подмножеств А_k таких, что каждый элемент множества А принадлежит одному и только одному из этих подмножеств, т.е.

АÈА_k, k Î K и А_iÇА_j = Æпри i ¹ j.

Итак, выше нами фактически установлена

Теорема 1. Всякое отношение эквивалентности определяет разбиение множества на классы эквивалентности относительно этого отношения.

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

Теорема 2. Всякое разбиение множества А определяет на нем отношение эквивалентности q: аq b тогда и только тогда, когда a и b принадлежат одному подмножеству разбиения.

Действительно, отношение q, очевидно, рефлексивно и симметрично. Докажем транзитивность. Пусть a q b и b q c, тогда a, bÎA₁, b, cÎA₂, где A₁ и A₂ – подмножества из разбиения множества А. Поскольку bÎA₁, bÎA₂, то A₁ = A₂.

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

Пример 9. Бинарное отношение t на множестве А = {a₁, a₂, a₃, a₄, a₅} задано матрицей

С_t= .

Показать, что t отношение эквивалентности, указать соответствующее ему разбиение множества А.

Матрица С_t имеет клеточную структуру. Рассмотрим соответствующее ей разбиение множества А: , где . Согласно теореме 2 данное разбиение задает отношение эквивалентности, которое, как легко видеть, совпадает с отношением t.

2.6. Отношение порядка. Упорядоченные множества.

Определение 10. Бинарное отношение j, заданное на множестве А, называется отношением порядка, если оно обладает свойствами:

1) рефлексивности (для любого а Î А а j а);

2) транзитивности (если a j b и bj c , то a j c);

3) антисимметричности (если a j b и b j a, то a = b).

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

1) для всех а а £ а;

2) если a £ b и b £ c, то a £ c;

3) если a £ b и b £ a, то а = b.

Запись a £ b означает, что пара (a, b) принадлежит отношению порядка j ((a, b) Î j Í A´A). Про элемент а при этом говорят, что он меньше либо равен (не превосходит) b или, что он содержится в b. Отношение j ^–1, обратное к отношению порядка j (а j ^–1 b Û b j a), само является отношением порядка. Порядок (£)^–1 называют двойственным к £ и обозначают символом ³. Будем писать a < b, если a £ b и а ¹ b. Таким образом, мы задали отношение строгого порядка, которое обладает только свойством транзитивности.

Определение 11. Частично упорядоченным множеством называется множество, на котором задано отношение порядка.

Таким образом, частично упорядоченное множество определяется двумя объектами: самим множеством А и определенным на нем отношением порядка – <А,£>. При этом на одном и том же множестве порядок можно задать различными способами, т. е. получить различные частично упорядоченные множества. В частности, таким образом получается так называемое двойственное частично упорядоченное множество <А,(£)^–1>.

Пример 10. Множество натуральных чисел N с обычным отношением порядка £ (a £ b Û b – a ³ 0) является частично упорядоченным множеством.

Пример 11. Множество натуральных чисел N будет частично упорядоченным множеством, если отношение порядка задать следующим образом: a £ b означает «b делится без остатка на а».

Легко убедиться, что данное отношение является отношением порядка, т.е. удовлетворяет условиям 1) – 3) определения 9.

Пример 12. Рассмотрим множество М = {a, b, c, 0, 1}. Бинарное отношение R на нем зададим перечислением пар: R = {(0, 0), (0, a), (0, b), (0, 1), (a, a), (a, 1), (b, b), (b, 1), (c, c), (c, 1), (1, 1)}. Свойства рефлексивности, транзитивности и антисимметричности очевидно выполняются, следовательно, это отношение порядка. Система <М, R> является частично упорядоченным множеством.

Отметим, что в примерах 9 и 10 мы имеем дело с одним и тем же множеством N, но с различными частично упорядоченными множествами.

С другой стороны, если на множестве А = {2, 4, 6, 10, 60} отношение порядка определено также, как в примере10, то достаточно очевидно, что это частично упорядоченное множество устроено (ведет себя) также, как и множество в примере 11 в смысле отношения порядка. Фактически, если переобозначить элементы множества А (2 « 0, 4 « a, 6 « b, 10 « c, 60«1), то получим упорядоченное множество из примера 11. Такое переобозначение можно сделать не единственным образом, но суть его состоит в том, что мы нашли взаимно однозначное соответствие между множествами А и М, причем такое которое «сохраняет» отношение порядка. Таким образом, мы приходим к понятию изоморфизма упорядоченных множеств.

Пусть А и А¢ – два частично упорядоченных множества и g – взаимно однозначное отображение А на А¢. Отображение g называется сохраняющим порядок, если из того, что a £ b (a, b Î A), следует, что g(a)£ g(b).

Определение 12. Взаимно однозначное отображение g частично упорядоченного множества А на А¢ называется изоморфизмом, а сами частично упорядоченные множества А и А¢ изоморфными, если g(a) £ g(b) тогда и только тогда, когда a £ b (a, b Î A).

Пусть А – частично упорядоченное множество из примера 9, а А¢ – из примера 10. Взаимно однозначное отображение g, которое каждому натуральному числу n ставит в соответствие его само (g(n)= n), будет сохранять порядок, но не будет изоморфизмом. Действительно, если m делится на n без остатка (n £ m (n, m Î A)), то очевидно, что m – n = g(m) – g(п) ³ 0, т.е. g(n) £ g(m), следовательно g сохраняет порядок. Однако, отображение g не является изоморфизмом частично упорядоченных множеств примеров 9 и 10 хотя бы в силу того, что в частично упорядоченном множестве А не любая пара его элементов сравнима (например, m = 5, n = 3), а в множестве А¢ любая пара элементов сравнима, так как для любых натуральных чисел m и n либо m £ n, либо n£ m.

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

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

Определение 13. Частично упорядоченное множество <А, £> называется линейно упорядоченным, если в нем сравнимы любые два элемента, т.е. для любых a и b из А либо a £ b, либо b £ a.

В примере 9 множество линейно упорядочено, а в примерах 10 и 11 множества таковыми не являются. В условиях примера 10 натуральное число 2 несравнимо с любым натуральным нечетным числом. В примере 11 – несравнимы между собой элементы a, b, c.

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

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

Введем еще более узкое, но весьма важное понятие полной упорядоченности. Для этого определим минимальный элемент частично упорядоченного множества. Элемент а частично упорядоченного множества А называется минимальным (наименьшим), если из b £ а следует, что b = a. По аналогии элемент с частично упорядоченного множества А называется максимальным (наибольшим), если из с £ b следует. что b = c.

Определение 14. Линейно упорядоченное множество называется вполне упорядоченным, если любое его непустое подмножество имеет минимальный (наименьший) элемент.

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

Множество всех рациональных чисел отрезка [0, 1] (с естественным отношением порядка) имеет минимальный элемент – 0 и максимальный элемент – 1, но не является вполне упорядоченным множеством, так как, например, его подмножество положительных рациональных чисел наименьшего элемента не имеет.

Множество натуральных чисел N (с естественным отношением порядка) не имеет наибольшего элемента, но имеет наименьший элемент – 1. В силу того, что любое его непустое подмножество обладает наименьшим элементом, N является не только линейно упорядоченным, но и вполне упорядоченным множеством.

Ясно, что всякое (непустое) подмножество вполне упорядоченного множества само вполне упорядочено.

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

Пример 13. Пусть А = {1, 2, 3, 5, 30}. Рассмотрим два упорядоченных множества: <A;£> и < А; j >. В первом задан естественный порядок, а во втором – aj b Û b делится на а без остатка. Изобразим соответствующие им диаграммы Хассе.

· 30

· 5

· 3

· 2

· 1

Рис. 5а.

· 30

2· 3· ·5

· 1

Рис. 5

Очевидно, что эти два частично упорядоченных множества неизоморфны.

2.7. Функции и отображения.

Определение 15.Функцией из А в В называется однозначное бинарное отношение f Í А ´ В, т.е. (a, b) Î f и (a, с) Î f Þ b = c.

Поскольку, любая функция являются бинарным отношением т.е. множеством, то, применяя интуитивный принцип объемности, получаем:две функции f и g равны (f = g), если они состоят из одних и тех же элементов. Область определения и область значения функции обозначаются и определяются так же как для бинарного отношения.

Если f – функция из Х в Y, то вместо (x, y) Î f привычно пишут у = f(x) и говорят, что у – значение, соответствующее аргументу х, или у – образ элемента х при отображении f. При этом х называют прообразом элемента у. Функцию f из X в Y (f Í X ´ Y) называют одноместной или функцией одной переменной. Это понятие можно обобщить на случай функции нескольких переменных следующим образом.

Функция f из Хⁿ в Y (f Î Хⁿ ´ Y) называется n-местной функцией из Х в Y или функцией n переменных и обозначается у = f(x₁, x₂, ..., x_n).

Определение 16. Функция f Í А ´ В, у которой область определения D_f совпадает с множеством А, называется отображением множества А в множество В или всюду определенной функцией.

Если при этом область значений Е_f совпадает с В (Е_f = B), то f – отображение А на множество В. Иногда говорят, что отображение f устанавливает однозначное соответствие между множествами А и В. Отображение обозначают: f: А ® В или .

Пусть f – отображение множества М в множество В. Совокупность всех элементов из М, образом которых является данный элемент b Î В, называется прообразом (или, точнее, полным прообразом) элемента b и обозначается f ^–1(b), т.е. f ^–1(b)={m| mÎM и f(m)= b}.

Если А Í М, то образом множества А при отображении f называется множество f(A) = {x| x Î B, x = f(a) для всех а Î А}, т.е. совокупность образов всех элементов множества А. В свою очередь для каждого подмножества C из B множество f ^–1(C) = {m| m = f ^–1(c) для всех c Î C} называется прообразом множества C, т.е. f ^–1(C) – совокупность всех тех элементов из М, образы которых принадлежат C. Если ни один элемент c из C не имеет прообраза, то полный прообраз f ^–1(C)=Æ.

Сформулируем основные самые общие свойства отображений.

Теорема 3. Прообраз объединения двух множеств равен объединению их прообразов:

f ^–1(АÈВ)= f ^–1(А)È f ^–1(В).

Прообраз пересечения двух множеств равен пересечению их прообразов:

f ^–1(АÇВ)= f ^–1(А)Çf ^–1(В).

Теорема 3 остается в силе для объединений и пересечений любого (конечного или бесконечного) числа множеств.

Теорема 4.Образ объединения двух множеств равен объединению их образов:

f (АÈВ)= f (А)Èf (В).

Утверждение аналогичное теореме 4 для пересечений не имеет места, т.е. в общем случае образ объединения двух множеств не совпадает с пересечением их образов.

Например, если отображение f – это проектирование плоскости на ось Ох, то множество А = {0 £ х £ 1, у = 0} и множество В={0 £ х £ 1, у = 1} не пересекаются (АÇВ = Æ), а их образы, очевидно, совпадают (f(A)= f(B)).

2.8. Операции. Понятие алгебры.

Рассмотрим важный частный случай отображений – операции.

Определение 17. Отображение f из А в A называется операцией на множестве А.

В этом случае f(a) Î A и операцию f называют унарной.

На множестве действительных чисел Rпримерамиунарных операций являются:

1) операция нахождения обратного числа: f(x)= x^–1, x ¹ 0, или в других обозначениях: f ={(x, x^–1)| x Î R, x ¹0};

2) операция нахождения противоположного числа: f(x)= – x, или иначе: f ={(x,–x)| x Î R};

3) операция f ={(x,0)| x Î R}, которая любое действительное число х отображает в 0.

Определение 18. Отображение из Аⁿ в А называется n-местной (n-арной) операциейна множестве А.

В случае n = 2 операция называется бинарной, а при n = 3 – тернарной. На множестве векторов трехмерного пространства R₃векторное умножение векторов – бинарная операция, а двойное векторное произведение – тернарная.

Операции сложения и умножения действительных чисел являются бинарными на множестве действительных чисел R. Например, операция сложения: f = {((x, y), x + y)| x, y Î R}.

Определение 19. Алгеброй называется совокупность двух множеств: некоторого множества А и множества F – операций, определенных на А.

Алгебры принято обозначать готическими буквами: Á, Â и т.д. Для алгебры Â =<А, F> множество А называется носителем алгебры, а множество F ее сигнатурой.

Пример 14. Множество натуральных чисел N c определенными на нем бинарными операциями сложения (+), умножения (´) является алгебрoй: <N; +, ´>. Сигнатура этой алгебры состоит из двух бинарных операций: F = {+, ´}.

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

Множество всех подмножеств (булеан) некоторого множества М с определенными на нем бинарными операциями объединения и пресечения и унарной операцией дополнения является алгеброй: Â_K = <S(М); È,Ç, ¢>. Иногда считают, что сигнатура данной алгебры кроме указанных трех операций содержит две нульарны (0-арные) операции: выделено пустое множество Æ и само множество М. Как мы видели в 1.4. эти операции удовлетворяют определенным свойствам (1–9).

Алгебра Â_K =<S(М);È, Ç, ¢,Æ, М> называется алгеброй Кантора. Существуют алгебры с другими носителями, на которых определены две бинарные, одна унарная операция и выделены два элемента, но которые обладают теми же свойствами, что и алгебра Кантора. Рассматривая все такие алгебры, мы приходим к понятию абстрактной булевой алгебры. Алгебры Буля находят широкое применение в прикладных задачах.

Определение 20. Булевой алгеброй называется непустое множество В с двумя бинарными операциями Ú, Ù, двумя отмеченными элементами 0, I и одной унарной операцией`, причем для любых a ,b, cÎB выполняются следующие равенства:

(А1) аÚb = bÚa,

аÙb = bÙa (коммутативность);

(A2) aÚ(bÚc) = (aÚb)Úc,

aÚ(bÚc) = (aÚb)Úc (ассоциативность);

(A3): аÚ(bÙc) = (aÚb)Ù(aÚc),

аÙ(bÚc) = (aÙb)Ú(aÙc) (дистрибутивность);

(A4): aÙa = a,

aÚa = a (идемпотентность);

(А5): аÙ(аÚb) = a,

аÚ(аÙb) = a (поглощение);

(А6): аÙ0 = 0, аÚ0 = а,

аÙI = а, аÚI = I (универсальные границы);

(А7): аÙ = 0, aÚ = 0 (дополнение);

(А8): = a (двойное дополнение или инволютивность);

(А9): ,

(законы де Моргана).

Отметим, что это определение носит аксиоматический характер. Мы считаем заданными пять операций на множестве В (две бинарные: Ú и Ù, одна унарная` , и две нульарные: 0, I) и перечисляем 19 тождеств, сгруппированные в девять аксиом (постулатов). Алгебра считается булевой алгеброй тогда и только тогда, когда она имеет такой набор операций (сигнатуру) и в ней выполняются все выписанные аксиомы. Очевидно, что способ обозначения операций не играет роли. Операции Ú и Ù называют соответственно булевой суммой, или объединением, и булевым произведением, или пересечением.

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

аÙ(bÚ(aÙc))=(aÙb)Ú(aÙc),

аÚ(bÙ(aÚc))=(aÚb)Ù(aÚc),

которые называются законами модулярности и могут быть получены из аксиом А1 – А5. Действительно, пользуясь последовательно аксиомами А3, А2, А5 и А3, получаем

аÙ(bÚ(aÙc)) = аÙ((bÚa)Ù(bÚc)) = (аÙ(bÚa))Ù(bÚc) =

= аÙ(bÚc) = (аÙb)Ú(aÙc).

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

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

Это следует из того, что множество аксиом А1 – А9 в целом не меняется при замене Ù на Ú и Ú на Ù. Поэтому при такой замене всякое доказательство превращается в доказательство двойственного утверждения.

Изоморфизмом между алгебрами Â₁=<А₁, F₁> и Â₂=<А₂, F₂> называется взаимно однозначное соответствие j между элементами носителей и сигнатур такое, что

f_m(a_1,..., a_n)= a Û j (f_m)(j(a₁), ..., j(a_n)) = j(a ),

где a₁, ..., a_n, a Î А₁, f_m Î F₁, j(a₁), ..., j(a_n), j(a) Î A₂,j(f_m) Î F₂.

При этом алгебры Â₁ и Â₂ называются изоморфными. Все законы алгебры Â₁ справедливы и в изоморфной ей алгебре Â₂.

Алгебру Кантора Â_K =< S(М); È, Ç,` >, очевидно, можно рассматривать как модель (интерпретацию) булевой алгебры, считая, что Ç«Ù, È«Ú, Æ«0, M«I. Более того, любую конечную булеву алгебру можно рассматривать как алгебру Кантора для некоторого конечного множества М.

Теорема 5. Любая конечная булева алгебра изоморфна алгебре всех подмножеств некоторого множества.