Отношение эквивалентности.

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

Определение 1:Пусть A ¹ Æ и {A_i},i= совокупность подмножеств таких, что A= . Тогда совокупность этих подмножеств называется покрытием множества A.

Например, {A, B}- покрытие AÈB; {A, AÈB, B, C}-покрытие AÈBÈC.

Замечание: В общем случае покрытие может быть и бесконечным. однако с точки зрения изучения конкретных свойств такая ситуация не вызывает энтузиазма.

Определение 2: Разбиением непустого множества А называется такое его покрытие , что если i¹ j, то A_iÇA_j=Æ.

Например, {A, A’} – разбиение U.

{AÇB, AÇB’, A’ÇB, A’ÇB’} – разбиение U,

{A\B, AÇB, B\A} – разбиение AÈB.

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

Определение 3: Бинарное отношение на множестве называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

Примеры:

1. На множестве всех треугольников: {(x, y)| x и y имеют одинаковую площадь}

2. На множестве всех программ: {(a, b)| a, b вычисляют одну и ту же функцию на конкретной машине}

Определение 4: Пусть R – отношение эквивалентности на множестве А и xÎA. Классом эквивалентности порожденным элементом х называется множество {y| xR y}=[x]_R.

Определение 5: Любой элемент класса эквивалентности называется представителемэтого класса. Полной системой представителей называется множество представителей, по одному из каждого класса.

Пример 3:

N – натуральные числа, s – фиксированный элемент. На Z определено отношение: r_s= {(x, y)| x-y=ns, nÎZ}. Отношение сравнения по модулю s ( запись: xºy(mod s)).

Нетрудно проверить, что отношение сравнения по модулю s, есть отношение эквивалентности на множестве Z.

Пусть, например, s=10. Тогда:

[1] = {11,21,-9,10 976 631,.... }

[1066] = {66,226,-24,... }

На самом деле есть всего 10 классов эквивалентности по этому отношению, а числа 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 образуют полную систему представителей. Классы эквивалентности по этому отношению эквивалентности называют классами вычетов по модулю s.

Определение 6: Фактор-множеством множества А по отношению эквивалентности R называется множество всех классов эквивалентности по этому отношению и обозначается A/R.

Множество классов вычетов по модулю s обозначают Z_s.

Имеет место

Теорема (о разбиении): Пусть R - отношение эквивалентности на непустом множестве А. Тогда фактор-множество A/R является разбиением множества А.

Доказательство:

"xÎA( xÎ[x]_R). Надо доказать, что каждый элемент множества А принадлежит в точности одному классу. То есть, докажем, что если классы имеют хотя бы один общий элемент, то они совпадают. Пусть cÎ[a] и cÎ[b]. Пусть xÎ[a], но тогда x R a, a R c, c R b Þ x R b(транзитивность R). Значит, [a] Ì [b]. ( где рефлексивность? а она есть!) Аналогично [b] Ì [a].

Что и требовалось доказать.

Имеет место и обратное утверждение. Пусть S- разбиение множества А и R_s – бинарное отношение на A, такое что: R={(x,y)ïx и y принадлежат одному элементу разбиения }, тогда R , будем называть– отношением, определяемым разбиением S.

Теорема (обратная): Отношение R на А, определяемое разбиением S, является отношением эквивалентности на А, причем A/R_s=S.(самостоятельно)

Упражнения:

1. Пусть А- конечное множество. Какие отношения эквивалентности дают наибольшее и наименьшее число классов эквивалентности.

2. Если {A₁, A₂, ..., A_n}- разбиение А и А конечно, то .

Отношение порядка.

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

Определение 1: Частичным порядкомна множестве А называется бинарное отношение, которое рефлексивно, антисимметрично и транзитивно.

Частичный порядок - это обобщение отношения £ на R. Можно ввести понятие строгого порядка, соответствующего отношению < на R. Отношение строгого порядка - только транзитивно(оно еще и антирефлексивно).

Если задан £, то можно определить <: a<b Û a£b Ù a¹b. Если задан <, то можно определить £: a£b Û a<b Ú a=b.

Множество, на котором задано отношение порядка, будем обозначать

(X, £) (или (X, <), если порядок строгий).

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

Пример: A - множество. (P(A),Í), легко проверить, что отношение Í является отношением порядка на P(A).

Определение 3: Отношение порядка R на А называется полным (линейным) порядком, если " x, yÎA (xR y Ú yR x). Множество (A, R) называется линейно упорядоченным.

Примеры:

1. отношение £ на R является отношением полного порядка. Таким образом (R, £) - линейно упорядочено.

2. а вот (P(A),Í) не является линейно упорядоченным

3. x£y Û y x на множестве N не является полным порядком

Определение 4: пусть (A, £) – частично упорядоченное множество. Элемент аÎА называетсянаименьшим /наибольшим/ в А, если " xÎA (a£ x) /x £ a /. Элемент bÎА называется минимальным /максимальным/ если " xÎA (x£ a Þ x=a) /a £ x Þ a=x /.

Задача: Доказать, что для линейно упорядоченного множества понятия наибольшего (наименьшего) и максимального (минимального) элементов совпадают. Привести пример частично упорядоченного множества, где они не совпадают.

Композиция отношений

Пусть заданы множества A, B и C и отношения S между A и B (то есть SÌA´B) и R между B и C (RÌB´C). Определим новое отношение между A и C следующим образом:

