Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 16
Текст из файла (страница 16)
Для каждого частичного порядка из предыдушего упражнения перечислите элементы: а) не сравнимые с а; б) не сравнимые с Ь; в) не сравнимые с с; г) не сравнимые с И. 7. Опишите симметричные отношения, которые являются отношениями частичного порядка. 2.7. ОТНОШЕНИЯ ЭКВИВАЛЕНТНОСТИ В разделе 2.5 были определены следуюшие свойства бинарных отношений. Отно- шение В на А рефлексивно, если (а, а) принадлежит В для всех а из А. Отноше- ние В силсиетрично, если для всех а и Ь из А из того, что (а, 6) принадлежит В, РАЗДЕЛ 27.
СЗтноогвноя зквовалвнтносто 107 следует, что (6, а) принадлежит Л. Отношение В траизитивно, если для всех а, Ь и с из А таких, что (а, Ь) и (Ь,с) принадлежат В, (а,с) также принадлежит В. Эти свойства объединены в приведенном ниже определении. ОПРЕДЕЛЕНИЕ 2.61. Отношение В на А есть отношение эквивалентности, если оно рефлексивно, симметрично и транзитивио. Пусть А = (1,2,3,4,5,61. В примере 2.33 уже было установлено, что отношение Вг на А, определенное как Вг = ((1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (1, 2), (1, 4), (2, 1), (2, 4), (3, 5), (5, 3), (4, 1), (4, 2)~, рефлексивно, транзитивно и симметрично, поэтому Вг есть отношение эквива- лентности на множестве А. ПРИМЕР 2.52. Пусть А — множество целых чисел. Определим отношение Вз ~ А х А посредством Лз = ((а,Ь): а — Ь = 5 6 для некоторого целого числа 6).
Например, (7,2) Е Вз, поскольку 7 — 2 = 5 = 5 1, и ( — 11,4) Е Вз, так как ( — 11) — 4 = — 15 = 5( — 3). Отношение Лз рефлексивно. Если а — целое число (т.е. а Е А), то а — а = О = 5 О = 5 6 для 6 = О, так что (а, а) Е Вз. Отношение Лз симметрично. Допустим, (а, Ь) Е Лз. Тогда существует такое целое число т, что а — Ь = 5 т и Ь вЂ” а= — (а — 6) = = — (5 т)= =5 ( — т) для целого числа — гп.
Таким образом, (6,а) Е Вз. Отношение Лз транзитивно. Предположим, что а, 6 и с — целые числа, (а, 6) е Вз и (Ь,с) Е Вз. По определению, если (а,Ь) Е Вз, тогда а — Ь = 5 6 для некоторого целого числа 6, и если (Ь,с) Е Лз, тогда Ь вЂ” с = 5 т для некоторого целого числа т. Суммирование левых и правых частей этих двух равенств дает (а — 6)+(Ь вЂ” с) =5 6+5 т или а — с= 5 (6+т) для целого числа 6+т. По определению Лз, (а, с) Е Лз, поэтому Вз транзитивно. Поскольку Лз рефлексивно, симметрично и транзитивно, оно является отношением эквивалентности. С) 108 ГЛАВА 2.
Теория множеств Отношение эквивалентности В на множестве А разбивает его на подмножества, элементы которых эквивалентны друг другу и не эквивалентны элементам других подмножеств. В контексте отношений эквивалентности эти подмножества называются классами эквивалентности по отношению В. Это разбиение можно представлять себе следующим образом. Пусть множество А — это набор разноцветных шаров, а отношение В задается условием: (а, Ь) е В тогда и только тогда, когда а и Ь имеют одинаковый цвет.
Поскольку  — отношение эквивалентности, каждый класс эквивалентности будет состоять из шаров, имеющих одинаковый цвет. Если определить отношение В условием: (а, Ь) Е В тогда и только тогда, когда шары а и Ь имеют одинаковый диаметр, то каждый класс эквивалентности будет состоять из шаров одинакового размера. ОПРЕДЕЛЕНИЕ 2.53. Пусть а е А, и  — отношение эквивалентности на А х А.
Пусть [а] обозначает множество (х: хВа) = (х; (х,а) я В), называемое классом эквивалентности, содержащим а. Символ (А]н обозначает множество всех классов эквивалентности множества А по отношению В. ПРИМЕР 2.54. Ранее было показано, что отношение Вд, определенное выше, есть отношение эквивалентности на множестве А = (1,2,3,4,5,6). Классы эквивалентности по отношению Вд были получены путем определения класса эквивалентности каждого элемента множества А: [Ц = (х: (х,1) Е Вд) = (х: хВд1) = (1,2,4), где 1 Е (Ц, поскольку (1,1) Е Вд, 2 Е [Ц, т.к.
(2,1) Е Вд, 4 Е [Ц, поскольку (4, 1) Е Вд, и не существует никакого иного х из А такого, что (х, 1) а Вд. Точно так же, получаем [2] = (х: (х,2) Е Вд) = (2,1,4); [3] = (х: (х, 3) Е Вд) = (3, 5); [4] = (х: (х,4) Е Вд) = (4, 1,2); (5] = (х: (х, 5) Е Вд) = (5, 3); [6] = (х: (х,б) Е Вд) = (6). Итак, имеется только три различных класса эквивалентности: [Ц = [2] = [4] = (1, 2, 4), [3] = [5] = (3, 5) РКЗДЕП 2.7. Отношения эквивалентности 109 так что [А]н, = ([Ц,[З],[6]) = ((1, 2, 4),(3, 5), (6)). Этот пример показывает, что любой элемент класса эквивалентности порождает класс эквивалентности; другими словами, если Ь Е [а], то [а] = [Ь).
На основании этого свойства говорят, что любой элемент класса эквивалентности представляет класс. Каждый класс эквивалентности содержит по крайней мере один элемент, поэтому, в силу рефлексивности отношения, множество всех элементов, эквивалентных элементу а, должно содержать а. С другой стороны, никакой элемент не может принадлежать двум различным классам эквивалентности. П ПРИМЕР 2.$5. Рассмотрим отношение эквивалентности Лз из примера 2.52. Для множества А всех целых чисел Лз С А х А было определено посредством Лз = ((а, Ь): а — Ь = 5 й для некоторого целого числа к). Поскольку [а] — (х: (х, а) е Лз) =. (х: хЛза) .= = (х:х — а = 5 Ь для некоторого целого числа й) = = (х; х = а + 5 .
й для некоторого целого к), получаем, что классы [0) = (..., - 15, -10, -5, 0, 5, 10, 15, 20, 25,...) = = .. = [-5] = [0) = [5] = [10] = [15] = "., [1] = (..., — 14, — 9, — 4, 1, 6, 11,...) = = [-9] = [-4] = (1] = (6] = [2] = (..., — 13, — 8, — 3, 2, 7, 12,...) = = [ — 3] = [ — 2] = [7] = (12] = [3] = (..., — 12, — 7, — 2,3,8,13,...) = = " = [-г] = [з] = [8] = [13] = ", [4] = (..., — 11, — 6, — 1, 4, 9, 14,...) = = [ — 6) = [-1] = [4] = [9] = . представляют собой различные классы эквивалентности по отношению Лз.
Таким образом, [А]н, = ([О], [1], [2], [3], (4)). Элементы (О] "похожи" в том смысле, что каждый из них кратен пяти. Элементы любого другого класса эквивалентности также "похожи" в том смысле, что имеют один и тот же остаток при делении на пять. П 110 ГЛЯВА 2. Теория множеств Как отмечалось выше, совокупность классов эквивалентности разделяет все множество А на непустые взаимоисключающие, или непересекающиеся подмножества, в том смысле, что никакие два из них не имеют общих элементов, Такое разделение множества называется его разбиением. ОПРЕДЕЛЕНИЕ 2.56.
Пусть А и 1 — множества и пусть (А) = (А,: 1 Е 1), где 1 непусто, есть множество непустых подмножеств множества А. Множество (А) называется разбиением А, если выполнены два условия: а) А,йА, =ьодля всехг~); б) А = [] А,, т.е, а принадлежит А тогда и только тогда, когда а е А, для ~ет некоторого 1 Е 1. ТЕОРЕМА 2.57. Непустое множество подмножеств (А) множества А есть разбиение А тогда и только тогда, когда (А) = [А]н по некоторому отношению эквивалентности Л. ДОКАЗАТЕЛЬСТВО. Пусть (А) = (А~, г Е 1) есть разбиение А. Определим отношение Л на А х А таким образом; аЛЬ тогда и только тогда, когда а и Ь принадлежат одному и тому же подмножеству А, для некоторого г, Несомненно, что для всех а из А имеем аЛа, поэтому Л рефлексивно, Если а и 6 принадлежат одному подмножеству А,, тогда Ь и а также принадлежат этому подмножеству А„ поэтому Л симметрично.
Если элементы а и Ь принадлежат одному подмножеству и элементы 6 и с принадлежат одному подмножеству, то а и с тоже находятся в одном подмножестве, в силу условия А, П А. = О для 1 ф ~. Следовательно, Л транзитивно и представляет собой отношение эквивалентности. Обратно, предположим, что Л вЂ” отношение эквивалентности. Необходимо показать, что [А]д = ([а]; а Е А) есть разбиение А.
Очевидно, [а] непусто для всех а, т.к, а е [а]. Очевидно также, что А есть объединение [а], так что а е А. Допустим, что пересечение [а] П [6] непусто и х Е [а] О [Ь]. Тогда хЛа и хЛЬ, и, в силу симметричности отношения, аЛх, Но поскольку аЛх и хЛЬ, то, в силу транзитивности отношения, аЛЬ. Поэтому, а е [Ь]. Если у а [а], то уЛа, а поскольку аЛЬ, то уЛЬ, в силу транзитивности отношения. Поэтому [а] С [Ь], Аналогично можно показать, что [6] С [а], поэтому [а] = [Ь] и [А]л представляет собой разбиение А.
ПРИМЕР 2.58. Пусть А = (П, й,(),*). Рассмотрим разбиение А = (Щ, А = (Л,0,*). Согласно доказательству предыдущей теоремы, необходимо определить Л таким образом; Л = ((а, Ь): а Е А, и Ь Е А, для некоторого 1). Итак, есть отношение, соответствующее заданному разбиению.
РАЗДЕЛ 2.7. Отношения эквивалентности 111 ° УПРАЖНЕНИЯ Установите, является ли каждое из перечисленных ниже отношений на А отношением эквивалентности. Для каждого отношения эквивалентности постройте классы эквивалентности. а) А — множество целых чисел, и Л есть отношение, заданное условием: (а,Ь) й Л, если а+6=0; б) А — множество целых чисел, и Л есть отношение вида (а,6) е Л, если а+6=5; в) А — множество высказываний, и Л есть отношение вида (р,д) е Л, если р логически эквивалентно о; г) А — множество упорядоченных пар целых чисел, и (а,Ь)Л(с,д), если ад= Ьс; д) А = ( — 10,— 9,— 8,— 7,...0,1,...,9,10), и (а 6) Е Л, если аз = Ьз; е) А=( — 10,— 9,— 8,— 7,...0,1,...,9,10), и (а,Ь) е Л, если аз=Ьз. Пусть А = (1,2,3).
Установите, является ли каждое из приведенных ниже отношений на А отношением эквивалентности. Для каждого отношения эквивалентности постройте классы эквивалентности. а) Л~ = ((2, 2),(1, 1)); б) Лз = ((1, 1), (2, 2), (3, 3)); в) Лз = ((1 1) (2 2) (3 3) (1 2);(2 1) (3 1) (1 3))' г) Л4 = ((1, 1),(2, 2), (3, 3),(1, 2), (3, 2),(2, 1)); д) Лз —— ((1, 1),(2, 2), (3, 3),(1, 2), (2, 1), (2, 3),(3, 2), (1, 3), (3, 1)). Установите, является ли каждое из приведенных ниже отношений на А отношением эквивалентности.
Для каждого из отношений эквивалентности постройте классы эквивалентности. а) А — множество всех подмножеств множества (а,б,с,Н), отношение Л определяется следующим образом: еЛг, если е и г содержат одинаковое количество элементов; б) А = (1,2,3,4,5,6,7,8,9,10), отношение Л определяется следующим образом: аЛЬ, если а+ Ь положительно; в) А = (1,2,3,4,5,6,7,8,9, 10), отношение Л определяется следующим образом: Ьу аЛЬ, если а + Ь четное; г) А — множество прямых в плоскости, отношение Л определяется следующим образом; пЛтп, если и и тп пересекаются; д) А — множество прямых в плоскости, отношение Л определяется следующим образом: пЛгп, если и и гп параллельны; е) А — множество компьютерных программ, написанных для ХА8А, отношение Л определяется следующим образом: рЛо, если р и а написаны на одном и том же языке программирования. 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
