8
$\begingroup$

I referenced 1 and 2. Source: p 29, How to Prove It by Daniel Velleman

The free variables [hereafter abbreviated to FV] in a statement stand for objects that the statement says something about...The fact that you can plug in different values for a free variable means that it is free to stand for anything.

Bound variables [hereafter abbreviated to BV], on the other hand, are simply letters that are used as a convenience to help express an idea and should not be thought of as standing for any particular object. A bound variable can always be replaced by a new variable without changing the meaning of the statement, and often the statement can be rephrased so that the bound variables are eliminated altogether.

Source: p 457, A Concise Introduction to Logic (12 Ed, 2014) by Patrick Hurley

The variables that occur in statement functions are called free variables because they are not bound by any quantifier.
In contrast, the variables that occur in statements are called bound variables.

The 3 examples below are from http://en.wikipedia.org/wiki/Free_variables_and_bound_variables:

$\color{green}{1. \lim_{h \rightarrow 0} \dfrac{f(x + h) - f(x)}{h} :}$
By definition $h :\approx 0$; so $h$ is a BV. Nothing binds $x$; so $x$ is a FV.

$\color{green}{2. \int...\int f(x_1,...,x_n) \, dx_1 ...\, dx_n:}$
How does the indefinite integral above bind $x_j \; \forall\, 1 \leq j \leq n$?

$\large{\color{green}{3. \forall x, \, \exists y, \phi(x, y, z):}}$ I am confused why Wikipedia states $x, y$ as BV and $z$ as FV.

$4.$ In the answer of user 'dtldarek', what is meant by: $x = x \land \forall x. x = x$ ?

$\endgroup$
10
$\begingroup$

Intuitively the variable is bound if it was introduced in the formula, while it is free if it comes "from the outside".

For example, in $$\forall x.\ \exists y.\ \phi(x,y,z)$$ we have $x$ introduced by $\forall$ quantifier and $y$ introduced by $\exists$ quantifier. On the other hand, $z$ comes from outside, or in other words, is not bound by any quantifier.

Please, beware of different variables with the same names, e.g. $x = x \land \forall x. x = x$ has two variables, which becomes obvious if you rewrite the formula as $x_1 = x_1 \land \forall x_2.\ x_2 = x_2$ (sometimes it might happen that we would like to say that there are even more than two variables, but I doubt you should concern yourself with such curiosities right now). As the example shows, one of the $x$-es is free ($x_1$) and the other $x$ ($x_2$) is bounded, even if at the beginning those had the same name. (Of course, it is a good practice to avoid such situations, however, as always, there might be some special cases where it would be even desirable.)

As for the second case, the integral sign $\int f(t) \, \mathrm{d}t$ binds $t$, similarly to how $\sum_{i = 0}^{n} a_i$ binds $i$, but NOT $n$. The dotted notation $\int \cdots \int$ is to be understood as those integrals are all there, that is for $n = 3$ we have $\iiint f(x_1,x_2,x_3) \, \mathrm{d}x_1 \, \mathrm{d}x_2 \, \mathrm{d}x_3$, i.e. all the $x_i$-s are introduced by integrals and none of them are free. This also the case in your $\int \cdots \int f(x_1,\ldots,x_n) \, \mathrm{d}x_1 \, \ldots \, \mathrm{d}x_n$. However, you missed one additional variable, namely $f$. It denotes a function, but it is still a variable (roughly a letter without any special meaning). None of the integrals bind $f$. $f$ and $n$ (appearing in $x_n)$ are free; that is, they could be substituted for anything (as long as the formula makes sense, so it has to be a function).

In the first case you correctly observed that $h$ is bound by the limit, or in my words introduced. You also correctly claimed that $x$ is free, and as in the second case, you missed $f$, which is also free.

Concluding, I would like to note, that $\phi$ from the third case might or might not be considered free, depending on whether you recognize it as a variable or not. The usual convention in logic is that $\phi$ (and any other symbol denoting formulae) is a special symbol and it is not to be considered a variable (and thus neither free, nor bound). Depending on the context and used convention, in analysis $f$ might or might not be treated as a variable, for example during the first semester of calculus usually it isn't to avoid confusion, but later, at functional analysis course it certainly is (consider problems like "solve for $f : \mathbb{R} \to \mathbb{R}$, $f(x+y) = f(x)\cdot f(y)$").

I hope this helps $\ddot\smile$

Edit: Thanks to user87690 for being scrupulous.

Edit 2: Some more explanations. Many, many, many more explanations. It may screw your mind or your computer screen, use at your own risk. Also, despite trying to be precise, I did fail. This is quite a long text, I don't know if I will be able correct all the mistakes, even if pointed out, so sorry if your comment might get ignored.


