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

핵심 정의와 기호

A×B는 ‘A 곱하기 B’라고 읽으며 a∈A,b∈B인 모든 순서쌍 (a,b)의 집합입니다. 관계 R은 A×B의 부분집합입니다. 예를 들어 {1,2}×{x,y}={(1,x),(1,y),(2,x),(2,y)}입니다.

반사·대칭·추이는 같은 집합 A 위 관계 R⊆A×A에 대해 다음처럼 정의합니다.

성질	모든 a,b,c∈A에 대한 조건
반사	(a,a)∈R
대칭	(a,b)∈R이면 (b,a)∈R
추이	(a,b),(b,c)∈R이면 (a,c)∈R

세 성질을 모두 만족하면 동치관계입니다. [a]는 ‘a의 동치류’라고 읽고 a와 관계가 있는 원소를 모읍니다.

가장 작은 예제

A={1,2,3}의 같은 홀짝 관계는 R={(1,1),(1,3),(3,1),(3,3),(2,2)}입니다. 자신과 홀짝이 같으므로 반사적이고, 홀짝이 같다는 판단은 양방향이므로 대칭적입니다. a와 b, b와 c의 홀짝이 같으면 a와 c도 같아 추이적입니다. 동치류는 {1,3}, {2}로 나뉩니다.

헷갈리는 반례

A에서 ‘a<b’는 추이적이지만 (1,1)이 없으므로 반사적이지 않고 (1,2)는 있으나 (2,1)은 없어 대칭적이지 않습니다. 성질 하나로 동치관계라고 판정할 수 없습니다.

손으로 풀어보기

R={(1,1),(2,2),(3,3),(1,2),(2,1)}을 확인합니다. 모든 대각 순서쌍이 있어 반사적이고, (1,2)의 반대 (2,1)이 있어 대칭적입니다. {1,2} 안의 가능한 연결은 모두 있고 {3}은 자기 자신에만 연결되므로 추이적입니다. 동치류는 {1,2},{3}입니다.

변형 문제: R에서 (2,1)만 제거하면 (1,2)의 반대가 없어 대칭성이 깨집니다. 원래 R에 빠진 쌍 때문에 결함이 있다는 뜻이 아닙니다.

선택: JavaScript로 검산하기

코드 직접 실행

본문 예제를 선택하고 실제 계산 결과를 확인합니다.

예제 크게 보기 (새 탭)

손풀이 뒤 선택해서 실행하는 짧은 전체 코드입니다. 브라우저 Console 또는 Node.js가 준비된 환경의 check.mjs에서 실행할 수 있으며 수학 학습에 설치는 필수가 아닙니다.

const R = new Set(['1,1', '2,2', '3,3', '1,2', '2,1']);
const A = [1, 2, 3];
const reflexive = A.every((a) => R.has(`${a},${a}`));
console.log({ reflexive });

기대 결과: { reflexive: true }가 출력됩니다.

코드는 반사성만 검사합니다. 대칭·추이까지 자동으로 확인한 결과로 해석하지 않습니다.

자주 발생하는 오해와 교정

대칭은 반대 방향 순서쌍의 존재, 추이는 두 연결의 이어짐에 관한 조건입니다. 자기 자신과의 쌍 (a,a)이 하나라도 빠지면 반사적이지 않습니다. 성질 하나만 확인한 코드를 동치관계 전체 판정으로 읽지 않습니다.

직접 풀어볼 문제와 해설

쉬운 개념

관계 R은 A×A에서 고른 순서쌍입니다. 반사는 모든 (a,a), 대칭은 (a,b)에 대한 (b,a), 추이는 (a,b)와 (b,c)에 대한 (a,c)를 요구합니다.

단계별 예제

1. A={1,2,3}, R={(1,1),(2,2),(3,3),(1,2)}를 적습니다.
2. 대각 순서쌍 세 개가 있어 반사적입니다.
3. (1,2)는 있지만 (2,1)이 없어 대칭적이지 않습니다.

직접 풀 문제

이 R은 추이적인가요? 한 순서쌍만 추가하여 동치관계로 만들고 동치류를 구하세요.

정답·해설 보기

1. (1,2)를 다른 쌍과 두 단계로 이어도 필요한 (1,2)만 나오므로 원래 R은 추이적입니다.
2. (2,1)을 추가하면 반사·대칭·추이를 모두 만족하고 동치류는 {1,2}, {3}입니다.
3. (1,2),(2,1)을 잇는 경우 (1,1),(2,2)도 이미 있으므로 추이가 유지됩니다.

다음 학습

5회차에서는 관계 가운데 모든 입력에 출력이 정확히 하나인 함수를 살펴봅니다. 다음 글 읽기

학습 완료 체크리스트

• 정의의 적용 범위와 기호를 말로 설명할 수 있습니다.
• 위 손풀이를 답을 가린 상태에서 다시 계산합니다.
• 반례가 어떤 조건을 어기는지 설명합니다.

알고리즘 수학 노트

누적 이전 체크포인트: discrete-step-03-proof. 아래는 이번 회차의 완성 예시입니다. 자신의 다른 예제 하나를 덧붙여도 좋습니다.

중복 데이터를 같은 그룹으로 묶으려면 ‘같음’ 기준이 반사·대칭·추이를 만족하는지 확인합니다. 가까운 점끼리 묶는 관계처럼 a가 b에 가깝고 b가 c에 가까워도 a가 c에 가깝지 않을 수 있으면 동치관계가 아닙니다. 곱집합→관계→성질→동치류 순서와 R의 체크표를 저장합니다.

완료 체크포인트

discrete-step-04-relation

다음 학습

이산수학 함수 쉽게 이해하기: 정의역 공역 치역과 단사 전사에서 다음 개념을 이어갑니다.