Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Apologies if this is actually mathematical gibberish.

I'm very familiar with mathematical functions at a simple level. A function relates a set of inputs to a set of outputs.

What I'm trying to denote is a function, G, which, when given a set F and a true/false value, $\delta$, returns another function which has $n$ as a free variable. For reference, 'match' is another function that matches $n$ and $f$ according to some algorithm.

$$ \mathrm{G}(F,\delta) \equiv (F=\varnothing \vee ( \delta \veebar \exists f \in F: \mathrm{match}(n,f))) $$

My concern with the expression above is that $n$ pops out of nowhere.

What I'd like to get to is

$$ A(n) \equiv G(F_A,\bot)$$


$$ B(n) \equiv G(F_B,\top)$$

So, I guess my question is: does that notation make sense? Or are there more standard forms of expressing these ideas?

share|cite|improve this question
@MarkDominus: are there typographical standard s for indicating that A is a function as opposed to a value? – Dancrumb May 13 '12 at 1:33
A function is a value. – Marc van Leeuwen Jul 27 '12 at 5:12
up vote 3 down vote accepted

The idea is fine. $G$ is a function whose codomain is a set of functions.

But your notation is a little funny: you say that $A(n) = G(F_A, \bot)$, but this is wrong; actually you mean that $A = G(F_A, \bot)$. This is why you're worried about free variable $n$, which seems to come out of nowhere. But if you write it the right way there is no free variable. $A(n)$ is the value of the function $A$ at the point $n$, and is not equal to $G(F_A,\bot)$, but $G(F_A,\bot)(n)$.

In your definition, $$ \mathrm{G}(F,\delta) \equiv (F=\varnothing \vee ( \delta \veebar \exists f \in F: \mathrm{match}(n,f))) $$

you have the free $n$ as well, and you are right to be concerned about this, because it is notationally wrong, for similar reasons as in the previous paragraph.

One way to write a function is like this:

$$\lambda x. \mathrm{expression}(x)$$

where $\mathrm{expression}(x)$ is some expression in which $x$ appears free. This denotes the function which, given some argument $x$, yields the value $\mathrm{expression}(x)$. Note that although $x$ is free in $\mathrm{expression}(x)$, it is bound by the $\lambda$, and so the full expression has no free variables.

If we have $ F = \lambda x. E(x)$ then we can say that $F(n) = E(n)$.

Similarly for functions of two variables we may write:

$$\lambda(x,y).E(x,y) $$

where again $E$ is an expression in which $x$ and $y$ appear free. Using this notation, I think the definition you meant to write is:

$$ \mathrm{G}(F,\delta) \equiv \lambda n.(F=\varnothing \vee ( \delta \veebar \exists f \in F: \mathrm{match}(n,f))) $$

That is, $\mathrm{G}(F,\delta)$ is a function which, given $n$, et cetera.

Using this notation, one also writes things like $\lambda x.\lambda y. E(x,y)$ for the function which, given some value $N$, returns the function $\lambda y.E(N,y)$ which, given some argument $M$, returns the value $E(N,M)$. Written in that style, your definition becomes:

$$ \mathrm{G} \equiv\lambda(F,\delta).\lambda n.(F=\varnothing \vee ( \delta \veebar \exists f \in F: \mathrm{match}(n,f))) $$

One warning: the $\lambda$ notation is common in computer science, and in certain branches of mathematics, but it is not universally common, even in areas of mathematics that might benefit from it. Sometimes you see the notation $$x\mapsto E(x)$$ instead, but that seems less clear to me.

I hope this was not way more than you wanted to know,

share|cite|improve this answer
That was just what I needed to know. One comment: you have $\lambda(n,f)$. However, $f$ is not a free variable. It is an element of $F$. Thus, am I right in thinking that what I would really use is $\mathrm{G} \equiv \lambda(F,\delta).\lambda(n).\mathrm{expression}(F,\delta,n)$? – Dancrumb May 13 '12 at 14:11
BTW: not trying to be nit-picky... just making sure I understood what you wrote properly – Dancrumb May 13 '12 at 14:13
I don't see how $x\mapsto E(x)$ is less clear than $\lambda x.E(x)$. For one thing $\lambda$ is used very frequently as a variable itself, which is incompatible with its lambda-calculus use, and the same goes to some extent for the dot; on the other hand I don't think I have ever seen "$\mapsto$" used to mean anything else than it does here. Also $x\mapsto(y\mapsto E(x,y))$ seems perfectly clear to me. – Marc van Leeuwen Jul 27 '12 at 7:15
@Mark: I'm not sure now why I wrote that. – MJD Jul 27 '12 at 13:26

Your Answer


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.