2
$\begingroup$

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)$

and

$ 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?

  • 0
    A function _is_ a value.2012-07-27

1 Answers 1

3

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,

  • 0
    @Mark: I'm not sure now why I wrote that.2012-07-27