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?


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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.