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.

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.

share|improve this question

1 Answer 1

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

share|improve this answer
    
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
1  
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

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.