Dlaczego nie można zadeklarować zasady indukcji cyfr Kościoła

Wyobraźmy sobie, że zdefiniowaliśmy liczby naturalne w rachunku różniczkowym lambda w zależności od typu jako liczby kościelne. Można je zdefiniować w następujący sposób:

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

Wydaje się jednak, że nie możemy zdefiniować cyfr kościelnych za pomocą następującego rodzaju zasady indukcji:

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

Dlaczego tak jest Jak mogę to udowodnić? Wydaje się, że problem polega na zdefiniowaniu typu Nat, który staje się rekurencyjny. Czy można zmienić rachunek lambda, aby to umożliwić?

Pytanie, które zadajesz, jest interesujące i znane. Używasz tak zwanego impredykatywnego kodowania liczb naturalnych. Pozwól, że wyjaśnię trochę tła.

Biorąc pod uwagę konstruktor typu , możemy być zainteresowani „minimalnym” typem A spełniającym A ≅ T ( A ) . Pod względem teorii kategorii T jest funktorem, a A jest początkową algebrą T. Na przykład, jeśli T ( X ) = 1 + X, to A odpowiada liczbom naturalnym. Jeśli T ( X ) = 1 $T : \mathsf{Type} \to \mathsf{Type}$$A$$A \cong T(A)$$T$$A$$T$$T(X) = 1 + X$$A$ a następnie A jest rodzajem skończonych drzew binarnych.$T(X) = 1 + X \times X$$A$

Pomysł z długą historią jest to, że początkowy -algebra jest typu : = Π X : T y P e ( T ( X ) → X ) → X . (Używasz notacji Agda dla produktów zależnych, ale używam bardziej tradycyjnej notacji matematycznej.) Dlaczego tak powinno być? Cóż, A zasadniczo koduje zasadę rekurencji dla początkowej T- algebry: biorąc pod uwagę dowolną T- algebrę Y o morfizmie struktury f : T ( $T$

$$A \mathrel{{:}{=}} \prod_{X : \mathsf{Type}} (T(X) \to X) \to X.$$ $A$$T$$T$$Y$ , otrzymujemy homomorfizm algebry ϕ : A → Y przez ϕ ( a ) = $f : T(Y) \to Y$$\phi : A \to Y$ Widzimy więc, że A jestz pewnościąsłabopoczątkowe. Aby było to początkowe, musielibyśmy wiedzieć, że ϕ jest również wyjątkowy. Nie jest to prawdą bez dalszych założeń, ale szczegóły są techniczne i nieprzyjemne i wymagają przeczytania jakiegoś materiału tła. Na przykład, jeśli potrafimy wykazać zadowalającetwierdzenie parametryczne, wówczas wygrywamy, ale są też inne metody (takie jak masowanie definicji A i zakładanie K- maksiomu i ekstensywności funkcji). $$\phi(a) = a \, Y \, f.$$ $A$$\phi$$A$$K$

$T(X) = 1 + X$

$$\mathsf{Nat} = \prod_{X : \mathsf{Type}} ((1 + X) \to X) \to X = \prod_{X : \mathsf{Type}} (X \times (X \to X)) \to X = \prod_{X : \mathsf{Type}} X \to (X \to X) \to X.$$

Techniczna odpowiedź na twoje pytanie brzmi: istnieją modele teorii typów, w których typ SimpleNatzawiera egzotyczne elementy, które nie odpowiadają cyfrom, a ponadto elementy te łamią zasadę indukcji. Typ SimpleNatw tych modelach jest zbyt duży i jest tylko słabą algebrą początkową.