[집합론] 대응관계 $($Relation$)$

대응관계

집합론에서 '관계', relation은 곱집합의 부분집합으로 정의한다.

이때 두 집합의 곱집합$($데카르트 곱$)$은 아래와 같이 정의한다.

 

집합 $A=\left\{a_{1}, a_{2}, ... \right\}$, 집합 $B=\left\{b_{1}, b_{2}, ... \right\}$에 대해

곱집합 $A \times B = \left\{(a, b) | a \in A, b \in B\right\}$이다. 

 

ex) 집합 $A=\left\{1,2,3\right\}$, 집합 $B=\left\{a,b,c\right\}$에 대해, 곱집합 $A\times B$는 다음과 같다.

$A \times B = \left\{(1,a), (1,b), (1,c), (2,a), (2,b), (2,c), (3,a), (3,b), (3,c) \right\}$

 

Relation은 곱집합의 부분집합이므로 아래와 같다. 

집합 $X$에 대해 $X$에서 정의된 relation $R$은 $R \subseteq X \times X$ 이다. 

 

ex) 자연수 집합에서 정의된 relation $\leq$ 은 $ \leq \subseteq \mathbb{N} \times \mathbb{N}$ 이다.

Relation $\leq$를 원소 나열법으로 보이면 $ \leq = \left\{(1,1), (1,2), (1,3), ...., (2,2), (2,3), (2,4), ... \right\} $ 와 같다.

$(1,2) \in \leq$처럼 나타낼 수 도 있다. 

 

Relation의 표기법은 몇 가지가 존재한다.

 

1. $(a,b) \in R$	ex) $(3, 5) \in \leq$
2. $a R b$	ex) $3 \leq 5$
3. $ a \rightarrow b$

 

이항관계의 종류

지금까지 알아본 relation 들은 모두 두 집합의 곱집합의 부분집합이었다.

하지만, 세 집합, 네 집합, $n$개의 집합의 곱집합의 부분집합도 relation이다.

 

우리가 앞으로 주로 다룰 relation은 두 집합의 곱집합의 부분집합이다.

이러한 relation을 이항관계라고 한다. 이항관계는 몇 가지 종류가 있다.

 

이항관계 $R \subseteq A \times A, A \neq \emptyset $에 대해 reflexive, symmetric, transitive는 무엇일지 알아보자.

Reflexive

$ \forall x \in A, (x,x) \in R$

즉, $A$의 모든 원소에 대해 자기 자신으로 가는 대응이 존재하는 관계이다. 

ex) $R = \left\{(1,1),(2,2),(1,2)\right\}$

 

Symmetric

If $(x,y) \in R$ then $(y,x) \in R$

즉, $A$의 어떤 두 원소에 대해 한 방향 대응이 존재하면 반대 방향 대응이 존재하는 관계이다. 

ex) $R = \left\{(1,2), (2,1), (3,4), (4,3), (5,5)\right\}$

 

Transitive

If $(x,y) \in R, (y,z) \in R$ then $(x,y) \in R$

한 문장으로 설명하긴 어렵지만, 예를 들자면 $3<4$이고 $4<5$일 때 $3<5$와 같은 식이 만족한다는 얘기이다.

ex) $R = \left\{(1,2), (2,3), (1,3)\right\}$

 

 

연습문제

자연수의 집합 $\mathbb{N}$에서 정의된 relation $\leq$는 reflexive인가?

모든 자연수 $n \in \mathbb{N}$에 대해 $n \leq n$ 이므로, $\leq$는 reflexive이다.

 

그렇다면 relation $\leq$는 symmetric인가?

반례 : $1 \leq 3$ 이지만 $3 \leq 1$ 이므로 symmetric이 아니다. 

 

그러면 relation $\leq$는 transitive인가?

직접 해보자.