World's most popular travel blog for travel bloggers.

what is variable capture in nominal logic?

, , No Comments
Problem Detail: 

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?

Asked By : alim

Answered By : alim

I find out it. in the higher-order unification, some function is found for variable $X$ such as $ [X \mapsto \lambda y.y ]$, substituting this for $X$ will not lead to variable capture.

in nominal unification, $\lambda a.X \approx \lambda b.b$ yields substitution $[X \mapsto a]$, applying this to original problem yields $\lambda a.a \approx \lambda b.b$ where $a$ is captured.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback