patternMinor
what is variable capture in nominal logic?
Viewed 0 times
whatcapturelogicvariablenominal
Problem
While reading a paper Nominal Unification from a Higher-Order Perspective, in the abstract I noticed something feel bit confusing,
Nominal Logic is an extension of first-order logic with equality,
name-binding, name-swapping, and freshness of names. Contrarily to
higher-order logic, bound variables are treated as atoms, and only free
variables are proper unknowns in nominal unification. This allows “variable
capture”, breaking a fundamental principle of lambda-calculus.
I know a bit about nominal logic, but as I know it respects $\alpha$-conversion, such as $\lambda x.x \approx_\alpha \lambda y.y$.
but I could not understand above statement.
I understand the notion of variable capture which leads to a wrong result during the substitution.
So does variable capture not lead to an incorrect result in nominal logic?
what does it mean saying breaking "variable capture" here?
Can anyone explain with examples?
Nominal Logic is an extension of first-order logic with equality,
name-binding, name-swapping, and freshness of names. Contrarily to
higher-order logic, bound variables are treated as atoms, and only free
variables are proper unknowns in nominal unification. This allows “variable
capture”, breaking a fundamental principle of lambda-calculus.
I know a bit about nominal logic, but as I know it respects $\alpha$-conversion, such as $\lambda x.x \approx_\alpha \lambda y.y$.
but I could not understand above statement.
I understand the notion of variable capture which leads to a wrong result during the substitution.
So does variable capture not lead to an incorrect result in nominal logic?
what does it mean saying breaking "variable capture" here?
Can anyone explain with examples?
Solution
Variable capture is the phenomenon which "breaks" things when you do your substitutions in a naive way. For example:
-
Correct: in the expression $$\int_0^1 (a + x)^2 dx$$ substitute $t^2$ for $a$, to get $$\int_0^1 (t^2 + x)^2 dx.$$
-
Correct: in the expression $$\int_0^1 (a + t)^2 dt$$ substitute $t^2$ for $a$, to get $$\int_0^1 (t^2 + u)^2 du$$ (we renamed the bound variable $t$ to $u$ on the fly to avoid capturing $t$).
-
Incorrect: in the expression $$\int_0^1 (a + t)^2 dt$$ substitute $t^2$ for $a$, to get $$\int_0^1 (t^2 + t)^2 dt.$$ (We ended up with a different intergral because $t$ was captured by $dt$).
Similarly, in $\lambda$-calculus:
-
Correct: $(\lambda x . \lambda y . y x)) y = \lambda z . z y$
-
Incorrect: $(\lambda x . \lambda y . y x)) y = \lambda y . y y$ (because $y$ was captured).
-
Correct: in the expression $$\int_0^1 (a + x)^2 dx$$ substitute $t^2$ for $a$, to get $$\int_0^1 (t^2 + x)^2 dx.$$
-
Correct: in the expression $$\int_0^1 (a + t)^2 dt$$ substitute $t^2$ for $a$, to get $$\int_0^1 (t^2 + u)^2 du$$ (we renamed the bound variable $t$ to $u$ on the fly to avoid capturing $t$).
-
Incorrect: in the expression $$\int_0^1 (a + t)^2 dt$$ substitute $t^2$ for $a$, to get $$\int_0^1 (t^2 + t)^2 dt.$$ (We ended up with a different intergral because $t$ was captured by $dt$).
Similarly, in $\lambda$-calculus:
-
Correct: $(\lambda x . \lambda y . y x)) y = \lambda z . z y$
-
Incorrect: $(\lambda x . \lambda y . y x)) y = \lambda y . y y$ (because $y$ was captured).
Context
StackExchange Computer Science Q#66070, answer score: 5
Revisions (0)
No revisions yet.