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

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

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

이산수학에서 관계를 처음 배우면 내용보다 표기가 먼저 눈에 들어옵니다. A × B, (x, y) ∈ R, xRy, R⁻¹, [a] 같은 기호가 한꺼번에 나오기 때문입니다. 각각을 따로 외우려고 하면 관계 단원은 금방 복잡해집니다.

처음에는 관계를 “연결 목록”으로 보면 됩니다. 어떤 원소가 어떤 원소와 연결되어 있는지 하나씩 적은 것이 순서쌍이고, 그 순서쌍을 모아 둔 것이 관계입니다. 즉 관계는 막연한 관련성이 아니라, 정해진 원소쌍들의 집합입니다.

문제를 풀 때도 이 기준부터 잡아야 덜 흔들립니다. 관계 R이 주어졌다면 먼저 “어떤 순서쌍이 들어 있는가”를 보고, 그다음 “그 순서쌍들이 어떤 규칙을 만족하는가”를 확인합니다. 반사적, 대칭적, 추이적 같은 말은 이 순서쌍 목록을 검사하는 기준입니다.

처음부터 모든 기호를 완벽히 외우려고 하기보다, 순서쌍 하나를 문장으로 읽는 연습이 먼저입니다. (1, a)는 “1이 a와 연결되어 있다”로 읽고, (2, b)는 “2가 b와 연결되어 있다”로 읽으면 됩니다. 이렇게 읽히기 시작하면 뒤에 나오는 도표와 행렬도 같은 내용을 다른 모양으로 바꾼 것이라는 점이 보입니다.

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

관계를 이해하려면 곱집합과 관계 R을 구분해야 합니다. 곱집합은 실제로 선택된 관계가 아니라, 만들 수 있는 모든 연결 후보입니다. 예를 들어 A에 1과 2가 있고, B에 a와 b가 있다면 A에서 B로 만들 수 있는 후보는 네 개입니다.

A = {1, 2}
B = {a, b}

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

여기서 (1,a)는 1이 a와 연결될 수 있다는 후보입니다. (1,b), (2,a), (2,b)도 같은 방식으로 읽습니다. A × B에 들어 있다는 말은 “연결될 수 있는 자리”가 있다는 뜻이지, 문제에서 그 연결을 실제로 선택했다는 뜻은 아닙니다.

관계 R은 이 후보 중 일부를 고른 것입니다. 문제에서 R = {(1,a), (2,b)}라고 했다면, 가능한 네 개의 연결 중 (1,a)와 (2,b)만 실제 관계로 선택한 것입니다.

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

R ⊆ A × B

그래서 “관계는 곱집합의 부분집합”이라는 표현이 나옵니다. 표현은 딱딱하지만 의미는 단순합니다. 전체 후보가 A × B이고, 실제로 고른 연결이 R입니다. 이 차이를 놓치면 곱집합을 구하는 문제와 관계를 판별하는 문제가 섞여 보입니다.

또 하나 자주 놓치는 부분은 순서입니다. (1,a)와 (a,1)은 같은 순서쌍이 아닙니다. 순서쌍은 앞자리와 뒷자리의 역할이 정해져 있습니다. A에서 B로 가는 관계라면 앞자리는 A의 원소, 뒷자리는 B의 원소가 됩니다.

시험 문제에서 A × B를 먼저 구하라고 하는 이유도 여기에 있습니다. 전체 후보를 알아야 R이 그 안에서 만들어진 관계인지 확인할 수 있습니다. 만약 R 안에 A나 B에 없는 원소가 들어 있다면, 그 관계는 주어진 A × B의 부분집합이라고 말할 수 없습니다.

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

관계는 순서쌍으로만 적지 않습니다. 같은 관계를 화살표 도표, 방향 그래프, 부울행렬로 바꿔 볼 수 있습니다. 처음에는 각각이 다른 개념처럼 보이지만, 실제로는 같은 순서쌍 목록을 다른 형식으로 표현한 것입니다.

예를 들어 집합 A = {1, 2, 3} 위의 관계 R이 아래처럼 주어졌다고 보겠습니다.

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

(1,1)은 1에서 1로 가는 연결입니다. 그림으로 그리면 자기 자신에게 돌아오는 화살표가 됩니다. (1,2)는 1에서 2로 가는 화살표이고, (2,3)은 2에서 3으로 가는 화살표입니다. (3,3)은 3에서 자기 자신으로 돌아오는 연결입니다.

화살표 도표나 방향 그래프는 연결 방향을 눈으로 확인할 때 유리합니다. 자기 자신으로 가는 고리가 있는지, 한쪽 방향만 있는지, 서로 왕복하는지 바로 보이기 때문입니다. 그래서 성질 판별 문제를 풀 때 그림으로 먼저 바꿔 보면 빠진 순서쌍을 찾기 쉬워집니다.

