What is the justsification for this restriction on UG?

Question

In my textbook, there is a restriction on universal generalization: UG must not be used within the scope of an indented sequence(i.e. conditional proof or indirect proof) if the instantial variable y is free in the first line of that sequence.

Then the book gives a example using conditional proof:

1.∀x(Rx)→∀x(Sx)$\quad Premise$

$\quad$2.Rx $\quad ACP$

$\quad$3.∀x(Rx) $\quad 2.UG(Invalid)$

$\quad$4.∀x(Sx) $\quad 1,3 \; MP$

$\quad$5.Sx $\quad 4.UI$

6.Rx→Sx $\quad 2-5\; CP$

7.∀x(Rx→Sx) $\quad 6\; UG$

This proof is invalid. However, I don't know what is the logic of this restriction. The UG used in line 3 looks perfectly fine to me. Since the "Rx" in the second line, as my book claims, is a statement function, which does not have truth value unless the variable is replaced by a constant, then what does the assertion of "Rx" in line 2 mean? Probably the assertion of "Rx" means that this statement function is always true. But if I take this meaning, then it seems that line 3 just reexpresses the sense of line 2, and then the UG used here just looks valid. And I find it interesting that this restriction applies only to conditional proof and indirect proof, but why only them? I'm just confused by it.

Answer 1

The problem is that :

$\varphi \rightarrow \forall x(\varphi)$

is not valid in first-order logic.

Basically, steps 2-3 in the (fallacious) proof of the question amounts to this; assume $\varphi$ [i.e. $Rx$] and infer $\forall x(\varphi)$ [i.e. $\forall x (Rx)$].

In order to show that the formula $\varphi \rightarrow \forall x \varphi$ is not in general correct, consider the following example :

$\varphi$ is $x > 0$

and take as the domain of the interpretation the set $\mathbb N$ of natural numbers.

Thus, the formula :

$\varphi \rightarrow \forall x(\varphi)$

means :

$x > 0 \rightarrow \forall x(x > 0)$

which is not true in $\mathbb N$.

We have to recall the basic semantic definitions; see Herbert Enderton, A Mathematical Introduction to Logic (2nd - 2001), page 83 :

we will define what it means for [a structure] $\mathfrak A$ to satisfy $\varphi$ with $s$ [where the assignement function $s : Var \to |\mathfrak A|$ is a function from the set $Var$ of all variables into the universe $|\mathfrak A|$ of $\mathfrak A$] :

$$\mathfrak A \vDash \varphi [s]$$

$\mathfrak A \vDash \varphi [s]$ if and only if the translation of $\varphi$ determined by $\mathfrak A$, where the variable $x$ is translated as $s(x)$ wherever it occurs free, is true.

In our example, if we consider $s$ such that $s(x)=1$, we have that :

$(x > 0)[s]$ is $1>0$, which is true in $\mathbb N$, while obviously $\forall x (x > 0)[s]$ is false in $\mathbb N$ [because not $0>0$].

Thus :

not $\mathbb N \vDash ((x > 0) \rightarrow \forall x(x > 0))[s]$

i.e. the above assignment $s$ does not satisfy our formula in $\mathbb N$.

Thus, according to the semantic "convention" regarding formulae with free variables, having found an assignment $s$ such that the formula is not satisfied by $s$ in $\mathbb N$, we say that the formula is not true in $\mathbb N$. [Note. Intuitively, a formula $\alpha(x)$ with free variable $x$ is said to be true in $\mathfrak A$ if every sentence obtained from it by replacing $x$ by an arbitrary element $s(x) \in |\mathfrak A|$ is true.]

Conclusion

Having found an interpretation in which the formula :

$\varphi \rightarrow \forall x(\varphi)$

is not true, we conclude that it is not valid.

---

This is the reason for the restriction regarding the application of $UG$ ...

---

Added

In David's answer you can find a different explanation : the key-point is the invalidity of :

$\varphi \rightarrow \forall x(\varphi)$.

As you probably know, there are different proof systems for first-order logic : Natural Deduction, Hilbert-style, ...

But all must be sound, i.e. they must not be able to prove invalid formulae.

In order to prevent this, there are some restrictions needed.

Regarding our example, we can roughly say that the problem is connected with the interplay between Generalization (your $UG$) and Conditional Proof (or Deduction Theorem).

Thus, different systems adopt different restrictions :

• we can have (see my answer) an unrestricted Conditional Proof and put restrictions on Generalization,

or (see David's answer) :

• we "prefer" an unrestricted Generalization, in which case we need restrictions on the Deduction Th.

Answer 2

I have used a different kind of format for these things, so don't know if this answer will help. But it seems kind of similar, so will give it a try.

Here is the version I have learnt of the Deduction Theorem, which I think is essentially the same as what you are calling conditional proof:

if a formula $\Psi$ can be proved from a set of assumptions $\Sigma\cup\{\Phi\}$, and if the proof never involves applying the generalisation rule to a variable which is free in $\Phi$, then $\Phi\to\Psi$ can be proved from $\Sigma$.

From this point of view, the problem is not actually in line 3 but in line 6: your formula $\Phi$ is $Rx$ and $\Psi$ is $Sx$ and $\Sigma$ contains the formula in line 1. Since $x$ is free in $\Phi$, it is not correct to say that line 6 is deduced from line 1.

To understand the reasons behind this, it may help to consider some simpler cases. An easy case of the Deduction Theorem used correctly is:

from $Rx$ we can prove (in one line!) $Rx$; therefore, $Rx\to Rx$ is a theorem.

This is clearly reasonable, because $Rx\to Rx$ is always true. On the other hand, here is a simple incorrect use of the Deduction Theorem:

from $Rx$ we can use generalisation to prove $\forall x\,Rx$; therefore $Rx\to\forall x\,Rx$ is a theorem.

This is clearly not reasonable, since $Rx\to\forall x\,Rx$ is not always true and therefore we would not want it as a theorem. I think perhaps where you are going astray is when you say

Probably the assertion of "$Rx$" means that this statement function is always true.

On the contrary, we are not asserting that $Rx$ is always true; and maybe even "asserting" is not a good word, we are just temporarily assuming it. After all, when we proved $Rx\to Rx$ as a theorem, it didn't matter whether $Rx$ is true or not, the theorem just says that if it's true, then it's true. However in the following example we are, in effect, saying that if $Rx$ is hypothetically true even in one case, then it must always be true, which is clearly wrong.

Not sure if all these words help, but see how you go.

Answer 3

You can not use generalization on x when x occurs free in undischarched assumptions of your proof. This is way of saying that you do not assume any properties of x so x can by any object. For more explanation you can consult logic and structure written by Dirk van Dalen or Mathematical Logic by Chiswell.

Answer 4

The answer is systemic but applies to each system. Generally, in prenex normal form, $M(\varphi) \vdash \forall x M(x)$, i.e., UG, is not allowed unless $M(x)$ does not include $\varphi$, where $\varphi$ an individual instantiation of the quantifier $x$. Informally, we can see that under this condition, what $\varphi$ is does not matter. The important thing is that $\varphi$ not be in $M(x)$. This preserves logical truth but not truth. See. Herbrandization, so soundness (of an inference) does not matter but consistency (of the system) does.

$\vdash M(\varphi)$ if and only if $\vdash \forall x M(x) : \varphi \not \in M(x)$.

This does not mean that $M(\phi) \vdash \forall x M(x)$ is sound even if $\varphi \not \in M(x)$.