4
$\begingroup$

What is the difference between

$\forall x (P(x)\implies Q(x))$ and $P(x)\implies Q(x)$

I know in the first one the variable x is bound but in the second one the variable is free. What are the consequences of this when proving it(Is the proof of the first statement different from the second)?

Also $ x>2 \implies x>4$ and $\forall x (x>2 \implies x>4)$ What is the difference(When proving how are the proofs different) ?

Also, in limits $\forall \epsilon >0 \exists \delta >0 \forall x ( |x-a|<\delta \implies |f(x)-L|<\epsilon)$. Are $\epsilon, \delta,x$ bound and $a,f(x)$ free?

$\endgroup$
  • 1
    $\begingroup$ In your example : $x>2 \rightarrow x>4$, there is no difference with the universally quantified formulation. When you prove it, you consider an $x$ whatever; thus by the logical rule below (Generalization), you are licensed to conclude with : $\forall x(x>2 \rightarrow x>4)$. $\endgroup$ – Mauro ALLEGRANZA May 19 '14 at 12:38
  • 1
    $\begingroup$ Regarding the "limit", obviously $\epsilon$, $\delta$ and $x$ are bound (you have put a quantifier in front of each). Regarding the function $f$, it is not necessarily so : if you are proving the property for a specific function $f$, you want to refer the proof to it. What about $a$ ? You are saying that the limit of $f(x)$ when $x$ "reach" $a$ is $L$; thus we assume $a$ fixed (i.e.known). $\endgroup$ – Mauro ALLEGRANZA May 19 '14 at 12:46
  • $\begingroup$ philosophy.stackexchange.com/questions/7827/… $\endgroup$ – Thomas Klimpel May 19 '14 at 22:53
2
$\begingroup$

In first-order logic typical rules governing the quantifiers are :

$${\Gamma \vdash \forall x \alpha \over \Gamma \vdash \alpha [x/t] }\, \, (\text{where} \, t \, \text{is substitutable for} \, x \text{in} \alpha)$$

$${\Gamma \vdash \alpha [x/y] \over \Gamma \vdash \forall x \alpha }\, \, (y \, \text{not free in} \, X \cup \alpha)$$

Thus, in your example, having proved :

$∀x[P(x) \rightarrow Q(x)]$

we can derive :

$P(t) \rightarrow Q(t)$

for every term $t$, included $x$ itself.

For the other "direction", if we have proved :

$\Gamma \vdash P(y) \rightarrow Q(y)$,

provided that $y$ is not free in any formula in $\Gamma$, we can conclude :

$\Gamma \vdash \forall x[P(x) \rightarrow Q(x)]$.

In the above proof $\Gamma$ is a set of formulae, and we can have $\Gamma = \emptyset$.

Thus, as a particular case of the above meta-theorem (usually called Generalization Theorem) we have :

if $\vdash \alpha[x/y]$, then $\vdash \forall x \alpha$.

The proviso is necessary in order to avoid fallacies.

If we assume $x = 0$, we can write the following derivation :

$x = 0 \vdash x = 0$;

from it, mis-applying the above rule [because $\Gamma = \{ x = 0 \}$ and $x$ is free in it]:

$x = 0 \vdash \forall x (x = 0)$.

By use of Deduction Theorem we can conclude :

$\vdash x = 0 \rightarrow \forall x (x = 0)$.

But this may not be because, by soundeness of first-order logic (i.e. : if $\vdash \alpha, then \vDash \alpha$) we expect that only valid formulae are provable, and the above formula is not valid.

Tho show that it is not, consider an interpretation with domain the set $\mathbb N$ of natural numbers and consider an assignement $s$ of value to the free variables [i.e. a function $s : Var \rightarrow \mathbb N$] such that $s(x)=0$.

Clearly :

$(x = 0 \rightarrow \forall x (x = 0))[s] = FALSE$

because $(x = 0)[s]$ is $0 = 0$, which is true, while $\forall x (x = 0)$ is false.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Pretty much nothing. Unless the quantifier is more specific like $\forall x \in (0, 1)$. Otherwise I would say there is absolutely no difference. $P(x) \implies Q(x)$ makes obvious the fact that the implication is true for each $x$. It means $Q(x)$ is true each time $P(x)$ is true. Makes no sense to put the quantifier at the beginning. Not a fan of doing it.

As for the question on the definition of the limit:- Again the quantifier $\forall x$ seems superfluous. But the quantifiers on $\epsilon$ and $\delta$ are absolutely necessary. I would just read it out in English "For any given $\epsilon \gt 0$ there is a positive number $\delta \gt 0$ such that $ |f(x) - L| $ is less than $\epsilon \;$ whenever $|x - a|$" is less than $\delta$. The "for each $x$" seems redundant. Just trying to make a point here about redundant quantifiers. I am not familiar with the terminology involving bound and free vaiables. Apologies.. Hope I helped.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @Ishfaqq Can you answer the second part also ? $\endgroup$ – Nameless May 19 '14 at 12:03
1
$\begingroup$

From my answer to What are the truth-values of intuitionistic logic?

