집합론, 그 스무 번째 이야기 | Order Isomorphism과 Order Isomorphic

이 글에서는 Order Isomorphism과 Order Isomorphic에 대해 설명하고 이들의 성질을 소개하고 증명할 것이다.

 

함수 $f:A\rightarrow B$가 순서집합 $(A,\leq_A)$와 $(B,\leq_B)$ 사이의 전단사함수이면서 동시에 임의의 $x,y\in A$에 대해 $x\leq_A y\Leftrightarrow f(x)\leq_B f(y)$가 성립한다면, 함수 $f$를 $(A,\leq_A)$에서 $(B,\leq_B)$로 가는 Order Isomorphism이라고 하며, 두 순서집합 $(X,\leq_X)$와 $(Y,\leq_Y)$ 사이에 Order Isomorphism이 존재한다면 두 순서집합 $(X,\leq_X)$와 $(Y,\leq_Y)$가 Order Isomorphic하다고 한다.

 

Order Isomorphism의 성질을 서술하기에 앞서, Order Isomorphism의 여러 성질을 증명하기 위한 보조정리를 언급하도록 하겠다.

 

Lemma 1. 만약 $(W,\leq)$가 정렬순서집합이라면, 함수 $f:W\rightarrow W$가 $x\lneq y\Rightarrow f(x)\lneq f(y)$를 만족한다면 $\forall x\in W,\;x\leq f(x)$를 만족한다.

 

집합 $X = \{x\in W\;|\;f(x)\lneq x\}$를 잡자.

만약 $X\neq\emptyset$이라면 $X$는 최소원소 $z\in X$를 가진다.

$w=f(z)$라고 하자. 그러면 집합 $X$의 정의로부터 $w\lneq z$이다.

이때, 함수 $f$가 $x\lneq y\Rightarrow f(x)\lneq f(y)$를 만족하므로 $f(w)\lneq f(z)=w$이다.

이는 $z$가 $X$의 최소원소임에 모순되므로 귀류법에 의해 $X=\emptyset$이다.

$\blacksquare$

 

다음은 Order Isomorphism의 여러 성질이다.

 

Theorem 1. 정렬순서집합의 Order Automorphism은 항등함수 뿐이다. Theorem 2. 두 정렬순서집합 $(W_1,\leq_1)$과 $(W_2,\leq_2)$가 Order Isomorphic하면 $W_1$에서 $W_2$로 가는 Order Isomorphism은 유일하다. Theorem 3. 그 어떤 정렬순서집합도 자기자신의 Initial Segment와 Order Isomorphic하지 않다. Theorem 4. 만약 $(W_1,\leq_1)$와 $(W_2,\leq_2)$가 정렬순서집합이라면 다음 중 하나를 만족한다. 1) $W_1$와 $W_2$가 Order Isomorphic하다. 2) $W_1$와 Order Isomorphic한 $W_2$의 Initial Segment가 존재한다. 3) $W_2$와 Order Isomorphic한 $W_1$의 Initial Segment가 존재한다.

 

Theorem 1. 정렬순서집합의 Order Automorphism은 항등함수 뿐이다.

 

증명하기에 앞서, 용어 하나를 설명하도록 하겠다. Order Automorphism은 자기자신과의 Order Isomorphism이다.

Lemma 1에 의해 Order Automorphism $f$는 모든 $x$에 대해 $x\leq f(x)$를 만족한다.

또한, $f$가 Order Automorphism이면 $f^{-1}$ 역시 Order Automorphism이므로 $x\leq f^{-1}(x)$ 역시 성립한다.

이때, $f$는 순서관계를 보존하므로 $f(x)\leq f(f^{-1}(x))=x$가 성립한다.

모든 $x$에 대해 $x\leq f(x)\leq x$를 만족하므로 $x=f(x)$를 만족한다.

$\blacksquare$

 

Theorem 2. 두 정렬순서집합 $(W_1,\leq_1)$과 $(W_2,\leq_2)$가 Order Isomorphic하면 $W_1$에서 $W_2$로 가는 Order Isomorphism은 유일하다.

 

