Warum ist es unmöglich, ein Induktionsprinzip für Zahlen der Kirche zu deklarieren?

17

Stellen Sie sich vor, wir definieren natürliche Zahlen in abhängig getippten Lambda-Berechnungen als Kirchenzahlen. Sie können folgendermaßen definiert werden:

SimpleNat = (R : Set) → R → (R → R) → R

zero : SimpleNat
zero = λ R z _ → z

suc : SimpleNat → SimpleNat
suc sn = λ R z s → s (sn R z s)

SimpleNatRec : (R : Set) → R → (R → R) → SimpleNat → R
SimpleNatRec R z s sn = sn R z s

Es scheint jedoch, dass wir mit dem folgenden Induktionsprinzip keine Kirchenzahlen definieren können:

NatInd : (C : Nat -> Set) -> (C zero) -> ((n : Nat) -> C n -> C (suc n)) -> (n : Nat) -> (C n)

Wieso ist es so? Wie kann ich das beweisen? Es scheint, dass das Problem darin besteht, einen Typ für Nat zu definieren, der rekursiv wird. Ist es möglich, die Lambda-Berechnung zu ändern, um dies zu ermöglichen?

Konstantin Solomatov
quelle

Antworten:

20

Die Frage, die Sie stellen, ist interessant und bekannt. Sie verwenden die sogenannte improvisatorische Kodierung der natürlichen Zahlen. Lassen Sie mich ein bisschen den Hintergrund erklären.

Bei einem gegebenen Typkonstruktor könnte uns der "minimale" Typ A interessieren , der A T ( A ) erfüllt . In Bezug auf die Kategorietheorie ist T ein Funktor und A ist die anfängliche T- Algebra. Wenn beispielsweise T ( X ) = 1 + X ist, entspricht A den natürlichen Zahlen. Wenn T ( X ) = 1 +T:TypeTypeAAT(A)TATT(X)=1+XA dann A ist die Art der endlichen binären Bäume.T(X)=1+X×XA

Eine Idee mit langer Geschichte ist , dass die anfängliche -Algebra der Typ A : = Π X : T y p e ( T ( X ) X ) X . (Sie verwenden die Agda-Notation für abhängige Produkte, aber ich verwende eine traditionellere mathematische Notation.) Warum sollte das so sein? Nun, A kodiert im Wesentlichen das Rekursionsprinzip für die anfängliche T- Algebra: Gegeben sei jede T- Algebra Y mit einem Strukturmorphismus f : T ( YT

A:=X:Type(T(X)X)X.
ATTY wir einen algebraischen Homomorphismus ϕ : A Y durch ϕ ( a ) = af:T(Y)Yϕ:AY So sehen wirdass A istschwachsicher initial. Damit es anfänglich ist, müssen wir wissen, dass ϕ auch einzigartig ist. Dies gilt nicht ohne weitere Annahmen, aber die Details sind technisch und unangenehm und erfordern das Lesen von Hintergrundmaterial. Zum Beispiel, wenn wir einen zufriedenstellenden zeigen parametricty Satzdann gewinnen wir, aber es gibt auch andere Methoden (wie die Definition von Massieren A und unter der Annahme des K -axiom und Funktion Extensionalität).
ϕ(a)=aYf.
AϕAK

T(X)=1+X

Nat=X:Type((1+X)X)X=X:Type(X×(XX))X=X:TypeX(XX)X.

Die technische Antwort auf Ihre Frage lautet: Es gibt Modelle der Typentheorie, in denen der Typ exotische Elemente SimpleNatenthält , die nicht den Ziffern entsprechen, und diese Elemente brechen darüber hinaus das Induktionsprinzip. Der Typ in diesen Modellen ist zu groß und ist nur eine schwache Anfangsalgebra.SimpleNat

Andrej Bauer
quelle
8
Ich stimme zu, dass die Antwort großartig ist, aber ein paar Referenzen könnten hier nützlich sein: Geuvers 'Artikel über die Nichtableitbarkeit der Induktion und Neel Ks und Derek Dreyers Artikel über das Erhalten (einiger) Induktionen aus der Parametrizität . Mir ist kein Artikel bekannt, der die Beziehung vollständig untersucht.
Cody
Ich bin nicht zu stark in Bezug auf Referenzen in diesem Bereich, danke @cody!
Andrej Bauer