# Proving Set Theory Basics

Quick introduction, I am a just graduated high school senior working on logic and proofs just to get a better feel for my mathematics degree this fall. My book does not have a solutions page. Here is my proof to the following equality. $$A \cup(B \cap C)=(A\cup B)\cap (A\cup C)$$

1. Suppose $$x \in (A\cup B)\cap (A\cup C)$$.

2. This means $$x$$ must lie in $$A\cup B$$ and $$A\cup C$$.

3. Since $$x \in A \cup B$$ and $$x \in A \cup C$$, then $$x \in A$$.

4. Since $$x \in A$$, then $$x \in A \cup (B\cap C)$$.

I am unsure if the last step is strong enough to show equivalence. Thanks for the help!

• Step 3 is incorrect: consider $A=\{1\}$, $B=C=\{2\}$, and $x=2$. Jun 13 at 2:33
• Thanks for the correction. I consider the case where $x \not\in A$ in Cornman's answer. Jun 13 at 3:07
• 3) isn't correct. But even if you were you have just proven $(A\cup B)\cap (A\cup C) \subseteq A \subseteq A\cup (B\cap C)$ [which isn't true BTW] and that is not equality. Jun 13 at 3:41

I would not say that how you write it down is sufficient to prove the equivalence. It reads more of a proof for $$x\in(A\cup B)\cap (A\cup C)$$. So $$A\cup (B\cap C)\subseteq (A\cup B)\cap (A\cup C)$$

Also you ignore the case where $$x\notin A$$. This can happen also. So you can distinguish two cases.

1. $$x\in A$$.

2. $$x\notin A$$, then $$x\in B\cap C$$, as $$x\in B$$ and $$x\in C$$ has to hold in this case.

Further more, you should adopt are more formal writing style. You do not have to exeggarate, what many beginners do, but I dont like this step 1. step 2. ... style.

I think you can now fix your proof accordingly.

Example for a more formal proof:

(Introduction not part of the proof) We want to show $$(A\cup B)\cap (A\cup C)=A\cup (B\cap C)$$.So an equality of sets. This is important to note, as there are many different mathematical objects. Sets, functions, numbers, ... and for every mathematical object equality is shown differently.

For sets we have to show equality by proving the both inclusions $$\subseteq$$ and $$\supseteq$$.

So when we want to proof two sets $$A$$ and $$B$$ are equal, hence $$A=B$$, this is done in two steps.

One is to show $$A\subseteq B$$. The other is $$A\supseteq B$$.

By definition of $$A\subseteq B$$ ($$A$$ is a subset of $$B$$), we have to proof that for every $$x\in A$$, we have $$x\in B$$.

Example: $$\{1,2\}\subseteq \{1,2,3\}$$, because every element in $$\{1,2\}$$ is also an element in $$\{1,2,3\}$$.

But $$\{1,2,4\}$$ is not a subset of $$\{1,2,3\}$$ as there is an element, namely $$4$$, which is not an element of $$\{1,2,3\}$$.

As your example involves a seperation of cases, let me give a different example.

DeMorgan's Law

Let $$A,B\subseteq X$$, then we have $$(A\cup B)^c=A^c\cap B^c$$, where $$A^c$$ notes the complement of $$A$$ in $$X$$. Hence $$A^c=X\setminus A$$. The set of all $$x\in X$$ with $$x\notin A$$.

We have to proof equality of sets. Hence $$(A\cup B)^c\subseteq A^c\cap B^c$$ and $$(A\cup B)^c\supseteq A^c\cap B^c$$.

We can do this like this:

$$x\in (A\cup B)^c\Rightarrow x\in X$$ and $$x\notin (A\cup B)$$

$$\Rightarrow x\in X$$ and $$x\notin A$$ and $$x\notin B$$.

$$\Rightarrow x\in X$$ and $$x\notin A$$ and $$x\in X$$ and $$x\notin B$$.

$$\Rightarrow x\in X\setminus A$$ and $$x\in X\setminus B$$

