[Math] Rules of distribution of quantifiers over conditional and biconditional

first-order-logiclogicpredicate-logicquantifiers

Which of the following propositional logic statements are true and why?

  1. $(∀x(P(x)⟹Q(x)))⟹((∀xP(x))⟹(∀xQ(x)))$
  2. $(∀x(P(x))⟹∀x(Q(x)))⟹(∀x(P(x)⟹Q(x)))$
  3. $(∀x(P(x))⇔(∀x(Q(x))))⟹(∀x(P(x)⇔Q(x)))$
  4. $(∀x(P(x)⇔Q(x)))⟹(∀x(P(x))⇔(∀x(Q(x))))$

  5. Are their any standard laws/rules of distribution of universal quantifier over conditional and binconditional that can help me solve this?

  6. Also rules for distribution of existential quantifier over conditional and binconditional?

Recently I came across distribution of quantifiers over $\vee$ and $\wedge$, which gave set theoretic interpretation of them as follows:

  • $((∀x)G(x)∨ (∀x)H(x))→ (∀x)(F(x)∨ G(x))$

    In set theoretic terms,
    if we have that $(f(G) = D ∨ f(H) = D)$, then we have $(f(G) ∪ f(H)) = D$

  • $(∃x)(G(x)∧ H(x))→((∃x)G(x)∧ (∃x)H(x))$

    In set theoretic terms,
    if we have that $(f(G) ∩ f(H)) ≥ 1$, then we have $(f(G) ≥ 1 ∧ f(H) ≥ 1)$

Can we say similar for distribution of quantifiers over conditional and biconditional (just to bring in more clarity)?

Best Answer

Formulas (1) and (4) are valid, i.e. they are true in every first-order $\mathcal{L}$-structure.

Formulas (2) and (3) are not valid, i.e. there exists a $\mathcal{L}$-structure in which they are not true. For instance, take the $\mathcal{L}$-structure $\mathcal{N}$ whose domain is $\mathbb{N}$ and whose interpretation of $P$ is $2\mathbb{N}$ (the set of even natural numbers), and whose interpretation of $Q$ is $\mathbb{N} \smallsetminus 2\mathbb{N}$ (the set of odd natural numbers). You have that the formula $\forall xP(x) \Rightarrow \forall x Q(x)$ is vacuously true in $\mathcal{N}$ (it claims that "if every natural number is even then every natural number is odd"), but the formula $\forall x(P(x) \Rightarrow Q(x))$ is false in $\mathcal{N}$ (it claims that "for every natural number, if it is even then it is odd"), therefore your formula (2) is false in $\mathcal{N}$. Similarly for the formula (3), since $A \Leftrightarrow B$ is equivalent to $(A \Rightarrow B) \land (B \Rightarrow A)$.

In general, when one talks about distributivity of something over something else (for instance, distributivity of $\land$ over $\lor$), one means that two formulas are logically equivalent. With this meaning, the answer to your question "Does the universal quantifier distribute over conditional or biconditional?" is negative since the formula $\forall xP(x) \Rightarrow \forall x Q(x)$ is not logically equivalent to the formula $\forall x(P(x) \Rightarrow Q(x))$ (your formula (1) is valid, but your formula (2) is not valid), and similarly the formula $\forall xP(x) \Leftrightarrow \forall x Q(x)$ is not logically equivalent to formula $\forall x(P(x) \Leftrightarrow Q(x))$ (your formula (4) is valid, but your formula (3) is not valid).