Type equivalence in $lambdaunderlineomega$ under lambda abstraction
$begingroup$
I'm going through "Type Theory and Formal Proof" by Nederpelt and Geuvers and just trying to play around with $lambdaunderlineomega$ after reading the chapter on it to better grasp the material. The text is a bit vague on some formalities, so I have a couple of questions.
Consider the term $t = lambda x : ((lambda alpha : *. alpha) nat). x$ (assuming $nat : *$ is in context). Can type-level abstractions and applications be used like this under lambda abstraction type annotations? So, is $t$ a valid term?
If it is, then clearly its type is $(lambda alpha : *. alpha) nat rightarrow (lambda alpha : *. alpha) nat$, which is $beta$-equivalent to $nat rightarrow nat$. But how does $t$ relate to $lambda x:nat.x$? In other words, can $beta$-reduction be done under the lambda abstraction type annotation?
lambda-calculus type-theory
asked Dec 26 '18 at 1:46
0xd34df00d0xd34df00d
419212
$endgroup$
add a comment |
$begingroup$
I'm going through "Type Theory and Formal Proof" by Nederpelt and Geuvers and just trying to play around with $lambdaunderlineomega$ after reading the chapter on it to better grasp the material. The text is a bit vague on some formalities, so I have a couple of questions.
Consider the term $t = lambda x : ((lambda alpha : *. alpha) nat). x$ (assuming $nat : *$ is in context). Can type-level abstractions and applications be used like this under lambda abstraction type annotations? So, is $t$ a valid term?
If it is, then clearly its type is $(lambda alpha : *. alpha) nat rightarrow (lambda alpha : *. alpha) nat$, which is $beta$-equivalent to $nat rightarrow nat$. But how does $t$ relate to $lambda x:nat.x$? In other words, can $beta$-reduction be done under the lambda abstraction type annotation?
lambda-calculus type-theory
asked Dec 26 '18 at 1:46
0xd34df00d0xd34df00d
419212
$endgroup$
$begingroup$
What do $nat$ and $*$ denote here?
$endgroup$
– Berci
Dec 26 '18 at 2:34
$begingroup$
$nat$ is some type of the kind $*$, and $*$ is, well, the kind of usual types (the ones you'd also encounter in STLC).
$endgroup$
– 0xd34df00d
Dec 26 '18 at 2:36
$begingroup$
Ah, so you want a 'varying type' or some, i.e. a lambda expression for the type part (after the colon). I think it has another formalism on that part (maybe 'dependent types') and lambda expressions are only for terms.. But I'm not a lambda calculus expert..
$endgroup$
– Berci
Dec 26 '18 at 3:24
$begingroup$
Yep, that's types dependent on types (basically STLC lifted to the type level).
$endgroup$
– 0xd34df00d
Dec 26 '18 at 4:25
add a comment |
$begingroup$
I'm going through "Type Theory and Formal Proof" by Nederpelt and Geuvers and just trying to play around with $lambdaunderlineomega$ after reading the chapter on it to better grasp the material. The text is a bit vague on some formalities, so I have a couple of questions.
Consider the term $t = lambda x : ((lambda alpha : *. alpha) nat). x$ (assuming $nat : *$ is in context). Can type-level abstractions and applications be used like this under lambda abstraction type annotations? So, is $t$ a valid term?
If it is, then clearly its type is $(lambda alpha : *. alpha) nat rightarrow (lambda alpha : *. alpha) nat$, which is $beta$-equivalent to $nat rightarrow nat$. But how does $t$ relate to $lambda x:nat.x$? In other words, can $beta$-reduction be done under the lambda abstraction type annotation?
lambda-calculus type-theory
asked Dec 26 '18 at 1:46
0xd34df00d0xd34df00d
419212
$endgroup$
I'm going through "Type Theory and Formal Proof" by Nederpelt and Geuvers and just trying to play around with $lambdaunderlineomega$ after reading the chapter on it to better grasp the material. The text is a bit vague on some formalities, so I have a couple of questions.
Consider the term $t = lambda x : ((lambda alpha : *. alpha) nat). x$ (assuming $nat : *$ is in context). Can type-level abstractions and applications be used like this under lambda abstraction type annotations? So, is $t$ a valid term?
If it is, then clearly its type is $(lambda alpha : *. alpha) nat rightarrow (lambda alpha : *. alpha) nat$, which is $beta$-equivalent to $nat rightarrow nat$. But how does $t$ relate to $lambda x:nat.x$? In other words, can $beta$-reduction be done under the lambda abstraction type annotation?
lambda-calculus type-theory
lambda-calculus type-theory
asked Dec 26 '18 at 1:46
0xd34df00d0xd34df00d
419212
asked Dec 26 '18 at 1:46
0xd34df00d0xd34df00d
419212
asked Dec 26 '18 at 1:46
0xd34df00d0xd34df00d
419212
asked Dec 26 '18 at 1:46
0xd34df00d0xd34df00d
419212
asked Dec 26 '18 at 1:46
0xd34df00d0xd34df00d
419212
419212
$begingroup$
What do $nat$ and $*$ denote here?
$endgroup$
– Berci
Dec 26 '18 at 2:34
$begingroup$
$nat$ is some type of the kind $*$, and $*$ is, well, the kind of usual types (the ones you'd also encounter in STLC).
$endgroup$
– 0xd34df00d
Dec 26 '18 at 2:36
$begingroup$
Ah, so you want a 'varying type' or some, i.e. a lambda expression for the type part (after the colon). I think it has another formalism on that part (maybe 'dependent types') and lambda expressions are only for terms.. But I'm not a lambda calculus expert..
$endgroup$
– Berci
Dec 26 '18 at 3:24
$begingroup$
Yep, that's types dependent on types (basically STLC lifted to the type level).
$endgroup$
– 0xd34df00d
Dec 26 '18 at 4:25
add a comment |
$begingroup$
What do $nat$ and $*$ denote here?
$endgroup$
– Berci
Dec 26 '18 at 2:34
$begingroup$
$nat$ is some type of the kind $*$, and $*$ is, well, the kind of usual types (the ones you'd also encounter in STLC).
$endgroup$
– 0xd34df00d
Dec 26 '18 at 2:36
$begingroup$
Ah, so you want a 'varying type' or some, i.e. a lambda expression for the type part (after the colon). I think it has another formalism on that part (maybe 'dependent types') and lambda expressions are only for terms.. But I'm not a lambda calculus expert..
$endgroup$
– Berci
Dec 26 '18 at 3:24
$begingroup$
Yep, that's types dependent on types (basically STLC lifted to the type level).
$endgroup$
– 0xd34df00d
Dec 26 '18 at 4:25
$begingroup$
What do $nat$ and $*$ denote here?
$endgroup$
– Berci
Dec 26 '18 at 2:34
$begingroup$
What do $nat$ and $*$ denote here?
$endgroup$
– Berci
Dec 26 '18 at 2:34
$begingroup$
$nat$ is some type of the kind $*$, and $*$ is, well, the kind of usual types (the ones you'd also encounter in STLC).
$endgroup$
– 0xd34df00d
Dec 26 '18 at 2:36
$begingroup$
$nat$ is some type of the kind $*$, and $*$ is, well, the kind of usual types (the ones you'd also encounter in STLC).
$endgroup$
– 0xd34df00d
Dec 26 '18 at 2:36
$begingroup$
Ah, so you want a 'varying type' or some, i.e. a lambda expression for the type part (after the colon). I think it has another formalism on that part (maybe 'dependent types') and lambda expressions are only for terms.. But I'm not a lambda calculus expert..
$endgroup$
– Berci
Dec 26 '18 at 3:24
$begingroup$
Ah, so you want a 'varying type' or some, i.e. a lambda expression for the type part (after the colon). I think it has another formalism on that part (maybe 'dependent types') and lambda expressions are only for terms.. But I'm not a lambda calculus expert..
$endgroup$
– Berci
Dec 26 '18 at 3:24
$begingroup$
Yep, that's types dependent on types (basically STLC lifted to the type level).
$endgroup$
– 0xd34df00d
Dec 26 '18 at 4:25
$begingroup$
Yep, that's types dependent on types (basically STLC lifted to the type level).
$endgroup$
– 0xd34df00d
Dec 26 '18 at 4:25
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3052574%2ftype-equivalence-in-lambda-underline-omega-under-lambda-abstraction%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3052574%2ftype-equivalence-in-lambda-underline-omega-under-lambda-abstraction%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
What do $nat$ and $*$ denote here?
$endgroup$
– Berci
Dec 26 '18 at 2:34
$begingroup$
$nat$ is some type of the kind $*$, and $*$ is, well, the kind of usual types (the ones you'd also encounter in STLC).
$endgroup$
– 0xd34df00d
Dec 26 '18 at 2:36
$begingroup$
Ah, so you want a 'varying type' or some, i.e. a lambda expression for the type part (after the colon). I think it has another formalism on that part (maybe 'dependent types') and lambda expressions are only for terms.. But I'm not a lambda calculus expert..
$endgroup$
– Berci
Dec 26 '18 at 3:24
$begingroup$
Yep, that's types dependent on types (basically STLC lifted to the type level).
$endgroup$
– 0xd34df00d
Dec 26 '18 at 4:25