Skip to main content
2 of 2
added 56 characters in body
Justin Hilburn
  • 1.5k
  • 1
  • 10
  • 20

The question you are trying to ask is "What is a denotational semantics for the untyped lambda calculus?"

This is a difficult problem because, as Bjorn Kjos-Hanssen said in his answer, if you try and make variables range over elements of some set $D$ you find that you must have $D \times D \cong D$ and $D^D \cong D$. Unfortunately this implies that $D$ is the singleton set and all lambda terms must represent the same function.

Dana Scott solved the problem of giving a denotational semantics to the untyped calculus with the invention of domain theory.

Justin Hilburn
  • 1.5k
  • 1
  • 10
  • 20