2
$\begingroup$

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

$\endgroup$
  • 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 '17 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 '17 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 '17 at 16:07
  • $\begingroup$ Great answers, thanks a lot. $\endgroup$ – Heptapod Aug 19 '17 at 16:09
4
$\begingroup$

One can give a more algebraic proof as follow $$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$$

$\endgroup$
0
$\begingroup$

No, the problem of your proof is that you are saying that if $x\subseteq C$ it is also $x\subseteq B$ because $x$ is arbitrary, which is wrong.

if you want to do it in this way you need to do it like this:

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

Case 1. $x\in B$.

Case 2. $x\in C$.

In case 1 $x\in B$ and since $x$ was arbitrary, $A\subseteq B$.

In case 2 $x\in C$ and $x\in A$ so $x \in A\cap C$ which implies that $x \in B\cap C$ therefore $x\in B$ and since $x$ was arbitrary, $A\subseteq B$.

EDIT:

in case 2 you can do it also like this:

Proof.

$\vdots$

In case 2 $x\in C$ and $x\in A$ so $x \in A\cap C$ which implies that $x \in B\cap C$ therefore $x\in B$ and we already showed that $A\subseteq B$ in this situation at case 1.

$\endgroup$

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.