# Predicates and Quantifiers

Question: Establish these logical equivalences, where x does not occur as a free variable in A. Assume that the domain is nonempty.

a) ∀x(A → P(x)) ≡ A → ∀xP(x)

b) ∃x(A → P(x)) ≡ A → ∃xP(x)

My Solution

a) Suppose A is false. Then A -> P(x) is trivially true because if hypothesis is false then conditional statement is trivially true. hence, both left-hand side and right-hand side are true.

Second case if A is true. Then there are two sub-cases.

(i) P(x) is true for every x, then left hand side is true, because if hypothesis and conclusion both are true then conditional proposition is true. Same reasoning can be given for right hand side also, right-hand side is also true as P(x) is true for every x.

(ii) P(x) is true for some x, left-hand side will be true for that x, as hypothesis is true and conclusion is also true. But for those x, where p(x) is false, Left hand side will be false as hypothesis is true and conclusion is false.

For right hand side it will always be false because A is true and ∀xP(x) is false

Hence, both propositions are not equivalent.

b) If A is false, then both left-hand and right-hand sides are trivially true as hypothesis is false.

If A is true, then there are two sub-cases.

i.P(x) is true for every x, then left-hand side is true, and same reasoning can be given for right hand-side, and right-hand side is also true.>

ii.If P(x) is true for some x, left hand side is true and right hand side is also true.

Hence, both propositions are equivalent.

Please validate if my solution is correct.

Your reasoning in a)ii) is not correct. IF $A$ is true, and some, but not all, of the objects in the domain have property $P$, then the left hand side, like the right hand side, is false, because for those objects that do not have property $P$, the conditional $A \rightarrow P(x)$ is false, and hence it is not true that for all objects in the domain $A \rightarrow P(x)$ is true. Since your reasoning for the other cases is correct, the two statements in ) are in fact equivalent.

Your reasoning for b) is all correct.

• yes, correct. So Can I conclude, for part a, both propositions are equivalent? – Manu Thakur Sep 14 '17 at 3:06
• @ManuThakur Yes, that is correct! – Bram28 Sep 14 '17 at 3:06
• apart from a)ii) is everything else correct in this given solution? – Manu Thakur Sep 14 '17 at 3:08
• @ManuThakur Yes, everything else was correct! – Bram28 Sep 14 '17 at 3:08

I came to the opposite conclusion...

a) $$\forall x (A \to P(x)) \equiv A \to \forall x P(x)$$ is logically equivalent

The following 4 cases result in a mismatch of Truth values between right and left side, however they are not possible:

i) $$\forall x (A \to P(x)) \equiv \mathbf T, A \equiv \mathbf T, \forall xP(x) \equiv \mathbf F$$

if $$A \equiv \mathbf T$$ than for $$\forall x (A \to P(x)) \equiv \mathbf T$$ $$P(x)$$ must be true for all values of $$x$$, therefore $$\forall xP(x) \equiv \mathbf F$$ is not possible.

ii) $$\forall x (A \to P(x)) \equiv \mathbf F, A \equiv \mathbf T, \forall xP(x) \equiv \mathbf T$$

if $$A \equiv \mathbf T$$ than for $$\forall x (A \to P(x)) \equiv \mathbf F$$ there is an $$x$$ for which $$P(x)$$ is false, therefore $$\forall xP(x) \equiv \mathbf T$$ is not possible.

iii) $$\forall x (A \to P(x)) \equiv \mathbf F, A \equiv \mathbf F, \forall xP(x) \equiv \mathbf T$$

if $$A \equiv \mathbf F$$ than $$\forall x (A \to P(x)) \equiv \mathbf F$$ is not possible as whether $$P(x)$$ is true or false the conditional statement will always evaluate to true.

iv) $$\forall x (A \to P(x)) \equiv \mathbf F, A \equiv \mathbf F, \forall xP(x) \equiv \mathbf F$$

not possible for the same reason as iii)

b) $$\exists x (A \to P(x)) \equiv A \to \exists xP(x)$$ is NOT logically equivalent

The following 4 cases result in a mistmath of Truth values between right and left side, while only one case is not possible, the other 3 are:

i) $$\exists x (A \to P(x)) \equiv \mathbf T, A \equiv \mathbf T, \exists xP(x) \equiv \mathbf F$$

if $$\exists xP(x) \equiv \mathbf F$$ than $$P(x)$$ is false for every $$x$$, and if $$A \equiv \mathbf T$$ than for $$\exists x (A \to P(x)) \equiv \mathbf T$$ there need to be an $$x$$ for which $$P(x)$$ is true.

The following cases are possible and result in the left side being false and the right side being true.

ii) $$\exists x (A \to P(x)) \equiv \mathbf F, A \equiv \mathbf T, \exists xP(x) \equiv \mathbf T$$

iii) $$\exists x (A \to P(x)) \equiv \mathbf F, A \equiv \mathbf F, \exists xP(x) \equiv \mathbf T$$

iv)$$\exists x (A \to P(x)) \equiv \mathbf F, A \equiv \mathbf F, \exists xP(x) \equiv \mathbf F$$