Conversation started Mar 25, 2022 at 14:40.
Mar 25, 2022 14:40
Looks like a lot of people don't like to talk about the inconsistencies and unsound assumptions they snuck into their formal systems or wish to sneak in, including Agda. This rare exception says:
> The grammar of possible size expressions [...] is usually restricted to size variables and addition by constants, so that sizes are nicely inferrable and don’t require complex solvers. However, this does restrict the number of things we can express. This is why most sized type theories (and Agda) also has an infinite size ∞. Just as Nat [s] represents a natural no larger than s, Nat [∞] then represents any possible natural, also referred to as a full natural, in contrast to sized naturals.
> Notice that all sizes are strictly smaller than ∞, including itself. This is how both the size parameter and the size argument of succ are ∞; if not, this function wouldn’t be implementable. This poses a problem for Agda in particular, because we simultaneous expect < to be a well-behaved strict order, but ∞ clearly violates this expectation. These two simple facts yield an inconsistency, as described by this Agda issue.
> There are a few proposed solutions to this problem, most of them centered around removing the ∞ < ∞ property of the infinite size. [...] The key insight is that it’s not that an unsized natural inherently has no possible size to it, but rather that it has some unknown size. We can express this in the type theory using an existentially-quantified inductive type, ∃α. Nat [α].
> It then appears that this solves the problem of the infinite size. There’s no way to reproduce the inconsistency in Agda where an infinite size is applied to well-founded induction because infinite sizes are “actually” just unknown concrete sizes. But ...
> Existential Size Quantification is Still Insufficient. You can imagine extending this technique for circumventing the infinite size for more inductive types than just the naturals. However, it only works for simple inductive types; when we extend to general inductive types, where the recursive argument of constructors can be a function that returns the inductive, it starts to break down.
> We now essentially have a new constructor for sizes. [...] Given that we’ve been freely using fst and snd on existential size pairs, it seems that we should promote sizes to being proper terms. (Incidentally, in Agda they are.) Assuming we have some type Size, we can write down the typing rules for the introduction forms.
in Sandbox, 7 secs ago, by user21820
Γ ⊢ s : Size -------------- Γ ⊢ suc s : Size Γ ⊢ A : Set ℓ Γ ⊢ f : A → Size ------------------ Γ ⊢ lim A f : Size
> Notice that we have an unbound universe level ℓ. This suggests that we need to pass ℓ as an argument to either lim itself or to Size. Since we’d like to treat sizes uniformly and be able to pass them around without worrying about the level, we’ll adopt the former solution. If we think of Size as an inductive type in Agda, this forces us to put it in Setω. This is a problem because inductive types contain a size as a parameter, meaning that they, too, all need to live in Setω.
> Take the naturals, for example: morally, they should be in Set, but [defining them in Agda using the above Sizes] would require
data Nat (α : Size) : Setω where ...
The problem would be solved if we could put Size in Set instead. In Agda, this requires Set to be impredicative, in a sense, which when combined with large elimination of types in Set in general would be inconsistent. It’s yet unclear to me whether only allowing Size to be in Set as a primitive formation rule would be consistent. Mar 25, 2022 15:15
Oh and I finally found the github issue on Agda: Equality is incompatible with sized types #2820. It was opened on 2017/10/27 and has lasted 3.5 years before it was finally 'resolved' on 2021/05/29 by simply blindly making it 'unsafe' (Sized types are no longer safe #5354). Clearly, almost nobody really cares about correctness of their formal systems. Very disappointing.
Mar 25, 2022 16:06
LOL. Everyone seems to be working blindly with impredicative stuff: Coq Issue #9458: Future of -impredicative-set, F* Issue #360: Paradoxes from impredicative polymorphism + excluded middle + large elimination, ...
23 hours later…
Mar 26, 2022 14:45
If "every intuition from set theory goes against [CoC]", and "slight modifications will jinx the consistency", why should we accept such a weird system? How do we even know it is consistent to begin with? — user21820 2 hours ago
@user21820 Yes, and it is exactly my belief that we shouldn't accept such a system! — Trebor 14 mins ago
72 hours later…
Mar 29, 2022 14:27
in Discussion between user21820 and Trebor, 2 days ago, by user21820
@Trebor: Oh and here's an unrelated question: The author of this PDF on CIC said "Impredicative systems are powerful but also very fragile in the sense that impredicativity does not interact very well with other features leading rapidly to inconsistent systems.". Do you agree, or do you actually think there is absolutely nothing wrong with impredicative Prop?
in Discussion between user21820 and Trebor, 2 days ago, by Trebor
@user21820 Maybe there's something wrong. That's debatable. But there's nothing wrong to claim that impredicative
Set
and Prop
is dangerous.in Discussion between user21820 and Trebor, 2 days ago, by Trebor
Personally I am very slightly in favor of predicative Prop.
in Discussion between user21820 and Trebor, 22 hours ago, by user21820
@Trebor: I think I have a better understanding of the issue of impredicative Prop, and I'd like to tell you what I think and hear your view on it. I think whether or not there is a problem with impredicative Prop depends on what we intend it to mean. In the PDF on CIC that I had quoted above, it seems that they would like to interpret "Π(x:A) . B" as a 'finished' type, and so the rule ( ( Γ ⊢ A : Type[i] ) ; ( Γ , x : A ⊢ B : Prop ) ⊢ ( Γ ⊢ Π(x:A) . B : Prop ) ) is indeed problematic.
in Discussion between user21820 and Trebor, 22 hours ago, by user21820
In particular, if we imagine each universe as being constructed (by an abstract generative process) based on the lower universes, then we have to finish Prop before we can construct Type[1], but the impredicative rule essentially breaks that. In particular, if every type is intended to be some kind of collection/set, then "Π(x:A) . B" may never be finished if A = Type[1], simply because Type[1] may never be finished.
in Discussion between user21820 and Trebor, 22 hours ago, by user21820
To evade an outright problem, one might think of the universes as being generated not necessarily in order of their hierarchy. But then one must accept that any type T may never be finished at any point; its membership may never stabilize. This applies even if ( T : Prop ) simply because of the impredicative rule. This implies that we cannot view membership in T classically, and so LEM would be completely unjustifiable.
in Discussion between user21820 and Trebor, 21 hours ago, by user21820
So basically, impredicative Prop plus LEM would be as bad as the impredicativity in full ZFC, because the situation is analogous there where set membership is boolean and hence the cumulative hierarchy cannot be used to justify full specification or full replacement. However, this argument does not imply any problem with plain CoC with impredicative Prop, as long as one is careful to never view a type as a fixed collection.
in Discussion between user21820 and Trebor, 21 hours ago, by Trebor
Hmm I think that's about right. But I can't be sure for ZFC, because apart from beginner facts I don't know a lot.
in Discussion between user21820 and Trebor, 21 hours ago, by Trebor
Oh I think I do know what you mean. It's probably correct.
Conversation ended Mar 29, 2022 at 14:28.
Impredicativity Problems
Mar '2225
Mar '2229
Participants
- user21820 100%
all times are UTC