To be more precise, we need to overformalize a bit, I will say some things are wrong, but that's unclear at best, because it's also wrong to overformalize. Mathematics has a long history of notation abuse and this is for the sake of simplicity, a valuable goal indeed. However, logic is peculiar in its ways, and to correctly resolve all the issues, we have to be specific, and this becomes cumbersome when you have to deal also with a number of special cases and tons of syntactic sugar. I will try not to confuse you, but it might be hard...

This being said, I also use some notations and conventions, and one cannot be free, because I would have to write a whole book to define all the concepts, and there still be many, many issues. One such convention is dot usage, e.g.

\begin{align} &\forall x.\ \exists y.\ \phi(x,y,z) \\ &\forall x{:}\ \exists y{:}\ \phi(x,y,z) \\ &\forall x\cdot\exists y\cdot\phi(x,y,z) \\ &\forall x \mid \exists y\mid\phi(x,y,z) \\ &\forall x\ \exists y\ \phi(x,y,z) \\ &\forall_x\ \exists_y\ \phi(x,y,z) \\ &\forall x\ \exists y\ (\phi(x,y,z)) \\ &\forall x\ (\exists y\ (\phi(x,y,z))) \\ &(\forall x)\ (\exists y)\ \phi(x,y,z) \\ &\bigwedge_x\bigvee_y\phi(x,y,z) \\ \end{align} would all denote the same formula with different notations. Each of those has its advantages and disadvantages, strengths and weaknesses. I picked the first because it works in wide range of contexts, e.g. it is similar to a dot in $\lambda$-calculus, doesn't clash with other separators (I can use comma for multiple variables or multiple formulas; colon is frequently used to denote types), and doesn't involve a huge number of parentheses, one huge weakness is that in hand-writing it is hardly visible, and, of course, there are those who hate dots used this way. One thing worth to mention is that $\bigwedge$ and $\bigvee$ can have nowadays a slightly different meaning, i.e. $\bigwedge_{i \in \mathbb{N}} x_i$ would be $x_0 \land x_1 \land x_2 \land \ldots$. Finally, observe that some formulas have dots or commas as text symbols, for example when a sentence or a phrase ends.

$4.$ The above should partially answer your confusion. To address the rest, $x = x \land \forall x.\ x = x$ could be rewritten using a brace (another wide-spread convention) as $$\begin{cases}x = x\\\forall x.\ x = x\end{cases}$$ or with variable indices $$\begin{cases}x_1 = x_1\\\forall x_2.\ x_2 = x_2\end{cases}$$ Please observe, that the quantifier is written before the formula it quantifies and its scope extends as far right as it can, so

$$\forall x. x = x \land x = x \quad \text{ is } \quad \forall x_1. x_1 = x_1 \land x_1 = x_1,$$

but

$$(\forall x. x = x) \land x = x \quad \text{ is } \quad (\forall x_1. x_1 = x_1) \land x_2 = x_2.$$

The use of a quantifier suggest that what follows is a logical formula (first order, or something else, depending on the context). Therefore, usage like "...contains no restrictions on $x_i$ $∀1≤i≤n$" is bad. Even if the meaning is clear, typing "for all" works independent of the context, while writing $∀1≤i≤n$ at the end of a sentence is mathematically ungrammatical, mixes text and math symbols ($g\nu\epsilon{}s_5\ \omega\hbar\gamma\ {+}\mathbf{h}\ddot\iota{}s\ \lfloor\mathrm{s}\ \beta\mathtt{a}\mathrm{d}$), breaks the flow and suggest some additional formality which is not there (creating even more confusion). On the other hand, with a proper use of quantifiers you employ the semantics of the logic in context (usually first- or second-order logic) and get (instead of intuitive explanation), a formal definition. Naturally, there is place for both and misusing/overusing any of the above is a bad practice.

$2.1.$ First I need to clarify one thing: $f(x)$ is a point, not a function. The function is $f$ and when applied to $x$ we get $f(x)$. When $x$ is free/unbound/whatever, then one may argue that $f(x)$ is an expression, but it certainly is not a function. The functions are $f$ or $x \mapsto f(x)$ (or in computer science we could write $\lambda x.\ f(x)$).

