범주론 그림으로 보는 순서

• 원소 집합 위의 이항 관계가 반사성·추이성·반대칭성 같은 법칙을 만족할 때 순서 구조 성립
• 선형 순서는 모든 두 원소가 비교 가능한 구조이며, 전순성을 제거하면 부분 순서가 됨
• 부분 순서에서는 사슬, 최댓원소·최솟원소, join·meet, Hasse 다이어그램으로 구조 파악 가능
• 색 혼합, 나눗셈 가능성, 집합 포함 관계는 부분 순서의 예시이며, join과 meet를 모두 가지는 경우 lattice 형성
• preorder는 반사성과 추이성만 가진 구조이며, 모든 preorder는 두 객체 사이에 최대 하나의 사상만 있는 범주로 해석 가능

순서

• 순서는 원소 집합과 그 위의 이항 관계로 구성되며, 특정 법칙을 만족할 때 수학적 구조 성립
  • 순서 기준 자체보다 원소들 사이의 관계가 어떤 성질을 가지는지가 핵심
  • 이항 관계는 집합의 두 원소 사이의 관계이며, 화살표로도 표시 가능
• 순서는 집합론에서는 원래 집합의 자기 자신과의 곱집합 부분집합, 프로그래밍에서는 두 객체를 비교하는 함수 형태로 표현 가능
  • 하지만 모든 비교 함수나 원소 쌍 집합이 순서를 정의하는 것은 아니며, 초기 배치와 무관하게 일관된 결과를 내려면 특정 규칙 필요

선형 순서

• 선형 순서는 모든 원소가 서로에 대해 자리를 가지는 순서이며, 어떤 원소가 다른 원소보다 앞서는지가모호하지 않은 구조

  • 예시로 빛의 파장 길이 또는 무지개에서의 배열에 따른 색 순서 제시
  • 선형 순서는 반사성, 추이성, 반대칭성, 전순성을 만족하는 이항 관계로 정의
  • 이 네 법칙이 순서 관계를 구성하는 조건

• 반사성

  • 모든 원소는 자기 자신보다 크거나 같아야 하며, 모든 $a$에 대해 $a \le a$ 성립
  • 이는 기저 사례를 다루는 규칙이며, 반대로 자기 자신과 관계를 맺지 않게 정의하면 strict order와 유사한 다른 유형 형성

• 추이성

  • $a \le b$ 이고 $b \le c$ 이면 $a \le c$ 가 되어야 하는 규칙
  • 순서의 핵심을 크게 규정하는 법칙

• 반대칭성

  • 모순된 비교 결과 금지 규칙이며, $x \le y$ 이고 $y \le x$ 인 경우는 $x = y$ 일 때만 허용
  • 동률이 허용되지 않는다는 표현과 함께 정리

• 전순성

  • 모든 두 원소가 반드시 비교 가능해야 하며, 임의의 두 원소에 대해 $a \le b \lor b \le a$ 성립
  • 어떤 두 원소든 하나가 다른 하나보다 크거나 같아야 함
  • 전순성은 $a$ 와 $b$ 가 같은 경우를 포함하므로 반사성을 특수 사례로 포함
  • 전순성을 제거하면 부분 순서가 되며, 선형 순서는 total order라고도 표기

• 자연수의 순서

  • 자연수는 크거나 같음 관계 아래에서 선형 순서 형성
  • 모든 유한 선형 순서는 첫 번째 원소를 1, 두 번째 원소를 2에 대응시키는 방식으로 자연수의 부분집합과 동형
  • 따라서 같은 크기의 모든 유한 선형 순서는 서로 동형
  • 범주론 관점에서는 모든 유한 선형 순서와 대부분의 무한 선형 순서의 도식이 동일하게 보인다는 점도 언급

부분 순서

• 부분 순서는 선형 순서에서 전순성을 제거한 구조이며, 반사성, 추이성, 반대칭성만 유지
  • partially-ordered set, poset라는 이름도 함께 사용
• 모든 선형 순서는 부분 순서이지만, 모든 부분 순서가 선형 순서는 아님
• 부분 순서는 동치 관계와도 연결되며, 동치 관계의 대칭성 대신 반대칭성이 들어간 구조
• 축구 실력 비교 예시에서 직접 또는 간접 비교 가능한 일부 인물만 있을 때는 선형 순서가 가능하지만, 서로 경기한 적 없는 사람이 포함되면 비선형 구조가 되어 부분 순서 형성
  • 부분 순서는 누가 더 낫다는 질문에 항상 결정적 답을 주지 못할 수 있음

• 사슬

  • 부분 순서는 여러 개의 선형 부분집합으로 구성될 수 있으며, 이런 선형 부분집합을 chain이라 부름
  • 예시로 $m \to g \to f$ 와 $d \to o$ 의 두 사슬 제시
  • 사슬들은 완전히 분리되어 있을 필요는 없으며, 모든 연결이 일대일로 이어져 하나의 사슬로 합쳐지지만 않으면 부분 순서 유지
  • 예시에서 $d \le g$ 와 $f \le g$ 는 알 수 있지만, $d$ 와 $f$ 의 관계는 미정 상태

