왜 관계의 “성질”을 따로 보는가

07편에서 관계는 곱집합의 부분집합이라고 정의했다. 그런데 같은 “관계”라도 어떤 것은 “같음”처럼 행동하고, 어떤 것은 “작거나 같음”처럼 행동한다. 이 차이를 만드는 것이 관계가 가지는 성질이다. 05편에서 배운 증명 기법(특히 직접 증명과 반례)을 그대로 활용해, 주어진 관계가 어떤 성질을 만족하는지 만족하지 않는지 하나씩 판정하는 것이 이번 문서의 핵심이다.

쉽게 말하면: 같은 “관계”라는 틀 안에서도, 규칙이 조금씩 다르면 완전히 다른 종류의 질서(동치관계는 “같음”, 순서관계는 “크기 비교”)를 만들어낼 수 있다.

이 문서 전체에서는 07편에서 다룬 ”$A = \{1,2,3,4\}$ 위에서 $a$는 $b$의 약수다”라는 관계 $R$을 계속 재사용한다.

네 가지 성질의 정의

집합 $A$ 위의 관계 $R$($R \subseteq A \times A$)에 대해 다음 네 성질을 정의한다.

자주 틀리는 점: 대칭과 반대칭을 “서로 반대되는 성질”이라 여겨 하나면 다른 하나는 자동으로 아니라고 오해하기 쉽다. 실제로는 두 성질을 동시에 만족하는 관계도 있고(예: “같다” 관계), 둘 다 만족하지 않는 관계도 있다(뒤에서 확인한다). 대칭은 “양방향이면 항상 성립”, 반대칭은 “양방향이면 원소가 같아야만 성립”이라는 서로 다른 조건임을 정확히 구분해야 한다.

약수 관계로 네 성질 판별하기

$A = \{1,2,3,4\}$ 위의 약수 관계 $R$이 각 성질을 만족하는지 하나씩 서술형으로 확인한다.

반사성 확인 — 직접 증명

명제: $R$은 반사적이다.

1. 가정: 임의의 $a \in A$를 취하자.
2. 정의 적용: “$a$는 $a$의 약수다”는 모든 정수에 대해 항상 참이다($a = 1 \times a$이므로).
3. 결론: 따라서 $(a,a) \in R$이다. $a$는 임의의 원소였으므로 $R$은 반사적이다. $\blacksquare$

실제로 $R$을 나열한 목록에도 $(1,1), (2,2), (3,3), (4,4)$가 모두 포함되어 있어 위 증명과 일치한다.

대칭성 확인 — 반례로 반증

주장: $R$은 대칭이 아니다.

성질이 성립하지 않음을 보일 때는 정의를 만족하지 않는 구체적인 예(반례, counterexample) 하나만 찾으면 충분하다(정의가 “모든 $a, b$에 대해”로 시작하는 전칭 명제이므로, 이를 부정하면 04편에서 배운 정량자 부정 규칙에 의해 “어떤 $a, b$가 존재해 성립하지 않는다”가 되기 때문이다).

1. 반례 제시: $(1, 2) \in R$이다(“1은 2의 약수다”가 참이므로).
2. 검증: 그런데 $(2, 1) \notin R$이다(“2는 1의 약수다”는 거짓이므로, $1 \div 2$는 정수가 아니다).
3. 결론: $(1,2) \in R$이지만 $(2,1) \notin R$이므로, 대칭의 정의(양방향 모두 성립해야 함)를 만족하지 않는 사례가 존재한다. 따라서 $R$은 대칭이 아니다. $\blacksquare$

추이성 확인 — 직접 증명

명제: $R$은 추이적이다.

1. 가정: $(a,b) \in R$이고 $(b,c) \in R$이라 하자.
2. 정의 적용: $a$는 $b$의 약수이므로 어떤 정수 $k$에 대해 $b = ak$이고, $b$는 $c$의 약수이므로 어떤 정수 $m$에 대해 $c = bm$이다.
3. 대입: $c = bm = (ak)m = a(km)$이다.
4. 결론: $km$은 정수이므로 $a$는 $c$의 약수, 즉 $(a,c) \in R$이다. $\blacksquare$

• $k$: $b = ak$를 만족하는 정수(약수 관계의 정의에서 나온 매개변수)
• $m$: $c = bm$을 만족하는 정수

반대칭성 확인 — 직접 증명

명제: $R$은 반대칭이다.

