순서

순서, 전순서

정의 1(순서의 공리). 공집합이 아닌 집합 $A$의 이항관계 $\leq$가 다음 조건을 만족한다면, $\leq$는 $A$의 순서order이고, $(A,\leq)$는 순서집합이라고 한다.

  1. 반사법칙 — 임의의 $a\in A$에 대하여 $a\leq a$.
  2. 반대칭법칙 — 임의의 $a,b\in A$에 대하여 $a\leq b$인 동시에 $b\leq a$이면, $a=b$이다.
  3. 추이법칙 — 임의의 $a,b,c\in A$에 대하여 $a\leq b$인 동시에 $b\leq c$이면, $a\leq c$이다. —

예 1. $\SetN$, $\SetZ$, $\SetQ$, $\SetR$ 상에 주어진 통상적인 순서는 순서의 공리를 만족한다. 앞으로도 별도의 언급 없이 순서집합으로서 $\SetN$, $\SetZ$, $\SetQ$, $\SetR$를 사용한다면, 통상적인 순서를 의미하는 것으로 한다. —

예 2. $\SetZ_{>0}$ 상에서, $b\in\SetZ_{>0}$가 $a\in\SetZ_{>0}$로 나누어 떨어질 때, $a\mid b$라고 하면, “$\mid$”는 순서이다. —

예 3. $\mathfrak M$을 임의의 집합계라고 할 때, $\mathfrak M$ 상의 이항관계인 포함관계 “$\subset$”은 순서의 공리를 만족한다. —

. 순서를 나타내는 이항관계의 기호로는 어떤 것을 사용해도 상관없지만, $\leq$는 그 중에서도 많이 사용되는 기호 중 하나이다. 앞으로는 별도의 언급이 없는 한 기호 $\leq$는 정의 1의 공리를 만족하는 순서관계를 나타내는 것으로 한다. 또한, 기호 $\leq$를 사용할 때에는, 기호 $\geq$, $<$, $>$를 동시에 도입하여:

  • “$a\leq b$”와 “$b\geq a$”는 같은 의미
  • “$a\leq b$인 동시에 $a\neq b$”와 “$a<b$”, “$b>a$”는 같은 의미

가 되도록 한다1. —

정의 2. 순서집합 $(A,\leq)$가 주어질 때, 임의의 $a,b\in A$에 대하여 $a\leq b$나 $a\geq b$ 중 적어도 하나가 성립한다면2, $\leq$는 $A$의 전순서total order이고, $(A,\leq)$는 전순서집합이라고 한다. —

예 4. 예 1에서의 순서는 전순서이다. 하지만 예 2와 예 3의 순서는 전순서이지 않다. —

최대, 최소, 극대, 극소

정의 3(최대, 최소). $(A,\leq)$를 순서집합이라고 하자. $a\in A$이고, 임의의 $x\in A$에 대하여 $x\leq a$가 성립한다면, $a$는 $A$의 최대greatest 원소라고 한다. 또한, $b\in A$이고, 임의의 $x\in A$에 대하여 $b\leq x$가 성립한다면, $b$는 $A$의 최소least 원소라고 한다. —

.

  • 당연하지만, 모든 순서집합에 최대 혹은 최소인 원소가 존재하지는 않는다. $\SetN$에는 최소 원소 $0$가 존재하지만, 최대 원소는 존재하지 않는다. $\SetZ$, $\SetQ$, $\SetR$에는 최소 원소와 최대 원소가 모두 존재하지 않는다.
  • 만약 $A$의 최대 원소가 존재한다면, 이는 유일하다. 실제로 $a,a’\in A$가 동시에 $A$의 최대 원소라고 한다면, 정의로부터 $a\leq a’$인 동시에 $a’\leq a$이므로 $a=a’$이다. 마찬가지로 최소 원소가 존재한다면, 이는 유일하다. 이 사실에 따라, $A$의 최대 원소 혹은 최소 원소가 존재한다면, 각각을 $\max A$와 $\min A$로 쓰기로 한다. —

