Category Theory Part.02

범주론에서의 카테고리에 대해 알아보자.

프로그래밍과 무슨 관계가 있는가?

• 왜 이런 메타수학에서 사용되는 개념이 프로그래밍에서 사용될까?
• 프로그래밍에서 공통적으로 나타내는 개념들 사이의 관계가 카테고리의 조건에 딱 들어맞는다.
• 모든 프로그래밍 언어에는 타입이 있다.
• 그리고 그 타입들 사이에는 함수로 불리는 “합성할 수 있는 관계”가 있다.

• 앞에서 봤던 그림이다.
• 타입은 대상, 타입간의 관계는 사상으로 생각할 수 있겠다.
• 당연히 타입은 실제 값들을 대변하는 하나의 집합이다.
• 그렇기 때문에 그 함수는 그 값들이 연결되는 관계들의 집합이라 볼 수 있다.
• 3차원으로 생각하는 것이 보다 직관적이다.
• 다만, 여기서 얘기하는 함수는 “순수 함수”일 경우이다.
• 순수 함수일 경우 함수 합성을 무조건 결합법칙을 만족시키기 때문이다.
• 부작용이 있는 함수의 경우 이 법칙을 만족시킬 수 없다.
• 앞으로 이렇게 프로그래밍 언어의 타입과 함수들로 만족하는 카테고리를 “타입 카테고리”로 부르겠다.

Set Category

• 그림을 보면 알겠지만 집합 카테코리와 비슷하다는 것을 알 수 있다.
• 실제로도 집합 카테고리를 이해하는 것이 중요하다.
• 카테고리 이론의 기초를 이루는 개념 중 상당수가 집합과 집합 사이 정의될 수 있는 개념을,
• 임의의 대상 사이에 정의될 수 있는 개념으로 “일반화”시킨 것이기 때문이다.
• “사상”이라는 단어 자체가 집합과 집합 사이에 정의되는 함수 개념을 확장한 거다.
• 앞으로의 카테고리 이론에서 등장하는 개념을 집합론에서 정의되는 개념을 바탕으로 설명하도록 하겠다.

Isomorphism (동형 사상)

• 옛날 학교에서 “일대일 대응”함수에 대해 배운 적이 있었다.
• 한자로는 “전단사 함수”, 영어로는 “Bijection”이라고 한다.
• 이는 두 집합의 원소를 중복 / 누락 없이 모두 대응시키는 함수를 말한다.
• 이 개념을 카테고리로 확장해보자.
• 그런데, 확장했을 때 일대일 대응이라는 개념 자체를 확장할 수는 없다.
• 이 대응이라는 개념은 집합이라는 대상에만 적용되는 개념이기 때문이다.
• 다른 카테고리에 사상에 해당되는 개념이 “대응”에 국한될 것이라는 보장이 없으니까.
  • 집합인 경우에는 대응으로 사상이 설명되었지만, 다른 카테고리에서는 대응이라는 개념이 사상으로 설명될 수도 있고, 그렇지 않을 수도 있다.
• 그렇기에 우리는 전단사 함수가 다른 함수들과 다른 어떠한 특성을 추출해야 한다.

• 그 특성이 바로 “역함수”가 존재한다는 것이다.
• 중복 / 누락 없이 대응시키는 함수가 존재한다는 것은 역함수가 존재한다는 것과 동치이다.
• 즉, 역함수의 존재는 함수가 전단사 함수가 되기 위한 필요충분조건이다.

• Isomorphism은 위 조건을 일반화한 것으로 정의된다.
• A, B라는 대상이 있고, A에서 B로 가는 어떤 사상 f가,
• B에서 A로 가는 그것의 역사상 $f^{-1}$이 가지고 있으며,
• $f^{-1}\circ f=i{d}_A$, $f\circ f^{-1}=i{d}_B$를 만족시키는 경우,
• $f$를 Isomorphism이라고 한다.

Isomorphism의 의미

