집합론(Set theory)

동치관계와 분할(Equivalence relations and partitions)

'같다고 봐도 되는' 관계. 반사·대칭·추이를 만족하면 집합⁠(set)⁠이 서로 겹치지 않는 덩어리(동치류⁠, equivalence class⁠)로 나뉜다.

a \sim a,\quad a \sim b \Rightarrow b \sim a,\quad a \sim b,\ b \sim c \Rightarrow a \sim c

먼저 보면 좋은 개념집합

수학은 자주 "다르지만 같다고 보는" 일을 합니다. 1/2과 2/4는 다르게 적혔지만 같은 수이고, 시계에서 13시와 1시는 같은 자리입니다. 이런 '같음'이 세 가지 규칙을 지키면 동치관계라 합니다. 관계를 $\sim$ 로 적으면, 자기 자신과 같고(반사성⁠(reflexivity)⁠, $a \sim a$ ), 순서를 바꿔도 같고(대칭성, $a \sim b$ 이면 $b \sim a$ ), 같음이 이어집니다(추이성⁠(transitivity)⁠, $a \sim b$ 이고 $b \sim c$ 이면 $a \sim c$ ).

동치관계⁠(equivalence relation)⁠는 집합을 서로 겹치지 않는 덩어리들로 나눕니다. 원소⁠(element)⁠ $a$ 와 같은 것들을 모은 덩어리(동치류)를 $[a]$ 라 하면, 반사성 덕분에 모든 원소는 자기 덩어리에 들어갑니다. 또 두 덩어리가 원소 하나라도 공유하면 대칭성과 추이성 때문에 두 덩어리는 통째로 같습니다. 거꾸로 집합을 겹치지 않게 나눈 방법(분할)이 있으면 "같은 조각에 있다"가 동치관계가 되니, 동치관계와 분할은 같은 것을 두 가지로 본 것입니다.

정수⁠(integer)⁠에서 " $n =$ 으로 나눈 나머지⁠(remainder)⁠가 같다"는 관계를 보겠습니다. 0부터 59까지의 수 $k$ 를 각도 $2\pi k/n$ 에 놓고 조금씩 바깥으로 찍으면, 같은 덩어리가 한 줄기를 이룹니다.

같은 색 = 같은 나머지 = 같은 동치류. n을 바꾸면 줄기의 수가 바뀝니다.

각 줄기가 동치류이고, 동치류 전체를 원소로 삼은 집합이 $\mathbb{Z}/n\mathbb{Z}$ 입니다. 여기서 덧셈과 곱셈을 하는 것이 모듈러 연산⁠(modular arithmetic)⁠입니다. 줄기들이 원을 따라 도는 모습은 원을 $n$ 등분하는 1의 거듭제곱근⁠(roots of unity)⁠과 같은 그림입니다.

분수도 동치류입니다. 유리수⁠(rational number)⁠ 하나는 " $ad = bc$ 이면 $a/b \sim c/d$ "( $b, d \ne 0$ )로 묶인 분수들의 덩어리이고, 유리수를 셀 때 약분되는 칸을 건너뛴 것이 바로 덩어리마다 대표를 하나만 고른 일입니다. 거꾸로, 어떤 함수⁠(function)⁠든 "같은 값으로 가는 입력끼리"라는 동치관계를 만듭니다. 각 동치류는 한 출력값으로 가는 입력 전체, 곧 그 값의 원상입니다.

방향 없는 그래프에서 '길로 이어져 있다'는 관계도 동치관계이고(길이 0인 길, 곧 제자리도 길로 칩니다), 그 동치류가 연결 성분입니다.

원소가 n개인 집합을 나눈 덩어리들의 크기만 적으면 n을 자연수⁠(natural number)⁠의 합으로 쪼갠 것이 됩니다. 순서를 무시하고 그렇게 쪼개는 방법의 수가 분할수⁠(partition number)⁠입니다. 집합을 나누는 방법의 수와는 다릅니다. 원소 4개짜리 집합을 나누는 방법은 15가지이지만, 덩어리 크기의 목록(4, 3+1, 2+2, 2+1+1, 1+1+1+1)은 5가지뿐입니다.

'같은 조상 낱말에서 왔다'는 관계는 여러 언어의 낱말들을 동족어⁠(cognate)⁠ 무리로 나눕니다(비교 언어학⁠(comparative linguistics)⁠).

이 개념이 나오는 긴 글

정수론과 암호 나머지로 지키는 비밀 한 번도 만난 적 없는 두 사람이 모두가 엿듣는 통신망에서 비밀 열쇠를 맞출 수 있을까? 답은 시계의 산수와 1640년 페르마의 정리에 있다. 집합론 무한에도 크기가 있다 자연수와 짝수는 어느 쪽이 많을까? 칸토어는 무한을 세는 법을 찾았고, 무한이 하나가 아님을 보였다. 그래프 이론 일곱 다리의 도시 쾨니히스베르크의 일곱 다리를 한 번씩만 건너 산책할 수 있을까? 오일러는 지도를 지우고 점과 선만 남겼다.

이 개념 위에 세워진 것

모듈러 연산

이 개념을 언급하는 페이지