부울행렬은 같은 관계를 0과 1로 표시한 표입니다. 행은 출발 원소, 열은 도착 원소로 두고, 관계가 있으면 1, 없으면 0을 적습니다.

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

M(R) =
[1 1 0]
[0 0 1]
[0 0 1]

첫 번째 행 두 번째 열이 1이라는 것은 1에서 2로 가는 관계가 있다는 뜻입니다. 두 번째 행 첫 번째 열이 0이라는 것은 2에서 1로 가는 관계가 없다는 뜻입니다. 행렬을 볼 때는 행과 열의 원소 순서를 먼저 고정해야 합니다. 순서가 바뀌면 같은 관계라도 행렬 모양이 달라집니다.

세 표현은 용도가 조금 다릅니다. 순서쌍은 가장 정확한 목록이고, 화살표와 방향 그래프는 연결 방향을 보기 좋고, 부울행렬은 관계를 표처럼 검사하기 좋습니다. 어느 하나만 외우기보다 같은 관계를 세 방식으로 바꿔 보는 연습이 필요합니다.

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

관계의 성질을 배울 때 가장 많이 나오는 말이 반사적, 대칭적, 추이적입니다. 이름은 낯설지만 실제로 하는 일은 순서쌍 목록을 검사하는 것입니다. 어떤 순서쌍이 반드시 있어야 하는데 빠졌는지 찾는 문제로 바꿔 보면 부담이 줄어듭니다.

먼저 반사적 관계는 모든 원소가 자기 자신과 연결되어 있어야 합니다. 집합 A가 {1, 2, 3}이라면 (1,1), (2,2), (3,3)이 모두 있어야 합니다. 하나라도 빠지면 반사적이지 않습니다.

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

반사적 확인:
(1,1) 있음
(2,2) 있음
(3,3) 있음
→ 반사적

대칭적 관계는 한쪽 방향이 있으면 반대 방향도 있어야 합니다. 예를 들어 (1,2)가 있으면 (2,1)도 있어야 합니다. 자기 자신으로 가는 (1,1) 같은 순서쌍은 뒤집어도 그대로이므로, 대칭성을 볼 때는 서로 다른 원소끼리 연결된 순서쌍을 특히 주의해서 봅니다.

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

대칭적 확인:
(1,2)가 있음
(2,1)이 없음
→ 대칭적이지 않음

추이적 관계는 두 번 이어진 연결이 있으면 한 번에 가는 연결도 있어야 합니다. 예를 들어 (1,2)와 (2,3)이 있으면 1에서 2를 거쳐 3으로 갈 수 있으므로 (1,3)도 있어야 합니다. 추이성은 두 순서쌍을 짝지어 확인해야 해서 반사성이나 대칭성보다 놓치기 쉽습니다.

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

추이적 확인:
(1,2)와 (2,3)이 있음
그러면 (1,3)이 있어야 함
하지만 (1,3)이 없음
→ 추이적이지 않음

성질 판별은 순서를 정해 두면 안정적입니다. 먼저 자기 자신 쌍을 확인하고, 다음으로 반대 방향 쌍을 확인하고, 마지막으로 두 단계 연결을 확인합니다. 세 성질을 한꺼번에 보려고 하면 빠진 순서쌍을 놓치기 쉽습니다.

부울행렬로 볼 때도 같은 기준을 씁니다. 반사성은 대각선 값이 모두 1인지, 대칭성은 대각선을 기준으로 좌우가 맞는지, 추이성은 두 번 갈 수 있는 경로가 있을 때 직접 가는 값도 1인지 확인합니다. 표현만 달라졌을 뿐 검사하는 내용은 순서쌍 기준과 같습니다.

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

관계에 익숙해지면 역관계와 합성관계가 나옵니다. 여기서도 기준은 연결입니다. 역관계는 연결 방향을 뒤집는 것이고, 합성관계는 두 관계를 이어 붙이는 것입니다.

역관계는 순서쌍의 앞뒤를 바꾸면 됩니다. (1,3)이 있었다면 역관계에는 (3,1)이 들어갑니다. A에서 B로 가던 관계를 B에서 A로 되돌려 보는 방식입니다.

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

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

합성관계는 중간 원소를 기준으로 연결을 이어 붙입니다. R로 한 번 가고, 그다음 S로 한 번 더 간 결과를 처음 원소와 마지막 원소의 관계로 적습니다.

R = {(1,a), (2,b)}
S = {(a,x), (b,y)}

