이산수학 관계 쉽게 이해하기: 곱집합과 동치관계 기준

이 글은 관계의 정의를 곱집합에서 시작해 표현 방법, 세 가지 성질, 역관계와 합성관계, 동치관계와 동치류까지 한 흐름으로 연결합니다. 공식 정의를 먼저 적고 작은 유한집합 예시로 바로 검산하므로, 기호를 외우기보다 어떤 순서쌍이 필요하고 무엇이 빠졌는지 판단하는 기준을 얻을 수 있습니다.

이 글에서 정리하는 내용

• 관계가 어렵게 느껴지는 지점
• 곱집합은 가능한 연결 후보이다
• 순서쌍·화살표·행렬은 같은 관계를 다르게 본 것이다
• 반사적·대칭적·추이적은 빠진 순서쌍을 찾는 문제다
• 역관계와 합성관계는 방향과 연결 순서를 보는 것이다
• 동치관계와 동치류는 같은 그룹으로 나누는 기준이다
• 관계 문제를 풀 때 확인할 순서

관계가 어렵게 느껴지는 지점

집합 A에서 집합 B로 가는 이항관계 R은 곱집합 A × B의 부분집합입니다. 기호로는 R ⊆ A × B라고 씁니다. (a,b) ∈ R이면 a가 b와 관계가 있다고 말하고 aRb로 줄여 쓰기도 합니다. 특히 A에서 A로 가는 관계, 즉 R ⊆ A × A를 집합 A 위의 관계라고 합니다.

A = {1, 2, 3}
B = {a, b}
R = {(1, a), (2, a), (3, b)}

이 예시에서 1과 a, 2와 a, 3과 b는 연결되어 있고 나머지 순서쌍은 연결되어 있지 않습니다. 관계는 각 입력에 출력이 하나만 있어야 하는 함수보다 넓은 개념입니다. 어떤 원소는 아무것과도 연결되지 않을 수 있고, 하나의 원소가 여러 원소와 연결될 수도 있습니다. 따라서 관계 문제에서는 먼저 함수의 규칙을 떠올리기보다 전체 후보 A × B 가운데 실제로 선택된 순서쌍을 표시하는 편이 안전합니다.

MIT OpenCourseWare의 관계 강의와 공개 이산수학 교재도 관계를 곱집합의 부분집합으로 정의합니다. 이 정의를 기준점으로 잡으면 그림이나 행렬은 새로운 대상이 아니라 같은 순서쌍 집합을 다른 방식으로 표시한 것임을 알 수 있습니다.

곱집합은 가능한 연결 후보이다

곱집합 A × B는 첫 번째 원소를 A에서, 두 번째 원소를 B에서 골라 만든 모든 순서쌍의 집합입니다. A = {1, 2}, B = {a, b}라면 후보는 정확히 네 개입니다.

A × B = {(1, a), (1, b), (2, a), (2, b)}

관계 R은 이 네 후보 중 일부 또는 전부를 고른 집합입니다. 아무것도 고르지 않은 ∅도 관계이고, 전부 고른 A × B도 관계입니다. A의 원소 수가 m, B의 원소 수가 n이면 곱집합에는 mn개의 순서쌍이 있고, 각 순서쌍을 포함할지 말지 독립적으로 고르므로 A에서 B로 가는 관계는 총 2^(mn)개입니다.

순서쌍은 순서가 중요합니다. 일반적으로 (1,a)와 (a,1)은 다르고, 앞의 순서쌍은 A × B에 속하지만 뒤의 순서쌍은 B × A에 속합니다. 관계의 방향을 바꾸는 역관계를 구할 때 두 좌표를 뒤집어야 하는 이유도 여기에 있습니다.

조건으로 주어진 관계를 순서쌍으로 바꾸기

관계가 목록 대신 조건으로 주어지기도 합니다. 예를 들어 A = {1, 2, 3, 4} 위에서 xRy ⇔ x가 y를 나눈다라고 정의하면, A × A의 모든 후보를 살펴 실제로 나누어떨어지는 순서쌍만 고릅니다.

R = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}

조건식이 복잡해 보여도 유한집합에서는 후보 생성 → 조건 검사 → 통과한 순서쌍 기록의 세 단계로 바꾸면 됩니다. 이후 성질 판정도 이 목록을 기준으로 확인할 수 있습니다.

순서쌍·화살표·행렬은 같은 관계를 다르게 본 것이다