1. 가정: $(a,b) \in R$이고 $(b,a) \in R$이라 하자.
2. 정의 적용: $a$는 $b$의 약수이고, 동시에 $b$는 $a$의 약수다.
3. 크기 비교: 자연수의 범위에서 $a$가 $b$의 약수이면 $a \le b$이고, $b$가 $a$의 약수이면 $b \le a$이다.
4. 결론: $a \le b$이고 $b \le a$이므로 $a = b$이다. $\blacksquare$

이 결과를 정리하면, 약수 관계 $R$은 반사·추이·반대칭을 만족하지만 대칭은 만족하지 않는다. 이런 조합(반사·반대칭·추이)을 가진 관계가 다음 절에서 다룰 순서관계의 대표적인 예다.

동치관계와 동치류

동치관계(equivalence relation)는 반사·대칭·추이 세 가지를 모두 만족하는 관계다. 세 성질을 모두 갖추면 이 관계는 수학적으로 “같다”라는 개념을 일반화한 것으로 취급할 수 있다.

동치관계 $R$이 집합 $A$ 위에 주어지면, 각 원소 $a \in A$에 대해 $a$와 관계를 맺는 원소를 모두 모은 집합을 그 원소의 동치류(equivalence class)라고 하고 $[a]$로 쓴다.

동치류의 핵심 성질은, 서로 다른 동치류끼리는 절대 겹치지 않으며(교집합이 공집합), 모든 동치류를 합치면 원래 집합 $A$ 전체가 된다는 것이다. 이렇게 집합을 겹치지 않는 부분집합들로 완전히 나누는 것을 분할(partition)이라 하며, 동치관계는 항상 집합의 분할을 만들어낸다.

예제 — 모듈로 3 합동

정수 집합 $\mathbb{Z}$ 위에서, $a \equiv b \pmod 3$(“$a$는 3을 법으로 $b$와 합동이다”)을 $a - b$가 3으로 나누어떨어진다는 뜻으로 정의하자. 이는 11편에서 다룰 합동(congruence) 개념의 예고편이다.

동치관계임을 확인:

1. 반사성: 모든 정수 $a$에 대해 $a - a = 0$이고 $0$은 3으로 나누어떨어지므로 $a \equiv a \pmod 3$이다.
2. 대칭성: $a \equiv b \pmod 3$이면 $a - b = 3k$(어떤 정수 $k$)이고, 양변에 $-1$을 곱하면 $b - a = 3(-k)$이므로 $b \equiv a \pmod 3$이다.
3. 추이성: $a \equiv b \pmod 3$이고 $b \equiv c \pmod 3$이면 $a - b = 3k$, $b - c = 3m$이고, 두 식을 더하면 $a - c = 3(k+m)$이므로 $a \equiv c \pmod 3$이다.

세 성질을 모두 만족하므로 이는 동치관계다. 이 관계가 만드는 동치류는 나머지에 따라 정확히 세 개로 나뉜다.

• $[0]$: 3으로 나눈 나머지가 0인 정수 전체
• 마찬가지로 $[1] = \{\ldots,-2,1,4,7,\ldots\}$(나머지 1), $[2] = \{\ldots,-1,2,5,8,\ldots\}$(나머지 2)이며, 이 세 동치류는 서로 겹치지 않고 합치면 정수 전체 $\mathbb{Z}$가 된다.

쉽게 말하면: 동치관계는 “결국 같은 부류로 취급해도 되는 것들”을 하나로 묶어주는 도구이며, 동치류는 그렇게 묶인 한 부류를 가리킨다. 시계를 볼 때 13시와 1시를 “같은 시각(1시)“으로 취급하는 것이 모듈로 12(또는 24) 합동의 동치류 개념과 같은 원리다.

부분순서와 전순서

부분순서(partial order)는 반사·반대칭·추이를 모두 만족하는 관계다. 앞서 확인했듯 약수 관계 $R$이 정확히 이 조합을 만족하므로, 약수 관계는 부분순서의 대표 예다. 부분순서를 가진 집합을 부분순서집합(poset, partially ordered set)이라 한다.

“부분”이라는 이름이 붙은 이유는, 부분순서에서는 모든 두 원소가 반드시 비교 가능하지는 않기 때문이다. 예를 들어 약수 관계에서 2와 3은 어느 쪽도 다른 쪽의 약수가 아니므로(2는 3의 약수가 아니고, 3도 2의 약수가 아니다) 두 원소는 비교 불가능(incomparable)하다.

이와 달리, 전순서(total order)는 부분순서이면서 추가로 집합의 모든 두 원소가 항상 비교 가능한 관계다.

정수나 실수에서의 “작거나 같다”($\le$) 관계가 전순서의 대표 예다. 임의의 두 정수는 항상 크기 비교가 가능하기 때문이다.

