Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The set $\Lambda$ is given inductively by:

  • $x\in\Lambda$, if $x$ is a variable;
  • $(\lambda x M)$, if $x$ is a variable and $M\in\Lambda$;
  • $(MN)$, if both $M,N\in\Lambda$.

Now, consider the structural induction principle associated with $\Lambda$. Say a property $P(M)$ over $M\in\Lambda$. Consider just the second case; is it(?)

  • $P(x)\wedge P(M)\implies P(\lambda x M)$, for all $x$ variable and $M\in\Lambda$.
share|cite|improve this question
up vote 0 down vote accepted

No. $P(x)$ doesn't even make sense, because $P$ is a property of lambda expressions, and $x$ is not an expression, it is just a variable. The correct induction principle is

  • $P(M) \implies P(\lambda x M)$ for all variables $x$ and $M\in\Lambda$.
share|cite|improve this answer
I considered that, but since the first case says that $x\in\Lambda$ whenever $x$ is a variable, I thought that I should include it too as the hypothesis. – user59517 Jan 24 '13 at 17:01
The definition given abuses the terminology a little bit. A single variable is an example of an expression, but the bound variable $x$ in $\lambda x.M$ is not an expression, it is a variable. – MJD Jan 24 '13 at 18:52

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.