같은 관계는 순서쌍 목록, 방향 그래프, 0과 1로 된 부울 행렬로 나타낼 수 있습니다. 어느 표현을 사용해도 관계 자체는 달라지지 않습니다. A = {1, 2, 3} 위의 관계 R = {(1,1), (1,2), (2,3), (3,1)}을 생각해 보겠습니다.

• 순서쌍: 포함된 연결을 가장 직접적으로 기록합니다.
• 방향 그래프: (x,y)를 정점 x에서 y로 향하는 화살표로 그립니다. (1,1)은 자기 자신으로 돌아오는 고리입니다.
• 부울 행렬: 행을 첫 번째 원소, 열을 두 번째 원소로 두고 관계가 있으면 1, 없으면 0을 적습니다.

행렬의 첫 행이 1, 1, 0인 이유는 (1,1)과 (1,2)는 R에 있고 (1,3)은 없기 때문입니다. 대각선, 전치 위치, 길이 2인 경로를 살피면 각각 반사성, 대칭성, 추이성을 빠르게 점검할 수 있습니다. 다만 행렬은 어디까지나 유한집합에서 편리한 표현이며 성질의 정의는 순서쌍과 논리식으로 판단해야 합니다.

반사적·대칭적·추이적은 빠진 순서쌍을 찾는 문제다

세 성질은 모두 집합 A 위의 관계 R ⊆ A × A에 대해 정의합니다. 말로만 외우면 헷갈리므로 조건과 반례의 모양을 함께 보는 것이 좋습니다.

A = {1, 2, 3}이고 R = {(1,1), (2,2), (3,3), (1,2)}이면 모든 (x,x)가 있으므로 반사적입니다. 하지만 (1,2)는 있는데 (2,1)이 없으므로 대칭적이지 않습니다. 성질이 성립하지 않음을 보일 때는 정의를 깨뜨리는 순서쌍 하나면 충분합니다.

추이성은 가운데 원소가 맞는 두 순서쌍을 찾습니다. S = {(1,1), (2,2), (3,3), (1,2), (2,3)}에는 (1,2)와 (2,3)이 있지만 필요한 (1,3)이 없으므로 추이적이지 않습니다. 반대로 이어지는 두 순서쌍 자체가 없다면 추이 조건은 반례가 없어 참일 수 있습니다. 결론에 필요한 순서쌍이 원래 목록에 있는지 끝까지 확인해야 합니다.

대칭과 반대칭은 서로의 부정이 아니다

반대칭은 (x,y) ∈ R이고 (y,x) ∈ R이면 x = y여야 한다는 조건입니다. 서로 다른 두 원소 사이에 양방향 연결이 없다는 뜻에 가깝습니다. 등호 관계는 대칭적이면서 반대칭적이고, 공집합 관계도 둘 다 만족할 수 있습니다. 따라서 대칭적이지 않다고 곧바로 반대칭적이라고 결론 내리면 안 됩니다.

역관계와 합성관계는 방향과 연결 순서를 보는 것이다

역관계는 모든 순서쌍의 방향을 뒤집는다

R이 A에서 B로 가는 관계라면 역관계 R⁻¹은 B에서 A로 가며, R의 모든 순서쌍에서 앞뒤를 바꿉니다.

R = {(1,a), (2,a), (3,b)}
R⁻¹ = {(a,1), (a,2), (b,3)}

대칭적인 A 위의 관계는 방향을 모두 뒤집어도 같으므로 R = R⁻¹입니다. 이 등식은 대칭성을 검사하는 또 다른 방법입니다.

합성관계는 중간 원소를 통해 두 단계를 잇는다

R이 A에서 B로, S가 B에서 C로 가는 관계라면 S ∘ R은 A에서 C로 갑니다. 어떤 b ∈ B가 있어 (a,b) ∈ R이고 (b,c) ∈ S일 때 (a,c)를 합성관계에 넣습니다. 표기 S ∘ R에서도 실제 적용 순서는 오른쪽 R이 먼저입니다.

R = {(1,a), (2,b), (3,a)}
S = {(a,X), (b,Y)}
S ∘ R = {(1,X), (2,Y), (3,X)}

합성을 계산할 때는 R의 두 번째 좌표와 S의 첫 번째 좌표가 같은지 연결하고, 중간 원소는 결과에서 제거합니다. 중간 집합이 맞지 않으면 합성을 정의할 수 없고, 같은 시작점과 끝점을 만드는 경로가 여러 개여도 관계는 집합이므로 결과 순서쌍은 한 번만 적습니다.

동치관계와 동치류는 같은 그룹으로 나누는 기준이다

