Спирина, М.С. Дискретная математика

тремя свойствами: рефлективностью, симметричностью и тран­ зитивностью, т.е. если для любых х, у, z выполняется: • xRx (рефлективность); • если xRy , то yRx (симметричность); • если xRy, a yRz, то xRz (транзитивность). Обозначение эквивалентных отношений: a Q b или а - Ь, что означает «а эквивалентно b в отношении Q», например, «быть равным на множестве чисел», быть подобным на множестве гео­ метрических фигур. Непересекающиеся подмножества, на которые разбивается множество М отношением эквивалентности, называются класса­ ми эквивалентности. Множество классов эквивалентности множе­ ства А относительно Q называется фактор-множеством и обозна­ чается A/Q. Например, множество всех рациональных чисел Q можно раз­ бить на классы эквивалентности, для которых а/b — рациональ­ ная дробь, где а е Z; b е N. Любая дробь с/b будет отнесена к тому же классу тогда и только тогда, когда ad = be, т. е. а/b и c/d экви­ валентны, если ad = be (например, -2 /4 — 3/6). Проверим выпол­ нимость свойств для такого отношения. Рефлективность. Для любой дроби а/b выполняется равенство ab = Ьа, значит а/b Q а/Ь. Симметричность. Если а/b Q c/d, то ad = be, но be = ad, значит c/d Q а/b. Симметричность равенства произведений влечет за собой сим­ метричность отношений между дробями. Транзитивность. Известно, что а/b Q c/d, c/d Q т/п. Докажем, что а/b Q т/п, т.е. ап = Ьт. Действительно, так как а/b Q c/d, то ad = be, аналогично c/d Q т/п, то сп = md. Умножим первое равен­ ство на п, а второе на Ь, тогда имеем adn = ben и ben = mdb. По свойству транзитивности adn = mdb или ап = mb. Известно, что такие дроби классифицируются по элементу, порождающему класс эквивалентности, которым в этом примере является не­ сократимая дробь (например, для 2/4 ~ 3/6 —4 /8 таковой будет 1 / 2 ). Отношение толерантности. Отношение А на множестве М назы­ вается отношением толерантности, если оно рефлективно и сим­ метрично. Очевидно, что отношение эквивалентности есть част­ ный случай толерантности, когда к двум перечисленным свой­ ствам добавляется транзитивность. Например, отношение «быть другом» рефлективно, симметрично, но не транзитивно. Таким образом, толерантность является более слабой мерой сходства, чем эквивалентность, но тем не менее помогает выявлять разли­ чия в схожих вещах. Пусть А и В имеют некоторые сходные признаки. Тогда А реф­ лективно А (признаки не только схожи, но и совпадают). Очевид­ 42