Is the occurrence of $x$ in $P$ bound?

Question

In S. M. Srivastava's book it is written that,

An occurrence of a variable $v$ in a formula $A$ is bound if it occurs in a subformula of the form $∃vB$; otherwise, the occurrence is called free. A variable is said to be free in $A$ if it has a free occurrence in $A$.

After which it is written that,

In the formula $$x ∈ y ∨ ∃x(x ∈ y)$$ all the occurrences of $y$ are free, the first occurrence of $x$ is free, and other occurrences of $x$ are bound.

I don't understand why the occurrence of $x$ is not bound according to the definition. If we denote $x ∈ y ∨ ∃x(x ∈ y)$ as $P$, $x ∈ y$ as $Q$ and $∃x(x ∈ y)$ as $R$ and then if I argue that,

1. Both $Q$ and $R$ are subformulas of $P$.

2. The occurrence of $x$ in $R$ is bound. In other words it occurs in a subformula of $P$ (namely $R$) which is of the form $\exists S$ (where $S$ is $(x\in y)$). Hence the occurrence of $x$ in $P$ is bound.

where will be the mistake in my argument?

Answer 1

The definition is, with emphasis added on the word "occurrence",

An occurrence of a variable $v$ in a formula $A$ is bound if it occurs in a subformula of the form $∃vB$; otherwise, the occurrence is called free.

It is not the symbol of the variable that may be bound or unbound, but only each individual use (that is, occurrence) of the variable's symbol that is either bound or unbound.

In the case of $x \in y \lor \exists x(x \in y)$, the symbol $x$ appears more than once. The rightmost appearance of the symbol $x$ is an occurrence of a variable and it does indeed appear in a subformula of the form $\exists x B$, therefore that occurrence of $x$ is bound. The leftmost appearance of the symbol $x$ is a separate occurrence of a variable, it does not appear in any subformula of the form $\exists x B$, and therefore that occurrence of $x$ is not bound.

---

Further discussion:

Some sources will write, "The variable $x$ is bound in $P$", meaning that there is an occurrence of $x$ that is bound in $P$. These same sources may also write, "The variable $x$ is free in $P$", meaning that there is an occurrence of $x$ that is free in $P$. I think it would be very unusual for any mathematician to write simply "the variable $x$ is bound" when what they meant was that all occurrences of $x$ are bound.

As we have found that it is possible for the same symbol, $x$, to occur as both a free occurrence of a variable and a bound occurrence of a variable within the same formula, sometimes a text on first-order logic (for example the Wikipedia article on that topic) will include a statement of the form "$x$ is both free and bound in $P$." What this means is that there is at least one free occurrence of $x$ in $P$, and there is also at least one bound occurrence of $x$ in $P$.

I think there is a legitimate question about whether it is proper to write something like, "The variable $x$ is bound in $P$." The concern is that when you have both free and bound occurrences of the same symbol $x$ in a formula, they do not behave like a single variable, and it is questionable what is might be that we might mean by "the variable $x$." For example, a value can be assigned to a free variable; when we assign a value to a free occurrence of $x$ in $P$, that assignment must also assign the same value to all free occurrences of $x$ in $P$, but that assignment does not assign a value to any bound occurrence of $x$ in $P$. The only way I can make sense of this is to assume that the phrase "the variable $x$ is bound" is meant to be read as "one or more occurrences of a variable named $x$ are bound." Since the latter phrasing is somewhat lengthy and clumsy, it is not hard to imagine why mathematicians would have adopted a more compact phrasing as shorthand for the longer statement.

Answer 2

$x$ occurs twice in $P$ once as free (in $Q$) and once as bound (in $R$). It's not really the same variable since $x \in y \vee \exists z (z \in y)$ is the same proposition.

My point being that a bound variable's name is only relevant in the bound context. It is a bad habit to reuse a bound variable's name outside its context. See CS concept of shadowing.

Answer 3

There is no reason for the first occurence of $x$ to be bound, because it is not in the scope of any quantifier. What would it be bound by? The existential quantifier occurs right to it, and quantifiers in predicate logic can never bind variables that occur before the quantifiers themselves.

As for your argument,

2. The occurrence of $x$ in $R$ is bound. In other words it occurs in a subformula of $P$ (namely $R$) which is of the form $\exists S$ (where $S$ is $(x\in y)$). Hence the occurrence of $x$ in $P$ is bound.

The mistake lies in "hence": You can not deduce from the boundedness of one occurence in a subformula to boundedness of all occurences of some larger formula.

The first $x$ is not the same one as the second $x$. In fact, it is more or less a coincidence that they have the same name, because they are not the same object. The first $x$ and the second $x$ are two different occurences of $x$ and do not refer to the same object, because they are inside a different scope.