Определение 1: Множество всех пар (x, y), таких, что существует zÎB такое, что (x, z)Î S и (z, y)Î R называется композицией отношенийS и R . Обозначается: R o S . Таким образом, R o S Ì A ´ C .

R oS = {(x, y)| $zÎB((x,z)ÎSÙ(z,y)ÎR)} или x R o Sy Û $zÎB(xSzÙzRy).

Пример 1: Пусть A={1, 2, 3}, B={1, 2, 3, 4, 5, 6}, C={3, 6, 9, 12}, s ={(1,2), (2,4), (3,6)}, r={(1,3), (2,6), (3,9), (4,12)}. Тогда r o s={(1,6), (2,12)}.

Проиллюстрируем ситуацию на картинке:

Пример 2: Пусть s и r - отношения на N такие, что

s = {(x,x+1)ïxÎN} и r = {(x²,x)ïxÎN}. Тогда D_r = {x²ïxÎN}={1,4,9,16,25,...}, а D_s= N.

D_ros={xïxÎNÙ x+1=y²}={3,8,15,24,...}.

В случае, когда отношение задано на множестве, оно может быть скомбинировано с самим собой:

sos = s² = {(x,x+2)½xÎN} и ror = r² = {(x⁴,x)½xÎN}.

Используя это обозначение, можно определить энную степень отношения:

, где nÎN, n>1.

Например, для отношений из примера 2 имеем:

,

Хотелось бы дополнить аналогию с умножением. Для этого введем следующее естественное определение:

Определение 2:Бинарные отношения называются равными, если они равны как подмножества, то есть R=S, если"x,y((x,y)ÎRÛ(x,y)ÎS).

Понятно, что отношения должны быть определены на одних и тех же множествах.

Теорема (свойства композиции отношений): Для любых бинарных отношений R, S, T имеют место равенства:

1. (RoS)oT = Ro(SoT)

2. (RoS)^-1 = S^-1o R^-1

Доказательство:

1) Для любых x и y имеем:

x(RoS)oTy º $z(xTzÙ(zRoSy)) º $z$t(xTzÙ(zStÙtRy)) º $z$t((xTzÙzSt)ÙtRy) º $t(($z(xTzÙzSt))ÙtRy) º $t((xSoTt)ÙtRy) º xRo(SoT)y.

2) x(RoS)^-1y º yRoSx º $z(ySzÙzRx) º $z(xR^-1zÙzS^-1y) º xS^-1oR^-1y.

Что и требовалось доказать.

Замечание: если R - отношение на множестве A, то ясно, что I_AoR=RoI_A=R. То есть I_A ведет себя как единица при умножении чисел. Однако полной аналогии провести нельзя. Поскольку, например, коммутативность, в общем случае места не имеет, так как RoS может быть определено, а SoR нет. Также как и не всегда имеет смысл равенство R^-1oR=RoR^-1= I_A.

Замыкание отношений

Понятие замыкания является фундаментальным математическим понятием и используется в большинстве разделов математики. Проиллюстрируем это понятие на общем примере: возьмем объект x₀ и процесс P, который, будучи примененный последовательно, порождает некоторое множество и, значит, определяет последовательность x₁, x₂, ..., x_n, ... так, что x₁ÎP(x₀), x₂ÎP(x₁),..., x_nÎP(x_n-1),...

Определение 1: множество, содержащее все элементы всех последовательностей, которые могут быть получены при помощи процесса P и начинающиеся с x₀, называется замыканием процессаP относительно x₀.

Ясно, что результат будет заключаться в нахождении Рⁿ(x₀) при некотором n. Это n мы заранее не знаем, оно зависит от самого процесса. Более того, если мы возьмем элемент y из этого замыкания и будем применять к нему процесс р, то не получим ничего нового. То есть множество таким путем расширено быть не может - оно замкнуто!

Пример:Возьмем квадрат S, обозначенный ABCD и рассмотрим процесс r, заключающийся в повороте квадрата по часовой стрелке на 90°:

Пусть отношение A задано на некотором множестве. Тогда:

Определение 2: Транзитивным замыканием отношения A на данном множестве называется отношение A⁺:

Таким образом, из не транзитивного отношения A на некотором множестве можно построить транзитивное A⁺.

Примеры:

1. r - отношение на N: r={(x, y)| y=x+1}, тогда r⁺={(x, y)| x<y}

2. s на Q: s={(x, y)| x<y}, тогда s⁺=s

3. t наQ: t={(x, y)| x×y=1}, тогда r⁺={(x, x)| x¹0}

4. Пусть L - множество станций лондонского метро; L={a, b, c} последовательные станции. N={(x, y)| y следует за x}.Значит (a, b), (b, c) ÎN; кроме того (a, a), (b, b), (c, c), (a, c) Î N². Значит, N⁺=L´L

Вообще говоря, транзитивное замыкание не является рефлексивным (пример 2).

Пусть A - отношение на X. Положим A⁰=I_X.

Определение 3: Рефлексивным замыканием А* отношения A называют отношение . То есть .

Примеры:

1. r*={(x, y)| x£y}

2. s*={(x, y)| x£y}

3. t* = t⁺È{(0,0)}

4. N*=N⁺

Не нашли, что искали? Воспользуйтесь поиском по сайту: