Which of the following formulas are valid?

Question

I have to find which of the following formulas is valid , and if it is not valid, give a model to show it.

$\forall u(P(u)\rightarrow R(u))\rightarrow(\forall uP(u)\rightarrow \forall uR(u))$

$(\forall uP(u)\rightarrow \forall uR(u))\rightarrow\forall u(P(u)\rightarrow R(u))$

I don't know how to start...

Answer 1

Hint

To show that:

$(∀uP(u)→∀uR(u))→∀u(P(u)→R(u))$

is not valid we have to manufacture a counterexample.

Consider the domain $\mathbb N$ of natural numbers and interpret $P(x)$ as $(x=0)$ and $R(x)$ as $(x > 0)$.

We have that $\forall u \ (u=0)$ is false in $\mathbb N$; thus, the conditional: $∀u \ (u=0) → ∀u \ (u>0)$ is true in $\mathbb N$.

But: $(u=0) → (u>0)$ is false for $0$ as value for $u$; thus $\forall u \ ((u=0) → (u>0))$ is false in $\mathbb N$.

In conclusion, the formula: $(∀uP(u)→∀uR(u))→∀u(P(u)→R(u))$ is false in $\mathbb N$ and thus it is not valid.

Answer 2

Well I'll address the other question then.

$$\forall u(P(u)\rightarrow R(u))\rightarrow(\forall uP(u)\rightarrow \forall uR(u))$$

You are asked to show that, in every model over a universe $W$ with predicates $P ~:~ W \to \mathbb{Bool}$ and $R ~:~ W \to \mathbb {Bool}$ , that in all of those models the above equation is true.

Each of those predicates can be reprented by a sets:

• $P_s$ is a set defined by $x \in P_s$ iff $P(x)$
• $R_s$ is a set defined by $x \in R_s$ iff $R(x)$

Then

• $\forall u~P(u) \implies R(u)$ translates to $P_s \subseteq R_s$.
• $\forall u~P(u)$ translates to $P_s = W$
• $\forall u~R(u)$ translates to $R_s = W$

(Also, aside, primite logic equations tend be be written as $A \implies (B \implies (C \implies D))$ because it is equivalent to $(A \land B \land C) \implies D$).

So, you can establish the formula is valid if you can establish that from the assumptions:

• $P_s \subseteq W$
• $R_s \subseteq W$
• $P_s \subseteq R_s$
• $P_s = W$

the conclusion that

• $R_s = W$

You can use any proof technique to establish that proposition. It doesn't have to be formal logic. A Venn diagram of $P_s, R_s,$ and $W$ is fine. Or just general set manipulation techniques is fine. Keep in mind $A = B$ iff $(A \subseteq B$ and $B \subseteq A)$.