Отношения эквивалентности и порядка.

Отношения, обладающие свойствами рефлексивности, симметричности и транзитивности, называются отношениями эквивалентности.

Пусть на множестве задано какое-то отношение. Будем говорить, что некоторое разбиение множества на классы подчинено данному отношению или это отношение порождает разбиение множества на классы, если любые два элемента, взятые в любом порядке, одного класса находятся в данном отношении, а любые два элемента в разных классах не находятся в данном отношении.

 

Теорема 1. Каждое отношение эквивалентности порождает разбиение множества на классы, подчиненные данному отношению.

 

Теорема 2. Если есть разбиение множества Х на классы, то существует отношение эквивалентности на этом множестве, которому подчинено данное разбиение.

 

Отношение Р = (Х, G_P) на множестве Х называется отношением строгого порядка, если оно антирефлексивно, транзитивно и асимметрично.

 

Отношение Р на множестве Х называется отношением нестрогого порядка, если оно рефлексивно, транзитивно и антисимметрично.

 

Множество Х, на котором задано отношение порядка строгого или нестрогого, называют частично упорядоченным множеством.

 

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

Пусть х,у,z – элементы множества Х, упорядоченного отношением Р. Если известно, что хРу и уРz, то говорят, что элемент у лежит между элементами х и z.

 

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

 

Множество Х, линейно упорядоченное отношением Р, называется плотным, если для любых двух различных элементов этого множества существует элемент множества, лежащий между ними.

 

Пример. Между учащимися некоторого класса существуют отношения: Р: «х живет дальше от школы, чем у»;

           R: «х занимается тем же видом спорта, что и у»

Выясните, какие из данных отношений являются отношением эквивалентности или отношением порядка.

Решение. Чтобы ответить на вопрос задачи, необходимо определить свойства заданных отношений.

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

Отношение «заниматься тем же видом спорта» не обладает свойством транзитивности: если х занимается тем же видом спорта, что и у, и у занимается тем же видом спорта, что и z, то учащийся х может и не заниматься тем же видом спорта, что и учащийся z. Следовательно, отношение «учащийся х занимается тем же видом спорта, что и учащийся у» не является ни отношением эквивалентности, ни отношением порядка.

 

Упражнение 14.

1. На множестве Х={х│хÎХ, х<12} задано отношение R: «х и у имеют один и тот же остаток при делении на 5».

а) покажите, что R – отношение эквивалентности;

б) запишите все классы эквивалентности, на которые разбивается множество Х данным отношением;

в) постройте граф отношения R.

2. А – множество прямых на плоскости. Выясните, какие из следующих отношений в множестве А являются отношением эквивалентности:

а) прямая х перпендикулярна прямой у;

б) прямая х параллельна прямой у;

в) прямая х пересекает прямую у.

3. Множество В={1, 2, 3, 4, 5, 6, 7} разбито на классы эквивалентности следующим образом: В={1, 3, 4}È{2, 7}È{5, 6}.

Запишите график соответствующий этому разбиению отношения эквивалентности и постройте его на координатной плоскости.

4. Уравнения: х – 2 = 0, (2х - 4)(х + 2) = 0, 4х = 8, 2х – 4 = 0, 14 + 7х = 0 заданы на множестве действительных чисел. Между ними имеет место отношение «уравнение х равносильно уравнению у». Является ли оно отношением эквивалентности? Назовите классы разбиения данного множества уравнений.

5. Какие из следующих отношений являются отношениями эквивалентности:

а) быть равноудаленным от Москвы (на множестве городов),

б) принадлежать одному и того же вида (на множестве животных),

в) иметь общую границу (на множестве городов).

6. Докажите, что отношение Н является отношением эквивалентности. Н = {(х,у)│хÎN, yÎN, (x + y) – четное число}.

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

а) быть старше по возрасту,

б) быть сестрой,

в) быть выше по росту,

г) жить в одном и том же доме,

д) быть другом,

е) быть начальником.

8. На множестве Х = {2, 4, 6, 8, 10} заданы отношения R и Q.

R: «х не больше у», Q: «х – делитель у». Докажите, что R и Q – отношения нестрогого порядка. Постройте графы этих отношений.