순서관계
순서관계는 반사적이고 반대칭적이며 추이적인 집합 위의 이항관계이다.
동기
순서는 일상에서도 늘 쓰는 개념이다. 많은 것을 어떤 기준으로 순서대로 늘어놓을 수 있다. 단어는 가나다순으로, 학생은 키 순서로, 상품은 가격 순서로 늘어놓는다. 이런 것을 모두 순서관계가 나타내는데, 순서관계는 보통 기호 ≤로 나타낸다. 관련된 기호로 <, >, ≥가 있다. 뜻은 분명하다.
이런 관계에 무엇을 기대할까? 기호만 보아도 순서관계에는 같은 원소끼리의 쌍도 들어 있다. 즉 우리가 정하려는 것은 ‘작거나 같다’라는 관계의 성질이다. 그러니 이 관계는 반사적이어야 한다. a ≤ a가 성립해야 한다.
그다음은? 대칭성은 분명히 성립하지 않는다. 가격 순서에서 자동차가 빵보다 싸다면, 빵이 동시에 자동차보다 쌀 수는 없다. 일반적으로 a ≤ b이고 동시에 b ≤ a인 일이 생긴다면 어떨까? 그것이 말이 되는 경우가 있을까? a = b이면 말이 된다. 관계에 넣은 원소의 순서가 상관없는 경우는 두 원소가 같을 때뿐이다. 그래서 순서관계는 반대칭적이다.
마지막으로 자동차가 빵보다 비싸고 비행기가 자동차보다 더 비싸다는 것을 안다면, 비행기는 당연히 빵보다 비쌀 것이라고 기대한다. 이것을 나타내는 것이 추이성이다.
부분 순서
방금 정의한 것은 사실 부분 순서일 뿐이고 전순서는 아니다. 왜 전순서가 아닐까? 집합에 순서를 정해 보자. 두 집합은 어떻게 비교할 수 있을까?
A ⊆ B, 즉 A가 B의 부분집합이면 집합 A가 집합 B보다 작거나 같다고 하자. 이렇게 정하는 것은 이치에 맞다. A = {1, 2}이고 B = {1, 2, 3}이면 A가 더 작다고 말할 수 있다. B에는 A와 같은 원소가 있고 수 3이 더 있기 때문이다. 그러니 예를 들어 다음이 성립한다.
- {a, c} ≤ {a, b, c, d}
- ∅ ≤ {5, n, x}
- {x, e, s} ≤ {x, e, s}
문제는 집합 A = {a, b}와 B = {a, c}를 비교하려고 할 때 생긴다. 어느 쪽이 더 작고 어느 쪽이 더 클까? 두 집합 모두 원소 a가 있지만 다른 원소는 서로 다르다. 어느 집합도 다른 집합의 부분집합이 아니므로 A ≤ B도 B ≤ A도 성립하지 않는다. 이런 두 집합은 우리가 정한 순서로는 비교할 수 없다.
그래서 집합의 어떤 두 원소도 비교할 수 있으면 그 집합을 전순서 집합 또는 사슬이라고 정의한다. 예를 들어 보통의 순서를 준 수의 집합이 그렇다. 어떤 두 실수 a, b에 대해서도 a ≤ b인지 b ≤ a인지 판단할 수 있다.
일상의 예
비교하지 않는 편이 나은 예로 외모에 따른 순서를 들 수 있다. 관계 <는 ‘덜 잘생겼다’는 뜻이 된다. 좀 더 예의 바르게 거꾸로 >를 ‘더 잘생겼다’로 정하는 편이 낫겠다 :-). 두 여자끼리, 예를 들어 “은지” < “소희”를 소희가 은지보다 더 예쁘다는 뜻으로 비교하는 것은 아마 의미가 있을 것이다. 두 남자끼리도 마찬가지이다. “준영” < “태호”는 태호가 준영보다 더 잘생겼다는 뜻이다.
문제는 남자와 여자의 외모는 비교하기 어렵다는 것이다. 소희가 더 예쁠까, 태호가 더 잘생겼을까? 은지와 준영 가운데 누가 덜 잘생겼을까? 따지지 않는 편이 낫다…
마지막 예에서 예를 들어 여자로만 범위를 좁히면 전순서 집합을 얻는다고 말할 수 있다. 모든 여자의 외모를 비교할 수 있기 때문이다.
극소 원소와 극대 원소, 최소 원소와 최대 원소
순서집합 M이 있을 때 x < min인 x ∈ M이 없으면 원소 min ∈ M을 극소 원소라고 한다. 즉 원소 min보다 작은 원소를 찾을 수 없다.
x > max인 x ∈ M이 없으면 원소 max ∈ M을 극대 원소라고 한다. 즉 더 큰 원소를 찾을 수 없다.
이 두 개념은 최소, 최대와는 다르다.
모든 x ∈ M에 대해 a ≤ x이면 원소 a ∈ M을 최소 원소라고 한다. 즉 최소 원소 a는 집합 M의 다른 모든 원소보다 작거나 같다.
모든 x ∈ M에 대해 b ≥ x이면 원소 b ∈ M을 최대 원소라고 한다. 최대 원소 b는 집합 M의 다른 모든 원소보다 크거나 같다.
최대 원소와 극대 원소는 무엇이 다를까? 집합이 꼭 전순서일 필요는 없으므로 극대 원소는 여러 개일 수 있다. 외모로 사람을 비교하는 예로 돌아가면, 소희가 가장 예쁜 여자이고 태호가 가장 잘생긴 남자라고 할 수 있다. 하지만 이 두 사람은 서로 비교할 수 없다. 소희와 태호 가운데 누가 더 잘생겼는지는 알 수 없다.
그러니 두 원소 모두 극대이다. 태호보다 더 잘생긴 사람은 찾을 수 없다. 태호는 다른 모든 남자보다 잘생겼고, 여자와는 비교할 수 없기 때문이다. 소희도 마찬가지이다. 소희는 모든 여자보다 예쁘고 남자와는 비교할 수 없다.
하지만 둘 다 최대, 이 경우에는 가장 잘생긴 사람은 아니다. 태호가 가장 잘생긴 사람, 즉 최대이려면 모든 여자를 포함해 모든 사람보다 잘생겨야 하기 때문이다. 그런데 앞에서 말했듯이 여자와는 비교할 수 없으므로 태호는 가장 잘생긴 사람일 수 없고, 순서 이론의 용어로 극대일 뿐이다.
집합에 최대 원소가 있으면 그 원소가 극대 원소이기도 하다는 것은 쉽게 알 수 있을 것이다. 원소 a가 집합의 다른 모든 원소보다 크면(최대 원소의 정의) 그보다 더 큰 원소는 당연히 찾을 수 없다(극대 원소의 정의).
최대 원소와 최소 원소가 있는 집합의 예로 닫힌구간 [0, 1]을 들 수 있다. 같은 구간이라도 열린구간 (0, 1)이면 최대 원소도 최소 원소도 없다.
극소 원소가 무한히 많은 순서를 원한다면 순서 R을 다음과 같이 정할 수 있다. 먼저 보조 집합 Mx를 정한다. 구간 (0, 1)의 모든 x에 대해 집합 Mx = {y | y = x + n}을 정한다. 여기서 n은 0 이상의 정수이다. 그러면 예를 들어 다음과 같은 집합을 얻는다.
각 집합 Mx에 보통의 순서를 정하고 이것을 Rx로 나타낸다. 마지막으로 이 순서들의 합집합을 구한다. R = ∪ Rx이다. 이 순서에서는 언제나 원래의 사슬 안에서만 비교할 수 있다. 0.5 ≤ 2.5인지는 알 수 있지만, 0.5 ≤ 2.7인지는 알 수 없다. 이 두 수는 같은 집합 Mx에 있지 않았으므로 둘 사이의 관계가 정해져 있지 않기 때문이다.
이 순서관계에서는 구간 (0, 1)의 모든 원소가 극소 원소이다.
하세 도표
순서집합은 하세 도표로 그릴 수 있다. 하세 도표는 그래프인데, 꼭짓점은 집합의 원소를 나타내고, 꼭짓점 사이의 변 (a, b)는 a < b이면서 a < c < b인 c가 없다는 것을 나타낸다. 즉 원소 a와 b 사이에는 다른 원소가 없다. 또 그래프에서 꼭짓점 a는 꼭짓점 b보다 아래에 있어야 한다. 하세 도표의 예는 다음과 같다.
이 하세 도표는 순서집합 {A, B, C, D, E, F}를 나타낸다. 여기서 A < B, B < E이고, 물론 A < E도 성립하지만 이 두 꼭짓점 사이에는 변이 없다. A < B < E인 꼭짓점 B가 있기 때문이다. 원소 E와 D는 비교할 수 없다. 어느 쪽도 다른 쪽의 위나 아래에 있지 않기 때문이다.
하세 도표는 보통 이렇게 보기 좋게 정렬해서 그리지만 꼭 그래야 하는 것은 아니다. 앞의 하세 도표는 이렇게 그려도 된다.
다른 예로 집합 A = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}을 보자. 60의 양의 약수들이다. 나누어떨어짐에 따른 순서는 다음과 같이 나타낼 수 있다.
나누어떨어짐에 따른 순서란 a가 b를 나눌 때 그리고 그때에만 (a, b) ∈ R이라는 뜻이다. 도표를 보면 각 수 위에는 그 수로 나누어떨어지는 수들이 있다. 예를 들어 6 위에는 12, 30, 60이 있다. 4 위에는 12, 20, 60이 있다. 다른 수도 마찬가지이다. 반면에 3 위에는 10이 없다. 3은 10을 나누지 않기 때문이다. 주의하자. 10은 그림에서는 3보다 위에 있지만, 3에서 10으로 ‘아래에서 위로’ 이어지는 선은 없다. 3에서 위로만 움직이면 15와 6으로 갈 수 있고, 거기서 30으로 갈 수 있다. 10에는 아래로 내려가야만 갈 수 있는데, 그렇게 해서는 안 된다.