Разбиение множества на классы
Введём понятие эквивалентности, которое будет обобщением понятия равенства.
Именно: Если дано какое-нибудь не пустое множество M={a, b, c,…}, между элементами которого установлено некоторое соотношение, обозначаемое записью вида: a~b, так, что для каждой пары элементов a, b из M известно, будет ли a~b или нет. И если это соотношение удовлетворяет следующим требованиям:
1) a~a для любого элемента aM (свойство рефлексивности),
2) из a~b следует, что b~a (свойство симметрии),
3) из a~b и b~c следует, что a~c (свойство транзитивности), то в этом случае это соотношение называется эквивалентностью.
Примеры:
М – множество людей на Земле. Рассмотрим соотношение между людьми "быть братом", т.е. a~b, если человек a является братом человека b. Это соотношение не является эквивалентностью, т.к. не выполняется требование рефлексивности. Действительно, человек a может быть мужчиной, но может быть и женщиной, и тогда фраза «а брат а» теряет смысл. Кроме того, не выполняется и требование симметричности: из условия «человек а брат человеку b» не обязательно следует, что «человек b брат человеку а» (b – может быть женщиной). Следовательно, рассмотренное соотношение не является эквивалентностью.
М – множество городов Земли. Рассмотрим соотношение между городами: "город a имеет одинаковую численность населения с городом b". Это соотношение:
рефлексивно, т.к. город а имеет ту же численность населения с самим собой (для любого города Земли),
симметрично, т.к. если "город а имеет одинаковую численность населения с городом b", то "город b имеет одинаковую численность населения с городом а",
транзитивно, т.к. если "город а имеет одинаковую численность населения с городом b", а "город b имеет одинаковую численность населения с городом с", то "город а имеет ту же численность населения, что и город с".
Следовательно, рассмотренное соотношение на множестве городов является отношением эквивалентности.
Рассмотрим множество целых чисел Z и возьмем некоторое натуральное число m>1. Согласно теоремы о делении с остатком для любого целого числа z и m существует и притом единственная пара целых чисел q и r, удовлетворяющая условиям:
1) z = mq + r,
2) 0 ≤ r < m
(r называют остатком от деления z на m, q называют неполным частным от деления z на m).
Разделим каждое число z на m. У каждого числа будет однозначно определен остаток. Остатками могут быть только числа: 0,1, 2,…, m-1.
Введем на множестве Z отношение «быть равноостаточными при делении на m», т.е. a~b тогда и только тогда, когда числа а и b при делении на m имеют один и тот же остаток.
Введенное отношение является отношением эквивалентным, т.к.
для любого целого числа а верно, что a~а,
если a~b, то b~a,
если a~b, b~с, то a~с.
В дальнейшем это отношение будем называть отношением сравнимости целых чисел по модулю m и если a~b, то будем писать а ≡ b (mod m).
Например, 5 ≡ 2 (mod 3), -2 ≡ 5 (mod 7), 13 ≡ 10 (mod 3), 5 ≠ 1(mod 3).
Возьмем какое-нибудь число аZ. Объединим в один класс (множество) все целые числа x, которые сравнимы с а по mod m, т.е. все целые числа х, которые имеют такой же остаток от деления на m, что и число а. Этот класс обозначим символом Cla. Число а называют представителем этого класса.
Если число b не попало в Cla, т.е., если число b при делении на m имеет другой остаток, то для этого числа мы создаем Clb, и т.д.
В результате множество Z разобьется на классы Cla, Clb, Clс, …. Каждый класс характеризуется своим представителем и всеми членами, сравнимыми с этим представителем по mod m. Так как, если а1 ≡ а2 (mod m), то если а1 и а2 равноостаточны при делении на m, то Clа1 ≡ Clа2 и, следовательно, любое число, входящее в данный класс, может считаться его представителем. Тогда, множество целых чисел может быть разбито по mod m на классы Cl0, Cl1, Cl2,…, Clm-1, где 0,1,2,…, m-1 – остатки при делении целых чисел по mod m. Эти классы называют классами вычетов по mod m, а их множество обозначают символом Zm и называют множеством классов вычетов по mod m.
Значит Zm={Cl0, Cl1, Cl2,…, Clm-1}. Для упрощения записи слово "класс" часто не пишут, т.е. пишут: Zm={0, 1, 2,…, m-1}. Но в этом случае не надо забывать, что символ "0" - это не символ числа, а символ класса вычетов Cl0={x | xZ, x = mq, qZ}, символ "1" – символ класса вычетов Cl1={x | xZ, x = mq +1, qZ} и т.д.
Заметим, что в каждом классе вычетов находится бесконечно много целых чисел.
Например, Z3 = {Cl0, Cl1, Cl2}, где
Cl0={x | xZ, x = 3q, qZ}={0, 3,-3, 6,-6, …{
Cl1={x | xZ, x = 3q + 1, qZ}={1, 4,-2, 7,-5, …}
Cl2={x | xZ, x = 3q + 2, qZ}={2, 5, -4, 8,-1, …}
Рассмотрим еще один пример.
Пусть М – множество людей Земли. Зададим на нем отношение ρ с помощью закона: xρy (читается: x находится в отношении с y) тогда и только тогда, когда х и у родились в одном и том же году. Очевидно, что ρ – отношение эквивалентности. Вместе с каждым человеком х рассмотрим множество людей Clx, которые родились в один и тот же год с х. Например, если а родился в 1960 г., то Cla – множество людей, родившихся в 1960 г. Если b родился в 1973 г., то Clb – множество людей родившихся в 1973 г. Причем, если с родился в 1973 г., то Clc ≡ Clb. Таким образом, ясно, что два множества (класса) Clx и Cly либо не имеют общих элементов, либо совпадают, и каждый элемент множества М лежит в каком-нибудь классе.
Система множеств Clx представляет собой так называемое разбиение множества всех людей на классы, т.е. такое множество непустых подмножеств множества М, для которых:
каждый элемент из М входит в какой-то из классов,
каждый элемент из М входит только в один из классов.
При этом говорят, что отношение эквивалентности ρ порождает разбиение множества М на классы.
Обобщим сказанное.
Если на множестве М ≠ Ø задано отношение ρ, являющееся эквивалентностью, то всегда на М можно построить разбиение по этому отношению эквивалентным. Это можно сделать следующим образом:
возьмем любой элемент аМ, построим Cla = {x | xМ, xρа,} ≠ Ø, т.к. аCla согласно условия рефлексивности отношения ρ,
если bCla, т.е. bρа, то строим Clb = {у | уМ, уρb}.
Cla и Clb не имеют общих элементов, т.к. если бы сCla и сClb, то сρа и сρb (в силу симметричности отношения ρ), а значит, и аρb (в силу транзитивности отношения ρ), т.е. bCla, что противоречит условию выбора элемента b.
Если kМ не вошел в Cla и Clb, то для него строим Clk и т.д.
Итак, каждый элемент из М войдет в один и только один класс, т.е. мы получим разбиение множества М по отношению эквивалентности ρ.
Верно и обратное. Каждое разбиение множества на классы порождает некоторое отношение эквивалентности.
Рассмотренная в настоящем разделе теория множеств представляет собой фундамент, на котором математика строит свое здание. Она дает универсальный аппарат для всей математики, в частности для алгебры.
|