Hasse 도표

Hasse 도표(Hasse diagram)는 부분순서집합의 구조를 시각적으로 나타내는 그림으로, 다음 규칙을 따른다.

• 반사 관계(자기 자신과의 관계)는 이미 항상 성립하는 것이 자명하므로 그리지 않는다.
• 추이로 유도되는 관계(예: $a \le b$이고 $b \le c$이면 자동으로 $a \le c$)도 이미 함의되므로 선을 긋지 않는다.
• $a$가 $b$보다 “작고”, 그 사이에 다른 원소가 끼어 있지 않을 때만 $a$를 아래에, $b$를 위에 놓고 두 점을 선으로 잇는다.

예제 — 약수 관계의 Hasse 도표

$A = \{1,2,3,4,6,12\}$ 위의 약수 관계에 대한 Hasse 도표를 그려 보자. 먼저 각 쌍이 약수 관계인지 확인해 “바로 위” 관계만 추린다.

• $1$은 $2, 3, 4, 6, 12$ 모두의 약수이지만, $2$와 $3$ 사이에 다른 원소가 끼지 않으므로 $1 \to 2$, $1 \to 3$만 직접 잇는다($1 \to 4$는 $1 \to 2 \to 4$로 이미 유도되므로 생략).
• $2$는 $4$와 $6$의 약수이므로 $2 \to 4$, $2 \to 6$을 잇는다.
• $3$은 $6$의 약수이므로 $3 \to 6$을 잇는다.
• $4$와 $6$은 모두 $12$의 약수이므로 $4 \to 12$, $6 \to 12$를 잇는다.

이 도표에서 아래쪽에 있을수록 “더 작은”(더 적은 원소를 약수로 가지는) 원소이고, 선으로 직접 연결되지 않은 두 원소(예: $2$와 $3$)는 비교 불가능하다는 뜻이다. $2$와 $3$을 예로 들면, 어느 쪽도 다른 쪽보다 위에 있지 않으며 직접 선으로 연결되지도 않았으므로 서로 비교 불가능하다.

자주 틀리는 점: Hasse 도표를 그릴 때 추이로 이미 유도되는 선(예: $1$에서 $4$로 바로 가는 선)까지 전부 그리는 실수가 흔하다. Hasse 도표는 바로 위 관계만 남기고 나머지는 생략하는 것이 규칙이다.

순서관계에서의 최대·최소 원소

부분순서집합에서 자주 묻는 개념으로 다음이 있다.

• 최대원소(maximum element): 집합의 모든 원소보다 크거나 같은 원소. 위 예에서는 $12$(다른 모든 원소가 $12$의 약수이므로).
• 극대원소(maximal element): 그 원소보다 큰 원소가 없는 원소. 최대원소가 없더라도 여러 개의 극대원소가 존재할 수 있다.
• 최소원소(minimum element): 위 예에서는 $1$.

전순서에서는 최대·최소가 존재하면 극대·극소와 항상 일치하지만, 부분순서에서는 비교 불가능한 원소들 때문에 극대원소가 여러 개일 수 있다는 점이 전순서와 다른 중요한 차이다. 예를 들어 $A = \{2,3,4,6\}$ 위의 약수 관계만 따로 보면, $4$와 $6$ 모두 자신보다 큰 원소(같은 집합 안에서)가 없으므로 둘 다 극대원소이며, 이 집합에는 단일한 최대원소가 존재하지 않는다.

핵심 정리

• 관계는 반사·대칭·추이·반대칭 네 성질을 각각 독립적으로 만족하거나 만족하지 않을 수 있으며, 대칭과 반대칭은 서로 반대말이 아니다.
• 성질이 성립함은 직접 증명(임의의 원소로 시작)으로, 성립하지 않음은 반례 하나로 보이면 충분하다.
• 동치관계(반사·대칭·추이)는 집합을 겹치지 않는 동치류들로 분할한다.
• 부분순서(반사·반대칭·추이)는 비교 불가능한 원소 쌍을 허용하며, 전순서는 모든 쌍이 비교 가능한 부분순서다.
• Hasse 도표는 반사·추이로 이미 유도되는 관계를 생략하고 “바로 위” 관계만 그린다.

마무리 복습

참고 자료

• 국가평생교육진흥원 독학학위제  — 독학사 시험 안내 및 이산수학 평가영역 공식 자료.
• IEEE Standards Association  — 순서관계·동치관계 표기의 관례가 인용되는 공학 표준 문서 저장소.