5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Git Gud Oct 23 '13 at 22:04
  • $\begingroup$ 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? $\endgroup$ – Arthur Oct 23 '13 at 22:05
  • $\begingroup$ @Arthur x is in A, but not in C. How can I combine the two to conclude they're subsets of each other? $\endgroup$ – Bob Shannon Oct 23 '13 at 22:09
  • $\begingroup$ @Bob They aren't subsets of each other. $\endgroup$ – Git Gud Oct 23 '13 at 22:11
  • 1
    $\begingroup$ @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. $\endgroup$ – Namaste Oct 24 '13 at 12:49
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Ah, so this would 'show' that they are subsets of each other? $\endgroup$ – Bob Shannon Oct 23 '13 at 22:05
  • $\begingroup$ I suppose I am confusing the word 'show' with 'prove'. $\endgroup$ – Bob Shannon Oct 23 '13 at 22:06
  • 1
    $\begingroup$ See the edited answer, Bob. $\endgroup$ – Namaste Oct 23 '13 at 22:07
  • $\begingroup$ @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. $\endgroup$ – Git Gud Oct 23 '13 at 22:09
  • 1
    $\begingroup$ @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]$. $\endgroup$ – Namaste Oct 24 '13 at 12:56
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ How do we know this about $x$? What is $x$? $\endgroup$ – Trevor Wilson Oct 23 '13 at 22:17
  • $\begingroup$ 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. $\endgroup$ – 1233dfv Oct 23 '13 at 22:36
  • $\begingroup$ 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. $\endgroup$ – Trevor Wilson Oct 23 '13 at 22:38
  • $\begingroup$ I understand. Is my edit acceptable? $\endgroup$ – 1233dfv Oct 23 '13 at 22:57
  • $\begingroup$ Yep, looks good now. $\endgroup$ – Trevor Wilson Oct 23 '13 at 23:02

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.