# Is it true that $\forall A\in \mathcal{F} P(A) \wedge\forall B\in\mathcal{G} P(B) \leftrightarrow\forall C\in(\mathcal{F}\cup\mathcal{G})P(C)$

While working on proof for $(\cap\mathcal{F})\cap(\cap\mathcal{G})=\cap(\mathcal{F}\cup\mathcal{G})$ I came up with this equivalence:

$$\forall A\in \mathcal{F} P(A) \wedge\forall B\in\mathcal{G} P(B) \leftrightarrow\forall C\in(\mathcal{F}\cup\mathcal{G})P(C),$$

where $\mathcal{F}$ and $\mathcal{G}$ are two non-empty set families.

The problem is I have intuitive notion why this equivalence works, but I cannot find a proof for it. I'm stuck with the part where bounded quantifiers $\forall A\in\mathcal{F}$ and $\forall B\in\mathcal{G}$ are recombined to a single quantifier $\forall C\in(\mathcal{F}\cup\mathcal{G})$. I know that universal quantifier distributes over conjunction, but I'm troubled with the way two quantifiers bounding to two different families are recombined to a single quantifier bounding to union of the two families.

Is this really an equivalence? If it is, is there a proof for it?

EDIT: Would this be a proof?

$$\forall A\in(\mathcal{F}\cup\mathcal{G})P(A)\\ \leftrightarrow \forall A(A\in(\mathcal{F}\cup\mathcal{G})\rightarrow P(A))\\ \leftrightarrow \forall A((A\notin\mathcal{F}\wedge A\notin\mathcal{G}) \vee P(A))\\ \leftrightarrow\forall A((A\notin\mathcal{F}\vee P(A)) \wedge(A\notin\mathcal{G}\vee P(A)))\\ \leftrightarrow\forall A(A\in\mathcal{F}\rightarrow P(A)\wedge\forall A(A\in\mathcal{G}\rightarrow P(A))\\ \leftrightarrow\forall A\in\mathcal{F} P(A)\wedge\forall A\in\mathcal{G}P(A)$$

Side question: Is there any good book or some other source that covers rules and identities for bounded quantifiers?

## 1 Answer

Unpack the definitions of the bounded quantifiers and the definition of set union. You are given $$(\forall a)(a \in F \to P(a))$$ and $$(\forall b)(b \in G \to P(b)).$$ You want to prove $$(\forall c)(\{c \in F \lor c \in G\} \to P(c)).$$ And that is now a simple exercise in first-order logic.

• I guess I'm just too paranoid about what I'm allowed to do. :) Thanks man for setting me back on track. – LavaScornedOven Nov 19 '12 at 17:49