3

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?

Thomas Ahle
  • 4,612
  • 1
    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 Jun 08 '13 at 09: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 08 '13 at 12:35
  • Also $i=\lambda x.x$ and $k=\lambda xy.x$ don't have free variables. – Thomas Ahle Jun 08 '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 Jun 08 '13 at 19:38
  • 1
    The Böhm out technique is an algorithm, which proceeds by induction on the structure of the normal forms. For $K$ and $I$, you can give $\vec{a}=KIft$. Then $I\vec{a}=KIft=It=t$ and $K\vec{a}=Kft=f$. – cody Mar 16 '17 at 13:33

0 Answers0