$$\Rightarrow x\in A^c$$ and $$x\in B^c$$

$$\Rightarrow x\in A^c\cap B^c$$.

So this ends the proof of $$(A\cup B)^c\subseteq A^c\cap B^c$$.

It remains to show that $$A^c\cap B^c\subseteq (A\cup B)^c$$. This can be done by reading the proof above "backwards", and justifying all the steps, changing every $$\Rightarrow$$ into $$\Leftrightarrow$$.

$$x\in A^c\cap B^c\Leftarrow x\in X\setminus A$$ and $$x\in X\setminus B$$

$$\Rightarrow x\in X$$ and $$x\notin A$$ and $$x\in X$$ and $$x\notin B$$

$$\Rightarrow x\in X$$ and $$x\notin A$$ and $$x\notin B$$

$$\Rightarrow x\in X$$ and $$x\notin (A\cup B)$$

$$\Rightarrow x\in X\setminus (A\cup B)$$

$$\Rightarrow x\in (A\cup B)^c$$.

Ending the proof.

So basically two times exactly the same proof, which can be shortend, by just writing:

$$x\in (A\cup B)^c\Rightarrow x\in X$$ and $$x\notin (A\cup B)$$

$$\Leftrightarrow x\in X$$ and $$x\notin A$$ and $$x\notin B$$.

$$\Leftrightarrow x\in X$$ and $$x\notin A$$ and $$x\in X$$ and $$x\notin B$$.

$$\Leftrightarrow x\in X\setminus A$$ and $$x\in X\setminus B$$

$$\Leftrightarrow x\in A^c$$ and $$x\in B^c$$

$$\Leftrightarrow x\in A^c\cap B^c$$.

So this would be an example for, what I consider, a formal proof.

• Thanks for the help. What would be an example of a more formal writing style? Here is what I have written down now: Suppose $x \in (A \cup B) \cap (A \cup C)$, then $x \in A \cup B$ and $x \in A \cup C$. This leaves us with two cases $x \in A$ or $x \not\in A$. If $x \in A$, then $x \in A \cup (B \cap C)$. If $x \not\in A$, then $x \in B \cap C$. Thus, $(A \cup B) \cap (A \cup C)=A \cup (B \cap C)$. Jun 13 at 2:58
• Yes, I would consider this "more formal", but as I said you do not have to exeggarate. You will learn how to write mathematically over time. At the end of the proof you skip one step. "Then x\in B\cap C$". You might (should!) note that then$x\in B$and$x\in C$. So$x\in A\cup B$and$x\in A\cup C$. So$x\in (A\cup B)\cap (A\cup C)$. This does not imply equality. You have proven$A\cup (B\cap C)\subseteq (A\cup B)\cap (A\cup C)$. Do you know why, and why this is not enough to show equality? You can now reverse all steps and show the other implication like that. Jun 13 at 3:08 • Oh. So to prove equality, I must do the same process from$A \cup (B \cap C)$to$(A \cup B) \cap (A \cup C)\$? It makes intuitive sense. Is proving equality like proving a biconditional statement? Jun 13 at 3:17
• Yes, exactly. This is very important, that showing set equality is a two-step affair. However, once you have proven one inclusion, the other one can be deduced normally directly by just reversing the steps. I am extending my answer at the moment by a full prove. Jun 13 at 3:19
• Thank you for answering my question, your advice was helpful. I think I am now going to write down all the set theory definitions and axioms into a list for easier access. Jun 13 at 3:38

Here's a set inclusion chart:

$$A$$ $$B$$ $$C$$ $$A\cup(B\cap C)$$ $$(A\cup B)\cap(A\cup C)$$
Y Y Y Y Y
Y Y N Y Y
Y N Y Y Y
Y N N Y Y
N Y Y Y Y
N Y N N N
N N Y N N
N N N N N

Because the last two columns are the same, the last two sets are the same.

• I like the logic table idea, but would this count as a proof? If it is informal, then what would be the formal way of saying this? Jun 13 at 16:56