• 동형 사상은 대상들 사이의 어떠한 동치 관계를 주기 때문에 중요하다.
• 즉, 두 대상 사이에 동형 사상이 하나라도 있다면, 그 두 대상을 Isomorphic하다, 동형이라고 한다.

• A, B가 동형이고,
• B, C가 동형이라면
• A, B사이에는 $f$, $f^{-1}$가 존재하고,
• B, C사이에는 $g$, $g^{-1}$가 존재한다.
• A에서 C로 가는 사상을 정의한다면 $g\circ f$가 된다.
• C에서 A로 가는 사상을 정의한다면 $f^{-1}\circ g^{-1}$가 된다.
• 이 때, A, C 역시 역 사상이 정의되게 되어 A, C는 동형이 된다.
• 즉, 동형은 “동치 관계”이다.

동형 대상들의 특징

• Set에 대해 위 예시를 생각해보자.
• 동형이기 위해서는 일대일 대응이어야 하니, A, B, C 집합의 원소수는 모두 같아야 한다.
• 역 사상이 존재해야 한다는 정의를 통해 실제 사례를 보니, 다른 특징들이 발생한다.
• 이런 공통적 특성을 찾게 해주는 것이 동형 사상이라 생각할 수 있겠다.
  • 동형 사상이라면 그 대상들 사이에서 공통의 속성을 갖는다.

Monomorphism (단사 사상)

• 옛날에 공부했을 때 “일대일 대응”과 함께 나오는 개념이 있었다. “일대일 함수”이다.
• 한자로는 “단사 함수”, 영어로는 “Injection”이라고 한다.
• 이 경우, 집합 두개가 있을 때 한 집합의 원소를 중복 없이 다른 집합에 일대일로 대응시키는 함수를 말한다.
• 이 개념은 어떻게 일반화 할 수 있을까?
• 대응의 개념 말고, 다른 방식으로 이를 설명할 수 있는 방법을 찾아야 한다.

• A에서 B로 가는 단사 함수 f가 있다고 하자.
• 그리고 Z가 있고, A로 가는 사상 g1, g2가 있다고 하자.
• 단사 함수는 $f\circ g1=f\circ g2$를 만족시킬 경우,
• $g1=g2$이라는 성질을 가지고 있다.
• 왜일까?
• 단사 함수는 한 원소를 다른 원소에 중복 없이 대응시키는 함수이다.
• 그렇기에 $f(a)=f(b)$일 경우, $a=b$이다.
• 그러니, $f\circ g1=f\circ g2$라는 말은,
• $g1$과 $g2$로 부터 나오는 값들 모두가 같다는 말이다.
• 이는 곧 $g1=g2$라는 말과 같다.

• Monomorphism은 위 조건을 일반화한 것으로 정의된다.
• A, B라는 대상이 있고, A에서 B로 가는 어떤 사상 f가,
• Z가 있고, A로 가는 사상 g1, g2가 있을 때,
• $f\circ g1=f\circ g2$를 일 때, $g1=g2$이면,
• $f$를 Monomorphism이라고 한다.

Epimorphism (전사 사상)

• 예전에 보면, 공역과 치역이 같은 함수들도 있었다.
• 이러한 형태의 함수들도 부르는 이름이 있다.
• 한자로는 “전사 함수”, 영어로는 “Surjection”이라고 한다.
• 즉, 공역의 모든 원소에 대해 해당 원소로 가는 정의역의 원소가 적어도 하나 있는 것을 전사함수라 한다.
• 이 역시 일반화 하기 위해 전사 함수가 갖는 특징을 살펴보자.

• A에서 B로 가는 전사 함수 f가 있다고 하자.
• 그리고 Z가 있고, B로 가는 사상 g1, g2가 있다고 하자.
• 전사 함수는 $g1\circ f=g2\circ f$를 만족시킬 경우,
• $g1=g2$이라는 성질을 가지고 있다.
• 왜일까?

