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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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 ;-)

Improve this answer
$\endgroup$
5
  • $\begingroup$ Are strong eliminations the same thing as large eliminations? $\endgroup$
    – NJay
    Mar 4, 2021 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, 2021 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, 2021 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, 2021 at 18:16
  • 1
    $\begingroup$ I've heard "large elimination" far more often than "strong elimination". For instance here, github.com/RobertHarper/hott-notes/blob/… with a conventional definition of large elimination, and no mention of "large elimination" in the entire notes. this may be the sort of definition that is really sensitive to the underling language constructs. $\endgroup$
    – user833970
    Sep 28, 2021 at 14:54

Your Answer

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

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