# Understanding the proof technique of $A\cup (B\cap C)\subseteq (A\cup B)\cap (A\cup C)$.

I used to learn it in a different way; \begin{align} x\in A\cup (B\cap C)&\implies x\in A \textrm{ or } (x\in B \textrm{ and } x\in C)\tag{1}\\ &\implies (x\in A \textrm{ or } x\in B) \textrm{ and } (x\in A \textrm{ or } x\in C)\tag{2}\\ &\implies x\in (A\cup B)\cap (A\cup C)\tag{3} \end{align} using the different rules.

This <link> on page 2 has shown another way which questioned me a lot but I will try to make short questions.

It starts to assume that $x\in A\cup (B\cap C)$, that is, assuming with two cases, $x\in A$ and $x\in B\cap C$. The first case seems no problem to me when knowing about or-introduction. But the last case doesn't really make sense to me. For example, if $x\in B\cap C$ then it means that $x$ is both in $B$ and $C$, so how can $x$ be in $A\cup B$ while ignoring the set $C$? I mean, where is the set $C$ if $x$ is in $A\cup B$? The same way, where the set $B$ is if $x\in A\cap C$.

How exactly is this proof technique structured? The proof above shows clearly what happens from $(1)$ to $(2)$, and from $(2)$ to $(3)$. This is the only thing that makes sense to me. But not like this link. It doesn't look like how it is implied but I feel like it's just checking if it's verified or that it only looks at the right side to make the left side imply.

• $x\in A\cup(B\cap C)$ means $x\in A$ or $x\in B\cap C$. I'm guessing you meant the or there, correct? – Daniel W. Farlow Jul 16 '15 at 22:58
• @DanielW.Farlow I understand what it means. I used "and" to the cases. Should I write "or" instead? – UnknownW Jul 16 '15 at 23:00
• I am referring the first sentence of your paragraph starting, "It starts to assume ..." – Daniel W. Farlow Jul 16 '15 at 23:01
• @DanielW.Farlow What I meant is that it shows the cases (i) $x\in A$, (ii) $x\in B\cap C$. Is it wrong to say "and" between the cases while knowing that it's not $x\in A\cap (B\cap C)$ I am talking about? – UnknownW Jul 16 '15 at 23:05

It starts to assume that $x∈A∪(B∩C)$ , that is, assuming with two cases, $x∈A$ and $x∈B∩C$ . The first case seems no problem to me when knowing about or-introduction. But the last case doesn't really make sense to me. For example, if $x∈B∩C$ then it means that $x$ is both in $B$ and $C$ , so how can $x$ be in $A∪B$ while ignoring the set $C$ ? I mean, where is the set $C$ if $x$ is in $A∪B$ ? The same way, where the set $B$ is if $x∈A∩C$ .

It's not ignored, it's just examined in parallel.   If you can start with premise $Z$, then prove $X$ by one path, and in parallel prove $Y$ by another, then you have proven the conjunction $X\wedge Y$.   (If $Z\vdash X$ and $Z\vdash Y$, then $Z\vdash X\wedge Y\;$.)

$$\cfrac{ \cfrac{ \cfrac{ \cfrac{ \cfrac{ \cfrac{ x\in B\cap C }{x\in B \wedge x\in C} }{x\in B} }{x\in A\vee x\in B} }{x\in A\cup B} \quad \cfrac{ \cfrac{ \cfrac{ \cfrac{ x\in B\cap C }{x\in B \wedge x\in C} }{x\in C} }{x\in A\vee x\in C} }{x\in A\cup C} }{x\in A\cup B \wedge x\in A\cup C} }{x\in (A\cup B)\cap(A\cup C)}$$

It uses the Implies-subset relation which states that (by definition)

$$[A\subseteq B]\iff\forall x[x\in A\implies x\in B]$$

$$[x\in A\cap B]\iff[x\in A\wedge x\in B]$$

($\wedge$ means "and") and

$$[x\in A\cup B]\iff[x\in A\vee x\in B]$$

and of course, $\vee$ means "or" (which is $x\in A$, $x\in B$ or both)

The last step (i.e., the "second case") makes sense, but it could be worded more clearly. To keep it firmly in mind, here it is:

In the second case (i.e., the case "$x\in B$ and $x\in C$"), we have $x\in A\cup B$ and $x\in A\cup C$, by the definition of a union. As before, by the definition of an intersection, it follows that $x\in (A\cup B)\cap (A\cup C)$.

Okay, let's dissect this and see how it makes sense. First, the author begins the proof with "Let $x\in A\cup (B\cap C)$." Since the second case is all about what happens when $x\in B\cap C$, you clearly have that $x\in A\cup B$ and $x\in A\cup C$ by the definition of a union (the size of $A$ and whether or not its elements intersect with those of $B$ and $C$ does not matter since you are considering the union). What you need, namely $x\in(A\cup B)\cap(A\cup C)$, simply follows from this observation.

If $x\in B\cap C$ then it means that $x$ is both in $B$ and $C$, so how can $x$ be in $A\cup B$ while ignoring the set $C$?

You are not ignoring the set $C$--you are simply stating that $x$ is in both $A\cup B$ and $A\cup C$ (<-- $C$ is not being ignored there). Does that make sense?

For what it's worth, the way you structured your own proof is much cleaner and elegant in my opinion. I would have done likewise. The proof in the PDF is verbose and convoluted.

Suppose $x \in A \cup (B \cap C)$. We have two cases here: $$x \in A \;\mathrm{or}\; x \in B \cap C$$

You already know the case where $x \in A$ so I will leave that. Let's assume that $x \in B \cap C$. So, we have $$x \in B \; \mathrm{and} \; x \in C$$

So, $$x \in B \subseteq A \cup B$$ and also $$x \in C \subseteq A \cup C$$ Hence, $$x \in (A \cup B) \cap (A \cup C)$$