동치관계와 부분순서

같은 학년으로 학생을 묶는 일과, 선행 작업에 따라 실행 순서를 정하는 일은 관계의 목적이 다릅니다. 반사·대칭·추이와 집합 분할을 연결해 두 종류를 이해합니다.

동치관계와 동치류

반사·대칭·추이를 모두 만족하는 관계가 동치관계입니다. 원소 a의 동치류 $[a]=\{x\in A\mid aRx\}$는 a와 동치인 원소들입니다. 정수에서 a-b가 3의 배수라는 관계를 사용하면 [0]은 …,-3,0,3,6,…, [1]은 …,-2,1,4,…, [2]는 …,-1,2,5,…입니다. 정수는 나머지 0,1,2의 세 그룹으로 나뉩니다.

동치류는 같거나 서로소입니다. [a]와 [b]가 공통원소 x를 가지면 aRx와 bRx입니다. 대칭성으로 xRb이고 추이성으로 aRb입니다. a와 연결된 임의의 y는 b와도 연결되므로 두 동치류가 같습니다. 반사성 덕분에 모든 a는 자기 동치류에 속해 빠지는 원소가 없습니다. 따라서 서로 다른 동치류의 모음은 분할입니다.

반대로 분할을 주고 '같은 블록에 있다'를 관계로 정의하면 동치관계입니다. 자신과 같은 블록이고, 함께 있는 순서를 바꿔도 같고, 한 원소가 두 블록에 동시에 속할 수 없어서 추이성이 성립합니다.

부분순서는 대칭 대신 반대칭

반사·반대칭·추이를 만족하면 부분순서입니다. 모든 두 원소를 비교할 수 있을 필요는 없습니다. {1,2}와 {2,3}은 서로 포함되지 않으므로 부분집합 관계에서 비교불가능합니다. 모든 쌍이 비교 가능하면 전순서입니다.

A={1,2,3,6}에서 '나눈다'를 순서로 사용해 봅시다. a가 b를 나눈다는 뜻은 b=ak인 정수 k가 있다는 것입니다. 1은 모두를 나누고, 2와 3은 6을 나누지만 서로를 나누지 않습니다. Hasse 도표에서는 자기 관계와 추이적으로 따라오는 관계를 생략하고 바로 위 연결만 표시합니다. 화살표를 생략하는 도표도 있지만 위로 갈수록 순서상 큰 원소라는 약속이 필요합니다.

최소원소는 모든 원소보다 작거나 같은 원소, 극소원소는 자기보다 엄격히 작은 원소가 없는 원소입니다. 최소는 있으면 하나지만 극소는 여러 개일 수 있습니다. {2,3,6}의 나눗셈 순서에는 극소 2,3이 있고 최소는 없습니다. 최대와 극대도 방향을 바꾸면 같습니다.

스스로 풀어보기

문제 1. {0,1,2,3,4,5}에서 같은 홀짝을 동치로 보면 동치류와 분할은 무엇인가요?

풀이: [0]=[2]=[4]={0,2,4}, [1]=[3]=[5]={1,3,5}입니다. 대표가 여섯 개여도 서로 다른 동치류는 두 개뿐입니다. 두 블록은 겹치지 않고 합집합이 원집합이라 분할입니다.

문제 2. 양의 정수 {2,4,6}의 나눗셈 순서에서 최소·최대·극대 원소를 찾으세요.

힌트: 숫자의 일반 크기가 아니라 나눗셈 관계로 비교합니다.

풀이: 2는 4와 6을 모두 나누므로 최소입니다. 4와 6 중 어느 것도 다른 쪽의 배수가 아니고 둘 다 위에 다른 원소가 없어 극대입니다. 모두가 나누는 원소는 집합 안에 없으므로 최대는 없습니다. 숫자 6이 가장 크다는 사실만으로 순서의 최대가 되지는 않습니다.

블록이 겹친다면 동치관계의 성질 중 어떤 것이 빠졌는지 돌아보세요. 한 입력의 유일한 출력은 함수, 선행 관계는 그래프로 연결합니다.