This is Velleman's exercise 3.5.4:

Suppose $A \cap C \subseteq B \cap C$ and $A \cup C\subseteq B \cup C$. Prove that $A \subseteq B$

This is the proof given by the book (which I understand completely):

Proof. Suppose x ∈ A. We now consider two cases:

Case 1. $x \in C$. Then $x ∈ A \cap C$, so since $A \cap C\subseteq B \cap C, x \in B \cap C$, and therefore $x \in B$.

Case 2. $x \notin C$. Since $x \in A, x \in A \cup C$, so since $A \cup C\subseteq B \cup C$, $x \in B \cup C$. But $x \notin C$, so we must have $x \in B$.

Thus, $x \in B$, and since x was arbitrary, $A \subseteq B$.

I was wondering if one could write a proof like this one in below:

Proof. Let x be an arbitrary element of A. Then by $A \cup C \subseteq B \cup C$, we have either $x \in B$ or $x \in C$. Now we consider these two cases:

Case 1. x is an element of B.

Case 2. x is an element of C.

Since in one of the cases $x \in B$ and since x was arbitrary, $A \subseteq B$.

  • 4
    $\begingroup$ No, this does not work. Because that is kinda the reason you have to consider 2 cases. When you have case 1, there is nothing to show. But when you have case 2, you are not done. $\endgroup$
    – Cornman
    Aug 19, 2017 at 16:01
  • 1
    $\begingroup$ Note that your attempt doesn't use at all the fact that $A\cap C\subseteq B\cap C$ and should be a big hint that it is missing steps and vital information to make it correct. In the real world, you may make conjectures all the time where not all of the hypotheses are necessary but while studying from a book at least 99 times out of 100 every given hypothesis is absolutely necessary. $\endgroup$
    – JMoravitz
    Aug 19, 2017 at 16:03
  • 2
    $\begingroup$ Note that $A\cup C\subseteq B\cup C$ does not by itself imply that $A\subseteq B$. For example $\{1\}\cup \{1\}\subseteq \emptyset\cup \{1\}$ but $\{1\}\not\subseteq\emptyset$ $\endgroup$
    – JMoravitz
    Aug 19, 2017 at 16:07

2 Answers 2


One can give a more algebraic proof as follow: $$ \begin{array}{lcl} A & = & A\cup (A \cap C)\subseteq A\cup(B\cap C) \\ & = & (A \cup B)\cap (A\cup C)\subseteq (A\cup B)\cap (B\cup C) \\ & =& B\cup(A \cap C)\subseteq B\cup (B\cap C) \\ & =& B \end{array} $$


First, from $A \cap C \subseteq B \cap C$, we have:

$A \cap C \subseteq B \cap C$

$\Rightarrow$ $A \cap C \subseteq B \cap C \subseteq B$

$\Rightarrow$ $A \cap C \subseteq B$

Then, from $A \cup C \subseteq B \cup C$, we have:

$A \cup C \subseteq B \cup C$

$\Rightarrow$ $A \subseteq A \cup C \subseteq B \cup C$

$\Rightarrow$ $A \subseteq B \cup C$

Also, $A \cap C \subseteq B$

$\Rightarrow$ $(A \cap C) \cup (A \setminus C) = A \subseteq B \cup (A \setminus C)$

And, $A \subseteq B \cup C$

$\Rightarrow$ $(A \setminus C) \subseteq (B \cup C) \setminus C = (B \setminus C) \subseteq B$

$\Rightarrow$ $(A \setminus C) \subseteq B$

$\Rightarrow$ $B \cup (A \setminus C) = B$

Therefore, $A \subseteq B \cup (A \setminus C) = B$, which means $A \subseteq B$ is true.


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.