초기 대수

이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "초기 대수학" – 뉴스 · 신문 · 책 · 학자 · JSTOR (2017년 12월) (이 템플릿 메시지를 제거하는 방법과 시기 학습)

수학에서 초기 대수학은 주어진 내분자 F에 대한 F-알게브라의 범주에 있는 초기 개체다. 이 초기성은 유도 및 재귀에 대한 일반적인 체계를 제공한다.

예

펑터 1 + X

Endofunctor F : Set → Set sending X를 1 + X로 설정한다. 여기서 1은 범주의 단자 객체인 원포인트(싱글톤) 세트다. 이 Endofunctor에 대한 대수학이란 함수 f : (1 + X) → X와 함께 집합 X(대수의 반송파라 불림)이다. 이러한 함수를 정의하는 것은 점 $x{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle X}$ ${\displaystyle$ x$\in X}$와 함수 X → X를 정의하는 양이다. 정의

${\displaystyle {\begin{aigned}\operatorname {zero} \colon 1&\longrightarrow \mathbf {N} \\*&\longmapsto 0\end{aigned}}}}$

그리고

${\displaystyle {\begin}\operatorname {such} \colon \mathbf {N} &\longrightarrow \mathbf {N} \n&\longmapsto n+1\end{정렬}}}$

그런 다음 자연수의 N을 함수 [제로,수치]: 1 + N → N과 함께 설정한 것이 초기 F-algebra이다. The initiality (the universal property for this case) is not hard to establish; the unique homomorphism to an arbitrary F-algebra (A, [e, f]), for e: 1 → A an element of A and f: A → A a function on A, is the function sending the natural number n to fⁿ(e), that is, f(f(…(f(e))…)), the n-fold application of f to e.

자연수 집합은 이 functor에 대한 초기 대수(점수는 0이고 함수는 후속함수)의 캐리어다.

펑터 1 + N × (-)

두 번째 예에서는 집합 범주의 Endofunctor 1 + N × (-)를 고려하십시오. 여기서 N은 자연수의 집합입니다. 이 Endofunctor에 대한 대수학은 함수 1 + N × X → X와 함께 설정된 X이다. 그러한 함수를 정의하려면 점 ${\displaystyle x}$ ${\displaystyle \in }$ X ${\displaystyle x\in X}$와 함수$$ N × X → X가 필요하다. 유한한 자연수 리스트의 집합은 이 functor의 초기 대수다. 포인트는 빈 리스트로, 함수는 cons로, 숫자와 유한 리스트를 취하며, 숫자가 맨 앞에 있는 새로운 유한 리스트를 반환한다.

이진 코프로덕트가 있는 범주에서 방금 주어진 정의는 각각 자연수 개체와 목록 개체의 일반적인 정의와 동일하다.

최종 연골

Dally, final collgebra는 F-collgebras 범주의 말단 물체다. 최종성은 코인전도와 핵심구조에 대한 일반적인 틀을 제공한다.

예를 들어, 이전과 동일한 functor 1 + (-)를 사용하여 collgebra는 함수 f : X → (1 + X)와 함께 집합 X로 정의된다. 그러한 함수를 정의하는 것은 f(x)가 1에 속하는$$ $x{\displaystyle }$ ${\displaystyle \in }$ X ${\displaystyle$ x$\in X}$에 의해 도메인이 형성되는 부분 함수 f': X ⇸ Y를 정의하는 것과 같다. 그러한 구조는 f′이 정의되지 않은 X₀, f′에 의해 X로₀ 매핑되는 X₁, f′ 등에 의해 X로₁ 매핑되는 X₂, X의 나머지 요소를 포함하는 X의_ω 집합체라고 볼 수 있다. $이$를 통해 새로운 원소 Ω으로 확장된 자연수 집합으로 구성된$$ $displaystyle$ $\cup$\\$omega \}}}$ 집합 N ${\displaystyle {\cup }^{}}$ ${\$은 양의$$ 나투랄에 대한 선행 함수(후속 함수의 역)가 된다., 그러나 새로운 원소 Ω의 ID와 같은 작용을 한다: f(n + 1) = n, f(Ω) = Ω. 이 세트 $N{\displaystyle \mathbf{}}$ ${\displaystyle \cup }${$$ {\$displaystyle \mathbf {N} \cup$ \cup $\{\omega \}}$은 1 +)의 최종 합금(-)의 캐리어인 결합수 집합으로 알려져 있다.

