Класи еквівалентності.

Класом еквівалентності елемента x по відношенню еквівалентності R A A будемо називати множину [x]R елементів y A, що знаходяться у відношенні

еквівалентності R з x (включаючи сам x)

[x]R={y A|(x,y) R}

Фактор-множиною множини A по відношенню еквівалентності R, будемо називати множину всіх

класів еквівалентності множини A по відношенню еквівалентності R.

A/R={x A|[x]R}

11

Приклади класів еквівалентності

Еквівалентність

Паралельність прямих Однакова остача

при діленні на 2 Бути родичами

x y mod 5

Класи

Напрямок

{парні},{непарні}

Сім’я, рід {1,6,..},{2,7,..}, {3,8,..},{4,9,..}, {5,10,..}

12

Канонічна сюр’єкція

R A×A, R – відношення еквівалентності

φR: A A/R при якому x A [x]R

R A / R

[x]R A/R φR-1([x]R)

φR-1([x]R) = x, оскільки x [x]R

13

Розбиття

A - розбиття A

1.A A

2.A A

14

Теорема про зв’язок еквівалентності та розбиття

Довільне відношення еквівалентності R на множині А породжує розбиття А на класи еквівалентності.

І навпаки кожне розбиття {Aα} множини A задає

на множині А відношення еквівалентності R,
таке що	xRy x, y A

15

еквівалентність=>розбиття

1.[a]R [b]R c [a], c [b]

aRc,bRc симетричність aRc,cRb

транзитивність aRb

Доведемо, що в цьому разі [a]=[b]

w [a] aRw, aRb симетричність bRa, aRw

транзитивність bRw w [b]

В зворотному напрямку аналогічно

2.A [d ]

a A aRa a [a] a [d ]

16

розбиття=>еквівалентність

xRy x, y A

1.	рефлексивність a A a A a A 0		aRa
2. симетрічність aRb a,b A 0		b, a A 0	bRa
3.	транзитивність aRb,bRc a,b A ,b,c A			2
		1

b A 1 A 2 1 2

a,b, c A 1 aRc

17

Відображення та еквівалентності

F: A B

F : x,y A , x F y F(x) = F(y)

Теорема.

Для довільного F: A B

F є відношенням еквівалентності

18

Доведення теореми

1.Рефлексивність	F(x)=F(x)
x A x F x
2.Симетричність	F(x)=F(y) F(y)=F(x)
x F y y F x

3.Транзитивність			F(x) = F(y), F(y) = F(z)
x F y , y F z
	x F z		F(x) = F(z)
			19