서로 다른 두 Order Isomorphism $f:W_1\rightarrow W_2$와 $g:W_1\rightarrow W_2$가 있다고 가정하자.

그러면 $g^{-1}:W_2\rightarrow W_1$ 역시 자명하게 Order Isomorphism이다.

따라서 $g^{-1}\circ f:W_1\rightarrow W_1$는 Order Automorphism이 된다.

같은 이유로 $f\circ g^{-1}:W_2\rightarrow W_2$ 역시 Order Automorphism이 된다.

이때, Theorem 1에 의해 $f\circ g^{-1}$과 $g^{-1}\circ f$ 둘 모두 항등함수이다.

따라서 $f^{-1} = g^{-1}$이 되고, 이로부터 $f=g$를 얻을 수 있다.

이는 $f$와 $g$가 서로 다르다는 가정에 모순되므로 귀류법에 의해 Order Isomorphism은 유일하다.

$\blacksquare$

 

Theorem 3. 그 어떤 정렬순서집합도 자기자신의 Initial Segment와 Order Isomorphic하지 않다.

 

증명하기에 앞서, 용어 하나를 설명하도록 하겠다.

만약 $(W,\leq)$가 정렬순서집합이고 $u\in W$일 때, 집합 $\{x\in W\;|\;x\lneq u\}$를 $W$의 $u$에 의한 Initial Segment라고 한다.

만약 Order Isomorphism $f$에 대해 $\text{ran}f=\{x\;|\;x\lneq u\}$라면, $f(u)\lneq u$이다.

하지만, 이는 Lemma 1에 모순된다. 따라서 귀류법에 의해 그러한 Order Isomorphism은 존재하지 않는다.

$\blacksquare$

 

Theorem 4. 만약 $(W_1,\leq_1)$와 $(W_2,\leq_2)$가 정렬순서집합이라면 다음 중 하나를 만족한다.
1) $W_1$와 $W_2$가 Order Isomorphic하다.
2) $W_1$와 Order Isomorphic한 $W_2$의 Initial Segment가 존재한다.
3) $W_2$와 Order Isomorphic한 $W_1$의 Initial Segment가 존재한다.

 

$u\in W_i,\;(i=1,2)$에 대해 $W_i$의 $u$에 의한 Initial Segment를 $W_i(u)$로 표현하자.

그리고 $f=\{(x,y)\in W_1\times W_2\;|\;W_1(x)\text{와 }W_2(y)\text{가 Order Isomorphic}\}$를 생각하자.

그러면 Theorem 3에 의해 $f$는 단사함수가 된다.

$W_1(x)$에서 $W_2(y)$로 가는 Order Isomorphism $h$를 생각하자.

그러면 $x'\lneq_1x$일 때 $W_1(x')$와 $W_2(h(x'))$가 Order Isomorphic하다.

따라서 $f$는 순서관계를 보존한다는 것을 알 수 있다.

만약 $\text{dom}f = W_1$과 $\text{ran}f = W_2$를 동시에 만족한다면 1) 조건을 만족한다.

만약 $y_1\lneq_2 y_2$이면서 $y_2\in\text{ran}f$라면 $y_1\in\text{ran}f$임은 자명하다.

따라서 만약 $\text{ran}f\neq W_2$이고 $W_2\setminus\text{ran}f$의 최소원소가 $y_0$라면 $\text{ran}f=W_2(y_0)$이다.

이때 $\text{dom}f\neq W_1$이라면 $W_1\setminus\text{dom}f$의 최소원소 $x_0$에 대해 $(x_0,y_0)\in f$가 되어 모순이 발생한다.

따라서 $\text{dom}f=W_1$이다. 이때에는 2) 조건을 만족한다.

비슷하게, $\text{dom}f\neq W_1$이라면 $\text{ran}f=W_2$이다. 이때에는 3) 조건을 만족한다.

$\blacksquare$