1 → a → x 이므로 (1,x)
2 → b → y 이므로 (2,y)

S ∘ R = {(1,x), (2,y)}

합성관계에서 헷갈리기 쉬운 부분은 순서입니다. S ∘ R은 보통 R을 먼저 적용하고, 그다음 S를 적용합니다. 표기만 보면 S가 앞에 있어서 S부터 하는 것처럼 느껴질 수 있지만, 실제 연결은 오른쪽에 있는 R부터 따라갑니다.

처음 공부할 때는 공식을 먼저 외우기보다 화살표를 따라가 보는 방식이 더 안정적입니다. 첫 번째 관계의 도착점과 두 번째 관계의 출발점이 같아야 이어 붙일 수 있습니다. 이 중간 원소가 맞지 않으면 합성관계에 새로운 순서쌍을 만들 수 없습니다.

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

동치관계는 반사적, 대칭적, 추이적 성질을 모두 만족하는 관계입니다. 이 문장만 보면 조건 세 개를 외우는 문제처럼 보입니다. 하지만 동치관계의 의미는 원소들을 같은 기준으로 묶을 수 있다는 데 있습니다.

예를 들어 사람들을 같은 반끼리 묶는다고 생각해 볼 수 있습니다. A와 B가 같은 반이면 B와 A도 같은 반입니다. A가 자기 자신과 같은 반이라는 것도 자연스럽습니다. 또 A와 B가 같은 반이고, B와 C가 같은 반이면 A와 C도 같은 반입니다. 이런 기준은 원소들을 겹치지 않는 그룹으로 나눕니다.

수학에서 자주 쓰는 예시는 나머지가 같은 관계입니다. 정수들을 3으로 나누었을 때 나머지가 같은 수끼리 묶어 보겠습니다.

정수 집합 Z에서
xRy ⇔ x와 y를 3으로 나눈 나머지가 같다

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

여기서 [0]은 0 하나만 뜻하지 않습니다. 0과 같은 부류에 속하는 모든 원소를 모은 집합입니다. 3으로 나누었을 때 나머지가 0인 수들이 모두 [0]에 들어갑니다. [1]과 [2]도 같은 방식으로 읽습니다.

처음에는 [a]처럼 원소 하나를 대괄호로 감싼 표기가 어색합니다. 하지만 [a]는 a와 관계 R로 연결되는 원소들의 묶음입니다. a를 대표처럼 세워 두고, 그와 같은 그룹에 속하는 원소 전체를 표시한 것입니다.

동치류가 중요한 이유는 집합 전체를 겹치지 않는 그룹들로 나눌 수 있기 때문입니다. 나머지가 0인 수, 1인 수, 2인 수는 서로 겹치지 않습니다. 그리고 모든 정수는 이 셋 중 하나에는 반드시 들어갑니다. 동치관계는 이렇게 원소들을 기준에 따라 분류하는 도구입니다.

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

관계 문제를 볼 때는 처음부터 모든 기호를 동시에 해석하려고 하지 않아도 됩니다. 먼저 집합이 무엇인지 확인하고, 그다음 관계 R에 들어 있는 순서쌍을 봅니다. 그 후에 문제에서 묻는 것이 표현 변환인지, 성질 판별인지, 역관계나 합성관계인지 나누면 됩니다.

관계 문제 확인 순서

1. 집합 A, B를 확인한다.
2. A × B가 필요한 문제인지 본다.
3. 관계 R에 들어 있는 순서쌍을 읽는다.
4. 화살표나 행렬로 바꿔야 하는지 확인한다.
5. 반사적, 대칭적, 추이적 조건을 하나씩 검사한다.
6. 역관계는 순서쌍을 뒤집는다.
7. 합성관계는 중간 원소가 이어지는지 확인한다.
8. 동치관계라면 어떤 기준으로 그룹이 나뉘는지 본다.

특히 성질 판별 문제에서는 “정의가 무엇이었지?”에서 멈추기보다 “어떤 순서쌍이 빠지면 안 되지?”로 바꿔 보는 것이 좋습니다. 반사성은 자기 자신 쌍, 대칭성은 반대 방향 쌍, 추이성은 두 단계 연결 뒤의 직접 연결을 찾는 문제입니다.

관계 단원은 기호가 많아서 어렵게 보이지만, 실제 중심은 연결입니다. 곱집합은 가능한 연결 후보, 관계는 실제 선택된 연결, 성질은 그 연결 목록의 규칙, 동치관계는 같은 그룹으로 묶을 수 있는 연결 기준입니다. 이 흐름으로 보면 관계 단원은 따로 흩어진 개념이 아니라 하나의 연결 구조로 정리됩니다.