예비지식 : 동치관계와 파티션
Math2008. 3. 25. 23:35 |대수를 하기위한, 집합, 수론따위에 관련된 예비지식을 살펴본다.
--------------------------------------------------------------------------------------------------
집합의 Cardinality 와 상등
A ⊂ B 일 땐 , |A| = |B| ⇒ A = B
--------------------------------------------------------------------------------------------------
Inverse image 의 포함관계 ( 역함수 아님 )
φ' ( E ) 를 E의 inverse image under φ 라고 하면... A ⊂ φ' ( φ ( A ) )
---------------------------------------------------------------------------------------------------
Function ( 특정한 조건을 만족하는 맵 또는 릴레이션 )
역시 카테션 곱으로 설명하자면, X 에서 Y 로의 함수 f 는... f ⊂ X x Y ( X 를 도메인, Y 를 코도메인, f(X) 를 레인지 ), 가령, (a,b) ∈ f 라고 하면, a 는 한번만 등장해야 함.
기본적으로, X into Y
f(X) = Y 일때, X onto Y , surjection 전사
x값이 다르면 f(x) 값도 다를때, one-to-one 일대일, injection 단사
one-to-one 앤 onto 일때 , one-to-one correspondence 일대일대응 , bijection 전단사
---------------------------------------------------------------------------------------------------
****************************************************************************************************
An Equivalence Relation on S ⇔ An Partition of S
****************************************************************************************************
S 를 nonempty set 이라고 하고, S 위에서 어떠한 동치관계 ~ 가 있다고 하자.
그리고, S 의 원소 a 에 대해, a 와 동치관계에 있는 것들의 집합을 [a] 라고 표현하자.
즉, [a] = { x ∈ S | x ~ a }
주장하는 바는, S 에서 어떠한 동치관계가 존재하면, S에서 그러한 동치관계에 있는것끼리 묶은 집합들은 S 의 파티션이 되고, 역으로, S의 어떠한 파티션이 있으면, "같은 셀(cell)에 포함되는 관계" 는 동치관계이다.
=> 방향 증명은, 일단 S의 모든원소는 a ~ a 이므로 포함되는 셀이 있으므로, 동시에 두 셀에 포함되지 않음을 보이면 충분하다. 그러면 자동으로 disjoint 가 된다.
<= 방향증명은 데피니션만 체크하면된다.
----------------------------------------------------------------------------------------------------
이제 동치관계 ~ 가 있을때, 그에 대응되는 파티션이 있으므로, 그러한 동치관계에 의해 파티션된 각각의 셀을 생각해 볼수 있는데, 이와같이 어떠한 동치관계에 의해 파티션된 각 셀을 ~ 에 대응되는 equivalence class (동치류) 라고 한다.
----------------------------------------------------------------------------------------------------
예) 자연수 전체의 집합을 패리티에 의해 두집합으로 나누자. 즉, 홀수집합과 짝수집합으로...
그러면 1 과 3 은 같은 equivalence class 에 속하고, 2 와 4 도 같은 equivalence class 에 속한다.
곧바로 Residue Class 로 이어지는것이 당연하다.
자연수집합을 n 으로 나눈 나머지들로 분류하여 파티션한것을 Residue Classes (잉여류) modulo n 이라고 한다.
자연수집합은 이에의해 n 개의 셀로 쪼개지고, 각 셀 ( residue class) 들에 속하는 관계는 당연히 equvalence relation 이다. 즉, Residue Classes 는 Equivalence Classes.
대응되는 동치관계는 n 에 대해 같은 나머지를 같는 관계이다.
어떠한 두 수가 같은 Residue Class 에 들어갈때 , 이 둘을 modulo n 에 대해 congruent 하다고 한다.
보통 a ≡ b ( mod n ) 으로 쓴다.
잉여류에 의한 정의대신, 수론 적으로 정의하자면, n | ( a - b ) 을 위와 같이 써도 된다.
반대로, " n에 대한 나머지가 같다 "라는 관계에 의해 자연수가 파티션된다면, 이것이 동치관계여야 할 것이다.
증명해보면... ( mod n 표기는 생략. )
1. a ≡ a ( 뻔함 )
2. a ≡ b ⇒ b ≡ a ( 뻔함 )
3. a ≡ b and b ≡ c ⇒ n | ( a - b ) and n | ( b - c ) ⇒ n | ( (a-b) + (b-c) )
⇒ n | ( a - c ) ⇒ a ≡ c