Communities

Writing
Writing
Codidact Meta
Codidact Meta
The Great Outdoors
The Great Outdoors
Photography & Video
Photography & Video
Scientific Speculation
Scientific Speculation
Cooking
Cooking
Electrical Engineering
Electrical Engineering
Judaism
Judaism
Languages & Linguistics
Languages & Linguistics
Software Development
Software Development
Mathematics
Mathematics
Christianity
Christianity
Code Golf
Code Golf
Music
Music
Physics
Physics
Linux Systems
Linux Systems
Power Users
Power Users
Tabletop RPGs
Tabletop RPGs
Community Proposals
Community Proposals
tag:snake search within a tag
answers:0 unanswered questions
user:xxxx search by author id
score:0.5 posts with 0.5+ score
"snake oil" exact phrase
votes:4 posts with 4+ votes
created:<1w created < 1 week ago
post_type:xxxx type of post
Search help
Notifications
Mark all as read See all your notifications »
Q&A

Comments on Defining the two universes from Calculus of Constructions in LF

Post

Defining the two universes from Calculus of Constructions in LF

+1
−0

Consider LF, the logical framework used to define UTT (unified theory of dependent types). The next two quotes are from here.

LF is a simple type system with terms of the following forms: $$\textbf {Type}, El(A), (x:K)K', [x:K]k', f(k),$$ where the free occurences of variable $x$ in $K'$ and $k'$ are bound by the binding operators $(x:K)$ and $[x:K]$, respectively.

(Note:$[x:K]b$ means $\lambda x:K. b$ and $(x:K)K'$ means $\Pi x:K.K'$.)

It has these judgements and these and these inference rules.

In the logical framework, there is a special kind $\textbf{Type}$, each of whose objects $A$ generates a kind $El(A)$. When specifying a type theory in LF, $\textbf{Type}$ corresponds to the conceptual universe of types of the type theory to be specified, and for any type $A$, i.e., any object of kind $\textbf{Type}$, kind $El(A)$ corresponds to the collection of objects of type $A$.

I was wondering how we could specify something like the Calculus of Constructions (or something close to it) in this LF? At the very least we should have two "things", $\ast$ and $\square$, such that $\ast: \square$. Sometimes $\ast$ is referred to as the type of all types (which I interpret as a universe of level zero), and $\square$ as the type of all kinds (which I interpret as a universe of level one). This note talks about defining universes in LF. To match its notation, let $U_0 = \ast, U_1 = \square$. Then, as suggested on page 3, we need to introduce constants

$$U_0 : \textbf{Type}, \ T_0: (U_0)\textbf{Type}, \ u_0: U_1, \ U_1:\textbf{Type}, T_1: (U_1)\textbf{Type}, $$ and assert the computation rule $T_1(u_0)=U_0 : \textbf{Type}$

Is this how it's done? But I never used $El(A)$ here, is it not needed for universe specification? I mean, $El$ corresponds to $T_0$, as noted in this answer, but if we can just introduce a constant named $T_0$ (and $T_1$), do we not need $El$ at all? In fact, it seems $T_0$ not used at all (unlike $T_1$ which is used in the assertion $T_1(u_0)=U_0 : \textbf{Type}$). But then I don't understand the purpose of adding $El(A)$ in the list of admissible terms of LF...

Further, this answer also says that $U_0$ corresponds to $\textbf{Type}$, does this mean that we should have $U_0=\textbf{Type}$ instead of $U_0=\ast$? (Maybe this is not a good question, but I just want to show which aspects made me confused.)

Lastly, this may be a topic for a separate question (feel free to ignore it in this question, I can ask about that separately), but there are 2 or 4 variations for most inference rules in CoC. Here's a picture from the book "Type theory and formal proof"; each of $s_1, s_2, $ and $s$ can be either $\ast$ or $\square$. How do inference rules in LF account for all these variations (assuming that we know how to introduce pi and lambdas - this is done here)? After introducing the constants for pi and lambda, and declaring appropriate computation rules, I thought only one set of inference rules will follow from LF's inference rulles (and that one set will correspond to $s_1=s_2=\ast$ as far as I understand).

History
Why does this post require moderator attention?
You might want to add some details to your flag.
Why should this post be closed?

2 comment threads

Crosspost https://math.stackexchange.com/q/4669016 (1 comment)
$El$ of the meta-language is not $T_0$ of the object lanugage (6 comments)
$El$ of the meta-language is not $T_0$ of the object lanugage
Derek Elkins‭ wrote about 1 year ago

