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?

Improve this question
$\endgroup$
1
  • $\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
    Commented Feb 3, 2019 at 19:25

1 Answer 1

Reset to default
10
$\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.

Improve this answer
$\endgroup$
2
  • 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
    Commented Jan 24, 2019 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
    Commented Jan 25, 2019 at 8:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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