6
$\begingroup$

It is known that impredicativity + large eliminations + excluded middle is inconsistent. Prop is impredicative and consistent with excluded middle, but does not allow large eliminations (except when constructing witnesses whose type lives in Prop). Set and Type(i) allow large eliminations and are consistent with excluded middle, but are predicative. If we use the -impredicative-set flag, then Set is impredicative, but does not allow large eliminations for large inductive types.

Is there a universe in Coq which is impredicative, allows large eliminations on any inductive type that lives in it, but is consistent in the absence of the axiom of excluded middle?

$\endgroup$
6
$\begingroup$

No: strong elimination of large inductive types (SELIT) is itself inconsistent because it breaks the layering of universes by trivially allowing you to smuggle a large value in a Prop box and take it back out unscathed.

In Is Impredicativity Implicitly Implicit? I proposed a restriction on SELIT which is a bit more permissive than Coq's while still enjoying consistency (I still don't have a proof for it, tho I believe I'm almost there ;-)

$\endgroup$
4
  • $\begingroup$ Are strong eliminations the same thing as large eliminations? $\endgroup$ – NJay Mar 4 at 23:51
  • 1
    $\begingroup$ @NJay: Yes. AFAIK "strong elimination" is the more correct term, but I could never find a definitive answer on that all-too-important part of the question ;-) $\endgroup$ – Stefan Mar 5 at 19:35
  • $\begingroup$ What do you mean by "more correct", out of curiosity? Are there parts of the literature that refer to this as "strong elimination"? $\endgroup$ – NJay Mar 6 at 9:31
  • $\begingroup$ @NJay: Just a hunch, really. I have the suspicion that the term "large elimination" is a mix-up between "large types" and "strong elimination" (a bit like some people end up mixing "higher-order functions" and "first class functions" into "higher-class functions" or "first-order functions"). I believe I've seen the term "strong elimination" used more often, at least in the context of CIC. But I really don't know if any of this is actually true. $\endgroup$ – Stefan Mar 7 at 18:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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