# 범주론 그림으로 보는 순서 > Clean Markdown view of GeekNews topic #28693. Use the original source for factual precision when an external source URL is present. ## Metadata - GeekNews HTML: [https://news.hada.io/topic?id=28693](https://news.hada.io/topic?id=28693) - GeekNews Markdown: [https://news.hada.io/topic/28693.md](https://news.hada.io/topic/28693.md) - Type: GN+ - Author: [neo](https://news.hada.io/@neo) - Published: 2026-04-20T03:41:38+09:00 - Updated: 2026-04-20T03:41:38+09:00 - Original source: [abuseofnotation.github.io](https://abuseofnotation.github.io/category-theory-illustrated/04_order/) - Points: 1 - Comments: 1 ## Topic Body - 원소 집합 위의 **이항 관계**가 **반사성·추이성·반대칭성** 같은 법칙을 만족할 때 순서 구조 성립 - **선형 순서**는 모든 두 원소가 비교 가능한 구조이며, 전순성을 제거하면 **부분 순서**가 됨 - 부분 순서에서는 **사슬**, **최댓원소·최솟원소**, **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 이해에도 도움 제공 - 또한 객체 사이 여러 사상의 차이에 관심이 없고 단순한 구조만 필요할 때 유용한 틀 ## Comments ### Comment 55855 - Author: neo - Created: 2026-04-20T03:41:39+09:00 - Points: 1 ###### [Hacker News 의견들](https://news.ycombinator.com/item?id=47813668) - 좀 더 **정통파** 방식으로 category theory를 배우고 싶다면, 많은 사람들이 무료인 Tom Leinster의 [Basic Category Theory](https://arxiv.org/pdf/1612.09375)를 추천함. 나도 곧 차근차근 볼 예정인데, 훑어본 인상으로는 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]` 그대로 나왔음. 내가 보기에 글의 수학적 정확도도 이와 비슷한 수준이었고, 자세한 지적은 [이 댓글](https://news.ycombinator.com/item?id=47814213)에 정리해뒀음 - 왜 그 코드가 꼭 **JavaScript**라고 가정하는지 의문이었음. 내가 본 바로는 원문 어디에도 언어 표시가 없었음 - 내가 보기엔 추상수학 전반, 특히 category theory의 진짜 장벽은 사람들이 "linear order"를 이해 못해서가 아님. 일상과 너무 멀리 떨어져 있어서 **쓸모없어 보이는 감각**이 더 큰 문제였음. 마치 완전히 매끈한 유리 위에 물을 붓는 느낌이었음 - category theory 쪽에도 처음 들었을 때 **머리가 띵하는 사실** 같은 게 있는지 궁금했음. 예전에 group theory로 5차 초과 다항식에 일반적인 해석해가 없다는 걸 증명할 수 있다는 얘길 처음 들었을 때 정말 놀랐는데, category theory에도 그런 대응물이 있는지 묻고 싶었음 - 이 지적이 생각보다 더 맞는 말이라고 느낌. 수학의 목적이 정확한 사고에 있다면, 그 글은 너무 **부정확**했음. 아무도 그걸 신경 쓰지 않거나 못 본 듯해서 오히려 놀라웠고, [내 다른 댓글](https://news.ycombinator.com/item?id=47814213)에 아주 불완전하지만 오류 목록을 적어뒀음. 내 결론은 일반 독자에게 이런 글이 별 도움이 안 된다는 쪽이었음. **틀린 수학**도 맞는 수학과 비슷하게 소비된다면 실용성은 더 의심스러워짐 - 나는 이건 가르치는 방식의 문제라고 봄. 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 같은 걸 가지고 추론하는 일이었음. 실제로 어떤 식인지 궁금한 사람을 위해 간단한 메모를 [여기](https://susam.net/26c.html#algebraic-graph-theory)에 올려뒀음. 내가 연구한 s-arc-transitivity 자체를 다루진 않지만, 분야의 분위기는 느낄 수 있음. graph theory의 상당 부분은 구체적인 그래프를 전혀 그리지 않고도 진행됨 - 나는 2015년 석사 때 category theory를 공부하면서 **순서 관계**가 data structures부터 algorithms까지 정말 많은 것에 영향을 준다는 걸 봤음. 꽤 **기초적이면서도 핵심적인 내용**으로 느껴졌음 - 이걸 보니 Haskell의 **type classes**가 떠올랐음. 자체 규칙 집합으로 order 개념을 우아하게 정의하면서, 관계를 깔끔하게 포착하는 방식이 닮아 보였음 - 이 자료는 **order relations**를 정말 명확하게 풀어준다고 느낌. 구조를 시각화해주니 추상적인 개념이 훨씬 소화하기 쉬워졌음