집합 A 위의 관계가 반사적·대칭적·추이적 세 조건을 모두 만족하면 동치관계라고 합니다. 동치관계는 원소들을 서로 겹치지 않는 그룹으로 묶습니다. 한 원소 a의 동치류는 [a] = {x ∈ A : xRa}처럼 a와 동치인 모든 원소의 집합입니다.

정수 집합 ℤ에서 xRy ⇔ x ≡ y (mod 3), 즉 x와 y를 3으로 나눈 나머지가 같다고 정의해 보겠습니다. 이 관계는 모든 정수가 자기 자신과 같은 나머지를 가지므로 반사적이고, 나머지가 같다는 조건은 방향을 바꿔도 같으므로 대칭적이며, 같은 나머지라는 조건이 이어지면 처음과 끝도 같으므로 추이적입니다.

[0] = {..., -6, -3, 0, 3, 6, ...}
[1] = {..., -5, -2, 1, 4, 7, ...}
[2] = {..., -4, -1, 2, 5, 8, ...}

동치류는 같거나 서로소입니다. 예를 들어 [1]과 [4]는 대표 원소는 다르지만 같은 집합이고, [0]과 [1]은 공통 원소가 없습니다. 모든 동치류를 합치면 원래 집합 ℤ 전체가 됩니다. 이를 동치관계가 집합의 분할을 만든다고 말합니다. 반대로 집합을 겹치지 않는 비어 있지 않은 블록들로 분할하면 같은 블록에 속한다는 규칙으로 동치관계를 만들 수 있습니다.

동치관계 판정에서 자주 놓치는 점

• 예시 몇 개가 맞는 것만으로 전체 성질이 증명되지는 않습니다. 정의의 임의의 원소에 대해 논증해야 합니다.
• 반사성은 관계에 등장한 원소만이 아니라 바탕집합 A의 모든 원소를 확인합니다.
• 동치류의 이름은 대표 원소가 달라도 실제 원소 집합이 같을 수 있습니다.
• 대칭 대신 반대칭을 만족하는 관계는 동치관계가 아니라 부분순서 후보일 수 있습니다.

관계 문제를 풀 때 확인할 순서

1. 바탕집합과 방향을 적습니다. R이 A에서 B로 가는지, A 위의 관계인지 먼저 고정합니다.
2. 곱집합 후보를 확인합니다. 조건식이 있으면 각 순서쌍이 조건을 만족하는지 검사합니다.
3. 표현을 하나로 통일합니다. 작은 문제는 순서쌍, 반복 계산은 행렬, 경로 해석은 방향 그래프가 편리합니다.
4. 성질별 반례를 찾습니다. 빠진 대각선, 짝이 없는 역방향, 지름길이 없는 두 단계 경로를 차례로 봅니다.
5. 역과 합성의 타입을 확인합니다. 좌표를 뒤집었는지, 중간 집합과 적용 순서가 맞는지 점검합니다.
6. 동치류는 집합으로 비교합니다. 대표 원소의 이름이 아니라 실제 원소가 같은지 확인합니다.

공개 교재로 다시 확인하기

• MIT OpenCourseWare 6.1200J Lecture 15: Relations — 관계, 합성, 동치관계와 분할을 다루는 대학 공개 강의 노트입니다.
• MIT OpenCourseWare: Mathematics for Computer Science 읽기 자료 — 공개 교재의 판본과 강의별 읽기 범위를 확인할 수 있습니다.
• Discrete Mathematics: An Open Introduction — Relations and Graphs — 관계·역관계·합성·동치류의 정의와 예시를 제공하는 공개 교재입니다.

다음 학습 경로

곱집합과 부분집합 표기가 낯설다면 먼저 이산수학 집합 기초를 복습하세요. 관계 가운데 각 입력에 출력이 정확히 하나인 특별한 경우는 이산수학 함수 단사 전사에서 이어집니다. 관계를 정점과 화살표로 해석하는 연습은 그래프 이론 기본 개념으로 확장할 수 있습니다.

결론: 관계 문제의 출발점은 항상 R ⊆ A × B입니다. 바탕집합과 순서쌍을 먼저 고정한 뒤 반사성은 대각선, 대칭성은 역방향 짝, 추이성은 두 단계 경로의 지름길로 확인하면 됩니다. 이 세 조건을 모두 통과한 동치관계는 동치류를 통해 원래 집합을 정확히 분할한다는 점까지 연결하면 정의와 계산이 하나의 체계로 정리됩니다.