• 최댓원소와 최솟원소

  • 어떤 원소 $a$ 가 모든 다른 원소 $x$ 에 대해 $x \le a$ 를 만족하면 그 원소는 greatest element
  • 일부 부분 순서에는 이런 원소가 존재하며, 예시 도식에서는 $m$ 이 greatest element
  • 여러 원소가 모두 다른 원소보다 크더라도 서로 동일하지 않으면 greatest element는 존재하지 않음
  • 같은 방식으로 least element도 정의

• 조인

  • 연결된 두 원소의 least upper bound를 join이라 부름
  • 정의 조건은 두 가지
    • $A \le G$ 이고 $B \le G$ 이어야 함
    • $A$ 와 $B$ 보다 큰 다른 임의의 원소 $P$ 에 대해 $G \le P$ 이어야 함
  • 한 원소가 다른 원소보다 크면 조인은 더 큰 원소 자체
  • 선형 순서에서는 임의의 두 원소의 조인이 곧 더 큰 원소
  • 동일한 크기의 여러 상계가 있으면 조인은 존재하지 않으며, 조인은 유일해야 함

• 미트

  • 두 원소보다 모두 작거나 같은 원소들 중 가장 큰 원소를 meet라 부름
  • 조인과 동일한 규칙이 반대 방향으로 적용

• Hasse 다이어그램

  • 이 절에서 사용하는 도식은 Hasse diagrams
  • 더 큰 원소를 항상 더 위에 배치하는 추가 규칙 존재
  • 화살표가 있다면 화살표가 향하는 점이 항상 더 위에 위치
  • 이 배치로 두 점의 위아래 관계만 보고 비교 가능하며, 조인도 공통으로 연결되는 원소 중 가장 낮은 것을 찾는 방식으로 식별 가능

• 색 혼합 부분 순서

  • 각 색이 자신을 포함하는 색으로 향하도록 정의한 color-mixing partial order 제시
  • 임의의 두 색의 조인은 두 색을 섞었을 때 만들어지는 색

• 나눗셈에 의한 수의 부분 순서

  • 수를 크기 비교가 아니라 나눗셈 가능성으로 정렬하면 부분 순서 형성
  • $a$ 가 $b$ 를 나누면 $a$ 가 $b$ 보다 앞선다고 정의
  • 예시로 $2 \times 5 = 10$ 이므로 2와 5는 10보다 앞서지만, 3은 10보다 앞서지 않음
  • 이 순서에서 조인은 최소공배수, 미트는 최대공약수

• 포함 부분 순서

  • 공통 원소 일부를 포함하는 여러 집합이 있을 때 inclusion order 정의 가능
  • 집합 $a$ 가 $b$ 를 포함하거나, 같은 말로 $b$ 가 $a$ 의 부분집합이면 $a$ 가 $b$ 보다 앞섬
  • 이 경우 조인은 합집합, 미트는 교집합
  • 각 집합에 포함된 색을 섞으면 앞서 본 색 혼합 부분 순서와 같은 구조 형성
  • 수의 나눗셈 순서는 반복을 허용하는 소수 집합 또는 prime powers의 포함 순서와 동형
  • 모든 수가 소수의 곱으로 정확히 하나의 방식으로 표현된다는 산술의 기본정리에 의해 확인 가능

Birkhoff의 표현 정리

• 색 혼합과 수의 나눗셈 부분 순서는 모두 어떤 기본 원소들의 가능한 집합 조합에 대한 포함 순서로 표현 가능
  • 전자에서는 기본 원소가 원색, 후자에서는 소수 또는 소수 거듭제곱
• 어떤 유한 부분 순서가 이런 방식으로 표현 가능한지는 Birkhoff’s representation theorem이 규정
  • 조건은 두 가지
    • 모든 원소 쌍에 대해 join과 meet 존재
    • join과 meet가 서로에 대해 분배적이어야 함. 표기 $∨$, $∧$ 를 쓰면 $x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z)$
• 모든 원소가 join과 meet를 가지는 부분 순서는 lattice
• 그 연산들이 서로 분배하면 distributive lattice
• 포함 순서를 구성하는 “소수적” 원소는 다른 원소들의 join으로 표현되지 않는 원소이며, join-irreducible elements라고 부름
• 정리는 각 distributive lattice는 자신의 join-irreducible elements의 inclusion order와 동형이라는 형태로도 서술
• distributive lattice가 아닌 부분 순서도 inclusion order와 동형일 수 있지만, 그 경우에는 모든 가능한 조합을 포함하지 않는 inclusion order와 대응

격자

• lattice는 모든 두 원소가 join과 meet를 가지는 부분 순서
  • 모든 lattice는 부분 순서이지만, 모든 부분 순서가 lattice는 아님
• 어떤 규칙으로 생성된 많은 부분 순서는 distributive lattice이며, 앞 절의 예시들도 완전하게 그리면 distributive lattice가 됨
• 색 혼합 예시에서는 위쪽에 검은 공, 아래쪽에 흰 공 추가
  • 그렇지 않으면 위쪽 세 원소는 join이 없고, 아래쪽 세 원소는 meet가 없음