Talking about $f(x)$ being a function is quite common, but it's wrong (if you want to being formal), in particular it is ok to write $\int f$ or $\int f(x) \mathrm{d}x$, but it's not ok to write $\int f(x)$. (The last one looks weird, right? Also, there are missing ranges in all those expressions.) A very similar example is $\int f(x) \mathrm{d}x = F(x)$ and there are two issues. First could be solved like this $\int f(x)\mathrm{d}x = F$ or $\int f(x)\mathrm{d}x = y \mapsto F(y)$ or $(\int f(x)\mathrm{d}x)(y) = F(y)$. The second is the fact that the expression is ambiguous with regard to integration constant (i.e. $y \mapsto F(y) + 1$ also fits). In fact $\int f$ or $\int f(x) \mathrm{d}x$ usually denotes the equivalence class for equivalence relation $$f \sim_1 g \stackrel{\text{def}}{\iff} \exists \alpha.\ \forall x. f(x) = g(x) + \alpha$$ or even (with Lebesgue integrals) $$f \sim_2 g \stackrel{\text{def}}{\iff} \text{ there exists $\alpha$ such that $f = g + \alpha$ almost everywhere}$$

Note that the addition operator $+$ was defined only for numbers, not functions, and $f = g + \alpha$ is another abuse/convention which formally should be written as $f(x) = g(x) + \alpha$ with some appropriately quantified $x$, or like this

$$f \sim_2 g \stackrel{\text{def}}{\iff} \exists \alpha. \mu(\{x \mid f(x) \neq g(x) + \alpha\}) = 0,$$

where $\mu$ is some measure. Here the set notation $\{x | \ldots\}$ also binds $x$ inside the braces (any $x$ outside the braces would be free).

Now to answer the main question, there are two main ways symbol $\int$ could be used:

  • with specified range: $\int_{[0,2\pi]} \sin = 0$ or $\int_0^{2\pi} \cos(\alpha)\ \mathrm{d}\alpha = 0$ (yet again, there are many conventions),
  • as a linear operator that "processes" functions, you put in one function, and it spits out another, or using mathematical terminology, its domain is a set of functions, and the value range are functions too (or to be more specific, equivalence classes of functions),
  • there is some mid-way when writing like $F(x) = \int_0^x f(t) \mathrm{d}t$, you use a definite integral, but extract a function $F$ out of it (here, it actually is a function, not an equivalence class); another way of writing it down would be $F = x \mapsto \int_0^x f(t) \mathrm{d}t$.

This bring us to what $F(x) = \int f(x) \mathrm{d}x$ means. First, there are two $x$-es which are different $F(x_1) = \int f(x_2) \mathrm{d}x_2$. Now we could interpret it in two ways:

  • $F = \int f(x_2) \mathrm{d}x_2$, the equivalence class (or some canonical representant),
  • $F(x_1) = \int_{?}^{x_1} \mathrm{d} x_2$, where we don't know actually what $?$ is, but it probably doesn't matter, i.e. the results would differ only by a constant, so we can again take the equivalence class.

All in all, by different interpretations we arrive at the same result (almost). Now, to answer how $\int \ldots \mathrm{d}x$ binds $x$, it all roughly means "$\mathrm{d}x$ tells us where the input should go", but let's consider those two cases:

  • A definite integral: $\int \Phi \mathrm{d}x$ specifies which symbol should be substituted for, that is, you calculate (by your definition) $\lim_{n \rightarrow \infty}\sum_{i = 1}^n \Phi[x \mapsto x_i^*] \Delta x$ by substituting $x_i^*$ for $x$ in $\Phi$ (here $\mapsto$ in brackets has different meaning), which later goes into its definition, where you replace all the occurrences of $x$ (this particular $x$, not other $x$-es if there are any).
  • An indefinite integral: $\int \Phi\mathrm{d}x$ specifies that your input is a function (or some other similar object) defined as $x \mapsto \Phi$ (here $\mapsto$ without the brackets has meaning as used at the beginning). With this approach the symbol $\mapsto$ binds $x$, for example if $\Phi = f(x)$, then $x \mapsto f(x)$ is equivalent to $f$ and the symbol $x$ was removed.

Analogical situation happens with derivatives, where $(x^2)' = 2x$ is yet another convention or notation abuse. The formal way to write it would be $(x \mapsto x^2)' = x \mapsto 2x$. That's why $f'(x)$ is ok, because it is $(x \mapsto f(x))'(x)$, but $(f(x))'$ is bad. This is in contrast with $\frac{\mathrm{d}}{\mathrm{d}x} f(x)$ where $\frac{\mathrm{d}}{\mathrm{d}x}f$ would be bad (in other words, $\frac{\mathrm{d}}{\mathrm{d}x}$ binds $x$).


That was some huge edit, I hope I didn't confuse you that much...

