Take the 2-minute tour ×
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.

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|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
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.