Please check this proof: $A \cap B \subseteq C \wedge A^c \cap B \subseteq C \Rightarrow B \subseteq C$

Question

I'm taking Discrete Math this semester. While I understand the mechanics of proofs, I find that I must refine my understanding of how to work them. To that end, I'm working through some extra problems on spring break. Please read over this proof I did from an exercise from the book. I apologize in advance for poor formatting. I just couldn't figure out how to make this one big block of LaTeX commands. I'm still learning.

Let A, B, C be subsets of a Universal set U.

Given $A \cap B \subseteq C \wedge A^c \cap B \subseteq C \Rightarrow B \subseteq C$

Proof: Part 1:

$$ \begin{array}{rcl} B & = & (A \cap B) \cup (A^c \cap B) \\ & = & (A \cap B) \cup B , \text{definition of intersection} \\ & = & B \, \square \end{array} $$

Part 2: Part 1 states $B = (A \cap B) \cup (A^c \cap B)$.
By assumption, $(A \cap B) \subseteq C \wedge (A^c \cap B) \subseteq C$
$\therefore B \subseteq C$

Thanks
Andy

Answer 1

Why is $ A^c \cap B = B $? I think there is a typo/mistake in that line. What I believe you want to say is that $ (A \cap B) \cup ( A^c \cap B ) = ( A \cup A^c) \cup B $, by the distributive law, and that $ = ( A \cup A^c) \cup B = U \cup B = B $.

Answer 2

Formatting looks good to me. There is a typo in part 1, as pointed out by user138320, but there is also a typo in what he mentioned: The distributive law yields $$(A \cap B) \cup ( A^c \cap B ) = ( A \cup A^c) \cap B = U \cap B = B$$ Part 2 is sufficient, but it lacks necessary formalism. Additionally, you made a typo by having $\cup$ instead of $\cap$ in the "By assumption" part. Now, when you want to show that a set is a subset of another, it is best to start with an arbitrary element in the subset and show that this element is also in the "larger" set. In your example, consider some $x \in B$. From the decomposition $$B = (A \cap B) \cup ( A^c \cap B )$$ you know that either $x \in A^c \cap B$ or $x \in A \cap B$, but by assumption $A \cap B \subseteq C$ and $A^c \cap B \subseteq C$, so $x \in C$. This shows that for every element $x \in B$ you also have $x \in C$, thus $B \subseteq C$.

Moreover, say that you are dealing with a different problem where you want to show that two sets are equal. In order to do this you would follow the same procedure given above, but both ways. In other words, suppose you want to show two sets $X$ and $Y$ are the same. You would first start out by showing that $$x \in X \Rightarrow x \in Y$$ and $$y \in Y \Rightarrow y \in X$$ Showing this guarantees that $X = Y$, as this is the definition of two sets being equal. Overall, appealing to an arbitrary element in a set is usually the most direct way of carrying out a formal proof involving sets. Hope this helps!

Answer 3

Here is an alternative proof which goes back to the definitions and solves the problem using the rules of logic: \begin{align} & A \cap B \subseteq C \;\land\; A^c \cap B \subseteq C \\ \equiv & \qquad \text{"definition of $\;\subseteq\;$, twice"} \\ & \langle \forall x :: x \in A \cap B \Rightarrow x \in C \rangle \;\land\; \langle \forall x :: x \in A^c \cap B \Rightarrow x \in C \rangle \\ \equiv & \qquad \text{"logic: simplify: $\;\forall\;$ distributes over $\;\land\;$"} \\ & \langle \forall x :: (x \in A \cap B \Rightarrow x \in C) \;\land\; (x \in A^c \cap B \Rightarrow x \in C) \rangle \\ \equiv & \qquad \text{"logic: simplify by merging consequents"} \\ & \langle \forall x :: x \in A \cap B \;\lor\; x \in A^c \cap B \;\Rightarrow\; x \in C \rangle \\ \equiv & \qquad \text{"definition of $\;\cap\;$, twice; definition of $\;^c\;$"} \\ & \langle \forall x :: (x \in A \;\land\; x \in B) \;\lor\; (x \;\not\in\; A \;\land\; x \in B) \;\Rightarrow\; x \in C \rangle \\ \equiv & \qquad \text{"logic: simplify: $\;\land\;$ distributes over $\;\lor\;$"} \\ & \langle \forall x :: (x \in A \;\lor\; x \not\in A) \;\land\; x \in B \;\Rightarrow\; x \in C \rangle \\ \equiv & \qquad \text{"logic: excluded middle; simplify"} \\ & \langle \forall x :: x \in B \;\Rightarrow\; x \in C \rangle \\ \equiv & \qquad \text{"definition of $\;\subseteq\;$"} \\ & B \;\subseteq\; C \\ \end{align}

Note how every step is actually an equivalence, so this also proves the other direction.