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

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

 

함수 $f:A\to B$가 순서집합 $(A,{\le }_A)$와 $(B,{\le }_B)$ 사이의 전단사함수이면서 동시에 임의의 $x,y\in A$에 대해 $x{\le }_{A}y\iff f(x){\le }_{B}f(y)$가 성립한다면, 함수 $f$를 $(A,{\le }_A)$에서 $(B,{\le }_B)$로 가는 Order Isomorphism이라고 하며, 두 순서집합 $(X,{\le }_X)$와 $(Y,{\le }_Y)$ 사이에 Order Isomorphism이 존재한다면 두 순서집합 $(X,{\le }_X)$와 $(Y,{\le }_Y)$가 Order Isomorphic하다고 한다.

 

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

 

Lemma 1. 만약 $(W,\le )$가 정렬순서집합이라면, 함수 $f:W\to W$가 $x⪇y\Rightarrow f(x)⪇f(y)$를 만족한다면 $\mathrm{\forall }x\in W,x\le f(x)$를 만족한다.

 

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

만약 $X\ne \mathrm{\varnothing }$이라면 $X$는 최소원소 $z\in X$를 가진다.

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

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

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

$◼$

 

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

 

Theorem 1. 정렬순서집합의 Order Automorphism은 항등함수 뿐이다. Theorem 2. 두 정렬순서집합 $(W_1,{\le }_1)$과 $(W_2,{\le }_2)$가 Order Isomorphic하면 $W_1$에서 $W_2$로 가는 Order Isomorphism은 유일하다. Theorem 3. 그 어떤 정렬순서집합도 자기자신의 Initial Segment와 Order Isomorphic하지 않다. Theorem 4. 만약 $(W_1,{\le }_1)$와 $(W_2,{\le }_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\le f(x)$를 만족한다.

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

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

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

$◼$

 

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

 

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

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

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

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

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

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

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

$◼$

 

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

 

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

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

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

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

$◼$

 

Theorem 4. 만약 $(W_1,{\le }_1)$와 $(W_2,{\le }_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^{\prime }{⪇}_{1}x$일 때 $W_1(x^{\prime })$와 $W_2(h(x^{\prime }))$가 Order Isomorphic하다.

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

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

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

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

이때 $\text{dom}f\ne 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\ne W_1$이라면 $\text{ran}f=W_2$이다. 이때에는 3) 조건을 만족한다.

$◼$