1P by GN⁺ 13시간전 | ★ favorite | 댓글 1개
  • 원소 집합 위의 이항 관계반사성·추이성·반대칭성 같은 법칙을 만족할 때 순서 구조 성립
  • 선형 순서는 모든 두 원소가 비교 가능한 구조이며, 전순성을 제거하면 부분 순서가 됨
  • 부분 순서에서는 사슬, 최댓원소·최솟원소, 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 boundjoin이라 부름
    • 정의 조건은 두 가지
      • $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이 규정
    • 조건은 두 가지
      • 모든 원소 쌍에 대해 joinmeet 존재
      • 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는 모든 두 원소가 joinmeet를 가지는 부분 순서
    • 모든 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 이해에도 도움 제공
    • 또한 객체 사이 여러 사상의 차이에 관심이 없고 단순한 구조만 필요할 때 유용한 틀
Hacker News 의견들
  • 좀 더 정통파 방식으로 category theory를 배우고 싶다면, 많은 사람들이 무료인 Tom Leinster의 Basic Category Theory를 추천함. 나도 곧 차근차근 볼 예정인데, 훑어본 인상으로는 TFA 같은 자료보다 더 수학적이지만 꽤 좋았음. 특히 category theory가 왜 하나의 연구 분야로 성립하는지 설명하는 데 더 설득력이 있었음
    • 다만 이 책도 그렇고 category theory 책 전반이 대체로 학부 수준 수학에 이미 익숙한 사람을 기준으로 쓰였다고 봄. algebraic structures, linear algebra, topology에 익숙하지 않다면 중간중간 다른 자료를 함께 찾아봐야 할 가능성이 큼. 그리고 category theory는 자기가 통합하려는 의미론적 맥락을 어느 정도 알고 있을 때 더 인상적으로 다가옴. 예를 들어 책에서 initial property를 처음엔 자명하게 보이게 소개하지만, 임의의 구조에서는 그냥 성립하는 게 아니라는 점을 알아차려야 핵심이 보임
  • 수학을 줄줄 검산할 생각 없이 글을 선의로 읽더라도, 글에 나온 이 JavaScript 예시만 봐도 신뢰가 흔들렸음: [1, 3, 2].sort((a, b) => { if (a > b) { return true } else { return false } }) 같은 코드는 유효한 comparator가 아님. API는 음수, 0, 양수를 기대하는데 boolean을 반환하고, 내 Chrome에서는 [1, 3, 2] 그대로 나왔음. 내가 보기에 글의 수학적 정확도도 이와 비슷한 수준이었고, 자세한 지적은 이 댓글에 정리해뒀음
    • 왜 그 코드가 꼭 JavaScript라고 가정하는지 의문이었음. 내가 본 바로는 원문 어디에도 언어 표시가 없었음
  • 내가 보기엔 추상수학 전반, 특히 category theory의 진짜 장벽은 사람들이 "linear order"를 이해 못해서가 아님. 일상과 너무 멀리 떨어져 있어서 쓸모없어 보이는 감각이 더 큰 문제였음. 마치 완전히 매끈한 유리 위에 물을 붓는 느낌이었음
    • category theory 쪽에도 처음 들었을 때 머리가 띵하는 사실 같은 게 있는지 궁금했음. 예전에 group theory로 5차 초과 다항식에 일반적인 해석해가 없다는 걸 증명할 수 있다는 얘길 처음 들었을 때 정말 놀랐는데, category theory에도 그런 대응물이 있는지 묻고 싶었음
    • 이 지적이 생각보다 더 맞는 말이라고 느낌. 수학의 목적이 정확한 사고에 있다면, 그 글은 너무 부정확했음. 아무도 그걸 신경 쓰지 않거나 못 본 듯해서 오히려 놀라웠고, 내 다른 댓글에 아주 불완전하지만 오류 목록을 적어뒀음. 내 결론은 일반 독자에게 이런 글이 별 도움이 안 된다는 쪽이었음. 틀린 수학도 맞는 수학과 비슷하게 소비된다면 실용성은 더 의심스러워짐
    • 나는 이건 가르치는 방식의 문제라고 봄. order theory는 프로그래밍에서 아주 유용함. 핵심은 세상이 totally ordered comparator 중심이라고 보는 습관에서 벗어나는 일이고, preorder가 특히 강력하다고 느낌. 예를 들어 state machine transition은 어떤 경우 preorder로 볼 수 있고, 그렇게만 만들 수 있으면 복잡한 테스트를 <= 성립 여부를 확인하는 문제로 줄일 수 있음. 물론 익숙해지기까지 생각이 많이 필요하지만, 반대로 일상적인 작업에 계속 끌어오면 점점 친숙해짐. 그러면 테스트를 보면서 "이 조건식은 어떤 preorder로 모델링되겠네" 같은 감각이 생김
    • 나는 이걸 박사과정 2년쯤 지나서야 의식적으로 깨달았음. 그리고 그 순간, 학위를 마치면 분야를 떠나고 싶다는 걸 바로 알게 됐음
  • 글쓴이의 문체와 괄호 남용이 너무 괴로웠음. 진짜 parenthetic material은 드문 편이고, 좋은 기술 글쓰기는 괄호를 훨씬 절제해서 쓴다고 생각함
    • 인터넷 전반, 특히 HN 댓글에서 괄호 표현이 과하게 많이 보인다고 느낌. 나도 가끔 그러긴 하지만, 중첩된 괄호를 설정한 단계 이상에서 접거나 취소선 처리해주는 브라우저 확장이 있으면 꽤 유용할 듯했음
    • 나는 사람의 ADHD 기질을 괄호 사용량으로 어느 정도 읽을 수 있다고 농담처럼 느낌. 물론 Lisp 프로그래머라면 예외일 수 있음
  • category theory를 깊게 읽어본 건 아니지만, 프로그래머가 원래 해오던 일을 좀 더 수학적으로 표현한 버전처럼 느껴졌음. 추상화 수준을 오르내리고, 그래프를 다루고, 한 종류의 object를 다른 종류로 바꾸는 함수를 다루는 식의 사고와 꽤 닮아 보였음
  • category theory를 사실상 화살표만의 이론으로 설명하는 방식도 가능하다고 봄. 모든 object는 정의상 identity arrow를 가지니, 그 identity arrow를 object 자체와 대응시키면 됨. 그런 관점에서는 object가 일종의 syntactic sugar처럼 보임
    • 나는 글을 열고 색깔 M&M 그림들로 가득한 걸 보자마자 이 점이 거의 즉시 자명하게 느껴졌고, 곧바로 닫아버렸음
  • 예전에 공책과 연필로 이런 종류의 도식을 그리던 사람을 본 적이 있음. 그땐 graph theory로 보였고, 내가 말을 걸 타이밍을 놓친 게 아쉬웠음. 그 사람이 취미처럼 작업하는 것처럼 보여서 더 궁금해졌음. 이런 이론이나 수학으로 쉽게 만들 수 있는 퍼즐이 있는지, 실무나 연구하는 사람들에게 추천을 묻고 싶었음
    • 나는 algebraic graph theory에서 s-arc transitive graphs 관련 작업을 해왔는데, 의외로 실제 그래프를 직접 그릴 일은 거의 없었음. 대부분은 group actions, automorphisms, arc-stabilisers 같은 걸 가지고 추론하는 일이었음. 실제로 어떤 식인지 궁금한 사람을 위해 간단한 메모를 여기에 올려뒀음. 내가 연구한 s-arc-transitivity 자체를 다루진 않지만, 분야의 분위기는 느낄 수 있음. graph theory의 상당 부분은 구체적인 그래프를 전혀 그리지 않고도 진행됨
  • 나는 2015년 석사 때 category theory를 공부하면서 순서 관계가 data structures부터 algorithms까지 정말 많은 것에 영향을 준다는 걸 봤음. 꽤 기초적이면서도 핵심적인 내용으로 느껴졌음
  • 이걸 보니 Haskell의 type classes가 떠올랐음. 자체 규칙 집합으로 order 개념을 우아하게 정의하면서, 관계를 깔끔하게 포착하는 방식이 닮아 보였음
  • 이 자료는 order relations를 정말 명확하게 풀어준다고 느낌. 구조를 시각화해주니 추상적인 개념이 훨씬 소화하기 쉬워졌음