0
$\begingroup$

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 Answers 1

2

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.

  • 0
    I guess I'm just too paranoid about what I'm allowed to do. :) Thanks man for setting me back on track.2012-11-19