집합의 이항 관계로서 정의되는 선형 순서, 부분 순서, 전순서와 격자, 조인과 밋, 그리고 범주론과의 연결을 설명합니다.
주어진 객체들의 집합이 있으면, 그것들을 정렬하는 기준은 매우 많을 수 있습니다(객체 자체에 따라 다르지만) — 크기, 무게, 나이, 알파벳순 등입니다.
하지만 지금 우리가 관심을 두는 것은 객체를 정렬하는 기준 이 아니라, 순서를 정의하는 관계의 성질 입니다. 그리고 이 또한 여러 종류가 있을 수 있습니다.
수학적으로 순서는 하나의 구성으로서, (모노이드와 비슷하게) 두 가지 요소로 표현됩니다.
순서란 어떤 원소들의 집합과, 그 집합의 원소들 사이에 있는 이항 관계 로서, 특정한 법칙들을 만족하는 것이다.
집합의 원소들은 늘 그렇듯 다음과 같이 나타냅니다.
그리고 이항 관계 는 두 원소 사이의 관계이며, 흔히 화살표로 나타냅니다.
법칙들은 순서의 종류에 따라 달라집니다.
예시부터 시작해 봅시다 — 우리가 가장 직관적으로 떠올리는 순서의 형태는 선형 순서 입니다. 즉, 모든 객체가 다른 모든 객체와의 관계에 따라 자기 자리를 갖는 순서입니다. 이 경우 정렬 기준은 완전히 결정적이며, 어떤 원소가 어떤 원소보다 앞서는지에 대해 모호함의 여지가 없습니다. 예를 들어, 색을 빛의 파장 길이(또는 무지개에서 보이는 방식)에 따라 정렬하는 경우가 그렇습니다.
집합론을 사용하면, 이 순서뿐 아니라 다른 어떤 순서도 그 순서의 바탕 집합과 자기 자신과의 순서쌍들의 집합(곱집합의 부분집합)으로 표현할 수 있습니다.
프로그래밍에서는 보통 두 객체를 받아 어느 쪽이 “더 큰지”(앞에 오는지), 어느 쪽이 “더 작은지”를 알려 주는 함수를 제공함으로써 순서를 정의합니다. 이 함수가 순서쌍의 집합을 정의한다는 것은 어렵지 않게 알 수 있습니다(순서쌍 하나가 주어졌을 때 그것이 그 집합에 속하는지 여부를 말하면 되기 때문입니다).
[1, 3, 2].sort((a, b) => {
if (a > b) {
return true
} else {
return false
}
})
하지만(여기서부터 흥미로워집니다) 이런 모든 함수가, 그리고 모든 순서쌍의 집합이, 순서를 정의하는 것은 아닙니다. 어떤 함수가 정말로 하나의 순서를 정의하려면, 즉 객체들이 처음에 어떻게 섞여 있었는지와 무관하게 매번 같은 결과를 내놓으려면, 몇 가지 규칙을 따라야 합니다.
우연히도(혹은 전혀 우연이 아니게도), 이 규칙들은 순서 관계의 성질을 정의하는 수학적 법칙들과 거의 같습니다. 즉, 어떤 원소가 어떤 원소를 가리킬 수 있는지를 정하는 규칙들입니다.
선형 순서는 어떤 원소들의 집합과, 그 집합 원소들 사이의 이항 관계 로서, 반사성, 추이성, 반대칭성, 전역성의 법칙을 만족하는 것이다.
이제 그것들이 무엇인지 살펴봅시다.
우선 가장 지루한 법칙부터 치워 봅시다 — 각 객체는 자기 자신보다 크거나 같아야 합니다. 즉, 모든 에 대해 입니다. (순서에서 원소 사이의 관계는 수식에서는 보통 같은 기호로 나타내지만, 첫 번째 객체에서 두 번째 객체로 가는 화살표로도 표현할 수 있습니다.)
이 법칙은 단지 “기저 경우”를 다루기 위해 존재합니다. 반대로 정식화해서, 각 객체는 자기 자신과 그런 관계를 가지지 않아야 한다 고 말할 수도 있습니다. 그렇게 하면 크다 에 해당하는 관계를 얻게 되고, 크거나 같다 와는 조금 다른 종류의 순서, 흔히 엄격한 순서라고 부르는 것을 얻게 됩니다.
두 번째 법칙은 아마 가장 덜 자명하지만(아마도 가장 본질적인 법칙이기도 합니다), 어떤 객체 가 객체 보다 크다면, 보다 작거나 같은 모든 객체보다도 자동으로 크다는 뜻입니다.
이 법칙이야말로 순서가 무엇인지를 상당 부분 규정합니다. 내가 축구를 우리 할머니보다 더 잘한다면, 할머니가 이기는 할머니의 친구보다도 나 역시 더 잘해야 합니다. 그렇지 않다면 내가 정말 할머니보다 더 낫다고 할 수 없을 것입니다.
세 번째 법칙은 반대칭성입니다. 이것은 순서를 정의하는 함수가 서로 모순되는 결과를 주어서는 안 된다는 뜻입니다(다르게 말하면 이고 오직 그럴 때만 입니다).
이것은 또한 동률이 허용되지 않는다는 뜻이기도 합니다 — 내가 축구를 할머니보다 더 잘하거나, 아니면 할머니가 나보다 더 잘하거나 둘 중 하나입니다.
마지막 법칙은 전역성 (또는 연결성)이라고 하며, 순서에 속한 모든 원소가 비교 가능 해야 한다고 요구합니다 (). 즉, 어떤 두 원소를 잡아도 언제나 한쪽이 다른 쪽보다 “더 커야” 합니다.
참고로 전역성 법칙이 있으면 반사성은 중복됩니다. 반사성은 과 가 같은 객체일 때의 전역성의 특수한 경우에 불과하기 때문입니다. 하지만 곧 분명해질 이유 때문에 여기서는 여전히 반사성을 따로 제시하고 싶습니다.
사실 바로 이것이 그 이유입니다. 전역성 법칙은 제거할 수 있습니다. 전역성 법칙을 따르지 않는 순서를 부분 순서 라고 하고, (선형 순서는 전순서 라고도 부릅니다.)
과제 1: 앞에서 이것과 꽤 비슷한 관계를 다룬 적이 있습니다. 기억나나요? 차이는 무엇일까요?
과제 2: 여러분이 알고 있는 몇 가지 순서를 떠올리고, 그것들이 부분 순서인지 전순서인지 생각해 보세요.
부분 순서는 사실 선형/전순서보다 훨씬 더 흥미롭습니다. 하지만 그 이야기에 들어가기 전에, 수에 대해 몇 가지 말해 봅시다.
자연수는 크거나 같다 라는 연산 아래 선형 순서를 이룹니다(우리가 수식에서 써 온 기호가 바로 이것입니다).
여러 면에서 자연수는 순서의 전형입니다 — 유한한 객체들의 모든 순서는 수의 순서의 어떤 부분집합과 동형입니다. 어떤 순서의 첫 번째 원소를 숫자 에, 두 번째 원소를 숫자 에 대응시키는 식으로 보낼 수 있기 때문입니다(반대 방향의 대응도 물론 할 수 있습니다).
생각해 보면, 이 동형은 법칙들로 정의된 선형 순서보다 오히려 일상적인 선형 순서의 관념에 더 가깝습니다. 대부분의 사람은 순서를 떠올릴 때 추이적이고, 반대칭적이며, 전역적인 관계를 떠올리는 것이 아니라, 무엇이 첫 번째이고 무엇이 두 번째인지 등을 정하게 해 주는 기준을 떠올리기 때문입니다. 따라서 이 두 개념이 동등하다는 점을 알아두는 것이 중요합니다.
어떤 유한 순서든 자연수와 동형이라는 사실로부터, 크기가 같은 모든 선형 순서는 서로 동형이라는 사실도 따라 나옵니다.
따라서 선형 순서는 단순하지만, 동시에(그리고 이 동형이 그것을 보여 준다고 생각합니다) 범주론적 관점에서 보았을 때 가장 지루한 순서이기도 합니다 — 모든 유한 선형 순서(그리고 대부분의 무한한 것들)는 자연수와 그냥 동형이므로, 그 도표들이 모두 같은 모양을 하기 때문입니다.
하지만 다음에 살펴볼 부분 순서들은 그렇지 않습니다.
전역성 법칙은 다른 법칙들만큼 그렇게 “절대적인” 것처럼 보이지는 않습니다. 즉, 적용되지 않는 상황을 쉽게 생각해 볼 수 있습니다. 예를 들어 모든 사람을 축구 실력으로 정렬하려고 한다면, 어떤 사람과 그 친구들, 그 친구의 친구들 등을 비교해 순위를 매길 여러 방법은 있겠지만, 서로 한 번도 같이 경기해 보지 않은 사람들 집단 사이에는 순서를 정할 방법이 없습니다.
선형 순서의 법칙들에서 전역성 법칙을 제거하면 부분 순서 (또는 부분 순서 집합, poset)를 얻게 됩니다.
부분 순서란 어떤 원소들의 집합과, 그 집합 원소들 사이의 이항 관계 로서, 반사성, 추이성, 반대칭성의 법칙을 만족하는 것이다.
모든 선형 순서는 부분 순서이기도 하지만(마치 군이 여전히 모노이드인 것처럼), 그 역은 성립하지 않습니다.
심지어 어느 것이 더 일반적인지를 기준으로 순서들의 순서 를 만들 수도 있습니다.
부분 순서는 1장에서 다루었던 동치 관계 와도 관련이 있습니다. 다만 대칭성 법칙이 반대칭성 으로 바뀝니다.
축구 선수 순위표 예시를 다시 보면, 나 m, 할머니 g, 그리고 할머니의 friend만 포함한 첫 번째 버전은 선형 순서입니다.
하지만 우리 중 누구와도 아직 경기해 보지 않은 이 other 사람을 포함시키면, 그 위계는 비선형이 되고, 즉 부분 순서가 됩니다.
이것이 부분 순서와 전순서의 핵심적인 차이입니다 — 부분 순서는 누가 누구보다 더 나은지에 대해 항상 확정적인 답을 주지 못합니다. 하지만 때로는 바로 그것이 우리가 원하는 것입니다 — 스포츠뿐 아니라 다른 영역에서도, 원소들을 선형적으로 평가하는 적절한 방법이 항상 존재하는 것은 아닙니다.
앞에서 모든 선형 순서는 동일한 사슬 모양의 도표로 표현될 수 있다고 했습니다. 이 말을 뒤집으면, 그 도표와 다른 모양을 띠는 모든 도표는 부분 순서를 나타낸다고 할 수 있습니다.
그 예로는 여러 개의 선형 정렬된 부분집합을 포함하는 부분 순서가 있습니다. 예를 들어 축구 예시에서는 함께 경기하는 친구들끼리 따로 그룹을 이루어 서로 안에서만 순위가 매겨지고, 다른 그룹 사람들과는 비교되지 않을 수 있습니다.
부분 순서를 이루는 서로 다른 선형 순서들을 사슬 이라고 합니다. 이 도표에는 두 개의 사슬 와 가 있습니다.
부분 순서 안의 사슬들은 부분 순서가 되기 위해 반드시 완전히 분리되어 있을 필요는 없습니다. 연결이 전부 일대일 연결, 즉 한 사슬의 마지막 원소가 다른 사슬의 첫 번째 원소에 연결되는 식이지만 않으면 됩니다(그 경우 사실상 둘이 하나의 사슬로 합쳐집니다).
위의 집합은 선형 순서가 아닙니다 — 이고 라는 것은 알지만, 와 사이의 관계는 알 수 없습니다 — 어느 쪽이 더 클 수도 있습니다.
부분 순서는 “누가 누구보다 더 나은가?”라는 질문에 대해 확정적인 답을 주지 못하지만, 그중 일부는 여전히 더 중요한 질문, 즉 “누가 1등인가?”에 대해서는 답을 줄 수 있습니다. 다시 말해 챔피언, 다른 누구보다도 더 나은 선수, 또는 더 일반적으로는 다른 모든 원소보다 큰 원소가 누구인지 말해 줄 수 있습니다.
순서의 최대 원소 는 원소 로서, 임의의 다른 원소 에 대해 가 성립하는 것이다. 일부(전부는 아님) 부분 순서는 이런 원소를 갖습니다 — 마지막 도표에서는 가 최대 원소이고, 다음 도표에서는 초록 원소가 가장 큰 원소입니다.
때로는 다른 모든 원소보다 큰 원소가 하나보다 많을 수도 있는데, 이 경우 그 어느 것도 최대 원소는 아닙니다.
최대 원소 외에도, 부분 순서는 같은 방식으로 정의되는 최소 원소를 가질 수 있습니다.
순서의 일부로 연결되어 있는 두 원소의 최소 상계 를 그 원소들의 조인 이라고 합니다. 예를 들어 초록 원소는 나머지 두 원소의 조인입니다.
와 의 조인은 그것들보다 큰 원소들 중 가장 작은 원소입니다. 형식적으로는 다음과 같습니다.
객체 와 의 조인 은 객체 로서, 다음을 만족한다:
- 이 객체는 두 객체보다 모두 크다. 즉 이고 이다.
- 이 객체는 그것들보다 큰 다른 어떤 객체보다도 작다. 즉, 임의의 다른 객체 에 대해 이고 이면, 도 성립해야 한다.
주어진 두 원소 중 하나가 다른 하나보다 클 때(예: ), 조인은 그 더 큰 원소입니다(이 경우 ).
예를 들어 선형 순서에서는, 두 원소의 조인 은 그냥 더 큰 원소입니다.
최대 원소의 경우와 마찬가지로, 두 원소가 똑같이 큰 여러 상계를 갖는다면 그중 어느 것도 조인 이 아닙니다(조인은 유일해야 합니다).
하지만 그 원소들 중 하나가 나머지보다 작다고 정해지는 순간, 즉시 조인이 됩니다.
과제 3: 범주론의 어떤 개념이 조인을 떠올리게 하나요?
주어진 두 원소에 대해, 둘보다 모두 작은 원소들 가운데 가장 큰 원소를 그 원소들의 밋 이라고 합니다.
조인에 대한 규칙들이 반대로 적용됩니다.
이 절에서 사용하는 도표들은 “하세 도표”라고 하며, 보통의 도표처럼 작동하지만 한 가지 추가 규칙이 있습니다 — 더 “큰” 원소는 항상 더 작은 원소 위에 배치됩니다.
화살표의 관점에서 말하면, 어떤 점에 화살표를 추가할 때 그 화살표가 향하는 점은 반드시 화살표가 시작하는 점보다 위에 있어야 한다는 뜻입니다.
이런 배치는 단지 어느 점이 다른 점보다 위에 있는지만 보아도 두 점을 비교할 수 있게 해 줍니다. 예를 들어 두 원소의 조인 은, 둘이 연결되는 원소들을 확인한 뒤 그중 가장 낮은 것을 찾으면 됩니다.
우리 모두 전순서의 예시는 많이 알고 있습니다(어떤 형태의 차트나 순위표든 전순서입니다). 하지만 부분 순서의 자명한 예시는 아마 그렇게 쉽게 떠오르지 않을 것입니다. 그러니 몇 가지를 살펴봅시다. 그러면 맥락을 얻을 수 있고, 조인이 무엇인지 이해하는 데도 도움이 됩니다.
형식을 유지하기 위해, 전에 보았던 색 혼합 모노이드를 다시 가져와서, 모든 색이 자신을 포함하는 색들을 가리키는 색 혼합 부분 순서 를 만들어 봅시다.
따라가 보면, 임의의 두 색의 조인은 그 둘을 섞었을 때 만들어지는 색이라는 것을 알게 될 것입니다. 멋지지 않나요?
수를 “크거나 같다”로 정렬하면 선형 순서를 이룬다고 보았습니다. 하지만 수는 부분 순서도 이룰 수 있습니다. 예를 들어 어떤 수가 어떤 수를 나누는가에 따라 정렬할 수 있습니다. 즉 가 를 나누면 는 앞에 옵니다. 예를 들어 이므로 , 은 앞에 옵니다(하지만 예를 들어 는 앞에 오지 않습니다.)
그리고 우연히도(사실 아주 좋은 이유로) 조인 연산은 다시 그 객체들의 맥락에서 중요한 연산과 대응합니다 — 이 부분 순서에서 두 수의 조인은 그들의 최소공배수 입니다.
그리고 밋 (조인의 반대)은 두 수의 최대공약수 입니다.
주어진 원소들의 집합의 여러 조합을 담고 있는 집합들의 모음을 생각해 봅시다…
…이들 집합에 대해 포함 순서 라고 불리는 것을 정의할 수 있습니다.
집합들의 포함 순서는 집합들의 모음(보통 어떤 공통 원소들을 포함하는 집합들)을 정렬하는 데 사용할 수 있는 이항 관계로서, 가 를 포함할 때 가 앞에 온다. 다시 말해 가 의 부분집합 일 때이다.
이 경우 두 집합의 조인 연산은 그들의 합집합 이고, 밋 연산은 집합의 교집합 입니다.
이 도표는 무언가를 떠올리게 할지도 모릅니다 — 각 집합에 포함된 색들을 하나의 색으로 섞어 보면, 앞에서 본 색 혼합 부분 순서를 얻게 됩니다.
수의 약수 예시도 어떤 포함 순서와 동형입니다. 정확히는 가능한 모든 소수 집합의 포함 순서와 동형이며, 중복도 포함합니다(또는 모든 소수 거듭제곱 의 집합이라고 해도 됩니다). 이는 산술의 기본정리에 의해 보장됩니다. 산술의 기본정리는 모든 수가 소수들의 곱으로 정확히 한 가지 방식으로만 쓰일 수 있다고 말합니다.
지금까지 우리는 두 가지 서로 다른 부분 순서를 보았습니다. 하나는 색 혼합에 기반하고, 다른 하나는 수의 나눗셈에 기반합니다. 이 둘은 어떤 기본 원소들 의 모든 가능한 집합 조합의 포함 순서로 표현될 수 있었습니다(첫 번째 경우에는 원색들, 두 번째 경우에는 소수들 또는 소수 거듭제곱들). 많은 다른 부분 순서들도 이런 방식으로 정의될 수 있습니다. 정확히 어떤 것들이 가능한지는 버코프의 표현 정리 라는 놀라운 결과가 답해 줍니다. 그것은 다음 두 조건을 만족하는 유한 부분 순서들입니다:
첫 번째 조건을 만족하는 부분 순서를 격자 라고 합니다. 두 번째 조건도 만족하는 것은 분배 격자 라고 합니다. 적어 보면 다음과 같습니다.
모든 원소가 조인 과 밋 을 갖는 부분 순서를 격자 라고 한다. 그 밋 과 조인 연산이 서로에 대해 분배 되는 격자를 분배 격자라고 한다.
그리고 포함 순서를 구성하는 데 사용하는 “소수 같은” 원소들은 다른 어떤 원소들의 조인 으로도 나타낼 수 없는 원소들입니다. 이것들을 조인 기약 원소라고도 합니다.
그러므로 정리를 다음과 같이 표현할 수 있습니다.
각 분배 격자는 그 조인 기약 원소들의 포함 순서와 동형이다.
참고로 분배 격자 가 아닌 부분 순서들도 포함 순서와 동형이긴 합니다. 다만 그 경우에는 원소들의 가능한 모든 조합을 다 포함하지 않는 포함 순서와 동형이라는 점이 다릅니다.
이제 격자 (버코프 정리가 적용되는 순서)에 대해 좀 더 이야기해 보겠습니다. 격자는 임의의 두 원소가 조인 과 밋 을 가지는 부분 순서입니다. 따라서 모든 격자는 부분 순서이지만, 모든 부분 순서가 격자인 것은 아닙니다(우리는 이 위계의 더 많은 구성원도 보게 될 것입니다).
어떤 규칙에 따라 만들어진 대부분의 부분 순서는 분배 격자입니다. 예를 들어 앞 절의 부분 순서들도 완전한 형태로 그리면 분배 격자가 됩니다. 색 혼합 순서가 그 예입니다.
맨 위에 검은 공을, 맨 아래에 흰 공을 추가했다는 점에 주목하세요. 그렇게 한 이유는, 그렇지 않으면 위쪽 세 원소는 조인 을 갖지 못하고, 아래쪽 세 원소는 밋 을 갖지 못하기 때문입니다.
우리의 색 혼합 격자는 최대 원소 (검은 공)와 최소 원소 (흰 공)를 가집니다. 최소 원소와 최대 원소를 가진 격자를 유계 격자 라고 합니다. 모든 유한 격자가 유계라는 것은 어렵지 않게 알 수 있습니다.
과제 4: 모든 유한 격자가 유계임을 증명해 보세요.
우리는 이미 순서 동형을 여러 번 언급했으니, 이제 그것이 무엇인지 자세히 설명할 때가 되었습니다.
두 집합이 있을 때(예시로는 나눗셈에 의한 수의 부분 순서와 소수 포함 순서를 사용하겠습니다), 그들 사이의 동형은 다음 두 함수로 이루어집니다.
순서 동형은 본질적으로 두 순서의 바탕 집합 사이의 동형, 즉 가역 함수입니다. 하지만 순서는 바탕 집합 외에도 그것들을 연결하는 화살표를 갖고 있으므로, 조건이 하나 더 있습니다. 가역 함수가 순서 동형이 되려면 그 화살표들을 보존 해야 합니다.
두 순서 사이의 동형이란 그 바탕 집합들 사이의 가역 함수로서, 한 집합에서 어떤 순서를 갖는 임의의 두 원소(이를 와 라고 합시다)에 이 함수를 적용했을 때, 다른 집합에서도 대응되는 순서를 갖는 두 원소가 되어야 한다(즉 이고 오직 그럴 때만 이다).
이런 함수를 순서 보존 함수라고 합니다.
앞 절에서 우리는 (선형) 순서의 법칙들에서 전역성 을 제거하면 부분 순서 라는, 조금 더 흥미로운 구조가 생긴다는 것을 보았습니다. 이제 다른 법칙 하나, 즉 반대칭성 법칙을 제거하면 무슨 일이 일어나는지 봅시다.
반대칭성 법칙은 어떤 객체가 동시에 다른 객체보다 작으면서 크는 일은 없다고 요구했습니다. (즉 이다.)
| 선형 순서 | 부분 순서 | 전순서 | |
|---|---|---|---|
| 원소 비교 가능성 | a≤b 또는 b≤a | a≤b 또는 b≤a 또는 둘 다 아님 | a≤b 또는 b≤a 또는 둘 다 아님 또는 둘 다임 |
| 반사성 | X | X | X |
| 추이성 | X | X | X |
| 반대칭성 | X | X | - |
| 전역성 | X | - | - |
그 결과로 얻는 구조가 전순서 입니다.
전순서란 어떤 원소들의 집합과, 그 집합 원소들 사이의 이항 관계 로서, 반사성과 추이성의 법칙을 만족하는 것이다.
전순서는 일상적인 의미의 순서와는 정확히 같지 않습니다 — 어떤 점에서 다른 어떤 점으로든 화살표가 갈 수 있습니다. 부분 순서가 누가 축구를 더 잘하는지를 모델링하는 데 쓰일 수 있다면, 전순서는 누가 누구를 이겼는지를 직접적으로든(직접 경기해서) 간접적으로든 모델링하는 데 쓰일 수 있습니다.
전순서에는 사실상 하나의 법칙만 있습니다 — 추이성 입니다(물론 반사성 도 세면 둘입니다). 간접 승리에 대한 이야기는 이 법칙의 결과입니다. 이 법칙 때문에 모든 간접 승리(직접 그 선수를 이긴 것이 아니라, 그 선수를 이긴 누군가를 이긴 경우)가 자동으로 직접적인 결과로 추가됩니다. 아래에서는 간접 승리를 더 연한 색으로 표시했습니다.
그리고 그 결과, 모든 “원형” 관계(예를 들어 약한 선수가 강한 선수를 이기는 경우)는 결국 서로 모두 연결된 객체들의 묶음이 됩니다.
이 모든 구조가 추이성이라는 단순한 법칙으로부터 자연스럽게 생겨납니다.
전순서는 부분 순서 와 동치 관계 의 중간쯤에 놓인 것으로 볼 수 있습니다. 이 두 구조가 서로 다른 정확히 그 성질, 즉 (반)대칭성이 빠져 있기 때문입니다. 그래서 전순서 안에서 어떤 객체들의 묶음이 대칭성 법칙을 만족하면, 그 객체들은 하나의 동치 관계를 이룹니다. 반대로 반대칭성 을 만족하면 부분 순서를 이룹니다.
| 동치 관계 | 전순서 | 부분 순서 |
|---|---|---|
| 반사성 | 반사성 | 반사성 |
| 추이성 | 추이성 | 추이성 |
| 대칭성 | - | 반대칭성 |
특히 위의 예처럼 서로 양방향으로 연결된 객체들의 부분집합은 대칭성 조건을 만족합니다. 따라서 그런 연결을 가진 모든 원소를 묶으면 여러 개의 집합을 얻게 되고, 각각은 전순서에 기반한 서로 다른 동치 관계 를 정의합니다. 이를 전순서의 동치류 라고 합니다.
그리고 더 흥미롭게도, 이 집합들의 원소들 사이에 있던 전순서의 연결을 집합들 자체 사이의 연결로 옮기면, 그 연결들은 반대칭성 을 만족하게 됩니다. 즉 하나의 부분 순서 를 이루게 됩니다.
요컨대, 모든 전순서에 대해 그 전순서의 동치류들의 부분 순서 를 정의할 수 있습니다.
전순서가 강력한 개념이라는 것을 보았으니, 이제 그것을 지배하는 법칙인 추이성을 더 깊이 살펴봅시다. 이 법칙이 말하는 것은, 관계 와 라는 두 쌍이 있으면 자동으로 세 번째 관계 가 생긴다는 것입니다.
다르게 말하면, 추이성 법칙은 그 관계가 합성된다고 말해 줍니다. 즉 “크다”라는 관계를 사상으로 보면, 추이성 법칙은 사실 범주론적 합성 의 정의와 같습니다.
(관계가 결합법칙도 만족하는지 확인해야 하지만, 그것은 쉽습니다)
그러니 전순서는 범주일 것 같지만, 정말 그럴까요? 범주의 정의를 다시 살펴봅시다.
범주란 객체 들(점이라고 생각해도 됩니다)과, 한 객체에서 다른 객체로 가는 사상 들(화살표)의 모음으로서, 다음을 만족한다:
- 각 객체는 항등 사상을 가져야 한다.
- 적절한 타입 시그니처를 가진 두 사상을 세 번째 사상으로 합성하는 방법이 있어야 하며, 그 합성은 결합적이어야 한다.
추이성 덕분에 2번 법칙은 충족된 것 같습니다. 그렇다면 항등 법칙은 어떨까요? 그것도 있습니다. 이름만 반사성 일 뿐입니다.
이제 공식입니다 — 전순서는 범주입니다(특히 포함 순서를 통해 전순서를 집합과 함수로 환원할 수 있다는 것도 이미 보았으니, 집합과 함수 자체가 하나의 범주를 이룬다는 점을 생각하면 꽤 자명하게 들리기도 합니다).
전순서는 범주의 특수한 종류입니다(모든 전순서는 범주이지만, 모든 범주가 전순서는 아닙니다). 대부분의 범주는 주어진 두 객체 사이에 여러 다른 사상을 가집니다. 예를 들어 집합의 범주에서는, 정수 집합과 불리언 값의 집합 사이에 잠재적으로 무한히 많은 함수가 있을 수 있고, 반대 방향의 함수도 많이 있을 수 있습니다.
반면 전순서에서는, 두 객체 사이에 최대 하나의 사상만 있습니다. 즉, 있거나 없거나 둘 중 하나입니다.
그러므로 모노이드가 객체를 하나만 가진 범주인 것처럼, 순서는 두 객체 사이에 최대 하나의 사상 만을 갖는 범주입니다.
주어진 두 객체 사이에 최대 하나의 사상만 있다는 사실로부터 따라오는 흥미로운 사실 하나는, 전순서에서는 모든 도표가 가환한다 는 것입니다.
과제 6: 이것을 증명해 보세요.
부분 순서와 전순서는 전순서의 일종이라고 했습니다. 즉, 그것들도 범주입니다.
특히 부분 순서는 범주론에서 skeletal 범주라고 하는 것과 관련이 있습니다 — 서로 동형인 객체가 없고, 다시 말해 동형인 모든 객체가 실제로는 동일한 범주입니다.
그리고 전순서에 대해서는 특별한 “범주론적” 이름이 따로 있는지는 모르겠지만, 그것 역시 하나의 특정한 종류의 범주입니다.
이전 장들의 도표를 다시 떠올리는 김에, 2장에서 보았던 범주에서 두 객체의 쌍대곱 을 정의하는 도표를 봅시다. 
기억하겠지만, 이것은 집합의 범주에서는 집합 포함 에 대응하는 연산입니다.
그런데 잠깐, 집합 포함에 대응하는 다른 연산도 있지 않았나요? 그렇습니다. 순서에서의 조인 입니다. 그것뿐 아니라, 순서에서의 조인은 범주론적 쌍대곱과 정확히 같은 방식으로 정의됩니다.
와 의 쌍대곱을 로 쓰면, 그것은 다음을 만족하는 객체이다:
- 두 개의 “사영” 사상 와 가 존재한다.
- 그런 사영 사상( 와 )을 가지는 임의의 가짜 쌍대곱 에 대해서도, 실제 쌍대곱에서 그 가짜 쌍대곱으로 가는 타입 시그니처 의 유일한 사상 가 존재해야 하며, 이때 가짜 쌍대곱의 사영은 실제 쌍대곱의 사영과 의 합성으로 주어져야 한다.
순서의 세계에서 조인은 다음과 같이 정의됩니다.
객체 와 의 조인 은 객체 로서, 다음을 만족한다:
- 이 객체는 두 객체보다 모두 크다. 즉 이고 이다.
- 이 객체는 그것들보다 큰 다른 어떤 객체보다도 작다. 즉, 임의의 다른 객체 에 대해 이고 이면, 도 성립해야 한다.
이 두 정의와 그에 대응하는 도표가 사실상 같다는 것을 볼 수 있습니다. 단지 “더 크다”를 “유일한 사상이 있다”로 바꿨을 뿐입니다(순서에서는 모든 사상이 유일하기 때문입니다).
범주론의 말로 표현하면 다음과 같습니다.
전순서의 범주 에서 범주론적 쌍대곱 은 조인 연산이다.
물론 이것은 곱 이 밋 에 대응한다는 뜻이기도 합니다(쌍대성).
범주론의 용어로, 주어진 타입 시그니처에 대해 최대 하나의 사상만 갖는 범주를 순서라고 하며, 이런 범주를 “얇은(thin)” 범주라고 부릅니다.
전순서, 즉 어떤 전순서든, 주어진 두 객체 사이에 최대 하나의 사상만 갖는 범주로 볼 수 있다 — 한 객체가 더 크면 그들 사이에 사상이 있다. 역도 성립한다. 주어진 두 객체 사이에 최대 하나의 사상만 갖는 모든 범주는 전순서(또는 얇은 범주)로 볼 수 있다.
얇은 범주는 보통의(얇지 않은) 범주보다 이해하기 쉬운 맥락에서 범주론적 개념을 탐구하는 데 자주 쓰입니다. 예를 들어 앞에서 보았듯이, 밋과 조인이라는 순서론적 개념을 이해하면 곱과 쌍대곱이라는 더 일반적인 범주론적 개념을 더 잘 이해할 수 있습니다.
얇은 범주는 또한 단순함을 유지하고 싶고, 한 객체에서 다른 객체로 가는 사상들 사이의 차이에 특별히 관심이 없을 때도 유용합니다. 다음 장에서 그런 예를 보게 될 것입니다.