1
$\begingroup$

Note: I am aware of the duplicate, but I would like to get my proof specifically checked.

I am trying to prove the following:

For all sets $A$, $B$, and $C$, if $A \cap C \subseteq B \cap C$ and $A \cup C \subseteq B \cup C$, then $A \subseteq B$.

I found this one a bit tricky, but I think I was able to get it in the end.

Proof:

Let $x \in A \cap C$.

Therefore, $x$ is an element of both $A$ and $C$. And by the hypothesis, $x$ is an element of both $B$ and $C$.

However, the problem here is that we're saying that, for all element $x$ that are in both $A$ and $B$ (we are excluding the ones that are in $A$ but not in $C$), $x$ is also an element of both $B$ and $C$. Therefore, if I am not mistaken, this is insufficient to to prove that $A \subseteq B$.

Now let $y \in A \cup C$.

Therefore, $y$ is an element of $A$ or $C$ or both.

Case 1: Let $y$ be an element of $A$ but not $C$. Then $A \subseteq B$, since $y$ would then, by the hypothesis, also be an element of $B$, since we would have that $A = A \cup C \subseteq B \cup C = B$, since $C = \emptyset$.

Case 2: Let $y$ be an element of $C$ but not $A$. Then we have that $A \subseteq B$, since we would have that $C = A \cup C \subseteq B \cup C$, since $A = \emptyset$.

Case 3: Let $y$ be an element of both $A$ and $C$. Then it must be that all elements in $A \cup C$ are in $A \cap C$, which implies that $A = C$. And since we have that $A \cap C \subseteq B$, we have that $A \cap A = A \subseteq B$.

Therefore, $A \subseteq B$.

Q.E.D.

I would greatly appreciate it if people could please take the time to review my proof.

EDIT:

Thank you all for the enlightening feedback. I understand where I went wrong and have written a new proof, taking your advice into account.

New Proof:

Let $x \in A$.

The hypothesis states (assumes) that $A \cap C \subseteq B \cap C$ and $A \cup C \subseteq B \cup C$.

These assumptions imply two possibilities: $x \in C$ or $x \not\in C$.

Case 1: Suppose that $x \in C$.

$\therefore x \in A \cap C \subseteq B \cap C$

$\therefore x \in B \cap C$

$\therefore x \in B$

$\therefore A \subseteq B$

Case 2: Suppose that $x \not\in C$.

$\therefore x \in A \cup C \subseteq B \cup C$

$\therefore x \in B \cup C$

$\therefore x \in B$ (Since $x \in B \cup C$ and $x \not\in C$.)

$\therefore A \subseteq B$

Therefore, we have that $A \subseteq B$.

Q.E.D.

$\endgroup$
  • 1
    $\begingroup$ Why not post your proof as an answer on the duplicate and ask for feedback there? $\endgroup$ – Chickenmancer Jul 31 '18 at 21:02
  • 2
    $\begingroup$ @Chickenmancer Posting it as an answer would imply that I know it's correct. The entire reason I'm posting it is to get it checked for correctness. Posting it as an answer sounds like a good way to get downvotes. $\endgroup$ – The Pointer Jul 31 '18 at 21:03
  • 2
    $\begingroup$ You want to show $A \subseteq B$. That means that the first strategy you should try should be to assume $x\in A$ and prove $x\in B$. $\endgroup$ – Arthur Jul 31 '18 at 21:04
  • 1
    $\begingroup$ You want to prove that $A \subseteq B$. That means you need to show that every element of $A$ is an element of $B$. Your proof is much longer than it could have been. $\endgroup$ – Mark Jul 31 '18 at 21:07
  • 1
    $\begingroup$ A good way to learn how to write proofs is to read some proofs. In this case, you have a good proof to read in the answers to the duplicate question. Your proof contains blind alleys ("if I am not mistaken ... this is insufficient") and what appear to be non sequiturs ("let $y$ be an element of $A$ but not $C$, ..., since $C = \emptyset$"). Proofs of this kind are essentially mechanical: if you follow standard strategies you will find the proof. $\endgroup$ – Rob Arthan Jul 31 '18 at 21:12
4
$\begingroup$

Many problems with your proof ....

First and foremost, the very set-up is not right. You need to assume that $x \in A$, and then show that $x \in B$ ... you never do this

But some other issues as well:

Case 1: Let $y$ be an element of $A$ but not $C$. Then $A \subseteq B$, since $y$ would then, by the hypothesis, also be an element of $B$, since we would have that $A = A \cup C \subseteq B \cup C = B$, since $C = \emptyset$.

Why would $C = \emptyset$? Just because $y$ is not in $C$? That does not follow

Case 2: Let $y$ be an element of $C$ but not $A$. Then we have that $A \subseteq B$, since we would have that $C = A \cup C \subseteq B \cup C$, since $A = \emptyset$.

Same mistake. Just because $y$ is not in $A$ does not mean there is nothing in $A$ at all

Case 3: Let $y$ be an element of both $A$ and $C$. Then it must be that all elements in $A \cup C$ are in $A \cap C$, which implies that $A = C$. And since we have that $A \cap C \subseteq B$, we have that $A \cap A = A \subseteq B$.

And a similar mistake again: just because $y$ is in both $A \cap C$ and $A \cup C$ does not mean that these two sets are the same.

$\endgroup$
  • $\begingroup$ Yes, I think you are correct. Thank you for the feedback. I will revise my proof. $\endgroup$ – The Pointer Jul 31 '18 at 21:10
  • 1
    $\begingroup$ @ThePointer Sounds good ... maybe explicitly add that to your post under the heading of 'Attempt 2' so that earlier comments can be understood in the context of your original attempt. $\endgroup$ – Bram28 Jul 31 '18 at 21:13
  • 1
    $\begingroup$ @Pointer your second attempt is good! Good job! $\endgroup$ – Bram28 Aug 1 '18 at 13:03
2
$\begingroup$

I'm assuming you're new to writing proofs. As you write proofs, make sure you focus on what your end goal is. A lot of people new to proofs often struggle with this.

What are you trying to show? You're trying to show that $A \subseteq B$.

How do you show this? Take an arbitrary element $x \in A$ and show that $x \in B$.

What assumptions do you have available? $A \cap C \subseteq B \cap C$ and $A \cup C \subseteq B \cup C$.


Here's a sketch on how to start, with thoughts in italics as I type these statements.


Let $x \in A$ be arbitrary.

Look at the assumptions you have available. They suggest two possible cases.

Then $x \in C$ or $x \notin C$.

Case 1. Suppose $x \in C$. Then since $x \in A$ and $x \in C$, $x \in A \cap C$. Therefore, $x \in B \cap C$ by assumption. Since $x \in B \cap C$, we have that $x \in B$ and $x \in C$. Since $x \in A \implies x \in B$, $A \subseteq B$.

Great, you've shown it for one case, now show it for the other:

Case 2. Suppose $x \notin C$. Then since $x \in A$, it follows that $x \in A \cup C$. [...]


Now, continue the proof.

$\endgroup$
  • $\begingroup$ Yes, thank you for the feedback. I am editing the main post now. $\endgroup$ – The Pointer Jul 31 '18 at 21:48
  • 1
    $\begingroup$ @ThePointer Good job. $\endgroup$ – Clarinetist Jul 31 '18 at 21:58
0
$\begingroup$

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

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