For formulas $\phi$, $\psi$ show (($\forall$$x_1$)($\phi$ -> $\psi$) ->(($\forall$$x_1$)$\phi$ -> ($\forall$$x_1$)$\psi$)) is logically valid.

Question

What is the difference between saying

($\forall$$x_1$)($\phi$ -> $\psi$) and saying ($\forall$$x_1$)$\phi$ -> ($\forall$$x_1$)$\psi$

Thanks

EDIT

I am trying to prove that for formulas $\phi$ and $\psi$ the formula (($\forall$$x_1$)($\phi$ -> $\psi$) ->(($\forall$$x_1$)$\phi$ -> ($\forall$$x_1$)$\psi$)) is logically valid. I am trying to do so using contradiction and showing that if $\theta$=(($\forall$$x_1$)($\phi$ -> $\psi$) ->(($\forall$$x_1$)$\phi$ -> ($\forall$$x_1$)$\psi$)) then v(\$theta$) cannot be F (hence the formula is logically valid).

if i need to show that v(((∀$x_1$)(ϕ -> ψ) ->((∀$x_1$)ϕ -> ($∀x_1$)ψ)))=T to show that it is logically valid, why is it wrong to try a contradiction and show that v((($∀x_1$)(ϕ -> ψ) ->(($∀x_1$)ϕ -> ($∀x_1$)ψ))) cannot be F, thus it must be T as required?

Answer 1

They are equivalent unless $x_1$ is free in $\phi$. But if $x_1$ is not free in $\phi$, then they are definitely not equivalent, even if $x_1$ is not free in $\psi$.

For instance, suppose $\phi$ is $(x_1 \ge 0)$, and $x_1$ is not free in $\psi$. Then $(\forall x_1)(\phi \to\psi$) has the same truth value as $\psi$. But $(\forall x_1)\phi \to (\forall x_1)\psi$ is vacuously true, because $(\forall x_1)\phi$ is false (assuming that $\exists x_1 \ge 0$).

Answer 2

Why not just a proof without contradiction?

1 |       Vx(Px -> Qx)       given
2 | |____ VxPx               Assumption
3 | | |_a                    variable fot universal introduction
4 | | |   Pa                 2 universal elimination
5 | | |   Pa  -> Qa          1 universal elimination
6 | | |   Qa                 4,5 Modus ponens
. | | <----------------------- end subproof
7 | |     VxQx               3-6 universal introduction
. | <------------------------- end subproof
8 |       VxPx -> VxQx       2-7 conditional proof

Answer 3

If you want to proceed by contradiction then, informally, the argument goes like this.

1. Suppose $\forall x(\phi \to \psi) \to (\forall x\phi \to \forall x\psi)$ is F.
2. Then (i) $\forall x(\phi \to \psi)$ is T and (ii) $\forall x\phi \to \forall x\psi$ is F.
3. From (ii) we get (iii) $\forall x\phi$ is T and (iv) $\forall x\psi$ is F
4. By (iv) some object in the domain doesn't satisfy $\psi$. Call it $a$. So $\psi(a)$ is F.
5. By (iii) $\phi(a)$ is T.
6. By (i) $\phi(a) \to \psi(a)$ is T.
7. Contradiction is now immediate.
8. So the initial supposition has to be false, i.e. the wff in question is logically true.

This argument of course formalises as a tableau proof.

Answer 4

Think about $\phi$ and $\psi$ as formulas defining sets in a structure. So we have two sets $R$ and $S$, defined by $\phi$ and $\psi$ respectively.

The statement $\forall x(\phi(x)\rightarrow\psi(x))$ reads now $\forall x(x\in R\rightarrow x\in S)$. This is precisely the definition for $R\subseteq S$.

The statement $(\forall x\phi)\rightarrow(\forall x\psi)$ reads $(\forall x(x\in R))\rightarrow(\forall x(x\in S))$, meaning "If $R$ is everything, then $S$ is everything".

Those are two different statements, of course. Now, assume that the first one holds; if $R$ is everything, and $R\subseteq S$, then $S$ has to be everything. This is true in an arbitrary structure, so it is indeed logically valid.

I'll leave you with the work of turning my explanation into a proper proof.

Answer 5

For any formulas $\varphi, \psi$ show that $(∀x_1)(\varphi \rightarrow \psi) \rightarrow ((∀x_1)\varphi \rightarrow (∀x_1)\psi))$ is logically valid [from Alan Hamilton, Logic for mathematicians (1978), Exercise 19, page 70].

We can follow the hint of page 69 :

In general, to prove logical validity we must show that an arbitrary valuation in an arbitrary interpretation satisfies the wff concerned.

Let $\mathcal I$ be an interpretation with domain $D_\mathcal I$ and let $v$ be a valuation in $\mathcal L$.

If $v$ does not satisfy $(∀x_1)(\varphi \rightarrow \psi)$ then $v$ satisfy the above formula.

Consider now a $v$ which satisfy $(∀x_1)(\varphi \rightarrow \psi)$ and suppose that $v$ does not satisfy $(∀x_1)\varphi \rightarrow (∀x_1)\psi$.

This means that $v$ satisfy $(∀x_1)\varphi$ and $v$ does not satisfy $(∀x_1)\psi$.

We have to recall Definition 3.20, page 70 :

(iv) $v$ satisfies $(\forall x_i)\beta$ if every valuation $v'$ which is $i$-equivalent to $v$ satisfies $\beta$

and Definition 3.19, page 69 :

Two valuations $v$ and $v'$ are $i$-equivalent if $v(x_j) = v'(x_j)$ for every $j \ne i$.

Thus, from definitions, if $v$ does not satisfy $(∀x_1)\psi$, there is a valuation $v'$ which is $1$-equivalent to $v$ which does not satisfy $\psi$.

But $v$ satisfy $(∀x_1)\varphi$; this means that every valuation which is $1$-equivalent to $v$ satisfy $\varphi$.

In conclusion, we have a valuation $v'$ which satisfy $\varphi$ and not satisfy $\psi$; thus, $v'$ does not satisfy $\varphi \rightarrow \psi$.

But this contradicts the fact that $v$ satisfy $(∀x_1)(\varphi \rightarrow \psi)$, which means that every valuation $v'$ which is $1$-equivalent to $v$ satisfies $\varphi \rightarrow \psi$.

Answer 6

Just a straightforward proof works. Note that this is exactly the same as the proof by Willemien above, just not as nicely written in natural deduction style.

Assume $\forall x(Px \to Qx)$.

Assume $\forall x(Px)$.

Take an $a$. Because of the first assumption we have $Pa \to Qa$ and because of the second assumption we have $Pa$. Therefore $Qa$.

Hence, discharging our pick of $a$, $\forall x(Qx)$.

Discharging the second assumption, we get $\forall x(Px) \to \forall x(Qx)$.

Discharging the first assumption, we get $\forall x(Px \to Qx) \to \forall x(Px) \to \forall x(Qx)$.

As for trying a proof by contradiction, that would be valid (unless you adhere to some form of intuitionistic logic), but I don't see how you'd get one to work that is not essentially hiding the argument given above by Willemien or by me.