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



страница3/12
Дата26.07.2014
Размер1.15 Mb.
ТипУчебно-методическое пособие
1   2   3   4   5   6   7   8   9   ...   12

Разбиение множества на классы


Введём понятие эквивалентности, которое будет обобщением понятия равенства.

Именно: Если дано какое-нибудь не пустое множество 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 (свойство транзитивности), то в этом случае это соотношение называется эквивалентностью.

Примеры:


  1. М – множество людей на Земле. Рассмотрим соотношение между людьми "быть братом", т.е. a~b, если человек a является братом человека b. Это соотношение не является эквивалентностью, т.к. не выполняется требование рефлексивности. Действительно, человек a может быть мужчиной, но может быть и женщиной, и тогда фраза «а брат а» теряет смысл. Кроме того, не выполняется и требование симметричности: из условия «человек а брат человеку b» не обязательно следует, что «человек b брат человеку а» (b – может быть женщиной). Следовательно, рассмотренное соотношение не является эквивалентностью.

  2. М – множество городов Земли. Рассмотрим соотношение между городами: "город a имеет одинаковую численность населения с городом b". Это соотношение:

  1. рефлексивно, т.к. город а имеет ту же численность населения с самим собой (для любого города Земли),

  2. симметрично, т.к. если "город а имеет одинаковую численность населения с городом b", то "город b имеет одинаковую численность населения с городом а",

  3. транзитивно, т.к. если "город а имеет одинаковую численность населения с городом 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 имеют один и тот же остаток.

Введенное отношение является отношением эквивалентным, т.к.


    1. для любого целого числа а верно, что a~а,

    2. если a~b, то b~a,

    3. если 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 | xZ, x = 3q, qZ}={0, 3,-3, 6,-6, …{

Cl1={x | xZ, x = 3q + 1, qZ}={1, 4,-2, 7,-5, …}

Cl2={x | xZ, x = 3q + 2, qZ}={2, 5, -4, 8,-1, …}

Рассмотрим еще один пример.

Пусть М – множество людей Земли. Зададим на нем отношение ρ с помощью закона: xρy (читается: x находится в отношении с y) тогда и только тогда, когда х и у родились в одном и том же году. Очевидно, что ρ – отношение эквивалентности. Вместе с каждым человеком х рассмотрим множество людей Clx, которые родились в один и тот же год с х. Например, если а родился в 1960 г., то Cla – множество людей, родившихся в 1960 г. Если b родился в 1973 г., то Clb – множество людей родившихся в 1973 г. Причем, если с родился в 1973 г., то Clc ≡ Clb. Таким образом, ясно, что два множества (класса) Clx и Cly либо не имеют общих элементов, либо совпадают, и каждый элемент множества М лежит в каком-нибудь классе.

Система множеств Clx представляет собой так называемое разбиение множества всех людей на классы, т.е. такое множество непустых подмножеств множества М, для которых:



  1. каждый элемент из М входит в какой-то из классов,

  2. каждый элемент из М входит только в один из классов.

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

Обобщим сказанное.

Если на множестве М ≠ Ø задано отношение ρ, являющееся эквивалентностью, то всегда на М можно построить разбиение по этому отношению эквивалентным. Это можно сделать следующим образом:


  1. возьмем любой элемент аМ, построим Cla = {x | xМ, xρа,} ≠ Ø, т.к. аCla согласно условия рефлексивности отношения ρ,

  2. если bCla, т.е. bρа, то строим Clb = {у | уМ, уρb}.

Cla и Clb не имеют общих элементов, т.к. если бы сCla и сClb, то сρа и сρb (в силу симметричности отношения ρ), а значит, и аρb (в силу транзитивности отношения ρ), т.е. bCla, что противоречит условию выбора элемента b.

Если kМ не вошел в Cla и Clb, то для него строим Clk и т.д.

Итак, каждый элемент из М войдет в один и только один класс, т.е. мы получим разбиение множества М по отношению эквивалентности ρ.

Верно и обратное. Каждое разбиение множества на классы порождает некоторое отношение эквивалентности.

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

1   2   3   4   5   6   7   8   9   ...   12

Похожие:

Учебно-методическое пособие для студентов гуманитарных направлений Саранск 2012 iconУчебно-методическое пособие для студентов-заочников направлений и специальностей Института информационных технологий и коммуникаций
Учебно- методическое пособие для студентов-заочников направлений и специальностей Института информационных технологий и
Учебно-методическое пособие для студентов гуманитарных направлений Саранск 2012 iconУчебно-методическое пособие по Новой истории стран Азии и Африки Брянск, 2008 Сагимбаев Алексей Викторович. Учебно-методическое пособие по курсу «Новая история стран Азии и Африки»
Учебно-методическое пособие предназначено для студентов дневного отделения Исторического факультета, обучающихся по специальности...
Учебно-методическое пособие для студентов гуманитарных направлений Саранск 2012 iconУчебно-методическое пособие для студентов педагогических колледжей. Предлагаемый практикум является учебно-методическим пособием нового типа. Он активизирует познавательную деятельность обучаемого
Педагогика: практикум. Учебно-методическое пособие для студентов педагогических колледжей
Учебно-методическое пособие для студентов гуманитарных направлений Саранск 2012 iconУчебно-методическое пособие по неорганической химии Алт гос техн ун-т им. И. И. Ползунова, бти. Бийск
Учебно-методическое пособие предназначено для студентов всех форм обучения, изучающих курс "Неорганическая химия"
Учебно-методическое пособие для студентов гуманитарных направлений Саранск 2012 iconУчебно-методическое пособие для студентов физико-математических специальностей вузов Балашов 2009 удк 004. 43 Ббк 32. 97
Данное учебно-методическое пособие состоит из лабораторных работ, которые условно можно разбить на несколько частей
Учебно-методическое пособие для студентов гуманитарных направлений Саранск 2012 iconУчебно-методическое пособие для студентов отделений журналистики и филологии Новосибирского госуниверситета Новосибирск 1999
Учебно-методическое пособие предназначено для студентов третьего курса отделения журналистики Новосибирского госуниверситета, изучающих...
Учебно-методическое пособие для студентов гуманитарных направлений Саранск 2012 iconУчебно-методическое пособие для студентов отделений журналистики и филологии Новосибирского госуниверситета Новосибирск 1999
Учебно-методическое пособие предназначено для студентов третьего курса отделения журналистики Новосибирского госуниверситета, изучающих...
Учебно-методическое пособие для студентов гуманитарных направлений Саранск 2012 iconУчебно-методическое пособие для студентов 4 курса (озо, одо) специальности 050602. 65 «Изобразительное искусство»
О. А. Бакиева. Народный костюм Севера: Учебно-методическое пособие для студентов 4 курса очной и заочной формы обучения специальности...
Учебно-методическое пособие для студентов гуманитарных направлений Саранск 2012 iconУчебно-методическое пособие для преподавателей и студентов санкт-Петербург 2008 г
Данное учебно-методическое пособие мы рассматриваем как одно из средств, способствующих конструированию новой образовательной среды,...
Учебно-методическое пособие для студентов гуманитарных направлений Саранск 2012 iconУчебно-методическое пособие для студентов, обучающихся по специальности «Информатика»
Учебно-методическое пособие предназначено для студентов, обучающихся по специальности «информатика», а также может использоваться...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org