Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Böhm's theorem says that given lambda terms $r$ and $s$ with non-equivalent normal forms, there exists $\vec{a}$ terms such that $r\vec{a}=t$ and $s\vec{a}=f$.

I'm finding it hard to determine what those $\vec{a}$ are though. Even separating simple terms like $i$ and $k$.

Is there a procedure one can apply to figure them out?

share|cite|improve this question
This has been answered recently on CS. Note that you can't separate $i$ and $k$, because they have free variables. Böhm's theorem applies only for closed terms. – Petr Pudlák Jun 8 '13 at 9:48
I can't quite figure out if the CS answer is just a proof of existence, or it has a simple algorithm built in. However it does seem to use a different, less neat, theorem than the one I'm looking at. – Thomas Ahle Jun 8 '13 at 12:35
Also $i=\lambda x.x$ and $k=\lambda xy.x$ don't have free variables. – Thomas Ahle Jun 8 '13 at 12:36
Oh, I didn't understand that you meant the combinators - the convention is that lower case letters are reserved for variables. – Petr Pudlák Jun 8 '13 at 19:38

Your Answer


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

Browse other questions tagged or ask your own question.