# Free variables?

So if I understand correctly, these are examples of free variables: (all occurrences of $x$ are free) $$x*0$$ $$0+x*0$$ $$f: y \mapsto x*0$$ $$x*12345*(1-1)$$ $$x*12345*(5-(10/2))$$

What is an example of a variable that is not free (expensive variable?)

Is this $x$ here one? $$f: x \mapsto x^{x^{x^{x^x}}}$$

-
$x$ in $f: x \to x*0$ is not free. May be reading this will help. – user2468 Jul 4 '12 at 20:17
@J.D. sorry, it was a typo – megazord Jul 4 '12 at 20:26
Then you got the example: $f : x \to x * 0$ is not free. – user2468 Jul 4 '12 at 20:29
@J.D. but $x*0 =0$, isn't it free if it's zero? – megazord Jul 4 '12 at 20:37
Few comments: the opposite of "free" is "bound", not "expensive". A variable is bound if it's within the "scope" of a quantifier. Think of it as an argument of a function "$f(x) =\text{ .. something something }x\text{ ..}$", here $x$ is bound by $f(x).$ Also, the expressions $x \mapsto x*0$ and $x \mapsto 0$ are 2 different expressions. It's true they're "equivalent" under arithmetic reductions, but as far as syntax goes, these are 2 different expressions. The bottom line, when we say $x$ is free in a particular expression $E$, we really mean in $E$; not in some other $E'$ equivalent to $E.$ – user2468 Jul 4 '12 at 20:57

Variables are free in expressions (or formulas, or whatever the book you are using calls such syntactic objects). So naming your expressions $a$, $b$, $c$, $d$, and $e$, one can say $x$ is free in $a$, $b$, $d$, and $e$, $f$ is free in $c$, and $x$ is bound (i.e., not free) in $c$.

And your $x^x^x^x$ has $x$ free.

-
Here's another example, which I hope helps answer @megazord's question: In the formula "there exists a $y$ such that $y=x^2$", the variable $x$ is free and $y$ is not. Note that the sense of of "there exists a $y$ such that $y=P^2$" is quite different: the original statement was talking about $x$, and this one is talking about $P$. On the other hand, "there exists a $z$ such that $z=x^2$", has exactly the same content as the original statement. – MJD Jul 4 '12 at 20:33
@MarkDominus I have a feeling you're assuming certain semantic for each expression. It doesn't matter which statement "is talking about" which variable. Free and bound is a statement about syntactic properties of an expression (atom of wff actually) within a particular formal system. – user2468 Jul 4 '12 at 20:37
@J.D. You didn't have any trouble assuming the syntactic properties of the original examples in your comments, and you shouldn't have any trouble assuming them here either, even though I wrote "there exists a $y$" instead of "$\exists y$". – MJD Jul 4 '12 at 20:38
Sorry, I fixed my example. Why is x "bound" in c? – megazord Jul 4 '12 at 20:39
@megazord I think Charles Moss made a mistake, or was referring to your example before you edited it. If I understand your $f:y\to x\ast 0$ example, $y$ is bound (as the formal parameter of the function) and $x$ is free. – MJD Jul 4 '12 at 20:41

For example $f(x)= x\bmod 2$ can be written as: $$f(x)=\begin{cases}0&\exists k:x=2k\\ 1&\forall k:x\neq 2k\end{cases}$$

In this expression $k$ is a bound variable, we do not assign it a particular value, but we make assertion based on whether or not a certain $k$ exists.

-