1

Prove or disprove the following: for any sets A, B, and C we have (A − B) − C = A − (B ∪ C). (If the statement is false, then construct an explicit counterexample.)

Correct Answer (1 of many I suppose):

 Let A = B = C; then (A − B) − C = ∅ − C = ∅ but A − (B − C) = A − ∅ = A. 

 As long as A is nonempty, this gives a counterexample.

My Question:

I'm not really understanding the proof stuff with Discrete Mathematics. Can somebody please dumb down this answer and explain how you get it?

I understand what sets are, so I guess I should imagine A, B, & C are sets... but honestly I'm at a complete loss after that.

Théophile
  • 24,627
I'm Hungry
  • 181
  • 1
    Well, that's a counter example of a different statement for one thing. – fleablood Dec 07 '17 at 19:41
  • You misstated the second expression in your supposed counterexample. Hint: start with three sets in general position (i.e the Venn diagram has $8$ regions) and look at each expression. – Ethan Bolker Dec 07 '17 at 19:42
  • Your counterexample doesn't work, because the second half should be $$A \setminus (B \cup C) = A \setminus (A \cup A) = A \setminus A = \emptyset,$$ and there is no contradiction. Try drawing a Venn diagram to understand the claim. – Théophile Dec 07 '17 at 19:42
  • Probably the $B \cup C$ should be a $B - C$. – S. M. Roch Dec 07 '17 at 19:43
  • 1
    That is a counter example to the statement $(A-B) -C = A - (B -C)$ which is false. The statement $(A-B) - C = A-(B\cup C)$ is actually true. – fleablood Dec 07 '17 at 19:45
  • Please amend your Q so that the proposition to be proved or disproved and the proposition in your A are the same so that we can tell which one is the right one and answer you. – DanielWainfleet Dec 07 '17 at 20:19

1 Answers1

1

That is a counter example for a different statement:

Statement 1: Which is false

$(A- B) - C = A - (B- C)$

Counter example: Let $A = B = C$ and suppose $A$ is not empty.

Then $(A- B) = (A - A) = \{x \in A| x\not \in A\}= \{\}$ (because nothing is both in and not in a set ) $= \emptyset$.

So $(A- B) - C = (A-A) - A = \emptyset - A = \{x \in \emptyset| x \not \in A\} = \{\} $ (because nothing is in the emptyset [whether or not it is in $A$]) $= \emptyset$.

However.

$A-(B-C) = A- (A-A) = A- \emptyset = \{x \in A| x \not \in A\} = A$ (because nothing is in the empty so as all of $A$ is not in the emptyset, so all of $A$ that is not in the empty set is the same thing as all of $A$).

So $(A-B) -C = \emptyset$ and $A-(B-C) = A$ and these are not equal. So that is a counter example

If you want $A = B = C =\{1\}$

$(A - B) - C = (\{1\} - \{1\}) - C = \emptyset - C = \{\} - \{1\} = \{\} = \emptyset$

$A - (B- C) = A - (\{1\} - \{1\}) = A- \{\} = A = \{1\}$.

Maybe it will be more useful if we considered:

$A = \{1,2,3,4,5\}, B= \{1,3,5,7,9,11\}, C=\{1,4,7,10,13\}$

$(A - B) - C = (\{1,2,3,4,5\}- \{1,3,5,7,9,11\}) - C = (\{\color{red}{\not 1}, 2, \color{red}{\not 3},4,\color{red}{\not 5}\}) - C = \{2,4\} - \{1,4, 7,10,13\} = \{2, \color{red}{\not 4}\} = \{2\}$

While

$A - (B - C) = A - (\{1,3,5,7,9,11\} - \{1,4,7,10,13\}) = A- (\{ \color{red}{\not 1},3,5, \color{red}{\not7},9,11\})= A - \{3,5,9,11\}= \{1,2,3,4,5\}- \{3,5,9,11\}= \{1,2,\color{red}{\not 3},4,\color{red}{\not 5}\} = \{1,2,4\}$

Which are two different sets.

Statement 2: Which is true

$(A - B) - C = A - (B\cup C)$.

Pf: $(A- B) = \{x\in A; x\not \in B\}$

$(A- B) - C = \{x\in A; x \not \in B; x \not \in C\}$.

where as

$B \cup C = \{x \in B\ OR \ x \in C\}$

$A - (B\cup C) = \{x \in A \ BUT \ (x \text { is not in } B\ \text{nor in } C)\}=$

$\{x \in A; x \not \in B; x \not \in C\}$.

Those are the same sets.

As an illustration to get a fell for it (but NOT a proof; an example is NEVER a proof)

Let $A = \{1,2,3,4,5\}, B= \{1,3,5,7,9,11\}, C=\{1,4,7,10,13\}$ (same as above)

$(A - B) - C = (\{1,2,3,4,5\}- \{1,3,5,7,9,11\}) - C = (\{\color{red}{\not 1}, 2, \color{red}{\not 3},4,\color{red}{\not 5}\}) - C = \{2,4\} - \{1,4, 7,10,13\} = \{2, \color{red}{\not 4}\} = \{2\}$

(same as above)

while

$A - (B \cup C) = A - ( \{1,3,5,7,9,11\}\cup \{1,4,7,10,13\}) = $

$A - (\{1,3,5,7,9,11, \text { and }\color{blue}{1},4,\color{blue}{7},10,13\} = A - \{1,3,4,5,7,9,10,11,13\}$

$ \{1,2,3,4,5\} - \{1,3,4,5,7,9,10,11,13\} = \{\color{red}{\not 1}, 2,\color{red}{\not 3}, \color{red}{\not 4}, \color{red}{\not 5}\} = \{2\}$.

These are the same sets.

fleablood
  • 124,253