순서관계의 정의

순서관계

정의 1 이항관계 $R$이 anti-symmetric_반대칭적이라는 것은

$x\mathrel{R}y$이고 $y\mathrel{R}x$이면 $x=y$

가 항상 성립하는 것이다.

그럼 순서관계는 다음과 같이 정의된다.

정의 2 이항관계 $(R,A,A)$가 order relation_순서관계이라는 것은 $R$이 reflexive하며, transitive, anti-symmetric한 것이다.

이 경우, 우리는 $A$가 $R$에 의해 순서가 부여되었다고 하고, 종종 $A$를 ordered set_순서집합이라고 부른다. 또, 동치관계 때와 비슷하게 $x\mathrel{R}y$를 $x\leq_{\tiny R}y$로 적는다.

예시 3 이항관계 $x=y$는 order relation이다. 관계 $x\subseteq y$ 또한 order relation이다. (§순서쌍, ⁋명제 2와 §순서쌍, ⁋명제 3)

Ordered set은 $ \leq $라는 관계가 추가적으로 정의된 집합이므로, 이들 사이의 함수를 생각할 때는 $ \leq $ 또한 보존하는 함수를 주로 생각하게 된다. 특별히 다음을 정의한다.

정의 4 만일 두 order relation $(R, A, A)$과 $(R’, A’,A’)$에 대해 어떠한 전단사함수 $f$가 존재하여 $x\leq_{\tiny R}y$와 $f(x)\leq_{\tiny R’}f(y)$가 동치라면 $f$를 order isomorphism이라 부른다.

앞으로 ordered set들 사이에서 isomorphism이라 하면 항상 order isomorphism을 뜻하는 것으로 이해한다.

§동치관계, ⁋명제 3과 비슷한 것을 순서관계에 대해서도 할 수 있다.

명제 5 이항관계 $(R,A,A)$가 order relation인 것은 다음의 두 조건과 동치이다.

\[R\circ R=R,\qquad R\cap R^{-1}=\Delta_A\]

증명

첫 번째 조건이 transitivity와 동등한 것은 §동치관계, ⁋명제 3의 증명에서 이미 살펴보았다. 두 번째 조건은 reflexive와 antisymmetry를 섞어둔 것이라는 것도 쉽게 보일 수 있다.

원순서관계

우선 다음 예시를 살펴보자.

예시 6 함수 $f:A\rightarrow B$를 생각하고, $B$ 위에 order relation $\leq$가 정의되었다고 하자. 그럼 우리는 함수로부터 동치관계를 유도하듯, $A$ 위에 다음과 같이 정의된 관계 $\preceq$를 정의할 수 있다. (§동치관계의 예시들, ⁋정의 2)

\[x\preceq y\iff f(x)\leq f(y)\]

정의로부터 $\preceq$는 reflexive하고 transitive하다. 하지만 일반적으로 $f$가 단사가 아닌 한 $\preceq$는 antisymmetry을 만족하지 않는다.

따라서 antisymmetry 조건을 빼서 다음과 같이 정의한다.

정의 7 Reflexive하고 transitive한 관계 $R$을 preorder relation_{원순서관계}라 부른다.

$R$이 preorder relation이라면 이를 $\preceq_{\tiny R}$과 같이 적기도 하지만, 많은 경우 preorder는 order relation과 비슷한 성질을 공유하기 때문에 order relation과 동일한 기호 $\leq_{\tiny R}$를 사용하기도 한다. 우리도 특별한 경우가 아닌 한 $\leq_{\tiny R}$를 사용한다.

Preorder relation의 성질을 알기 위해 우리는 order relation의 성질이지만 preorder의 성질은 아닌 antisymmetry를 좀 더 살펴봐야 한다. 만일 관계 $R$이 order relation이었다면, antisymmetry는 $(x\leq_{\tiny R}y)\wedge(y\leq_{\tiny R}x)\implies x=y$를 뜻한다. Preorder에 대해서는 이것이 성립하지 않는다는 것을 살펴보았지만, 이 경우는 다음 명제에 의해 일반화된 등호, 즉 동치관계가 똑같은 성질을 준다.

명제 8 $R$이 preorder relation이라 하자. 그럼 관계 $x\leq_{\tiny R}y$이고 $y\leq_{\tiny R}x$은 동치관계다.

증명

위의 관계를 $S$라 하자. 우리는 $S$가 reflexive, symmetric, transitive함을 보여야 한다. 우선 이 관계가 reflexive함은 자명하다. $R$이 preorder이므로, 임의의 $x$에 대해 $x\mathrel{R}x$가 항상 성립하기 때문이다. 한편, 임의의 $x$, $y$에 대하여 $x\mathrel{S}y$라 하자. 그럼

\[x\mathrel{S}y\iff(x\leq_{\tiny R}y)\wedge(y\leq_{\tiny R}x)\iff(y\leq_{\tiny R}x)\wedge(x\leq_{\tiny R}y)\iff y\mathrel{S}x\]

이므로 $S$는 symmetric하다. 마지막으로 만일 $x\mathrel{S}y$, $y\mathrel{S}z$라면

\[\begin{aligned} (x\mathrel{S}y)\wedge(y\mathrel{S}z)&\iff((x\leq_{\tiny R}y)\wedge(y\leq_{\tiny R}x))\wedge((y\leq_{\tiny R}z)\wedge(z\leq_{\tiny R}y))\\ &\iff(x\leq_{\tiny R}y)\wedge(y\leq_{\tiny R}x)\wedge(y\leq_{\tiny R}z)\wedge(z\leq_{\tiny R}y)\\ &\iff(x\leq_{\tiny R}y)\wedge(y\leq_{\tiny R}z)\wedge(z\leq_{\tiny R}y)\wedge(y\leq_{\tiny R}x)\\ &\iff((x\leq_{\tiny R}y)\wedge(y\leq_{\tiny R}z))\wedge((z\leq_{\tiny R}y)\wedge(y\leq_{\tiny R}x))\\ &\iff(x\leq_{\tiny R}z)\wedge(z\leq_{\tiny R}x)\\ &\iff x\mathrel{S}z \end{aligned}\]