정의 4(극대, 극소). $(A,\leq)$를 순서집합이라고 하자. $a\in A$이고, $a<x$인 $x\in A$가 존재하지 않는다면, $a$는 $A$의 극대maximal 원소라고 한다. 또한, $b\in A$이고, 임의의 $x\in A$에 대하여 $x<b$인 $x\in A$가 존재하지 않는다면, $b$는 $A$의 극소minimal 원소라고 한다. —

명제 1. $(A,\leq)$를 순서집합이라고 하자. $\max A$가 존재한다면, 이는 $A$의 유일한 극대 원소이다. 마찬가지로, $\min A$가 존재한다면, 이는 $A$의 유일한 극소 원소이다. —

증명. $a=\max A$라고 하자. 정의로부터 $a$가 $A$의 극대 원소인 것은 분명하다. 또한, $a\neq a’$인 $a’\in A$에 대하여 $a’\leq a$가 성립, $a'<a$이므로, $a’$는 극대 원소일 수 없다. 따라서 $a$는 $A$의 유일한 극대 원소이다. 최소 원소에 대해서도 마찬가지. $\square$

.

  • 최대/최소와 마찬가지로, 극대/극소인 원소가 항상 존재하리라는 보장은 없다.
  • 명제 1에서 보인 것처럼 최대/최소인 원소가 존재한다면 이는 항상 유일한 극대/극소 원소가 되지만, 최대/최소인 원소가 존재하지 않아도 극대/극소인 원소가 존재할 수 있다. 이 경우, 극대/극소인 원소는 복수 존재할 수 있다.
    • 예를 들어, 예 2의 순서를 $\SetZ_{>1}$에 적용하면, 소수인 원소는 극소 원소가 되며, 이는 무수히 존재한다는 것을 알 수 있다.
  • 전순서집합에서는 최대/최소인 것과 극대/극소인 것은 서로 동치이다. —

상계, 하계, 상한, 하한

정의 5(상계, 하계, 유계). $(A,\leq)$를 순서집합, $M$을 $M\neq\emptyset$인 $A$의 부분집합이라고 하자.

  • $a\in A$이고, 임의의 $x\in M$에 대하여 $x\leq a$가 성립한다면, $a$는 $M$의 상계upper bound라고 하며, 상계가 존재하는 $A$의 부분집합을 위로 유계bounded from above인 $A$의 부분집합이라고 한다.
  • 마찬가지로, $b\in A$이고, 임의의 $x\in M$에 대하여 $b\leq x$가 성립한다면, $b$는 $M$의 하계lower bound라고 하며, 하계가 존재하는 $A$의 부분집합을 아래로 유계bounded from below인 $A$의 부분집합이라고 한다.
  • 위와 아래로 동시에 유계인 $A$의 부분집합을 $A$의 유계bounded인 부분집합이라고 한다. —

당연하지만, 부분집합 $M$을 순서집합으로 볼 때, $\max M$이 존재한다면, $M$은 위로 유계이다. 하지만, $M$이 위로 유계인 순서집합이라고 해도 그 상계가 $M$에 속하지 않을 수도 있으므로, 이 경우 $\max M$이 존재하리라는 보장은 없다.

순서집합 $(A,\leq)$의 부분집합 $M$에 대하여, $M$의 상계 전체의 집합을 $M^*$, 하계 전체의 집합을 $M_*$으로 나타낸다면, $M$이 위로 유계인 것은 $M^*\neq\emptyset$인 것과 동치이다. 마찬가지로, $M$이 아래로 유계인 것은 $M_*\neq\emptyset$과 동치.

