Is there a right identity for Application in Lambda calculus?
$begingroup$
Such a function E
that:
∀F (F E = F)
It's obviously, that the left identity E' (E' F = F)
is a function (λx.x)
. Indeed: (λx.x) F == F
.
But is there a right one like that?
Or is there evidence that such an element does not exist?
In common case, is there a chain of elements (E1 E2 … En)
for every well-formed expression (function) of Lambda calculus which fulfills the condition:
∀F (F E1 E2 … En = F) (n >=1)
Is there a method to build such a chain?
PS For some functions it is easy, for example:
Let F := (λa.λb.a b), then E1 := (λс.c) and E2 := F:
(λa.λb.a b) (λс.c) (λa.λb.a b) =>β
(λb.(λс.c) b) (λa.λb.a b) =>β
(λb.b) (λa.λb.a b) =>α
(λb.b) (λa.λc.a c) =>β
λa.λc.a c) =>α
(λa.λb.a b)
but what about, for example (λa.λb.a b a)
?
applications lambda-calculus
$endgroup$
add a comment |
$begingroup$
Such a function E
that:
∀F (F E = F)
It's obviously, that the left identity E' (E' F = F)
is a function (λx.x)
. Indeed: (λx.x) F == F
.
But is there a right one like that?
Or is there evidence that such an element does not exist?
In common case, is there a chain of elements (E1 E2 … En)
for every well-formed expression (function) of Lambda calculus which fulfills the condition:
∀F (F E1 E2 … En = F) (n >=1)
Is there a method to build such a chain?
PS For some functions it is easy, for example:
Let F := (λa.λb.a b), then E1 := (λс.c) and E2 := F:
(λa.λb.a b) (λс.c) (λa.λb.a b) =>β
(λb.(λс.c) b) (λa.λb.a b) =>β
(λb.b) (λa.λb.a b) =>α
(λb.b) (λa.λc.a c) =>β
λa.λc.a c) =>α
(λa.λb.a b)
but what about, for example (λa.λb.a b a)
?
applications lambda-calculus
$endgroup$
add a comment |
$begingroup$
Such a function E
that:
∀F (F E = F)
It's obviously, that the left identity E' (E' F = F)
is a function (λx.x)
. Indeed: (λx.x) F == F
.
But is there a right one like that?
Or is there evidence that such an element does not exist?
In common case, is there a chain of elements (E1 E2 … En)
for every well-formed expression (function) of Lambda calculus which fulfills the condition:
∀F (F E1 E2 … En = F) (n >=1)
Is there a method to build such a chain?
PS For some functions it is easy, for example:
Let F := (λa.λb.a b), then E1 := (λс.c) and E2 := F:
(λa.λb.a b) (λс.c) (λa.λb.a b) =>β
(λb.(λс.c) b) (λa.λb.a b) =>β
(λb.b) (λa.λb.a b) =>α
(λb.b) (λa.λc.a c) =>β
λa.λc.a c) =>α
(λa.λb.a b)
but what about, for example (λa.λb.a b a)
?
applications lambda-calculus
$endgroup$
Such a function E
that:
∀F (F E = F)
It's obviously, that the left identity E' (E' F = F)
is a function (λx.x)
. Indeed: (λx.x) F == F
.
But is there a right one like that?
Or is there evidence that such an element does not exist?
In common case, is there a chain of elements (E1 E2 … En)
for every well-formed expression (function) of Lambda calculus which fulfills the condition:
∀F (F E1 E2 … En = F) (n >=1)
Is there a method to build such a chain?
PS For some functions it is easy, for example:
Let F := (λa.λb.a b), then E1 := (λс.c) and E2 := F:
(λa.λb.a b) (λс.c) (λa.λb.a b) =>β
(λb.(λс.c) b) (λa.λb.a b) =>β
(λb.b) (λa.λb.a b) =>α
(λb.b) (λa.λc.a c) =>β
λa.λc.a c) =>α
(λa.λb.a b)
but what about, for example (λa.λb.a b a)
?
applications lambda-calculus
applications lambda-calculus
edited Dec 17 '18 at 14:25
asianirish
asked Dec 17 '18 at 14:03
asianirishasianirish
1034
1034
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
If I understand correctly, the answer is definitely no - at least, in any reasonable context.
The short version: think about any constant map $lambda x.p$, and what the existence of a right identity says about this map.
In more detail:
For simplicity I'll play a bit fast and loose with the details below.
I'll take as my context an arbitrary partial applicative structure $(A,cdot)$. First, suppose our PAS is total. A reasonable requirement is for constant maps to exist: for each $ain A$ there should be some $c_ain A$ with $c_ax=a$ for all $xin A$. We now have a problem. If each element $x$ of $A$ has a right identity $e_x$, then we must have $$c_ae_{c_a}=c_a$$ for each $ain A$. But $c_ae_{c_a}=a$ for each $ain A$, so we get $$a=c_a$$ for every $ain A$. We are thus in the degenerate situation where every functional is constant.
So total PASs don't have right identities unless they're extremely trivial, and in particular there is exactly one (fine, up to isomorphism) PAS of a given cardinality which has right identities. But essentially the same problem happens even if we drop totality. Call an element $ain A$ almost constant if there is some $v_a$ such that $ab=v_a$ whenever $ab$ is defined. Then - yet again - a right fixed point $c$ for $a$ must make $ac$ defined, and so we get $ac=v_a=a$. In particular, for each $v$ there is at most one functional in $A$ which is only ever $v$ when defined, and that element is $v$ itself. At this point the mere existence of a "nearly constant" map for an arbitrary $vin A$ collapses everything yet again: an element $a$ of $A$ is characterized completely by the subset $D_a$ of $A$ on which it is defined, and for each $din D_a$ we have $ad=a$. This does give more variety than the total case, but not much more, and in particular I think any reasonable semantics for anything like $lambda$-calculus will not be satisfied by such a thing.
And in particular, no nontrivial partial combinatory algebra - and these are to my understanding the "best" PASs - can have this property. First, note that for each $a$ the object $Ka$ is equal to $a$ on all inputs (that is, $Kab=a$ for all $b$); by the above, this means $Ka=a$. In particular, since $Ka$ is total we get that each $ain A$ behaves as the constant function $lambda x.a$. In particular, our algebra is total. But now consider the $S$-object. By the above we have $Sa=S$ for every $a$. However, by the above we also know that $(ac)(bc)=ab=a$ for all $a,b,cin A$; the $S$-axiom then tells us that $Sabc=(ac)(bc)=a$ for all $a,b,cin A$. But $Sabc=((Sa)b)c=S$, and so we get $a=S$ - that is, our PCA has only one element.
$endgroup$
$begingroup$
@Noah_Schweber Thank you very much !
$endgroup$
– asianirish
Dec 18 '18 at 14:14
add a comment |
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%2f3043981%2fis-there-a-right-identity-for-application-in-lambda-calculus%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
If I understand correctly, the answer is definitely no - at least, in any reasonable context.
The short version: think about any constant map $lambda x.p$, and what the existence of a right identity says about this map.
In more detail:
For simplicity I'll play a bit fast and loose with the details below.
I'll take as my context an arbitrary partial applicative structure $(A,cdot)$. First, suppose our PAS is total. A reasonable requirement is for constant maps to exist: for each $ain A$ there should be some $c_ain A$ with $c_ax=a$ for all $xin A$. We now have a problem. If each element $x$ of $A$ has a right identity $e_x$, then we must have $$c_ae_{c_a}=c_a$$ for each $ain A$. But $c_ae_{c_a}=a$ for each $ain A$, so we get $$a=c_a$$ for every $ain A$. We are thus in the degenerate situation where every functional is constant.
So total PASs don't have right identities unless they're extremely trivial, and in particular there is exactly one (fine, up to isomorphism) PAS of a given cardinality which has right identities. But essentially the same problem happens even if we drop totality. Call an element $ain A$ almost constant if there is some $v_a$ such that $ab=v_a$ whenever $ab$ is defined. Then - yet again - a right fixed point $c$ for $a$ must make $ac$ defined, and so we get $ac=v_a=a$. In particular, for each $v$ there is at most one functional in $A$ which is only ever $v$ when defined, and that element is $v$ itself. At this point the mere existence of a "nearly constant" map for an arbitrary $vin A$ collapses everything yet again: an element $a$ of $A$ is characterized completely by the subset $D_a$ of $A$ on which it is defined, and for each $din D_a$ we have $ad=a$. This does give more variety than the total case, but not much more, and in particular I think any reasonable semantics for anything like $lambda$-calculus will not be satisfied by such a thing.
And in particular, no nontrivial partial combinatory algebra - and these are to my understanding the "best" PASs - can have this property. First, note that for each $a$ the object $Ka$ is equal to $a$ on all inputs (that is, $Kab=a$ for all $b$); by the above, this means $Ka=a$. In particular, since $Ka$ is total we get that each $ain A$ behaves as the constant function $lambda x.a$. In particular, our algebra is total. But now consider the $S$-object. By the above we have $Sa=S$ for every $a$. However, by the above we also know that $(ac)(bc)=ab=a$ for all $a,b,cin A$; the $S$-axiom then tells us that $Sabc=(ac)(bc)=a$ for all $a,b,cin A$. But $Sabc=((Sa)b)c=S$, and so we get $a=S$ - that is, our PCA has only one element.
$endgroup$
$begingroup$
@Noah_Schweber Thank you very much !
$endgroup$
– asianirish
Dec 18 '18 at 14:14
add a comment |
$begingroup$
If I understand correctly, the answer is definitely no - at least, in any reasonable context.
The short version: think about any constant map $lambda x.p$, and what the existence of a right identity says about this map.
In more detail:
For simplicity I'll play a bit fast and loose with the details below.
I'll take as my context an arbitrary partial applicative structure $(A,cdot)$. First, suppose our PAS is total. A reasonable requirement is for constant maps to exist: for each $ain A$ there should be some $c_ain A$ with $c_ax=a$ for all $xin A$. We now have a problem. If each element $x$ of $A$ has a right identity $e_x$, then we must have $$c_ae_{c_a}=c_a$$ for each $ain A$. But $c_ae_{c_a}=a$ for each $ain A$, so we get $$a=c_a$$ for every $ain A$. We are thus in the degenerate situation where every functional is constant.
So total PASs don't have right identities unless they're extremely trivial, and in particular there is exactly one (fine, up to isomorphism) PAS of a given cardinality which has right identities. But essentially the same problem happens even if we drop totality. Call an element $ain A$ almost constant if there is some $v_a$ such that $ab=v_a$ whenever $ab$ is defined. Then - yet again - a right fixed point $c$ for $a$ must make $ac$ defined, and so we get $ac=v_a=a$. In particular, for each $v$ there is at most one functional in $A$ which is only ever $v$ when defined, and that element is $v$ itself. At this point the mere existence of a "nearly constant" map for an arbitrary $vin A$ collapses everything yet again: an element $a$ of $A$ is characterized completely by the subset $D_a$ of $A$ on which it is defined, and for each $din D_a$ we have $ad=a$. This does give more variety than the total case, but not much more, and in particular I think any reasonable semantics for anything like $lambda$-calculus will not be satisfied by such a thing.
And in particular, no nontrivial partial combinatory algebra - and these are to my understanding the "best" PASs - can have this property. First, note that for each $a$ the object $Ka$ is equal to $a$ on all inputs (that is, $Kab=a$ for all $b$); by the above, this means $Ka=a$. In particular, since $Ka$ is total we get that each $ain A$ behaves as the constant function $lambda x.a$. In particular, our algebra is total. But now consider the $S$-object. By the above we have $Sa=S$ for every $a$. However, by the above we also know that $(ac)(bc)=ab=a$ for all $a,b,cin A$; the $S$-axiom then tells us that $Sabc=(ac)(bc)=a$ for all $a,b,cin A$. But $Sabc=((Sa)b)c=S$, and so we get $a=S$ - that is, our PCA has only one element.
$endgroup$
$begingroup$
@Noah_Schweber Thank you very much !
$endgroup$
– asianirish
Dec 18 '18 at 14:14
add a comment |
$begingroup$
If I understand correctly, the answer is definitely no - at least, in any reasonable context.
The short version: think about any constant map $lambda x.p$, and what the existence of a right identity says about this map.
In more detail:
For simplicity I'll play a bit fast and loose with the details below.
I'll take as my context an arbitrary partial applicative structure $(A,cdot)$. First, suppose our PAS is total. A reasonable requirement is for constant maps to exist: for each $ain A$ there should be some $c_ain A$ with $c_ax=a$ for all $xin A$. We now have a problem. If each element $x$ of $A$ has a right identity $e_x$, then we must have $$c_ae_{c_a}=c_a$$ for each $ain A$. But $c_ae_{c_a}=a$ for each $ain A$, so we get $$a=c_a$$ for every $ain A$. We are thus in the degenerate situation where every functional is constant.
So total PASs don't have right identities unless they're extremely trivial, and in particular there is exactly one (fine, up to isomorphism) PAS of a given cardinality which has right identities. But essentially the same problem happens even if we drop totality. Call an element $ain A$ almost constant if there is some $v_a$ such that $ab=v_a$ whenever $ab$ is defined. Then - yet again - a right fixed point $c$ for $a$ must make $ac$ defined, and so we get $ac=v_a=a$. In particular, for each $v$ there is at most one functional in $A$ which is only ever $v$ when defined, and that element is $v$ itself. At this point the mere existence of a "nearly constant" map for an arbitrary $vin A$ collapses everything yet again: an element $a$ of $A$ is characterized completely by the subset $D_a$ of $A$ on which it is defined, and for each $din D_a$ we have $ad=a$. This does give more variety than the total case, but not much more, and in particular I think any reasonable semantics for anything like $lambda$-calculus will not be satisfied by such a thing.
And in particular, no nontrivial partial combinatory algebra - and these are to my understanding the "best" PASs - can have this property. First, note that for each $a$ the object $Ka$ is equal to $a$ on all inputs (that is, $Kab=a$ for all $b$); by the above, this means $Ka=a$. In particular, since $Ka$ is total we get that each $ain A$ behaves as the constant function $lambda x.a$. In particular, our algebra is total. But now consider the $S$-object. By the above we have $Sa=S$ for every $a$. However, by the above we also know that $(ac)(bc)=ab=a$ for all $a,b,cin A$; the $S$-axiom then tells us that $Sabc=(ac)(bc)=a$ for all $a,b,cin A$. But $Sabc=((Sa)b)c=S$, and so we get $a=S$ - that is, our PCA has only one element.
$endgroup$
If I understand correctly, the answer is definitely no - at least, in any reasonable context.
The short version: think about any constant map $lambda x.p$, and what the existence of a right identity says about this map.
In more detail:
For simplicity I'll play a bit fast and loose with the details below.
I'll take as my context an arbitrary partial applicative structure $(A,cdot)$. First, suppose our PAS is total. A reasonable requirement is for constant maps to exist: for each $ain A$ there should be some $c_ain A$ with $c_ax=a$ for all $xin A$. We now have a problem. If each element $x$ of $A$ has a right identity $e_x$, then we must have $$c_ae_{c_a}=c_a$$ for each $ain A$. But $c_ae_{c_a}=a$ for each $ain A$, so we get $$a=c_a$$ for every $ain A$. We are thus in the degenerate situation where every functional is constant.
So total PASs don't have right identities unless they're extremely trivial, and in particular there is exactly one (fine, up to isomorphism) PAS of a given cardinality which has right identities. But essentially the same problem happens even if we drop totality. Call an element $ain A$ almost constant if there is some $v_a$ such that $ab=v_a$ whenever $ab$ is defined. Then - yet again - a right fixed point $c$ for $a$ must make $ac$ defined, and so we get $ac=v_a=a$. In particular, for each $v$ there is at most one functional in $A$ which is only ever $v$ when defined, and that element is $v$ itself. At this point the mere existence of a "nearly constant" map for an arbitrary $vin A$ collapses everything yet again: an element $a$ of $A$ is characterized completely by the subset $D_a$ of $A$ on which it is defined, and for each $din D_a$ we have $ad=a$. This does give more variety than the total case, but not much more, and in particular I think any reasonable semantics for anything like $lambda$-calculus will not be satisfied by such a thing.
And in particular, no nontrivial partial combinatory algebra - and these are to my understanding the "best" PASs - can have this property. First, note that for each $a$ the object $Ka$ is equal to $a$ on all inputs (that is, $Kab=a$ for all $b$); by the above, this means $Ka=a$. In particular, since $Ka$ is total we get that each $ain A$ behaves as the constant function $lambda x.a$. In particular, our algebra is total. But now consider the $S$-object. By the above we have $Sa=S$ for every $a$. However, by the above we also know that $(ac)(bc)=ab=a$ for all $a,b,cin A$; the $S$-axiom then tells us that $Sabc=(ac)(bc)=a$ for all $a,b,cin A$. But $Sabc=((Sa)b)c=S$, and so we get $a=S$ - that is, our PCA has only one element.
edited Dec 17 '18 at 15:23
answered Dec 17 '18 at 14:39
Noah SchweberNoah Schweber
125k10150288
125k10150288
$begingroup$
@Noah_Schweber Thank you very much !
$endgroup$
– asianirish
Dec 18 '18 at 14:14
add a comment |
$begingroup$
@Noah_Schweber Thank you very much !
$endgroup$
– asianirish
Dec 18 '18 at 14:14
$begingroup$
@Noah_Schweber Thank you very much !
$endgroup$
– asianirish
Dec 18 '18 at 14:14
$begingroup$
@Noah_Schweber Thank you very much !
$endgroup$
– asianirish
Dec 18 '18 at 14:14
add a comment |
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%2f3043981%2fis-there-a-right-identity-for-application-in-lambda-calculus%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