4
$\begingroup$

Prove by element-wise: $A \cup (B \cap C) = (A \cup B) \cap (A \cup C).$

This is easy to prove by Venn Diagram, which I have already done. I do not, however, know how to prove using this technique. I know it has to do with proving each is a subset, but I do not understand the general method to prove this formally?

  • 0
    No, sorry I have never heard o$f$ that?2011-02-28

3 Answers 3

4

Proving "by element-wise" (I do hope you are translating; that's awful abuse of language) means showing that each side is a subset of the other. In other words, the argument looks something like:

Suppose $x\in A\cup(B\cap C)$; then .... stuff ...., so $x\in (A\cup B)\cap (A\cup B)$; therefore, $A\cup(B\cap C) \subseteq (A\cup B)\cap (A\cup C)$.

Now suppose that $y\in (A\cup B)\cap (A\cup C)$. Then ... stuff..., so $y\in A\cup (B\cap C)$. Therefore, $(A\cup B)\cap (A\cup C) \subseteq A\cup(B\cap C)$.

Since each is contained in the other, $A\cup(B\cap C)=(A\cup B)\cap(A\cup C)$. QED.

Or you can try to do both inclusions at the same time using equivalences. Then you would have something like

$x\in A\cup (B\cap C) \Longleftrightarrow$ stuff $\Longleftrightarrow$ more stuff $\Longleftrightarrow$ even more stuff $\Longleftrightarrow x\in (A\cup B)\cap (A\cup C)$.

In other words, "element-wise" means "chasing an element": pick an element in one side, show it has to be in the other and vice versa. After all, equality of sets is defined in terms of them containing the same elements, not in terms of Venn diagrams.

  • 0
    Sorry, I wasn't aware of my apparent "awful abuse of language"? :( Thanks for the explanation!2011-02-28
1

$(\Rightarrow)$: Suppose $x \in A \cup (B \cap C)$. Then $x \in A$ or $x \in B$ and $x \in C$. So $x \in A$ or $x \in B$ and $x \in A$ or $x \in C$. So $x \in (A \cap B) \cap (A \cup C)$.

$(\Leftarrow)$: Try this one.

  • 1
    The crucial step, from 2nd to 3rd statement, is not obvious (at this level). How do you justify the manipulation of English 'and's and 'or's?2011-02-28
0

“Element-wise” means using the definitions of an intersection and a union and an equality of sets:

$\forall x. x\in(A\cup B) \leftrightarrow x\in A\lor x\in B$

$\forall x. x\in(A\cap B) \leftrightarrow x\in A\land x\in B$

$(A=B) \leftrightarrow (\forall x.x\in A \leftrightarrow x\in B)$

Reason about $x$ which is “an element”. Then the deduction rules of intuitionistic logic give you the desired theorem.