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$



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!

  • $\begingroup$ I'm marking this one as the answer simply because it addressed more of the problems that I deal with in writing good proofs. I remember my professor telling me that I need to show some $x$ in a smaller set exists in the larger set. For some reason, I just have brain block in putting that on paper. $\endgroup$ – Andrew Falanga Mar 27 '14 at 20:01

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 $.

  • $\begingroup$ You're correct. There is a mistake on that line. That's why I posted here. I see that I was on the right track but should have used distribution. I was thinking that $A^c \cap B = B$ because it seems reasonable to me that $x \notin A$ intersected with $B$ must only be $B$. That's probably not sound though I was visualizing it. The distribution that you point out is what I should have gone for. $\endgroup$ – Andrew Falanga Mar 27 '14 at 19:55
  • $\begingroup$ The distributive law yields $ (A \cap B) \cup ( A^c \cap B ) = ( A \cup A^c) \cap B $, not $ ( A \cup A^c) \cup B$. $\endgroup$ – dsm Mar 27 '14 at 21:08
  • $\begingroup$ I think I see where I confused people. I wasn't saying that $(A \cap B) \cup (A^c \cap B) = (A \cap B) \cup B$ because of distribution. I was treating $(A^c \cap B)$ by itself. Because the premise stated that A,B,C were subsets of U, I think I was correct that this was equal to B. However, the more I think about it, this just wasn't good reasoning. $\endgroup$ – Andrew Falanga Mar 27 '14 at 23:37

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.

  • $\begingroup$ Thanks for the alternative approach. Not to mention, thanks so much for some new LaTeX commands so that I can embed text in the math. $\endgroup$ – Andrew Falanga Mar 27 '14 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.