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

Отношение эквивалентности. Определение и примеры.
Определение 1.31. Пусть {X1, X2,... ,Хп} - непустые множества. Тогда п-местным отношением, заданным на декартовом произведении Х1 × Х2 × ... × Хп, называют подмножество S Х1 × Х2 × ... × Хп,. При этом, если (х1,2,..., хп) S, то говорят, что элементы {х1, x2,..., хп} множества X связаны отношением S; если же (х1,2,..., хп) S то говорят, что элементы {х1, x2 ,..., хп} не связаны отношением S.
Примеры.
1) На декартовой плоскости R2 = R × R рассмотрим подмножество S - прямую, являющуюся биссектрисой первой и третьей четверти. Ясно, что пара чисел {х1,х2} из R связана двуместным отношением S тогда и только тогда, когда (х1,х2) S,TO есть х1 = х2.
Рисунок.
2) Рассмотрим 3-местное отношение на R3, заданное следующим образом: (х1,х2,x3) тогда и только тогда, когда = x3. Ясно, что в этом случае подмножество S –параболоид вращения.
Рисунок.
Двуместные отношения называют бинарными. Для бинарных отношений вместо записи (х,у) S принята запись хαу: элементы х и у находятся в отношении α. За наиболее распространенными бинарными отношениями закреплены специальные обозначения: {=,≤,<,>,≥,С,~}.
Определение 1.32. Пусть α - бинарное отношение на X × Y, β - бинарное отношение на Y × Z. Тогда композицией отнтшенип α и β называется бинарное отношение, обозначаемое α о β, на X × Z, определенное следующим образом: х(а о β)y тогда и только тогда, когда существует такой элемент у Y, ЧТО хαу и yβz.

Для композиции отношений выполняется свойство ассоциативности, то есть (α о β) о γ = α о (β о γ) для любых бинарных отношений α, β,γ - Заметим, однако, что для произвольных бинарных отношений α и β не выполняется коммутативность то есть α о β ≠ β о α.
Определение 1.33. Бинарным отношением на множестве X называется бинарное отношение на X × X.
Примеры.
1)Пусть X = R. Тогда на этом множестве можно определить следующее бинарное отношение α: хαу тогда и только тогда, когда х2 = у2 (х и у - элементы множества R.)
2) Пусть X = N. Тогда на множестве N определим следующем образом бинарное отношение <:
п1 ≤ n2 тогда и только тогда, когда (n2 — n1) N {0} .
3) Пусть X = N. Тогда на множестве N определим следующем образом бинарное отношение <:
п1 < п2 тогда и только тогда, когда (п2 — п1) N.
Далее сформулируем определения основных свойств бинарных отношений: рефлексивности, транзитивности, симметричности и антисимметричности. С помощью этих свойств выделяются два важнейших вида бинарных отношений: отношение порядка и отношение эквивалентности.
Определение 1.34. Бинарное отношение α на множестве X называется рефлексивным, если для любого элемента х из множества X выполняется отношение хαх.
Определение 1.35. Бинарное отношение α на множестве X называется транзитивным, если для любых элементов х, у, z из множества X таких, что хαу и yαz, следует, что xαz.
Определение 1.36. Бинарное отношение α называется симметричным, если для любых элементов x, у из множества X таких, что хαу, следует, что уαх.
Определение 1.37. Бинарное отношение α на множестве X называется антисимметричным, если для любых элементов х, у из множества X таких, что хαу и уαх, следует, что x = у.
Примеры.
1) Отношение = на любом множестве X является рефлексивным, транзитивным и симметричным.
2) Отношение ≤ на множестве N является рефлексивным, транзитивным и антисимметричным.
3) Отношение < на множестве N является транзитивным, но не является рефлексивным, симметричным и антисимметричным.
4) Пусть X - произвольное непустое множество. Тогда на множестве 2X (множество всех подмножеств множества X) рассмотрим бинарное отношение (Х1 Х2). Это бинарное отношение будет рефлексивным, транзитивным и антисимметричным.
Определение 1.38. Бинарное отношение α на множестве X называется отношением порядка, если оно рефлексивно, транзитивно и антисимметрично. При этом, если для любых элементов х, у из множества X справедливо либо хαу, либо уαх, то α называют линейным порядком, а пару (X, α) (множество X с линейным порядком α) - линейно упорядоченным множеством; в противном случае α - частичный порядок, а (Х,α) - частично упорядоченное множество.
Примеры.
1) (N, ≤), (R, ≤) - линейно упорядоченные множества.
2) {2А, ) - частично упорядоченное множество, если |А| > 1. Если же |А| = 1, то (2A, ) - линейно упорядоченное множество.
Определение 1.39. Бинарное отношение α на множестве X называется отношением эквивалентности, если оно рефлексивно, транзитивно и симметрично.
Примеры.
1) Отношение α на множестве R такое, что хαу тогда и только тогда, когда х2 = у2, является отношением эквивалентности.
2) Отношение = на N, R и на любом множестве X является отношением эквивалентности.
Определение 1.40. Пусть α - отношение эквивалентности на множестве X, х - произвольный элемент множества X. Тогда классом эквивалентности (смежности) элемента х по отношению эквивалентности α называется множество [х]α = {у X | хαу}.
Примеры.
1) Пусть на множестве R задано отношение α: хαу тогда и только тогда, когда х2 = у2. Тогда [1]α = {1,-1}.
2) В любом множестве X с отношением эквивалентности =: [х]= = {х} для любого элемента х множества X.

