6
$\begingroup$

It is not possible to derive induction for Church-encoded datatypes on the Calculus of Constructions (source). Moreover, according to the accepted answer to another question, it is also not possible to derive induction for Church-encoded datatypes on CoIC, despite the presence of inductive datatypes. As such, I wonder if we assume induction for Church-encoded Nat, cnat_ind; that is:

cnat_ind :
  (n : CNat) ->
  (P : CNat -> Type) ->
  (S : ∀ (n : CNat) -> P n -> P (csucc n)) ->
  (Z : P czero) ->
  P n

where CNat, csucc and czero are the usual Church-encoded Nat type and constructors, would that allow us to inhabit the empty type ∀ (P : *) -> P?

$\endgroup$
  • $\begingroup$ Probably worth noting that cnat_ind is inhabited in the "simple" proof-irrelevant model (where cnat only has one inhabitant. This gives a simple proof of consistency, but is a little usatisfying, since we also would like this to hold in the presence of czero =/= (csucc czero) (or some large elimination axiom). $\endgroup$ – cody Feb 3 at 19:25
9
$\begingroup$

One way to show that it is consistent to add cnat_ind is to internalize parametricity, i.e., we extend the type system with enough structure so that it can prove its own parametricity, from which it then follows that the Church encoding of natural numbers does indeed give natural numbers. See for instance the PhD dissertation Internalizing Parametricity by Guilhem Moulin.

$\endgroup$
  • 1
    $\begingroup$ Is there by chance any simplified implementation of this proposal available? I was following along until the part of hypercubes and so on. The notation from page 31 onwards is kinda cryptic... $\endgroup$ – MaiaVictor Jan 24 at 16:01
  • 1
    $\begingroup$ I don't know about "implementation" but you could try the corresponding paper A Presheaf Model of Parametric Type Theory. $\endgroup$ – Andrej Bauer Jan 25 at 8:08

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.