# A problem with lambda calculus notation and semantics for function-valued functions

I would like to understand how to use the $\lambda$-notation to write usual (set-theoretic) functions, and if it is possible at all.

Here are my naïve attempts. Assume that all variables are real-valued. (I am using here the notation with "$\mapsto$" instead of "$\lambda$".)

Example 1.

If $f = x\mapsto \dfrac{1}{x}$ and $g_1 = x\mapsto 2x$, then $g_1\circ f = x\mapsto 2\cdot\dfrac{1}{x}$, and the domain of definition of $g_1\circ f$ is $D_{g_1\circ f}=\mathbb{R}\setminus\{0\}$.

Example 2.

If $h_1 = x\mapsto \left(y\mapsto \dfrac{y}{x}\right)$, then $D_{h_1}=\mathbb{R}$, and $h_1(0)$ is the empty (nowhere defined) function.

Example 3.

If $h_2 = x\mapsto \left(y\mapsto \dfrac{1}{x}\cdot y\right)$, then $h_2 = h_1$ and $D_{h_2}=\mathbb{R}$.

My question.

Consider now $f = x\mapsto \dfrac{1}{x}$ and $g_2 = x\mapsto(y\mapsto xy)$. Then obviously $D_{g_2\circ f} = \mathbb{R}\setminus\{0\}$.

What is the simplest way to write $g_2\circ f$ in $\lambda$-notation (preferably with "$\mapsto$")?

A problem: my naïve attempt to write $g_2\circ f$ gave me, after $\beta$-reduction, the same term as for $h_2$. However, $h_2$ is defined at $0$, but $g_2\circ f$ is not.

-

I don't know whether "I am asking this question here because i am lazy to read through the whole Wikipedia article and to think." is an attempt at honesty or a bad pun. Nevertheless, I think you might benefit from the hint below.

Hint:

The composition operator $\circ$ may be defined as follows (in various notations, pick the one that suits you best):

• $\operatorname{compose}(f,g)(x) = f (g (x))$,
• $\operatorname{compose}(f,g) = x \mapsto f (g (x))$,
• $\operatorname{compose} = (f,g) \mapsto x \mapsto f (g (x))$,
• $\operatorname{compose} = \lambda (f,g).\ \lambda x.\ f (g\ x)$,
• $f \circ g \equiv x \mapsto f(g(x))$.

Get to work (and good luck)! :-P

-
Wikipedia article didn't help. It seems there is a semantical bug in lambda calculus: there is no way to write $g_2\circ f$. The formula i suggested reduces by $\beta$-reduction to $x\mapsto(y\mapsto\frac{1}{x}y)$, which is $h_2$, not $g_2\circ f$. – Alexey Mar 23 '13 at 8:19
@Alexey Why do you think that $g_2 \circ f \not\equiv h_2$? – dtldarek Mar 23 '13 at 8:43
$h_2$ is defined at $0$, but $g_2\circ f$ is not. – Alexey Mar 23 '13 at 8:55
I was trying to see how to use $\lambda$-calculus to describe and manipulate usual (set-theoretic) functions or computer programs, and it seems that $\lambda$-calculus sometimes fails to distinguish distinct ones. – Alexey Mar 23 '13 at 9:00
The formal solution is to define the semantics of your system and fully specify what calculation order do you use. The simplest way it probably to write a comment like "Consider the $λ$-calculus with $XYZ$ evaluation order." There are also some approaches in-between. Whatever you pick, you can always describe this with natural language (i.e. regular text explanation). Consider also looking at typed theories, e.g. this and this. – dtldarek Mar 23 '13 at 12:07