# Impredicativity + large eliminations (with no excluded middle) in Coq

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?

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 ;-)

• Are strong eliminations the same thing as large eliminations?
– NJay
Mar 4, 2021 at 23:51
• @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 ;-) Mar 5, 2021 at 19:35
• What do you mean by "more correct", out of curiosity? Are there parts of the literature that refer to this as "strong elimination"?
– NJay
Mar 6, 2021 at 9:31
• @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. Mar 7, 2021 at 18:16
• 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. Sep 28, 2021 at 14:54