집합
… 사건은 그 부분집합입니다(확률). 소수를 모은 소수 집합, 나머지가 같은 수끼리 묶는동치류도 모두 집합입니다. 아무 조건이나 모아 집합을 만들어도 된다고 하면 곤란해집니다. '자기 자신을 원소로 …
집합의 크기
… 크기의 층이 끝없이 있습니다. 전단사로 짝지을 수 있다는 관계는 반사·대칭·추이를 모두 만족합니다(동치관계). 전단사를 뒤집으면 역방향 전단사가 되고, 두 전단사를 이으면 다시 전단사이기 때문입니다. 집합의 …
무리수
… 적은 모양은 다르지만 비가 같으니 같은 수로 칩니다. 이렇게 비가 같은 분수들을 한 덩어리로 묶는 약속을동치관계라 하고, 그 덩어리 하나하나가 유리수 하나입니다. √2가 분수가 아니라는 것을 그림으로 보는 방법이 …
모듈러 연산
… 9 + 5 = 14 ≡ 2). 나머지로만 수를 본다는 것은 정수 전체를 n 개의 무리로 나누는 일이고(동치관계와 분할), 원을 n 등분한 점들은 복소평면의 1의 n제곱근과 정확히 같은 모양입니다. 거기서 " a 칸 …
중국인의 나머지 정리
… 뽑은 확률이 N 을 키울 때 다가가는 값으로 읽어야 합니다. 끝으로, 칸 하나에 속하는 정수 전체는동치류두 개(' m 으로 나눈 나머지가 같은 수들'과 ' n 으로 나눈 나머지가 같은 수들')의 교집합이고, …
심슨의 역설
… 가파른 작은 결석 화살표가 길어서 합 화살표는 A 쪽이 더 완만해질 수 있습니다. 전체 집합을 어떻게분할하느냐에 따라 결론이 달라지는 셈입니다. 흔히 인용되는 또 하나의 예는 1973년 미국 버클리 대학원 입학 …
그래프
… 값을 가집니다. 지금은 . 변을 따라 오갈 수 있는 점끼리 같은 색으로 칠했습니다. '길로 이어져 있다'는동치관계라서 꼭짓점들이 서로 겹치지 않는 연결 성분 으로 나뉩니다. 지금은 개입니다. 그래프를 표로 적은 것이 …
4색 정리
… 이 지도에서 다 칠하고 나면 같은 색 나라들의 모임이 나라 전체를 서로 겹치지 않는 묶음으로 나눕니다(동치류로 나눈 분할). 1879년 영국의 변호사이자 수학자 앨프리드 켐프가 4색 정리의 증명을 발표했지만, …
보로노이 다이어그램
… 나누어 옮기는 최적 수송 문제의 답이 이런 모양입니다. 평면을 이렇게 겹치지 않는 조각들로 나누는 일(분할)은 1850년 디리클레, 1908년 보로노이가 연구했습니다. 1854년 런던 콜레라 때 존 스노가 …
분할수
… 쪼개면 순환의 길이들이 n의 분할을 이룹니다. 수 대신 집합을 겹치지 않는 조각들로 나누는 일은동치관계를 정하는 일과 같고(같은 조각에 든 것끼리를 '같다'고 보면 됩니다), 그 수를 미국의 수학자 에릭 템플 …
트리
… 무리인지는 뿌리가 같은지로 확인하고, 두 무리를 합칠 때는 한 뿌리를 다른 뿌리 아래에 매답니다. 그래서동치류를 빠르게 합치고 확인할 수 있습니다. 공통 조상에서 갈라져 나온 언어나 생물의 계통수도 트리입니다. 옛 …
최소 신장 트리
… 한쪽 끝 조각'과 나머지를 가르는 절단에서 가장 짧은 변입니다. 두 점이 이미 같은 조각인지는, 조각들을동치류로 보고 조각마다 대표 점 하나를 정해 두어 두 점의 대표가 같은지 비교하는 합집합-찾기 구조로 거의 즉시 …
수 체계: 자연수에서 실수까지
… 5), (1, 3), (10, 12)는 모두 −2입니다. 이렇게 같다고 칠 것끼리 한 덩어리로 묶는 약속이동치관계이고, 덩어리 하나가 정수 하나입니다. 이 정의에는 자연수와 덧셈만 쓰였다는 점이 중요합니다. 새 수가 옛 …
군
… 있습니다. 군을 공리로 정의하는 방식은 공리와 공준에서, 같은 것끼리 묶어 새 대상을 만드는 방법은동치관계에서, 대칭이 수학 전체에서 하는 일은 대칭과 불변량에서 이어집니다. 군 하나는 대상이 하나뿐이고 모든 …
호모토피 타입 이론
… 고리를 이어 붙이는 연산이 군을 이룬다는 것이 기본군의 요점이고, 원의 기본군 ℤ가 그림의 감긴 수입니다.동치 관계: 같은 것끼리 묶는다는 점에서 경로는 동치 관계를 넓힌 것입니다. 동치 관계가 '같은가'만 말한다면 …
보편 성질: 곱, 쌍대곱, 극한
… f(a) = g(b)\} 로, 부분집합의 교집합과 역상이 모두 이 모양입니다. 방향을 뒤집은 쌍대극한에는동치관계로 나눈 몫집합(쌍대동등자)과, 두 공간을 경계에서 붙이는 일(밀어냄: 원판 두 장을 경계에서 붙이면 …

이 페이지가 가리키는 개념

모듈러 연산 1의 거듭제곱근 가산 집합 함수 그래프 분할수 비교 언어학