두 번째 예에서는 이전과 동일한 펑터 1 + N × (-)를 고려하십시오. 이 경우 최종 합금선의 운반자는 무한대뿐만 아니라 유한한 모든 자연수 목록으로 구성된다. 이 작업은 목록이 비어 있는지 여부를 테스트하는 시험 기능이며, 비어 있지 않은 목록에 정의된 해체 함수는 입력 목록의 머리와 꼬리로 구성된 쌍을 반환하는 기능이다.

정리

• 초기 알헤브라는 미미하다(즉, 적절한 하위 알헤브라가 없다).
• 최종 결합형은 단순하다(즉, 적절한 인용구가 없다).

컴퓨터 공학에서 사용하다.

목록과 나무와 같이 프로그래밍에 사용되는 다양한 유한 데이터 구조는 특정 엔드폰터의 초기 알제브라로 얻을 수 있다. 주어진 엔도분자에 대한 초기 알헤브라가 여러 개 있을 수 있지만, 그것들은 이소모르프까지 유일하며, 이것은 비공식적으로 데이터 구조의 "관측 가능한" 특성이 초기 대수로서 정의함으로써 적절하게 포착될 수 있다는 것을 의미한다.

요소가 집합 A의 멤버인 목록의 유형 목록(A)을 얻으려면 목록 형식 작업이 다음과 같음을 고려하십시오.

• ${\displaystyle \mathrm {nil} \colon 1\to \mathrm {List}(A)}$
• ${\displaystyle \mathrm {cons} \colon A\times \mathrm {List}(A)\to \mathrm {List}(A)}$

하나의 기능으로 결합하여 다음과 같은 기능을 제공한다.

• ${\displaystyle [\mathrm {nil} ,\mathrm {cons} ]\colon(1+A\times \mathrm {List}(A)\mathrmatrm {List}(A),}$

X를 1 +(A × X)로 보내는 끝단 F를 위한 F-알지브라로 만든다. 사실, 이것은 초기 F-알지브라 입니다. 초기성은 Haskell과 ML과 같은 기능 프로그래밍 언어에서 foldr로 알려진 기능에 의해 확립된다.

마찬가지로 잎에 원소가 있는 이항 트리는 초기 대수로서 얻을 수 있다.

• ${\displaystyle [\mathrm {tip} ,\mathrm {join} ]\colon A+(\mathrm {Tree})(A)\times \mathrm {Tree}(A)\to \mathrmatrm {Tree}(A).}$

이렇게 얻은 유형을 대수 데이터 유형이라고 한다.

functor F와 함께 최소 고정 점 구조를 사용하여 정의한 형식은 파라메트릭성이 형식을 유지한다면 초기 F-algebra로 간주할 수 있다.^[1]

이중으로, 가장 큰 고정점 개념과 단자 F-석탄점 사이에 유사한 관계가 존재하며, 유도형식의 응용이 있다. 이는 강력한 표준화 속성을 유지하면서 잠재적으로 무한 확장 가능한 개체를 허용하는 데 사용될 수 있다.^[1] 강력한 정규화(각 프로그램이 종료됨) 자선 프로그래밍 언어에서, 동전 유도 데이터 유형은 놀라운 결과를 얻기 위해 사용될 수 있다. 예를 들어, Ackermann 기능과 같은 "강력한" 기능을 구현하기 위한 조회 구조를 정의하는 것이다.^[2]

참고 항목

• 대수 데이터 유형
• 카타모르피즘
• 아나모르피즘

메모들

외부 링크

• Varmo Vene에 의한 유도형 및 유도형 범주형 프로그래밍
• 1990-2014년 글래스고 대학 필립 와들러의 재귀형 무료!
• J.J.M.Rutten과 D.의 동시성을 위한 초기 대수학 및 최종 연골 의미론 투리
• CLiki의 초기성 및 최종성
• Oleg Kiseyov의 Tagless 최종 통역자 입력