동치관계(equivalence relation)/동치류(Equivalence Class)

동치관계(Equivalence relation)

반사관계, 대칭관계, 추이관계가 모두 성립하는 관계 R 

A relation on a set A is called an equivalence relation if it is reflexive, symmetric, and transitive.

 

동치

동치관계에 있는 관계는 서로 "동치"라고 한다. notation은 a~b이다.

Two elements a, and b that are related by an equivalence relation are called equivalent. The notation a ∼ b is often used to denote that a and b are equivalent elements with respect to a particular equivalence relation.

 

모듈로 (Congruence Modulo m)

정수 m 이 있고, 이 m은 m>1이다. 아래 relation이 동치인지 확인해보자

답)

a ≡ b (mod m) 는 a-b 가 m으로 나뉠 때 가능하다.

반사 관계 (Reflexivity) : a ≡ a (mod m) since a − a = 0 is divisible by m since 0 = 0 ∙ m

대칭 관계(Symmetry): Suppose that a ≡ b (mod m).

Then a − b is divisible by m, and so a − b = km, where k is an integer. It follows that b − a = (− k) m, so b ≡ a (mod m).

추이 관계(Transitivity)

1. Suppose that a ≡ b (mod m) and b ≡ c (mod m).

2. m divides both a − b and b − c.

3. there are integers k and l with a − b = km and b − c = lm.

4. We obtain by adding the equations: a − c = (a − b) + (b − c) = km + lm = (k + l) m.

5. Therefore, a ≡ c (mod m).

 

동치류(Equivalence class)

집합 A에 대한 관계 R이 동치관계일 때, 집합 A의 각 원소 a와 순서쌍을 이루는 원소들의 집합

[a] = {x| (a,x) ∈ R}

The set of all elements that are related to an element a of A is called the equivalence class of a.

The equivalence class of a with respect to R is denoted by [a]R .