For example, it is theoretically totally fine (though confusing) to write $\exists x (P(x)) \land \exists x (R(x))$, where the first and the second existential quantifier quantify over different variables. They happen to both be named $x$, but their "power", i.e. their scope is limited to the bracketed parts, thus the $x$ coming after the conjunction is a different $x$ than the first occurence of it. The scope of the first $\exists$ is limited to $P(x)$, and the scope of the second $\exists$ is limited to $R(x)$, i.e. the first $\exists$ does not affect the $x$ occuring in the second conjunct and vice versa.
You could even write $\exists x (P(x)) \land R(x)$ without the $x$ in $R(x)$ being bound. The $\exists$ only binds what is within the bracket, so the later occurence of $x$ is not affected by it and a different object which just happens to have the same name.
In both examples, things would obviously look differently if the bracketing was changed.

So two occurences of $x$ may belong to the same variable, i.e. be co-referential if they are inside or outside the scope of a certain quantifier, but they may also belong to distinct variables and denote different objects despite being named the same way.
In a formla like $\forall x (P(x) \to R(x))$, the two occurences of $x$ in $P(x)$ and $R(x)$ respectively do refer to the same object, because they are both bound by the univeral quantifier. Hence, you cou could re-write the formula as as $\forall y (P(y) \to R(y))$ without changing the meaning; the choice of bound variable names is arbitrary as long as the use within the scope of boundedness is consistent. Conversely, you can not re-write it to $\forall y (P(y) \to R(x))$, because here $y$ is bound while $x$ is not, hence $x$ is not affected by the universal quantification which it should be.
In a formula like $R(x,y)$ where both $x$ and $y$ occur freely, it is not permissible to rewrite this statement as $R(x,x)$ without chaning the meaning. You can not really speak of scopal relations here because there is no quantifier involved (that's why the variables are free and not bound), but it does matter how you name your variable here.¹

All this means that you can write $x \in y \lor \exists x (x \in y)$ without the first $x$ being affected by the second one. The scope of $\exists x$ is, as indicated by the bracket, limited to $(x \in y)$, so the first occurence of $x$ is not bound by it.
That they are both labelled $x$ is merely a coincidence - they are not the same object, so you can not infer boundedness of the first variable from the boundedness of the second variable if there is nothing that binds it.

---

¹ Some excursus on assignment function and the interpretation of variables:
This is because the interpretation of the variables will depend on a particular assignment function. A free variable of $x$ in a statement like $R(x)$ will be assigned its reference by the particular assignment function you chose for that formula. And if you rename these variables, their interpretation will be a different one because the respective reference is defined particularly for that variable ($x$, $y$, ...). The choice of the variable name for such free variables is thus restricted by the fact its assignment to an entity in the domain is directly linked to the name of the variable.
With the use of quantifiers however, this assignment is "cancelled out": As soon as you use quantifiers, you start ranging over all possible assignments of a variable to an object in the domain, saying "There is at least one thing which is ..." or "For all things, if this thing is ..., then this thing is...", making the choice of a name for this "thing" irrelevant, because it reference changes with every iteration you make throught the evaluation of the formula. After you then tried out all possible assignments, you check whether the statment was true in at least one/each of the iterations for that thing that the variable currently mapped to, so the variable assignment given for the formula as a whole gets "overwritten" by the fact that the quantifier triggers an iteration through other possible assignments. This makes the name for these quantifier bound variables irrelevant, as their interpretation is no longer dependent on a static given assignment function.
But for the free variables, no such alternative assignment evaluation happens, you check for only that one x and not for all x there could be, so the interpretation of such free, unbound variables is directly determined by a particular assignment function, meaning that you can not change their name without chaning their meaning.

Answer 4

The only thing that the first occurrence of $x$ and the second occurrence of $x$ have in common here is that they are represented by the same symbol, but they should be regarded as different objects.

The first occurrence of $x$ can be seen as a place-holder, uninstantiated, and as such the subformula $Q$ for instance, doesn't express a proposition (the same symbols could be used to name a predicate though) and is not subject to truth values. On the other hand, in the second occurrence, $x$ acts as a "dummy variable", such as, for example, $n$ in the expression $\sum_{n=1}^{5} 10^n$ - the value of this expression does not depend on $n$. Unlike $Q$, $R$ affirms something, namely, that there exists an element of the universe that holds the property in question.

Consider the formula $P'$ obtained from $P$ by substituting every free occurrence of $x$ in $P$ by an $r$. Note how $P$ and $P'$ are logically equivalent, i.e. if $P(c)$ is an instance of $P$ (obtained by replacing $x$ by a closed term denoting the element $c$ of the universe) and likewise for $P'$, then for all $c$, $P(c) \vDash P'(c)$ and $P'(c) \vDash P(c)$.

Indeed, free and bound variables can be regarded as distinct things. Hilbert, for example, used two different sets of letters to denote free and bound variables, so as to emphasise this and avoid the type of confusion that comes from formulas such as $P$. I have seen this type of formula be referred to as 'dirty', by the way.

Two interesting exercises then would be (1) showing that any dirty formula has a logically equivalent clean formula and (2) modifying the definition of formula so as to make only clean formulas be well-formed.