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

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

share|cite|improve this question
$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.

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

share|cite|improve this answer

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.