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?

  • $\begingroup$ @MarkDominus: are there typographical standard s for indicating that A is a function as opposed to a value? $\endgroup$
    – Dancrumb
    May 13, 2012 at 1:33
  • $\begingroup$ A function is a value. $\endgroup$ Jul 27, 2012 at 5:12

1 Answer 1


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,

  • 1
    $\begingroup$ 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)$? $\endgroup$
    – Dancrumb
    May 13, 2012 at 14:11
  • $\begingroup$ BTW: not trying to be nit-picky... just making sure I understood what you wrote properly $\endgroup$
    – Dancrumb
    May 13, 2012 at 14:13
  • $\begingroup$ 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. $\endgroup$ Jul 27, 2012 at 7:15
  • $\begingroup$ @Mark: I'm not sure now why I wrote that. $\endgroup$
    – MJD
    Jul 27, 2012 at 13:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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