정의 6(상한, 하한). $(A,\leq)$를 순서집합, $M$을 $M\neq\emptyset$인 $A$의 부분집합이라고 하자. $M$의 상계 전체의 집합 $M^*$에 대하여, $\min M^*$이 존재한다면, 이를 상한supremum이라고 하여, $\sup M$와 같이 나타낸다. 마찬가지로, $M$의 하계 전체의 집합 $M_*$에 대하여, $\min M_*$이 존재한다면, 이를 하한infimum이라고 하여, $\inf M$와 같이 나타낸다. —

명제 2. $(A,\leq)$를 순서집합, $M$을 $M\neq\emptyset$인 $A$의 부분집합이라고 하자. $\max M$이 존재한다면, 이는 $\sup M$과 일치한다. 역으로, $\sup M$이 존재하는 동시에 $\sup M\in M$이라면, 이는 $\max M$과 일치한다. 마찬가지로, $\min M$과 $\inf M$에 대해서도 이와 같은 성질이 성립한다. —

증명. $a = \sup M$은 다음 두 조건을 만족하는 것과 동치이다.

  1. 임의의 $x\in M$에 대하여 $x\leq a$.
  2. $a’\in A$라고 할 때, 임의의 $x\in M$에 대하여 $x\leq a’$라면 $a\leq a’$.

$a=\max M$이 존재한다면, 조건 1을 만족하는 것은 당연하다. 또한, $a\in M$이므로 임의의 $x\in M$에 대하여 $x\leq a’$인 $a’\in A$에 대하여 $a\leq a’$인 것 역시 당연. 따라서 $a=\sup M$.

반대로, $\sup M$이 존재한다면, 1의 조건을 만족하고, $\sup M\in M$이므로, $\sup M = \max M$이다. $\min M$과 $\inf M$에 대해서도 마찬가지. $\square$

. $\max M$이 존재하지 않더라도, $\sup M$이 존재할 수 있다. 예를 들어, 순서집합 $A=\SetR$의 부분집합 $M=(-\infty,0)$의 경우, $\max M$이 존재하지 않지만, $\sup M=0$인 것을 확인할 수 있다. 실제로, 임의의 $\SetR$의 위로 유계인 부분집합 $M$은 항상 상한 $\sup M$을 갖는다. 이러한 성질을 실수의 연속성continuity of real numbers 혹은 실수의 완비성이라고 한다. —

예 5. 순서집합 $\SetQ$의 부분집합 $M\coloneqq \left\{ x\in\SetQ\mid x>0, x^2<2 \right\}$는 $\SetQ$ 상에서 상한을 갖지 않는다. 만약, 상한 $a=\sup M$이 존재한다고 가정한다면 $a>0$이고, $a^2=2$일 수는 없으므로 $a^2<2$이거나 $a^2>2$이다.

  • $a^2<2$인 경우: $a\in M$이므로, $a=\max M$이다. 하지만, $a’=(3a+4)/(2a+3)$으로 두면, $a’\in M$인 동시에 $a<a’$인 것을 알 수 있다. 이는 모순.
  • $a^2>2$인 경우: 역시 $a’=(3a+4)/(2a+3)$으로 두면, $a’$는 $M$의 상계인 동시에 $a'<a$이다. 이는 $a$가 상한이라는 가정에 모순.

따라서 $\sup M$은 존재하지 않는다. —

이 포스트에서는…

  • 순서전순서를 정의했다.
  • 순서집합의 최대, 최소, 극대, 극소 원소의 개념을 정의했다.
  • 순서집합과 그 부분집합이 주어졌을 때의 상계, 하계, 상한, 하한의 개념을 정의했다.

참고문헌

  • 松坂 和夫,『集合・位相入門』,岩波書店,1968.

  1. 이 경우, $a<b$이면 $b<a$이지 않다. 또한 $a<b$, $b<c$이면 $a<c$이다.↩︎

  2. “$a<b$, $a=b$, $a>b$의 셋 중 하나가 성립한다면”으로 바꾸어 말할 수 있다. 세 조건 중 하나가 성립한다면, 그 하나만이 유일하게 성립한다.↩︎

Leave a Reply

Your email address will not be published. Required fields are marked *