As I explicitly state in the answer you reference, if we're modeling a language with a cumulative hierarchy within LF, then the $El$ of LF has no particular relation to the $T_0$ in the object language. As I state there, they aren't even the same kind of thing in that context.

Derek Elkins‭ wrote about 1 year ago

More generally, by design the type structure of LF is not reflected in the object language. We want to use LF to describe any language we desire which may or may not have pi types or universes or may have pi types/universes that work in a different way than in LF. The reason LF has pi types and a universe is because that is what is useful for manipulating contexts and derivations. The reason it has one universe and not an infinite hierarchy is because one suffices for its goals. Ironically, part of the reason LF has one universe is to clearly separate what is and is not part of the object language. If we add a list type constructor, then $\mathsf{List}(A)$ is a type of our object language and in LF is $\mathsf{List}:(A:\mathsf{Type})\mathsf{Type}$. But we don't have $(A:\mathsf{Type})\mathsf{List}(A):\mathsf{Type}$ so $\mathsf{List}((A:\mathsf{Type})\mathsf{List}(A))$ is nonsense as desired. We don't want the pi types of the meta-language to show up as types in the object language.

user205‭ wrote about 1 year ago · edited about 1 year ago

Oh, this makes things much clearer. (I know you partially restated what you had said in your answer, but sometimes restatements are very helpful, and this is one such case.) So essentially Luo chooses to use the symnol $El$ instead of $T_0$ when defining LF itself, and when we use LF to define other type theories, we use the notation $T_i$. I'm not sure if I got your point with $(A:Type)List(A):Type$, though (but I'll keep re-reading that part as I progress with my understanding of type theory).

But anyway, is it correct that the two universes in CoC would be defined in LF by saying the following?

$$U_0 : \textbf{Type}, \ T_0: (U_0)\textbf{Type}, \ U_1:\textbf{Type}, \ u_0: U_1, \ T_1: (U_1)\textbf{Type}, \ T_1(u_0)=U_0 : \textbf{Type}$$

And if there $T_0$ isn't really used here (i.e., there are no any computation rules like $T_0(\text{something})=\text{something}$), do we still need to declare the constant $T_0$?

Derek Elkins‭ wrote about 1 year ago

You are correct with that being how you would axiomatize two Tarski-style universes. You do need $T_0$ much as LF needs $El$. Because it gets cluttered, invocations of $El$ are suppresed, but they should actually be all over the place. For example, the type of the identity function would be written like $(A:\mathsf{Type})(x:A)A$, but technically it should be $(A:\mathsf{Type})(x:El(A))El(A)$. Also, in practice, as illustrated in the universes paper, whenever you introduce a type within the object language, you'll need to introduce a code for it as well and an equation relating the code and the type, e.g. the $T_0(\mathsf{nat})=\mathsf{Nat}$ where $\mathsf{nat}:\mathcal U_0$. The reason the LF descriptions don't typically add such equations for $El$ is we have no need or desire to reflect the object language's types into LF types. To the object language, the elements of LF's $\mathsf{Type}$ are the types, but to LF they are just codes.

user205‭ wrote about 1 year ago · edited about 1 year ago

Thank you, now the purpose of declaring the constant $T_0$ is clear. Regarding $(A:Type)(x:El(A))El(A)$, to check my understanding, is the term $(A:Type)(x:A)A$ ill-formed in LF because it is not possible to prove that $\Gamma \vdash (x:A)A \textbf{ kind}$ for any $\Gamma$ using the derivation rules in LF, and so it's not of the form $(x:K)K'$? In contrast, it is possible to prove that $A:Type \vdash (x:El(A))El(A) \textbf{ kind}$, and as a result, the LF-term $(A:Type)(x:El(A))El(A) $ is of the form $(x:K)K'$ where $x=A$, $K=Type$, $K' = (x:El(A))El(A)$. And in general, when declaring a constant $C:L$ in the object theory, $L$ should be derivable from the empty context using LF rules; otherwise, $L$ won't be well-formed, right?

Derek Elkins‭ wrote about 1 year ago

Yes, this is basically correct. The only caveat is you need to factor in how later defined constants can depend on earlier defined constants. One approach (which I dislike but is technically fine) is to have later constants declared with respect to a context containing all earlier constants, so the context may not be empty if this approach is taken. It is still constrained, though. You'd still need to derive the result in a given context, not just any context.