이항관계

이항관계

우선 정의부터 시작한다. 다음 정의는 별다른 것은 아니고, §순서쌍에서 순서쌍을 도입해야 하는 당위성을 설명하며 나왔던 순서쌍들의 집합에 이름을 준 것에 불과하다.

정의 1 집합 $R$이 이항관계_{binary relation}라는 것은 $R$의 모든 원소가 순서쌍이라는 것이다.¹

따라서, 다음과 같이 집합들 사이에 정의된 등호 ($=$)는 더 이상 이항관계라고 할 수 없다.

예시 2 집합들 사이에서 $=$가 이항관계라면, 이를 나타내는 집합

\[E=\{(A,A)\mid\text{$A$ any set}\}\]

이 존재한다. 즉, $E$는 전체집합 두 개의 곱이어야 한다.

전체집합 두 개의 곱이 존재한다면, 다음 명제에 의해 전체집합 또한 존재해야 하고 이는 §ZFC 공리계, ⁋예시 4에 모순이므로 모든 집합들 사이에 정의된 $=$는 이항관계가 될 수 없다.

명제 3 $R$이 이항관계라 하자. 그럼 유일한 두 개의 집합 $A$, $B$가 존재하여,

• $x\in A$인 것과 어떤 $y$가 존재하여 $(x,y)\in R$인 것이 동치이고,
• $y\in B$인 것과 어떤 $x$가 존재하여 $(x,y)\in R$인 것이 동치이다.

증명

$R$이 이항관계라 하고 $\bigcup(\bigcup R)$를 생각하자. 계산을 통해 $(x,y)\in R\implies x,y\in\bigcup(\bigcup R))$임을 알 수 있다. $P$를

$P(t)$: 어떠한 $s$가 존재하여 $(s,t)\in R$이다.

로 정의하면, 다음의 집합

\[A=\left\{x\mid\left(x\in\bigcup\left(\bigcup R\right)\right)\wedge P(x)\right\}\]

를 얻는다. 따라서 첫 번째 주장이 성립하며, 이와 유사하게 성질 $Q$를

$Q(s)$: 어떠한 $t$가 존재하여 $(s,t)\in R$이다.

로 정의하면 집합 $B$를 얻는다.

§순서쌍, ⁋정의 7과 마찬가지로 이들을 각각 첫 번째와 두 번째 projection이라 부르고, $\pr_1R$과 $\pr_2R$로 쓴다.

간혹 이항관계의 첫 번째 성분과 두 번째 성분이 어느 집합에 속하는지를 명확하게 해야 할 때가 있다. 이를 위해 주어진 두 집합 $A,B$와 $\pr_1R\subseteq A$, $\pr_2R\subseteq B$를 만족하는 이항관계 $R$을 triple $(R,A,B)$와 같이 생각하기도 한다. 이 경우, $A$를 $R$의 source, $B$를 $R$의 target이라 부르며, 이런 상황에서는 같은 집합 $R$에 대해서도 $(R,A,B)$와 $(R,A’,B’)$를 다른 것으로 생각한다.

참고 위의 조건 $\pr_1R\subseteq A$, $\pr_2R\subseteq B$를 만족하는 이항관계 $R$이 주어졌다 하자. §순서쌍, ⁋명제 9에 의하여,

\[R\subseteq \pr_1 R\times\pr_2R\subseteq A\times B\]

이므로 데카르트 곱 $A\times B$는 $A$를 source로, $B$를 target으로 갖는 이항관계 중 가장 큰 것이라 할 수 있다.

이항관계의 정의역과 상

정의 5 이항관계 $(R,A,B)$와 부분집합 $A’\subseteq A$를 생각하자. 그럼 $R$에 의해 $A'$의 원소와 관계되는 모든 원소들의 집합을 $R$에 의한 $A’$의 image_상이라 부르고 , $R(A’)$로 표기한다.

위의 정의를 식으로 풀어쓰면

\[R(A')=\bigcup_{x\in A'} \{y\in B\mid(x,y)\in R\}\]

이다. 엄밀히 이야기하자면 우변의 집합 $\{y\in B\mid(x,y)\in R\}$은 이항관계 $R$의 target $B$가 주어지지 않았다면

\[\{y\mid(x,y)\in R\}\]

과 같은 형태가 되며, comprehension schema에 의하여 존재성이 보장되는 위의 집합과 달리 이 집합은 존재하지 않을 수도 있다.

이와 같은 문제는 집합론을 공부하며 항상 주의해야 한다. 다만 우리는 집합론을 공부하는 게 목적이 아니라, 다른 곳에서 유용하게 사용할 명제들을 증명하는 것이 목적이므로 앞으로 이 정도의 사소한 서술상의 문제는 별 생각없이 넘어가기로 한다.

명제 6 $R$이 이항관계라 하고, 임의의 집합 $A$와 그 부분집합 $X$를 생각하자. 그럼 $R(X)\subseteq R(A)$가 성립한다.

증명

$y\in R(X)$라 하자. 그럼 어떤 $x\in X$가 존재하여 $(x,y)\in R(X)$이다. 이제 $X\subseteq A$로부터 $x\in A$이므로, $y\in R(A)$이다.

위의 명제에 의하여 임의의 $A$에 대해

\[R(A)=\pr_2\{z\in R\mid\text{$\pr_1z\in A$}\}\subset\pr_2R\]

이고, 따라서 $R(A)\subset\pr_2R$가 성립한다. 특히 $A=\emptyset$이라면 $R(A)=\emptyset$이며, 더 일반적으로 만일 $A\cap\pr_1R=\emptyset$이라면 $R(A)=\emptyset$이다.

만일 어떤 $x$에 대해 $A=\{x\}$라면 $R(A)$를 마치 $x$에서의 $R$의 함숫값처럼 생각할 수 있다.

정의 7 이항관계 $R$에 대하여, 집합 $R(\{x\})$를 $x$에서의 $R$의 section_단면이라 부른다.

이 집합을 마치 $x$에서의 $R$의 함숫값처럼 $R(x)$로 적기도 한다. 이 함숫값은 유일하지 않으며, 따라서 $R(x)$ 또한 여러 개의 원소를 가질 수 있다.

---

참고문헌

[HJJ] K. Hrbacek, T.J. Jeck, and T. Jech. Introduction to Set Theory. Lecture Notes in Pure and Applied Mathematics. M. Dekker, 1978.
[Bou] N. Bourbaki, Theory of Sets. Elements of mathematics. Springer Berlin-Heidelberg, 2013.

---

1. [Bou]에서는 이러한 집합을 그래프라 부르고, 이항관계 중 그래프를 갖는 것과 갖지 않는 것을 구분하여 생각한다. 이는 그렇게 흔한 정의는 아니므로, 우리는 [HJJ]를 따라 위의 정의를 그대로 사용한다. 이 경우 관계라는 단어의 정의가 애매해지긴 하는데, 이는 따로 정의하지 않고 넘어간다. ↩