$\endgroup$
6
  • $\begingroup$ Note that the verb is "to bind", not "to bound". The quantifiers, integral notation, etc. binds variables. In a "bound" variable, "bound" is the past participle of "to bind". $\endgroup$ Aug 24 '13 at 10:24
  • $\begingroup$ @HenningMakholm I got carried away, thanks. $\endgroup$
    – dtldarek
    Aug 24 '13 at 12:27
  • $\begingroup$ @LePressentiment 2.1 First we need the exact definition of $\int f(x) \mathrm{d}x$ in your context (one of possibilities might be $t \mapsto \int_0^t f(x) \mathrm{d}x$, but we need to be sure). 4. This expression is parenthesized this way: $(x = x) \land (\forall x. (x = x))$, in particular quantifiers should be written before their scope, not after. Quantifiers have very precise meaning, those are not just shorthands for "for all" and "exists". Your phrase "binds $x_j$ $∀ 1≤j≤n$" is a horrible abuse (sorry), it would be many, many times better just to spell it out as "for all". $\endgroup$
    – dtldarek
    Aug 25 '13 at 12:56
  • $\begingroup$ @dtldarek: Many thanks. $\large{2.1.}$I updated the OP with definitions. $\large{4.}$ Why the period and not a comma: Is $(x = x) \wedge (\forall x {\Huge{\color{red}{,}}} (x = x)$ identical to your expression? Also, no worries! Could you please dilate on how and why my phrase is horrible? Isn't it identical to that obtained after writing out "for all"? $\endgroup$
    – NNOX Apps
    Aug 26 '13 at 18:04
  • $\begingroup$ @LePressentiment See the edit. I tried to answer your questions, however, should you have more problems, unfortunately, I doubt I will be able to spare more time for you in near future, sorry. Good luck (and take it with a pinch of salt)! $\endgroup$
    – dtldarek
    Aug 26 '13 at 22:06
3
$\begingroup$

The concept of bound and free occurrences of variables is a matter of structure of notation, it's a matter of syntax. You can think of a mathematical expression as a tree structure. Variables and constants are end-nodes. Function symbols or operators have their operands as child nodes and a subtree represents a subexpression. There are symbols which bind the occurrences of variables in the subexpression. The logical quantifiers are the most obvious example.

For your third example, $x$ and $y$ are bound and $z$ is free because there are quantifiers binding $x$ and $y$. Note that being free or bound is a property of variable occurrence not the variable itself. For example in $(x = z) ∨ ∀x, ∀y, φ(x, y, z)$, the first occurrence of $x$ is free and the second is bound. One important thing about this concept is, that it makes sense to substitute only into free occurrences, and that's how substitution is formally defined and why the concept of free and bound occurrence is needed. So if you substitute $x = 3$ into example above, you get $(3 = z) ∨ ∀x, ∀y, φ(x, y, z)$. That's also hint how to distinguish them since e.g. $∀3, ∀y, φ(3, y, z)$ doesn't make sense.

For your first example $\lim_{h \to 0}$ is syntactic element which binds the variable $h$ and that's why $h$ is bound. For your second example $∫…∫ (–) dx_1 … dx_n$ is a syntactic element which binds variables $x_1, …, x_n$, so they are bound. Note that $∫\cos(x)dx = ∫\cos = \sin = \sin(x)$ so when you write $∫\cos(x)dx = \sin(x)$, then the $x$ on RHS is actually different $x$ then the one on LHS.

$\endgroup$
6
  • $\begingroup$ It is a property of variable, not it's occurence! In $x = x \land \forall x.\ x = x$ we have two variables, only with the same name. This formula could be rewritten as $x_1 = x_1 \land \forall x_2.\ x_2 = x_2$ and now it is obvious there are two variables there. $\endgroup$
    – dtldarek
    Aug 24 '13 at 8:55
  • $\begingroup$ @dtldarek: So you call a “variable occurence” by “variable” and “variable” by “variable name”? It's just a matter of convention. Ok maybe your “variable” is a class of equivalent occurences in equivalent formulas, where the equivalence comes from substitution rule. $\endgroup$
    – user87690
    Aug 24 '13 at 9:00
  • $\begingroup$ Then how do you call my "variable occurrence", maybe "variable occurrence occurrence"? $\endgroup$
    – dtldarek
    Aug 24 '13 at 9:04
  • $\begingroup$ Regarding the comment edit, yeah, something along the lines. There are more precise definitions, but I would say that your description is very good (it captures precisely the properties we would like the variables to have). $\endgroup$
    – dtldarek
    Aug 24 '13 at 9:06
  • $\begingroup$ @dtldarek: So let's say that being bound or free is a property of both certain variable occurence and variable if we use your higher-level definition rather than my lower-level symbolic definition. $\endgroup$
    – user87690
    Aug 24 '13 at 9:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.