4 ms·
From https://rzk-lang.github.io/rzk/v0.6.4/reference/introduction.rzk/#soundness https://rzk-lang.github.io/rzk/v0.6.4/reference/introduction... > rzk-1 assume
by skulk 3y ago
From https://rzk-lang.github.io/rzk/v0.6.4/reference/introduction.rzk/#soundness https://rzk-lang.github.io/rzk/v0.6.4/reference/introduction...
> rzk-1 assumes "type-in-type", that is U has type U. This is known to make the type system unsound (due to Russell and Curry-style paradoxes), however, it is sometimes considered acceptable in proof assistants. And, since it simplifies implementation, rzk-1 embraces this assumption, at least for now.
I do this too (in my HoTT-book-inspired proof-checker)! I do plan on eventually implementing a hierarchy of universes but it doesn't seem to be a problem to let U be of type U. I wonder where the first practical issue comes up when you allow this.
---
After writing this comment, I decided to put it up on GitHub. Here is the entire source code of my proof-checker as well as some of the theorems from the HoTT book: https://github.com/sid-code/metalogic/blob/main/dts.org https://github.com/sid-code/metalogic/blob/main/dts.org. It was never meant to be used or even read by anyone else, but here it is.
Here is where the universe is defined (unsoundly): https://github.com/sid-code/metalogic/blob/main/dts.org#the-universe https://github.com/sid-code/metalogic/blob/main/dts.org#the-...
To see the theorems, scroll down past the machinery to the `(env-define-checked)` calls. Here is the proof that multiplication of natural numbers is associative: https://github.com/sid-code/metalogic/blob/main/dts.org#associativity-of-multiplication https://github.com/sid-code/metalogic/blob/main/dts.org#asso.... There is no type inference, so it's pretty gross. I think it's pretty cool how little you need to actually have a working proof-checker.
- gylterud 3y agoInterestingly, even thought type-in-type is inconsistent, there are no normal terms of the “empty” type. So, if you restrict to normal terms you do not get full explosion. There are however types A such that both A and not A have normal terms. It is just that if you combine them with modus ponens the term diverges. Another cool thing is that type-in-type is inconsistent, but has models. In particular, Palmgren constructed a model, based on domain theory, of Martin-Löf type theory with type-in-type.
- skulk 3y agoIn this context, what do you mean by "normal terms"?
- gylterud 3y agoType theories usually come with a reduction relation on terms. It computes things like β-reduction for function, inserting arguments into function bodies, computes projections out of tuples, etc A normal term is one where no further reductions can be made. Without type-in-type you can prove that all terms can be reduced to a normal form. With type-in-type some terms normalise while other diverges. In fact, using type-in-type you can define the fixed point operator and do general recursion!
- xavxav 3y agowow that's really cool, I wonder what the essential difference is between type-in-type and other classic "nice" inconsistencies in type theories. It seems like it's "almost" consistent.