• 유계 격자

  • greatest element와 least element를 모두 가진 lattice를 bounded lattice라 부름
  • 색 혼합 lattice에서는 검은 공이 greatest element, 흰 공이 least element
  • 모든 유한 lattice는 bounded라는 점도 함께 언급

순서 동형

• 순서 동형은 두 순서의 바탕 집합 사이의 가역 함수이면서, 순서 화살표를 보존하는 함수
• 수의 나눗셈 순서와 소수 포함 순서를 예로 들면 두 함수로 구성
  • 소수 포함 순서에서 수의 순서로 가는 함수는 집합 원소들의 곱셈
  • 수의 순서에서 소수 포함 순서로 가는 함수는 수를 곱으로 분해하는 prime factorization
• 순서 동형의 핵심 조건은 두 원소 $a$, $b$ 에 대해 $a \le b$ 이면 그리고 그럴 때에만 $F(a) \le F(b)$
• 이런 함수는 order-preserving 함수라고 부름

전순서

• preorder는 선형 순서에서 반대칭성을 제거한 구조이며, 반사성과 추이성만 유지
• 비교 가능성 기준으로 보면
  • 선형 순서는 $a \le b$ 또는 $b \le a$
  • 부분 순서는 둘 중 하나이거나 둘 다 아닐 수 있음
  • 전순서는 둘 중 하나, 둘 다 아님, 혹은 둘 다 참도 가능
• 전순서는 일상적 의미의 순서와는 다르며, 임의의 점에서 다른 점으로 화살표가 갈 수 있음
  • 축구에서 “누가 누구를 이겼는가”를 직접 또는 간접 승리까지 포함해 모델링하는 예시 제시
• 추이성 때문에 간접 승리도 직접 관계처럼 추가되며, 이 결과로 순환 관계가 있으면 여러 객체가 서로 모두 연결된 구조 형성

• 전순서와 동치 관계

  • 전순서는 부분 순서와 동치 관계의 중간 구조
  • 둘이 다른 지점인 (반)대칭성만 빠져 있기 때문
  • 전순서 안에서 서로 양방향으로 연결된 원소들은 대칭성을 만족하므로 동치 관계 이룸
  • 이런 원소들을 묶으면 전순서의 equivalence classes 형성
  • 각 동치류 사이의 연결만 옮기면 그 연결은 반대칭성을 만족하게 되어 부분 순서 형성
  • 따라서 모든 전순서에 대해 그 전순서의 동치류 위의 부분 순서 정의 가능

전순서와 범주

• 전순서의 추이성은 $a \le b$ 와 $b \le c$ 가 있으면 $a \le c$ 가 생기는 규칙이며, 관계의 합성으로 해석 가능
• 범주의 정의는 다음 두 조건 포함
  • 각 객체에 항등 사상 존재
  • 적절한 두 사상을 합성할 수 있고, 그 합성이 결합적이어야 함
• 전순서에서는 추이성이 합성을 담당하고, 반사성이 항등 사상 역할 수행
• 따라서 모든 전순서는 범주
• 일반 범주에는 두 객체 사이에 여러 사상이 있을 수 있지만, 전순서에서는 임의의 두 객체 사이에 최대 하나의 사상만 존재
  • $a \le b$ 가 있거나 없거나 둘 중 하나
• 모노이드가 객체 하나를 가진 범주인 것처럼, 순서는 두 객체 사이에 최대 하나의 사상만 갖는 범주로 정리 가능
• 이런 성질 때문에 전순서에서는 모든 도식이 가환

• 부분 순서와 전순서의 범주적 성질

  • 부분 순서와 전순서는 모두 전순서의 특수한 경우이므로 범주이기도 함
  • 전순서는 범주론에서 skeletal categories로 언급되며, 동형인 객체가 서로 구별된 채 공존하지 않는 범주

• 곱과 쌍대곱

  • 범주의 coproduct 정의는 두 사상 $A \to A + B$, $B \to A + B$ 와 보편 성질로 구성
  • 순서에서의 join 정의와 정확히 같은 형태
  • 순서에서는 모든 사상이 유일하므로 “더 큼”이 “유일한 사상이 존재함”으로 대응
  • 따라서 전순서의 범주에서 categorical coproduct는 join
  • 쌍대성에 따라 product는 meet에 대응

• 형식적 정의

  • 범주론에서 순서처럼 두 객체 사이에 최대 하나의 사상만 가지는 범주를 thin categories라고 부름
  • 모든 전순서는 이런 thin category로 볼 수 있으며, 반대로 그런 범주는 전순서로 해석 가능
  • thin category는 일반 범주보다 이해하기 쉬운 맥락에서 범주 개념 탐구에 활용
  • meet와 join을 이해하면 더 일반적인 범주 개념인 product와 coproduct 이해에도 도움 제공
  • 또한 객체 사이 여러 사상의 차이에 관심이 없고 단순한 구조만 필요할 때 유용한 틀