# Showing one set is a subset of another

Let's say you have sets $A,\, B,$ and $C.$

How would you show that $[(A-B) - C]\subseteq (A-C)$ using a venn diagram or logical translations?

How can this even be done when you don't know the members of $A,\, B,$ or $C$?

• Look at this for some examples. I also recommend you look at the book How to Prove It: A Structured Approach, by D.J. Velleman. – Git Gud Oct 23 '13 at 22:04
• If $x \in [(A-B)-C]$ that means $x$ is in $A$, but in neither $B$ nor $C$. How would you characterize an element of $(A-C)$ similarily? – Arthur Oct 23 '13 at 22:05
• @Arthur x is in A, but not in C. How can I combine the two to conclude they're subsets of each other? – Bob Shannon Oct 23 '13 at 22:09
• @Bob They aren't subsets of each other. – Git Gud Oct 23 '13 at 22:11
• @Bob: but the two sets are not equal (not equivalent). What IS TRUE is that $\,(A - B) - C\,$ is a subset of $\,A - C,\,$ which simply means that all of $\,(A-B) - C\,$ is "contained within" $A - C$. By definition of "subset", that means every element of $\,(A - B) - C\,$ is necessarily also an element of $\,A - C\,$ but not necessarily the other way around. Two sets $X, Y$ are equal if and only if $X\subseteq Y$ AND $Y\subseteq X$. Here we have only one containment. – Namaste Oct 24 '13 at 12:49

You'd need to use logical translations, implicitly (no need for logic symbols though - words work fine), in the sense that you need to use the definition of set-minus where $\;x \in X - Y\;$ means that $\;x \in X\;$ AND $\,x \notin Y.$

Showing that set-membership in $\,X\,$ implies set-membership in $\,Y,\,$ proves that $\,X\subseteq Y$. Logically, this is establishing that $\,x \in [(A - B) - C] \implies x \in (A - C).$

In this case, start by assuming $\,x \in (A - B) - C,\,$ and then unpack what this means using the definition of set-minus. Using this you can argue that it must follow that $\,x \in A-C.\,$ This is equivalent to proving that $\,(A-B) -C \subseteq A - C$.

• Ah, so this would 'show' that they are subsets of each other? – Bob Shannon Oct 23 '13 at 22:05
• I suppose I am confusing the word 'show' with 'prove'. – Bob Shannon Oct 23 '13 at 22:06
• See the edited answer, Bob. – Namaste Oct 23 '13 at 22:07
• @Bob To clarify, this only proves that $(A-B)-C\subseteq A-C$. It doesn't prove that they are subsets of each other, it just proves one is a subset of the other. – Git Gud Oct 23 '13 at 22:09
• @Bob What my answer is saying is that we can express $[(A - B) - C] \subseteq (A - C)$ as the logically equivalent statement $\,x \in [(A-B)-C] \rightarrow x \in (A-C).\,$ So to prove $\,[(A - B) - C] \subseteq (A - C),\,$ we need to prove $\,x \in [(A-B)-C] \rightarrow x \in (A-C).\,$ To prove this, we start by assuming $\,x \in [(A - B) - C]$, and show that this implies $(\rightarrow)\,$ that $\,x \in (A-C).\,$ That's a very straightforward task, but once you've done that, you've proven the equivalent statement $\,[(A - B) - C] \subseteq [A - C]$. – Namaste Oct 24 '13 at 12:56

Let $x\in(A-B)-C$. By the definition of set difference we know that $x\in A-B$ and $x\notin C$. Since $x\in A-B$ we know that $x\in A$ and $x\notin B$. Thus we have $x\in A$ and $x\notin C$ which implies that $x\in A-C$ and we can conclude that $(A-B)-C\subseteq A-C$.

• How do we know this about $x$? What is $x$? – Trevor Wilson Oct 23 '13 at 22:17
• amWhy posted the first step for Bob by letting x be an element of (A-B)-C. I was just letting Bob know what needs to follow by using the definition of set difference. – 1233dfv Oct 23 '13 at 22:36
• Oh, I see. But I think if you're going to post this as an answer rather than a comment on amWhy's answer, then it should be self-contained. – Trevor Wilson Oct 23 '13 at 22:38
• I understand. Is my edit acceptable? – 1233dfv Oct 23 '13 at 22:57
• Yep, looks good now. – Trevor Wilson Oct 23 '13 at 23:02