• 전사 함수는 공역의 모든 원소에 대해 해당 원소로 가는 정의역의 원소가 적어도 하나 있는 함수이다.
• $f$는 A의 부분집합에 대해서는 “전단사”함수라 볼 수 있다.
  • 전단사 함수는 $f(a)=f(b)$일 경우, $a=b$이다.
• 그렇기에 $g1\circ f=g2\circ f$라는 말은,
• $f$로 부터 나오는 값들 모두가 같다는 말이다.
• 당연히 $f(x)$의 결과가 모두 같고, 이 결과가 $g_1$과 $g_2$로 들어가서 나온 결과가 모두 같다는 말은,
• $g_1$과 $g_2$가 같다는 말이다.

• Epimorphism은 위 조건을 일반화한 것으로 정의된다.
• A, B라는 대상이 있고, A에서 B로 가는 어떤 사상 f가,
• Z가 있고, B로 가는 사상 g1, g2가 있을 때,
• $g1\circ f=g2\circ f$를 일 때, $g1=g2$이면,
• $f$를 Epimorphism이라고 한다.

Terminal Object (종단 대상)

• 원소가 하나뿐인 집합들은 독특한 특징이 있다.
• 모든 다른 집합으로 부터 이 원소가 하나인 집합으로 가는 함수를 생각해보았을 때,
• 딱 한개만 존재한다.
• A에서 원소가 하나인 집합 B로 가는 함수가 있다고 했을 때,
• A의 모든 원소가 B에 존재하는 하나의 원소로 갈 수 밖에 없다.
• 이는 일종의 상수 함수라 생각할 수 있다.

• 카테고리 이론에서는 이를 “종단 대상”이라고 한다.
• 카테고리의 모든 대상이 이 종단 대상으로 가는 사상을 단 하나만 가지고 있는 대상을 말한다.

Initial Object (초기 대상)

• 공집합은 반대로 모든 집합의 부분집합이다.
• 그렇기 때문에 임의의 모든 집합에 대해 공집합에서 해당 집합으로 가는 사상이 존재한다.
• 이 부분이 좀 어려울 수 있는데, 그렇게 정의하는 것이 수학적으로 엄밀하기 때문에 그렇게 한 듯하다.
• 이건 $a^0=1$이라던가, $a\ast 0=0$, $0!=1$ 등등의 수학적 정의와 같은 느낌이다.
• 있다고 하는 것이 보다 논리적으로 자연스럽기도 하다.
• 만약 공집합에 대해 해당 집합으로 가는 사상이 존재하지 않는다고 하면,
• 일단 공집합은 “항등 사상”이 없는 거다.
• 그말은 곧 Set이 카테고리가 못된다는 말이다.
  • 모든 대상은 그 대상으로 가는 항등 사상이 있어야 카테고리가 될 수 있음

• 이처럼 카테고리의 어떤 대상이 다른 모든 대상으로 가는 사상을 하나만 가지고 잇을 경우 이를 “초기 대상”이라고 한다.
• 이것도 다른 대상으로 사상이 하나밖에 없음을 생각해보면 알 수 있다.

카테고리 이론의 의미

• 이렇듯 카테고리 이론은 다르다고 생각했던 영역에서의 공통된 원리를 찾아 함께 다룰 수 있게 해준다.
• 프로그래밍에서 생각해본다면,
• Curry-Howard correspondence
  • 논리학의 증명 연산과 프로그래밍의 타입 체계가 대응된다는 개념
  • 다른 개념이라 생각했던 것을 묶어 생각할 수 있게 해주어 함수형 프로그래밍에 기여함.

서로다른 카테고리의 관계를 어떻게 찾는가?

• 그렇다면 서로다른 카테고리들을 어떤 방식으로 연결지을 수 있을지 고민해봐야 한다.
• 그 수단이 바로 Functor, 함자이다.

Reference

• 모나드의 모든 것
• FunctionalProgramming
• 커리-하워드 대응
• Curry–Howard correspondence
• 람다 대수