2

In the $\lambda$-calculus.

Proposition: For any terms $M$,$N$ such that $M =_\beta N$, there is a term $L$ such that $L \twoheadrightarrow_\beta M$ and $L \twoheadrightarrow_\beta N$.

Is this true or false? A proof sketch or counterexample would be lovely.

drdo
  • 23
  • Welcome to MathSE. What have you tried to do to prove or disprove it? – Mike Pierce Jun 26 '15 at 23:42
  • Not much, asked some people around and no ideas have come where to start. We're not even sure if this is an open question or not. – drdo Jun 26 '15 at 23:46
  • It seems like it ought to be possible to find some form that reduces to $M$ in normal order and to $N$ in another order. – MJD Jun 27 '15 at 13:23
  • No, that will never work, because it neglects the assumption that M and N are $\beta$-equivalent, and that assumption is required. – MJD Jun 27 '15 at 14:12
  • It won't work in general, since that would imply that that every term is β-equivalent to every term. – drdo Jun 27 '15 at 15:04
  • Yes. I had in mind some simple construction that doesn't look at the actual values of $M$ and $N$, and it can't be anything like that. – MJD Jun 27 '15 at 17:31

0 Answers0