3
$\begingroup$

I'm typing up some notes on logic for myself and I've come across the section on quantification, namely that quantifiers bind variables. I've thought of a way that helps me to understand why quantifiers bind variables, but I'm not entirely sure if it's correct. Am I correct in saying that free variables allow one statement to be a substitute for several? I've written out my notes below.

~~~

"When we make a statement of the form $\forall x\mathbf{P}(x)$ , $\exists x\mathbf{P}(x)$ , or $\exists!x\mathbf{P}(x)$ then we are not actually making a statement which can have varying truth values for different values of $x$ . If one says

$\forall x(x\in\mathbb{Z})$

when the universe of discourse is anything larger than $\mathbb{Z}$ , then we can say for certain that this statement is false, because there must exist some value of $x$ which is not an integer. We say that quantifiers $bind$ variables. If we have:

$\forall x\exists y(x=y+z)$

then we can say that both $x$ and $y$ are bound, and $z$ is free, as no quantifier has been attached to $z$ . In principle the validity of the statement could depend on $z$ , even though in reality if $x,y\,\textrm{and}\, z$ were real numbers this statement would always be true.

Another way of thinking about this is that if a statement contains free variables then it is in fact several statements at once, so from the above example we can extract several statements:

$\forall x\exists y(x=y+1)$

$\forall x\exists y(x=y+2)$

$\vdots$

$\forall x\exists y(x=y+2^{50})$

$\vdots$

so even though in every case the statement is true, in principle the truth values could differ. If we wanted to remove all free variables from our formula we could say:

$\forall x\forall z\exists y(x=y+z)$

once again being careful with the position of our quantifiers so that we do not say there is a single value of $y$ which would work for every value of $z$."

~~~

If there's anything else about my notes that immediately strikes you as wrong, I'd appreciate having that pointed out, too. :)

$\endgroup$
  • $\begingroup$ The only thing that strikes me as somewhat iffy is "if a statement contains free variables then it is in fact several statements at once". $\endgroup$ – Regret Mar 2 '15 at 11:40
  • $\begingroup$ Mm, that's what I'm iffy on, I'm wondering if it's not correct to say that $\endgroup$ – Nethesis Mar 2 '15 at 11:47
  • $\begingroup$ Consider the statement $\pi < 4$. Would you call $\pi$ an unbound variable? Would you say that it is several statements at once? $\endgroup$ – DanielV Mar 2 '15 at 11:49
  • $\begingroup$ No, that is one statement $\endgroup$ – Nethesis Mar 2 '15 at 11:51
  • 1
    $\begingroup$ @DanielV: in the context of first-order logic, $\pi$ is a constant, not a variable. $\endgroup$ – Carl Mummert Mar 2 '15 at 12:03
6
$\begingroup$

On the subject of substituting one statement for several, an older notation for the quantifiers was:

$$ \bigvee_x ( x = 3) \qquad \text{ for } \qquad (\exists x) [ x = 3] $$ $$ \bigwedge_x ( x = 3) \qquad \text{ for } \qquad (\forall x) [ x = 3] $$

The idea is that $\vee$ stands for "or", $\wedge$ stands for "and", and the quantifiers were viewed as representing (possibly infinite) conjunctions and disjunctions, with one conjunct or disjunct for each element of the model.

$\endgroup$
  • $\begingroup$ That's very cool! I did not know this. $\endgroup$ – Regret Mar 2 '15 at 12:08
  • $\begingroup$ Yeah, so if all the variables are bound by quantifiers then there is only one statement, albeit long. But if there are any free variables then that one statement is actual several at once. $\endgroup$ – Nethesis Mar 2 '15 at 12:18
  • $\begingroup$ No, @Nethesis . $(x^2 = 4)$ is a statement. There are two real values for which it is true, and infinite many for which it is false. However, it is just one statement. $\endgroup$ – Graham Kemp Mar 2 '15 at 23:16
  • $\begingroup$ @GrahamKemp Okay, so is this wording less controversial: If a statement contains free variables then one can extract several different statements which have a definite truth value from that statement, so for the above example we could extract:..." ? $\endgroup$ – Nethesis Mar 3 '15 at 7:32
  • $\begingroup$ @Nethesis I'd say simply that the truth value of the statement is a function of the particular value(s) of the unbound variable(s) - which is(/are) defined external to the statement. $\endgroup$ – Graham Kemp Mar 3 '15 at 8:34
1
$\begingroup$

OP wrote:

If we have:

$\forall x\exists y(x=y+z)$

then we can say that both $x$ and $y$ are bound, and $z$ is free, as no quantifier has been attached to $z$ . In principle the validity of the statement could depend on $z$ , even though in reality if $x,y\,\textrm{and}\, z$ were real numbers this statement would always be true.

Another way of thinking about this is that if a statement contains free variables then it is in fact several statements at once, so from the above example we can extract several statements:

$\forall x\exists y(x=y+1)$

$\forall x\exists y(x=y+2)$

$\vdots$

It depends on the context. In the context of a formal proof, you can substitute $1$ for $z$ only if you have proven or if you have explicitly assumed that $z=1$.

In more informal contexts, the commutativity of addition, for example, is often given in textbooks as simply

$x+y=y+x$

where, it is assumed that any values can be substituted for $x$ and $y$.

$\endgroup$

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.