관계의 표현과 성질

'팔로우한다', '같은 그룹이다', '먼저 실행해야 한다'는 모두 대상 사이의 관계지만 성질은 다릅니다. 곱집합을 바탕으로 관계를 정확히 정의하고 그 성질을 검사합니다.

관계는 허용한 순서쌍의 집합

A에서 B로의 이항관계 R은 A×B의 부분집합입니다. $(a,b)\in R$을 aRb라고도 씁니다. 같은 집합 A 안의 관계는 A×A의 부분집합입니다. A={1,2,3}에서 R={(1,1),(1,2),(2,3)}이면 1은 1,2와 관계 있고 2는 3과 관계 있습니다. (2,1)이 없으므로 방향을 바꾸어 읽으면 안 됩니다.

원소 순서를 1,2,3으로 고정한 관계 행렬은 i번째 원소에서 j번째 원소로 관계가 있으면 $M_{ij}=1$, 없으면 0입니다. 위 R의 행은 (1,1,0),(0,0,1),(0,0,0)입니다. 방향 그래프로 표현하면 순서쌍마다 화살표를 그립니다. (1,1)은 자기 자신으로 돌아오는 루프입니다.

성질은 모든 원소에서 검사한다

위 R은 (2,2),(3,3)이 없어 반사적이지 않고, (1,2)에 대한 (2,1)이 없어 대칭적이지 않습니다. 서로 다른 원소를 양방향으로 잇는 쌍은 없어서 반대칭적입니다. 그러나 (1,2),(2,3)은 있는데 (1,3)이 없으므로 추이적이지 않습니다.

반대칭은 '대칭이 아님'과 다릅니다. 항등관계 {(1,1),(2,2),(3,3)}는 대칭이면서 반대칭입니다. 서로 다른 두 원소의 양방향 관계만 금지하기 때문입니다. 빈 관계는 비어 있지 않은 집합에서 반사적이지 않지만 대칭·반대칭·추이 조건은 위반하는 쌍이 없어 성립합니다.

정수의 ≤ 관계는 반사·반대칭·추이를 만족하지만 대칭은 아닙니다. '<'는 반사성이 없고 x<x를 허용하지 않는 비반사 관계입니다. '반사적이지 않다'는 대각선 중 일부가 빠져도 해당하지만, 비반사성은 모든 자기 관계가 없음을 요구합니다.

스스로 풀어보기

문제 1. A={a,b}에서 R={(a,a),(b,b),(a,b),(b,a)}의 네 성질을 판정하세요.

풀이: R=A×A라 대각선과 반대 방향과 모든 합성 쌍이 있어서 반사·대칭·추이적입니다. a≠b인데 aRb와 bRa가 모두 있으므로 반대칭은 아닙니다. 같은 집합에서 서로 다른 두 원소의 양방향 관계 한 쌍만 찾아도 반대칭 실패를 보일 수 있습니다.

문제 2. 정수에서 aRb를 'a-b가 짝수이다'로 정의했습니다. 대칭성과 추이성을 증명하세요.

힌트: 짝수를 2k로 쓰고 음수·합의 형태를 확인합니다.

풀이: a-b=2k이면 b-a=-2k=2(-k)라 대칭적입니다. a-b=2r,b-c=2s이면 a-c=(a-b)+(b-c)=2(r+s)라 추이적입니다. 정의를 식으로 풀어 직접증명했습니다.

판정할 때 해당 쌍이 없다는 이유만으로 모든 성질이 실패한다고 말하지 마세요. 빠진 쌍을 최소한 추가하는 방법은 합성과 폐포로 이어집니다.