3
$\begingroup$

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

  • 2
    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.$2012-07-04

2 Answers 2

1

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.

  • 0
    @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.2012-07-04
1

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.