The truth values of classical propositional logic form a Boolean algebra. The only subdirectly irreducible Boolean algebra has cardinality 2 (True & False). Hence the equational theory of classical propositional logic is completely determined by the two element Boolean algebra.

Classical logic can be regarded as the logic of (arbitrary) subsets. Then the formula $P(x)\implies Q(x)$ represents the subset $S=\{x\in X:P(x)\implies Q(x)\}$ of the set $X$. If $S=X$ the proposition is true, if $S=\emptyset$ it is false. The formula $\forall x (P(x)\implies Q(x))$ represents the subset $T=\{y\in \{()\}:\forall x (P(x)\implies Q(x))\}$ of the set $\{()\}$. If $T=\{()\}$ the proposition is true, if $T=\emptyset$ it is false. (The notation "$()$" for the empty tuple is really used in some fields.)

It's easy to see that $S$ is true if and only if $T$ is true. If $\lnot S$ is true then $\lnot T$ is also true. However, if $\lnot T$ is true it is not necessary that $\lnot S$ is also true. This is no big magic, but just the fact that $\lnot(\forall x (P(x)\implies Q(x)))$ doesn't necessarily imply $\lnot(P(x)\implies Q(x))$.


An interesting point is that $P\implies Q$ could also be written as $P(x)\implies Q(x)$, if one wants to emphasise that even a classical proposition is not necessarily bivalued. However, this sort of question normally arises in the exactly opposite way. Somebody who assumes that classical logic is necessarily bivalued has problems making any sense of $P(x)\implies Q(x)$ at all, and hopes to fix this by defining it to mean $\forall x (P(x)\implies Q(x))$. The issue with the negation is slightly annoying, but it's not really a big problem (and it's easy to see what goes wrong). More problematic is that the functoriality of truth values of subformulas has been destroyed by this definition. However, as long as you stay with classical logic, these problems are sufficently small and don't cause too much pain. But if you want to treat intuitionistic logic as the logic of open subsets, it may help if you accept that free variables can be given a prefectly fine meaning. (You can assign them slightly different meanings in different contexts, as long as the functoriality of truth values holds.)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Very interesting. I think can be useful (for not experienced readers) to explain a little more in detail while we can have that "S is true if and only if T is true. If ¬S is true then ¬T is also true. However, if ¬T is true it is not necessary that ¬S is also true." For "classical-minded" readers, from "S is true if and only if T is true", followe "¬S is true if and only if ¬T is true." $\endgroup$ – Mauro ALLEGRANZA May 19 '14 at 19:47
  • $\begingroup$ About the purported difficulty by "somebody who assumes that classical logic is necessarily bivalued [in] making any sense of $P(x) \rightarrow Q(x)$ at all", I do not agree. In a "classical setting, $P(x)$ has no fixed meaning; when we "instantiate" it with a "name" $c$ in place of $x$ we get a perfectly correct sentence with fixed meaning and truth-value. Of course, for different "names" we get different meanings and truth-values. $\endgroup$ – Mauro ALLEGRANZA May 19 '14 at 19:50
  • $\begingroup$ @MauroALLEGRANZA I tried to incorporate your suggestiongs into my anser. I agree that $P(x)$ has no fixed meaning. There are many reasonable ways to assign meaning to it. It makes most sense to strive for functoriality of truth values for these meanings. The drawback of the definition I gave is that it hides the fact that even $\forall x (P(x)\implies Q(x))$ can take truth values in a Boolean algebra. But I hope that it might be relatively easy to understand for somebody with a "bivalued" classical mindset. $\endgroup$ – Thomas Klimpel May 19 '14 at 20:13
1
$\begingroup$

What is the difference between

$\forall x (P(x)\implies Q(x))$ and $P(x)\implies Q(x)$

I know in the first one the variable x is bound but in the second one the variable is free.

Correct.

What are the consequences of this when proving it? Is the proof of the first statement different from the second?

Under the right circumstances, $\forall x(P(x)\implies Q(x))$ can actually be derived from $P(x)\implies Q(x).$

If, for example, we started a proof with the assumption that $P(x)$ is true (i.e. for a particular $x$), and were able to prove that $Q(x)$ would also have to be true, then we could conclude that $P(x)\implies Q(x)$ (for that same, particular $x$).

Since $x$ was introduced in the original premise at the beginning of the proof, we could then make a universal generalization about $x$, namely that $\forall x(P(x)\implies Q(x)).$ (Note that universal generalization can also be applied in other circumstances.)

We could not, however, generalize to obtain $\forall x(P(x)\implies Q(x))$ if we simply assumed from the start that $P(x)\implies Q(x).$ We cannot conclude that something is true for all $x$ by simply assuming it is true for a particular $x.$

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

you can use the completness theorem to show that from $P(x)\rightarrow Q(x)$ you can prove $\forall x (P(x)\rightarrow Q(x))$ (using GEN) and the same for the opposing direction (using IMPLIFICATION AX, and MP).

Which shows that they are logically equivalent.

| cite | improve this answer | |
$\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.