You are here
Homefree and bound variables
Primary tabs
free and bound variables
In the entry firstorder language, I have mentioned the use of variables without mentioning what variables really are. A variable is a symbol that is supposed to range over the universe of discourse. Unlike a constant, it has no fixed value.
There are two ways in which a variable can occur in a formula: free or bound. Informally, a variable is said to occur free in a formula $\varphi$ if and only if it is not within the “scope” of a quantifier. For instance, $x$ occurs free in $\varphi$ if and only if it occurs in it as a symbol, and no subformula of $\varphi$ is of the form $\exists x.\psi$. Here the $x$ after the $\exists$ is to be taken literally : it is $x$ and no other symbol.
Variables in Terms
To formally define free (resp. bound) variables in a formula, we start by defining variables occurring in terms, which can be easily done inductively: let ${t}$ be a term (in a firstorder language), then $\operatorname{Var}(t)$ is

if $t$ is a variable $v$, then $\operatorname{Var}(t)$ is $\{v\}$

if $t$ is $f(t_{1},\ldots,t_{n})$, where $f$ is a function symbol of arity $n$, and each $t_{i}$ is a term, then $\operatorname{Var}(t)$ is the union of all the $\operatorname{Var}(t_{i})$.
Free Variables
Now, let $\varphi$ be a formula. Then the set $\operatorname{FV}(\varphi)$ of free variables of $\varphi$ is now defined inductively as follows:

if $\varphi$ is $t_{1}=t_{2}$, then $\operatorname{FV}(\varphi)$ is $\operatorname{Var}(t_{1})\cup\operatorname{Var}(t_{2})$,

if $\varphi$ is $R(t_{1},\ldots,t_{n})$, then $\operatorname{FV}(\varphi)$ is $\operatorname{Var}(t_{1})\cup\cdots\cup\operatorname{Var}(t_{n})$

if $\varphi$ is $\neg\psi$, then $\operatorname{FV}(\varphi)$ is $\operatorname{FV}(\psi)$

if $\varphi$ is $\psi\vee\sigma$, then $\operatorname{FV}(\varphi)$ is $\operatorname{FV}(\psi)\cup\operatorname{FV}(\sigma)$, and

if $\varphi$ is $\exists x\psi$, then $\operatorname{FV}(\varphi)$ is $\operatorname{FV}(\psi)\{x\}$.
If $\operatorname{FV}(\varphi)\neq\varnothing$, it is customary to write $\varphi$ as $\varphi(x_{1},\ldots,x_{n}),$ in order to stress the fact that there are some free variables left in $\varphi$, and that those free variables are among $x_{1},\ldots,x_{n}$. When $x_{1},\ldots,x_{n}$ appear free in $\varphi$, then they are considered as placeholders, and it is understood that we will have to supply “values” for them, when we want to determine the truth of $\varphi$. If $\operatorname{FV}(\varphi)=\varnothing$, then $\varphi$ is called a sentence. Another name for a sentence is a closed formula. A formula that is not closed is said to be open.
Bound Variables
Bound variables in formulas are inductively defined as well: let $\varphi$ be a formula. Then the set $\operatorname{BV}(\varphi)$ of bound variables of $\varphi$

if $\varphi$ is an atomic formula, then $\operatorname{BV}(\varphi)$ is $\varnothing$, the empty set,

if $\varphi$ is $\neg\psi$, then $\operatorname{BV}(\varphi)$ is $\operatorname{BV}(\psi)$

if $\varphi$ is $\psi\vee\sigma$, then $\operatorname{BV}(\varphi)$ is $\operatorname{BV}(\psi)\cup\operatorname{BV}(\sigma)$, and

if $\varphi$ is $\exists x\psi$, then $\operatorname{BV}(\varphi)$ is $\operatorname{BV}(\psi)\cup\{x\}$.
Thus, a variable $x$ is bound in $\varphi$ if and only if $\exists x\psi$ is a subformula of $\varphi$ for some formula $\psi$.
The set of all variables occurring in a formula $\varphi$ is denoted $\operatorname{Var}(\varphi)$, and is $\operatorname{FV}(\varphi)\cup\operatorname{BV}(\varphi)$.
Note that it is possible for a variable to be both free and bound. In other words, $\operatorname{FV}(\varphi)$ and $\operatorname{BV}(\varphi)$ are not necessarily disjoint. For example, consider the following formula $\varphi$ of the lenguage $\{+,\cdot,0,1\}$ of ring theory :
$x+1=0\wedge\exists x(x+y=1)$ 
Then $\operatorname{FV}(\varphi)=\{x,y\}$ and $\operatorname{BV}(\varphi)=\{x\}$: the variable $x$ occurs both free and bound. However, the following lemma tells us that we can always avoid this situation :
Lemma 1. It is possible to rename the bound variables without affecting the truth of a formula. In other words, if $\varphi=\exists x(\psi)$, or $\forall x(\psi)$, and $z$ is a variable not occurring in $\psi$, then $\vdash\varphi\Leftrightarrow\exists z(\psi[z/x])$, where $\psi[z/x]$ is the formula obtained from $\psi$ by replacing every free occurrence of $x$ by $z$.
As a result of the lemma above, we see that every formula is logically equivalent to a formula $\varphi$ such that $\operatorname{FV}(\varphi)\cap\operatorname{BV}(\varphi)=\varnothing$.
Mathematics Subject Classification
03C07 no label found03B10 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections
Comments
Space of hilbert space linear operators
If F and G are hilbert spaces, is the banach space L(F,G) of bounded linear operators from F to G necessarily a hilbert space?
Re: Space of hilbert space linear operators
Either it's way too hot, or, if we equip L(F,G) with the operator norm (A=sup_{x=1} Ax), F=G=R^2 will be a counterexample.
It cannot be a Hilbert space because A=((1,0),(0,0)) and B=((0,0),(0,1)) don't satisfy the parallelogram identity A+B^2+AB^2=2(A^2+B^2) valid in any Hilbert space.
Of course, in this particular example, you can use the Frechet norm (identifying the 2x2Matrices with R^4) and get the same topology on L(F,G) from a scalar product...
Re: Space of hilbert space linear operators
In general L(F,G) won't be a Banach space. What you usually do is the following: take o.n. bases {f_i} and {g_j} (you have to suppose F and G separable). Then put
(AB)=sum (A f_ig_j)
where the sum is over all i,j. This is the HilbertSchmidt (HS) product. Now call HS(F,G) the subspace of all operators for which (AA)<infinity (you have to prove it is a subspace). This is a Hilbert space under the HS product, and in general it is smaller then L(F,G).
When you are dealing with R^n and R^m you just get the usual dot product in R^nm (identify matrices with long vectors).
The space HS(F,G) has some nice properties and there is an alternative description when F=L^2 (X), G=L^2 (Y). In this case an operator A will belong to HS iff it is of the following form:
(A f)(y) = int_X K(x,y)f(x)dx
where int is the integral and K belongs to L^2 (X*Y). Moreover you have (AA)=K^2.
I hope I have somehow answered your question.
Bye
PS (think what you can do when F, G are not separable)