원순서관계의 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.
댓글남기기