Теорема 1.41. Пусть α отношение эквивалентности на множестве X, X ≠ Ø. Тогда:
1) [х]а ≠ Ø для любого элемента х множества X;
2) для любых элементов х и у из множества X таких, что [х]а [у]а ≠ Ø; следует, что [х]а = [у]а
3)
Доказательство. 1) Отношение α - рефлексивно, следовательно, для любого х из множества X выполняется хαх. Таким образом х [x]α и [x]α ≠ Ø.
3) Так как х [х]α, то , следовательно
2) Пусть [х]α [у]α ≠ Ø. Тогда найдется такой элемент z множества X, что xαz и yαz. Пусть t - произвольный элемент из класса [х]α Тогда xαt и xαz, следовательно, выполняется tαz (мы воспользовались транзитивностью и симметричностю). Аналогично, так как tαz и yαz, то tαy. Таким образом [х]α [у]α. Точно также доказывается, что [у]α [х]а , и свойство 2) доказано.

Определение 1.42. Пусть α - отношение эквивалентности на множестве X. Фактор-множеством множества X по отношению эквивалентности α называется множество, обозначаемое Х/α, элементами которого являются классы эквивалентности [х]α множества X по отношению эквивалентности α.
Определение 1.43. Пусть α - отношение эквивалентности на множестве X. Множество X' (X' X) называется системой различных представителей по отношению эквивалентности α, если для любого х из множества X выполняется условие: |Х' [х]α | = 1.

Заметим, что можно выбирать различные системы представителей по отношению эквивалентности α на множестве X, однако количество элементов в каждой такой системе одно и тоже. Справедлива следующая теорема, которую мы сформулируем без доказательства.

Теорема 1.44. Если α - отношение эквивалентности на множестве X, X' - система различных представителей по отношению эквивалентности α на множестве X, то существует биективное отображение φ : Х/α → X'. В частности, если Х/α -конечное множество, то |Х/α| = |Х'| .

Отношение эквивалентности на множестве обычно обозначают знаком ~.

Пример. На множестве Z рассмотрим следующее отношение эквивалентности: z1 ~ z2 тогда и только тогда, когда z1 — z2 делится нацело на 2. Тогда множество Z разбивается на два непересекающихся класса эквивалентности:
[0]~ = {0,±2,±4,...,±2n,...},
[1]~ = {±1,±3,...,±(2n+1),...}.

Любая система различных представителей в этом случае содержит 2 элемента. Например, {0,1} и {4,-5} - системы различных представителей множества Z по отношению эквивалентности ~.

Powered by Drupal - Design by artinet