Proving a Subset - $(A∪B)∩C⊆A∪(B∩C).$

Question

I'm having a hard time with my subset proof. I think I'm skipping over some steps.

Let $A$, $B$, and $C$ be sets. Prove that $(A ∪ B) ∩ C ⊆ A ∪ (B ∩ C).$

Theorem: $(A ∪ B) ∩ C ⊆ A ∪ (B ∩ C).$

Proof:

Let $x ∈ (A ∪ B) ∩ C$

Assume:

If $x ∈ A$ or $x ∈ B$, then $x ∈ C$; since $(A ∪ B) ∩ C$

If $x ∈ A$, then $x ∈ C$

If $x ∈ B$, then $x ∈ C$

$∴ x ∈ A ∪ (B ∩ C)$

Answer 1

I'm not really sure why that "assume" line is there. It should probably be "by our assumption that $x \in \cdots$".

---

Anyhow, I feel like you get the general idea of how this proof is meant to go - if you want to prove $A \subseteq B$, you want to show $x \in A \implies x \in B$. However, these things are a bit more complicated than that when you have multiple sets and such on each side.

I like to think of this in two steps - "unraveling" the left-hand side to figure out what sets $x$ is in, and what it isn't in, and trying to "ravel it back up" to make the right-hand side.

Some of your wording obscures this idea but you get the idea, I believe. Rewriting it would help your clarity come through.

• Assumption: $x \in (A \cup B) \cap C$
• Thus: $x \in (A \cup B)$ and $x \in C$ (to be in the intersection, it must be in both)
• Thus: $x \in A$ or $x \in B$ (to be in the union, it must be in one or the other, possibly both)

So, we know for sure $x\in C$, and $x$ is in one of (or both) $A,B$. We have "unraveled" this half of the proof, so to speak.

At this point it gets a bit tricky. It's handy here to take this by "cases" where $x \in A$ or $x \in B$.

• Suppose $x \in A$. Then $x \in A \cup (B \cap C)$
• Suppose $x \in B$ instead. Then since $x \in C$, $x \in B \cap C$ and thus $x \in A \cup (B \cap C)$

Thus, $x \in (A \cup B) \cap C \implies x \in A \cup (B \cap C)$, showing $(A \cup B) \cap C \subseteq A \cup (B \cap C)$, completing the proof.

---

I feel like you get the idea of what's going on and the basic idea - your writing simply obscures that fact. It's important to keep in mind why everything follows from one step to the next; writing that explanation out would be very helpful, both for your professor to follow your proof, and for yourself to justify what's going on.

Answer 2

It seems like you confuse the assumption and what you have to show.

You begin correct:

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

We want to show, that $x\in A\cup (B\cap C)$.

Since $x\in (A\cup B)\cap C$. It is $x\in A$ or $x\in B$ and $x\in C$.

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

If $x\notin A$, then $x\in B$. Hence $x\in B\cap C$. And therefore $x\in A\cup (B\cap C)$.

Answer 3

As Cornman notes, it seems you are having an issue primarily with sorting what you are given and how exactly that is meant to be used in what you are trying to prove. You write, "If $x\in A$ or $x\in B$, then $x\in C$," but you do not have an implication there. The overall implication you are trying to show is that $$ x\in(A\cup B)\cap C\implies x\in A\cup(B\cap C);\tag{1} $$ that is, you are trying to show that $(A\cup B)\cap C\subseteq A\cup(B\cap C)$ [recall that the definition of subset involves an implication, namely $A\subseteq B=\{x : x\in A\implies x\in B\}$].

To that end, you want to start by assuming $x\in(A\cup B)\cap C$, and then show that this assumption implies that $x\in A\cup(B\cap C)$. Note that if $(A\cup B)\cap C$ is somehow empty, then $(1)$ is vacuously true. So let's start by assuming $x\in(A\cup B)\cap C$ and see if we can establish that this necessarily implies that $x\in A\cup(B\cap C)$, as desired.

Here is one way of looking at it: $$ \begin{align*} x\in(A\cup B)\cap C &\implies x\in A\cup B\ \text{and}\ x\in C & \text{(def. of $\cap$)}\\[0.5em] &\implies (x\in A\ \text{or}\ x\in B)\ \text{and}\ x\in C & \text{(def. of $\cup$)}\\[0.5em] &\implies (x\in A\ \text{and}\ x\in C)\ \text{or}\ (x\in B\ \text{and}\ x\in C) & \text{(case analysis/distrib.)}\\[0.5em] &\implies (x\in A)\ \text{or}\ (x\in B\ \text{and}\ x\in C) & (\text{since}\ A\cap C\subseteq A)\\[0.5em] &\implies x\in A\ \text{or}\ x\in B\cap C & \text{(def. of $\cap$)}\\[0.5em] &\implies x\in A\cup(B\cap C) & \text{(def. of $\cup$)} \end{align*} $$ Ultimately, you should definitely know distributivity rules concerning $\cap$ and $\cup$, which tells us that $$ (A\cup B)\cap C=(A\cap C)\cup(B\cap C), $$ whereby it should be clear that we have $$ (A\cup B)\cap C\subseteq A\cup(B\cap C) $$ as a natural result since $A\cup(B\cap C)$ is certainly "bigger" than $(A\cap C)\cup(B\cap C)$.

Answer 4

Theorem: (A ∪ B) ∩ C ⊆ A ∪ (B ∩ C).

Proof:let x ∈ (A ∪ B) ∩ C Assume: if x ∈ A or x ∈ B,then x ∈ C; since (A ∪ B) ∩ C if x ∈ A,then x ∈ C if x ∈ B,then x ∈ C ∴ x ∈ A ∪ (B ∩ C)

You are trying to do a proof by cases.   The form is to establish that the premise may be split into two(or more) cases, and that the conclusion can be derived in every case.

• Take any $x$ such that $x\in(A\cup B)\cap C$.
• That is: $x\in A$ or $x\in B$, and also $x\in C$.
• So it may be the case that $x\in A$ and $x\in C$, or else the case that $x\in B$ and $x\in C$.
  • Assuming first case, then ...something goes here... ; and so $x\in A\cup(B\cap C)$ in that case.
  • Assuming the second case, then ...something else goes here... ; and so $x\in A\cup(B\cap C)$ in that case too.
• Therefore $x\in (A\cup B)\cap C$ entails $x\in A\cup(B\cap C)$.
• Hence $(A\cup B)\cap C\subseteq A\cup(B\cap C)$.

Answer 5

Your proof isn't correct because it's not the case that if $x \in A$ or $x \in B$, then $x \in C$. But there are a couple of ways to see this. First, we can use Boolean algebra:

$$(A \cup B) \cap C = (A \cap C) \cup (B \cap C) \subseteq A \cup (B \cap C) \text{ because } A \cap C \subseteq A.$$

Second, we can prove it directly. If $x \in (A \cup B) \cap C$, then $x \in C$. If $x \in B$, then $x \in B \cap C$, which means $x \in A \cup (B \cap C)$. If $x \notin B$, then because $x \in A \cup B$, we know that $x \in A$, which again means $x \in A \cup (B \cap C)$. Thus, if $x \in (A \cup B) \cap C$, we have proved that $x \in A \cup (B \cap C)$ so $(A \cup B) \cap C \subseteq A \cup (B \cap C).$