이므로 $S$는 transitive하고, 따라서 $S$는 동치관계가 된다.

Strict order

주어진 order relation $\leq$에 대하여, $ < $을 $x\leq y$이고 $x\neq y$로 정의된 관계라 하자. 이 때 $ < $는 antisymmetry를 만족하지 않으므로 order relation이 될 수는 없고, 또 reflexive하지도 않으므로 preorder 또한 될 수 없다. 대신 다음을 정의하자.

정의 9 관계 $R$이 asymmetric_비대칭적이라는 것은 $x\mathrel{R}y$이면 $y\not \mathrel{R}x$인 것이다. Asymmetric, transitive relation을 strict order라 부른다.

Strict order를 표현하기 위해서 우리는 $<_{\tiny S}$를 사용한다. 그럼 다음이 성립한다.

명제 10 $R$이 order relation이라 하자. 그럼 새로운 관계 $x\leq_{\tiny R}y$이고 $x\neq y$는 strict order이다.

반대로 $S$가 strict order라 하자. 그럼 새로운 관계 $x<_{\tiny S}y$이거나 $x=y$는 order relation이다.

증명

우선 $R$이 order relation이라 하고, 새로운 relation $S$를 $x\leq_{\tiny R}y$이고 $x\neq y$으로 정의하자. Asymmetry를 보이기 위해 우리는 $x\mathrel{S}y$와 $y\mathrel{S}x$가 동시에 성립할 수 없음을 보여야 한다. $(x\mathrel{S}y)\wedge(y\mathrel{S}x)$를 풀어 쓰면 다음과 같다.

\[((x\leq_{\tiny R}y)\wedge(x\neq y))\wedge((y\leq_{\tiny R}x)\wedge(y\neq x))\]

그런데 이는 다음과 같이 쓸 수 있다.

\[((x\leq_{\tiny R}y)\wedge(y\leq_{\tiny R}x))\wedge(x\neq y)\]

이는 $R$의 antisymmetry에 의하여 $(x=y)\wedge(x\neq y)$이고, 이는 항상 거짓이므로 $x\mathrel{S} y$이면 $y\not\mathrel{S}x$이다.

반대로 $S$가 strict order라 하고, 새로운 relation $R$을 $x<_{\tiny S}y$이거나 $x=y$로 정의하자. 우선 $x=x$이므로, 뒤쪽 조건에 걸려 $x\mathrel{R}x$이다. Antisymmetry를 보이기 위해, $x\mathrel{R}y$와 $y\mathrel{R}x$가 성립한다고 가정하자. 그럼

\[\begin{aligned} (x\mathrel{R}y)\wedge(y\mathrel{R}x)&\iff((x<_{\tiny S}y)\vee(x=y))\wedge((y<_{\tiny S}x)\vee(y=x))\\ &\iff ((x<_{\tiny S}y)\wedge(y<_{\tiny S}x))\vee(x=y) \end{aligned}\]

이다. Asymmetry에 의하여 $(x<_{\tiny S}y)\wedge(y<_{\tiny S}x)$는 불가능하므로, $(x\mathrel{R}y)\wedge(y\mathrel{R}x)$가 성립한다면 반드시 $x=y$가 성립한다. 마지막으로 transitivity을 보이기 위해 $x\mathrel{R}y$이고 $y\mathrel{R}z$라 하자. 그럼

\[\begin{aligned} (x\mathrel{R}y)\wedge(y\mathrel{R}z)&\iff ((x<_{\tiny S}y)\vee(x=y))\wedge((y<_{\tiny S}z)\vee(y=z))\\ &\iff ((x<_{\tiny S}y)\wedge((y<_{\tiny S}z)\vee(y=z)))\vee((x=y)\wedge((y<_{\tiny S}z)\vee(y=z)))\\ &\iff ((x<_{\tiny S}y)\wedge(y<_{\tiny S}z))\vee((x<_{\tiny S}y)\wedge(y=z))\\ &\phantom{asdfghjkl}\vee((x=y)\wedge (y<_{\tiny S}z))\vee((x=y)\wedge(y=z))\\ &\implies (x<_{\tiny S}z)\vee(x<_{\tiny S}z)\vee(x<_{\tiny S}z)\vee(x=y=z)\\ &\iff x\mathrel{R}z \end{aligned}\]

이므로 $R$은 transitive하다. 따라서 $R$은 order relation이 된다.

앞으로 order relation $R$에 의해 얻어지는 strict order를 $<_{\tiny R}$, 그리고 strict order $S$에 의해 얻어지는 order relation을 $\leq_{\tiny S}$으로 적기로 한다.

참고 일반적으로 $x\not\leq y$라 하여 $x>y$인 것은 아니다. $S=\left\{a,b\right\}$라 하고, $\mathcal{P}(S)$ 위에 정의된 relation $\leq$를 부분집합들 간의 포함관계로 정의하자. 그럼 이는 자명하게 order relation이 된다. 이 때, $\left\{a\right\}\not\leq \left\{b\right\}$이지만 $\left\{a\right\}>\left\{b\right\}$ 또한 성립하지 않는다.

---

참고문헌

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

---