이산수학 동치 관계와 분할

동치 관계와 분할

이산수학에서 집합의 원소들 사이의 관계를 이해하는 것은 알고리즘, 데이터 분류, 네트워크 구조 설계에 매우 중요합니다. 그중에서도 동치 관계(Equivalence Relation)는 집합을 체계적으로 나누고 분류할 수 있어서 분할이라는 개념이 자동적으로 나옵니다. 분할은 구조설계에 있어서 중요하기에 반드시 알아야 하는 개념입니다.

이번 글에서는 동치 관계가 무엇이며, 그것이 어떻게 집합을 분할(Partition)하는지 살펴보겠습니다.

1. 동치 관계란?

동치 관계(Equivalence Relation)는 이름 그대로 "같다"는 의미를 일반화한 관계입니다. 세 가지 중요한 성질을 동시에 만족해야 합니다.

동치 관계의 세 가지 조건

성질	의미
반사성	모든 원소는 자기 자신과 관계를 맺는다. (a, a) ∈ R
대칭성	관계가 성립하면, 그 역도 성립한다. (a, b) ∈ R → (b, a) ∈ R
추이성	관계가 이어지면, 그 끝도 관계가 성립. (a, b), (b, c) ∈ R → (a, c) ∈ R

이 세 조건을 모두 만족하는 관계가 동치 관계입니다.

🎯 예시 1: 같은 나머지를 갖는 관계

집합 A = {1, 2, 3, 4, 5, 6}에서
"같은 수를 3으로 나눴을 때 나머지가 같다"는 관계 R을 생각해봅시다.

• 1 % 3 = 1, 4 % 3 = 1 → (1, 4) ∈ R
• 2 % 3 = 2, 5 % 3 = 2 → (2, 5) ∈ R
• 3 % 3 = 0, 6 % 3 = 0 → (3, 6) ∈ R

이 관계는 반사적이고, 대칭적이고, 추이적입니다. 따라서 동치 관계입니다.

2. 동치류(Equivalence Class)

동치 관계가 있으면, 원소들을 서로 동치인 것끼리 묶을 수 있습니다. 이를 동치류라고 부릅니다.

a ∈ A가 있을 때, a의 동치류는 [a] = { x ∈ A | (a, x) ∈ R }

즉, a와 관계 R을 맺는 모든 x를 모은 집합입니다.

위 예시에서 보면 나누기는 나머지가 같은 숫자들이 나옵니다. 나머지가 같은 류로 묶을 수 있습니다.

• [1] = {1, 4}
• [2] = {2, 5}
• [3] = {3, 6}

3. 분할(Partition)이란?

분할이란 집합을 서로 겹치지 않는 부분 집합들로 완전히 나누는 것을 의미합니다. 위와 같은

어떤 집합 A의 분할은 {A₁, A₂, ..., Aₙ}의 집합족으로,

• 각 Aᵢ는 공집합이 아니고,
• Aᵢ ∩ Aⱼ = ∅ (i ≠ j),
• A₁ ∪ A₂ ∪ ... ∪ Aₙ = A

즉, 완전히 나누되, 중복 없이 빠짐없이 나눠야 합니다.
[[4.Projects/블로그/발행한 글/이산수학 집합족(Family of sets)]]

4. 동치 관계와 분할의 연결

놀라운 사실 하나!

모든 동치 관계는 하나의 분할을 만든다.
모든 분할은 하나의 동치 관계를 정의한다.

즉, 동치 관계 ↔ 분할은 1:1 대응입니다.

🔄 어떻게 연결되는가?

• 동치 관계가 주어지면 → 동치류들로 분할됨
• 분할이 주어지면 → 같은 집합에 속하는 원소끼리 동치라고 정의 가능

5. 실생활 예시

상황	동치 관계 기준	동치류 (= 분할된 집합들)
학교에서 반편성	같은 반에 소속	반별로 학생 분류
SNS 유저 프로필	같은 나이대	연령대 그룹으로 사용자 나누기
이미지 분류	같은 객체로 인식됨	객체별 이미지 분할
모듈 연산	같은 나머지를 가짐	나머지별 그룹 (mod 클래스)

마치며

동치 관계와 분할은 데이터를 구조화하고 그룹화하기 위해 사용됩니다. 수학과 컴퓨터과학에서는 군집화(Clustering), 데이터베이스 정규화, 상태 분류 및 추상화, 대수 구조의 기초인 군,링 등에서 쓰이고 있습니다. 이처럼 동치 관계는 단순한 수학 개념을 넘어, 구조적 사고의 기반이 됨으로써 생각하기 편해지고 사고를 확장할 수가 있습니다.

 

함께보면 좋은글

이산수학, 집합 연산 정복

이산수학 집합족(Family of sets)