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

  • 0
    $x$ in $f: x \to x*0$ is not free. May be [reading this](http://en.wikipedia.org/wiki/Free_variables_and_bound_variables) will help.2012-07-04
  • 0
    @J.D. sorry, it was a typo2012-07-04
  • 0
    Then you got the example: $f : x \to x * 0$ is not free.2012-07-04
  • 0
    @J.D. but $x*0 =0$, isn't it free if it's zero?2012-07-04
  • 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
    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.2012-07-04
  • 0
    @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.2012-07-04
  • 2
    @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$".2012-07-04
  • 0
    Sorry, I fixed my example. Why is x "bound" in c?2012-07-04
  • 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.