Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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