원순서관계의 restriction
Preorder relation $(R,A,A)$을 생각하고, 임의의 부분집합 $A’\subseteq A$가 주어졌다 하자. 그럼 $R\cap (A’\times A’)$로 정의된 관계는 $A’$ 위에 preorder relation을 정의한다.
명제 1 위의 집합 $R\cap (A’\times A’)$는 $A’$ 위에 정의된 preorder relation이다.
증명
우선 임의의 $x\in A’$에 대하여, $x$는 $A$의 원소이기도 하므로 $(x,x)\in R$이다. 또, $(x,x)\in A’\times A’$이므로 $(x,x)\in R\cap(A’\times A’)$이다.
이제 $(x,y),(y,z)\in R\cap (A’\times A’)$이라 가정하자. 그럼 $x,y,z\in A’$이고 $(x,y),(y,z)\in R$이다. $R$은 transitive하므로 $(x,z)\in R$이고, $x,z\in A’$로부터 $(x,z)\in R\cap(A’\times A’)$임을 안다.
직관적으로 생각하여 이 관계는 $\leq_R$을 $A’$로 제한한 것과 같다. 약간의 표기법의 남용을 통해 이 관계 또한 $\leq_R$로 적는다.
원순서관계의 곱
임의의 index set $I$에 대하여, preorder relation들 $(R_i,A_i,A_i)$이 주어졌다 하자. 그럼 곱집합 $\prod_{i\in I} A_i$의 임의의 두 원소 $x=(x_i)_{i\in I}$와 $y=(y_i)_{i\in I}$에 대하여 다음과 같은 관계
\[x\leq y\iff \forall i((i\in I)\implies(x_i\leq_{\tiny R_i} y_i))\]를 생각할 수 있다.
명제 2 위의 관계 $\leq$는 $\prod A_i$ 위에 정의된 preorder relation이다.
증명
임의의 $(x_i)\in \prod A_i$에 대하여, $x_i\leq_{\tiny R_i} x_i$가 모든 $i\in I$에 대해 성립하므로 $(x_i)\leq (x_i)$이다.
이제 $(x_i)\leq (y_i)$이고 $(y_i)\leq (z_i)$라 하자. 그럼 모든 $i\in I$에 대하여,
\[x_i\leq y_i\leq z_i\implies x_i\leq z_i\]가 성립하므로 $(x_i)\leq (z_i)$이다.
예시 3 임의의 집합 $A$에서 $B$로의 함수 $f$는 index set을 $A$로 하여, 각각의 $a\in A$마다 $B$를 곱한 집합 $B^A=\prod_{a\in A}B$의 원소로 볼 수 있다.
이제 집합 $B$ 위에 preorder relation $R$이 정의되었다 하자. 앞선 명제 2에 의하여 preorder relation들의 곱은 함수들의 집합 $B^A$ 위에 preorder relation을 정의한다. 이를 $\leq$라 적기로 하면, $f\leq g$는 임의의 $x\in A$에 대하여 $f(x)\leq_{\tiny R} g(x)$임을 의미한다.
앞선 두 절의 내용은 preorder relation을 모두 order relation으로 바꾸어도 성립한다. 즉 원래 주어진 preorder relation이 antisymmetry를 가져서 order relation이 되었다면, 명제 1과 명제 2에서 얻어지는 preorder relation 또한 antisymmetry를 만족하고 따라서 order relation이 된다.
이 경우 strict order를 살펴볼 때에는 약간의 주의가 필요하다. 가령 집합 $B$에 order relation $R$이 주어졌다 하고, $R$에 의해 정의되는 strict order를 $S$라 하자. 예시 3을 통해 만들어진 order relation $\leq$로부터 만들어지는 strict order $<$는 다음의 관계
\[f< g\iff\forall x\bigl((x\in A)\implies (f(x)<_{\tiny R}g(x))\bigr)\]로 정의되는 관계와는
단조함수
정의 4 Preorder $R,R’$가 주어진 집합 $A$와 $A’$를 생각하자. 함수 $f:A\rightarrow A’$가 증가함수increasing function이라는 것은 $x\leq_{\tiny R} y\implies f(x)\leq_{\tiny R’} f(y)$가 항상 성립하는 것이다. 만약 $x\leq_{\tiny R}y\implies f(y)\leq_{\tiny R’} f(x)$가 항상 성립한다면, 이 함수는 감소함수decreasing function라 불린다. 증가함수와 감소함수를 통틀어 단조함수monotone function라 부른다.
참고 임의의 상수함수는 증가함수인 동시에 감소함수이다. 그러나 이 역이 성립하는 것은 아니다. $A$가 하나 이상의 원소를 갖는 집합이라 하고. 이 위에 정의된 order relation $=$를 생각하자. 그럼 $A$에서 $A$로의 항등함수는 증가함수인 동시에 감소함수지만 상수함수는 아니다.
그리고, $\leq$를 $<$로 바꾸면 다음 정의를 얻는다.
정의 5 Strict order $S,S’$가 주어진 집합 $A$와 $A’$를 생각하자. 함수 $f:A\rightarrow A’$가 순증가함수strictly increasing function라는 것은 $x <_{\tiny S} y\implies f(x) <_{\tiny S’} f(y)$가 항상 참인 것이고, 순감소함수strictly decreasing function라는 것은 $x <_{\tiny S} y\implies f(y)<_{\tiny S’}f(x)$가 항상 성립하는 것이다. 순증가함수, 순감소함수들을 통틀어 순단조함수strictly monotone function라 한다.
참고 정의에 의해 단조인 단사함수는 항상 순단조함수다. 그러나 이 역 또한 항상 성립하는 것은 아니다. 예컨대, $\mathbb{N}$ 위에 strict order $\prec$을 다음의 식
\[m\prec n\iff ((m-n\text{ is even}) \wedge (m<n))\]으로 정의하고, 이 집합을 $A$라 하자. 즉, $A$에서는 짝수는 짝수끼리, 홀수는 홀수끼리 크기 비교가 가능하지만 짝수와 홀수의 크기 비교는 불가능하다. 또, 자연수 집합 $\mathbb{N}$에 일상적인 strict order $<$를 부여한 ordered set을 $B$라 하자. 그럼 $A$에서 $B$로의 함수 $m\mapsto \lfloor m/2\rfloor$은 순증가지만 단사함수는 아니다.
명제 6 $A$, $A’$가 ordered set이고 $u:A\rightarrow A’$, $v:A’\rightarrow A$가 감소함수이며, $v(u(x))\geq x$와 $u(v(x’))\geq x’$이 모든 $x\in A$, $x’\in A’$에 대해 성립한다고 하자. 그럼 $u\circ v\circ u=u$ 이고 $v\circ u\circ v=v$이다.
증명
주어진 가정과 $u$가 감소함수라는 것에서 자명하다. 즉, $u$는 감소함수이므로, $v(u(x))\geq x$에서 $u(v(u(x)))\leq u(x)$가 모든 $x$에 대해 성립하지만, 가정의 두 번째 부분에서 $u(v(u(x)))\geq u(x)$이 성립한다.
참고문헌
[Bou] N. Bourbaki, Theory of Sets. Elements of mathematics. Springer Berlin-Heidelberg, 2013.
댓글남기기