2
$\begingroup$

I'm working on this proof for some students I am tutoring and I've gotten a little stuck. I want to show them how to do a proof in complete, extravagant detail and get them familiar with ''element chasing'' in set proofs for an intro to discrete class. I just got stuck and maybe I'm just too tired to see it. Here's where I am so far.

Notation: $A^c$ is the complement of $A$. $A\backslash B$ means $A \cap B^c$.

Prove that $A\setminus (B\setminus C) = (A\setminus B) \cup (A\setminus C^c)$ for sets $A,\ B,\ C$ in some Universal Set $U$.

Proof: ($\Leftarrow$)

Let $x \in (A \backslash B) \cup (A\backslash C^c)$.

This means that $x\in (A \cap B^c) \cup (A \cap C^{c^c})$.

Simplifying, this means that $x \in (A \cap B^c) \cup (A \cap C)$.

So $x\in (A \cap B^c)$ or $x\in (A\cap C)$.

Now we have two cases.

Case 1: $ x \in A \cap B^c.$

So $x \in A$ and $ x\in B^c$.

Note: Now we must think outside the box a little bit. We want to show that $x$ must be in $C$ but we don't have anything to do with $C$ in what we are able to derive from our assumptions. We only have that $x$ is in $A$ and not in $B$. This is where we must consider our problem. We have the Universe $U$. We know that $A,B,C$ are all in the universe. So any point we chose in those sets must also be in $U$. So think about this for a moment. We don't know if our $x$ is in $C$ or not. We need it to be in order to have the solution we are after. So where is $x$ in relation to $C$? It's either in it or not in it. So $x \in C$ or $x\in C^c$. So we can examine each of these cases and we will find that if $x \in C^c$, we will get a contradiction.

Case 1.a. Suppose $x \in C$.

Then $x \in A$ and $x \in B^c$ and $x \in C$.

So $x \in A$ and $ x\in (B^c \cap C)$.

So $x \in A \cap (B^c \cap C)$.

So $x \in A \cap (B \cap C^c)^c$.

So $x \in A \cap (B\backslash C)^c$.

So $x \in A \backslash (B \backslash C)$.

Case 1.b. Suppose $x \in C^c$.

Then $x \in A$ and $x\in B^c$ and $x\in C^c$.

So $x \in A \cap C^c$ and $x \in A\cap B^c$.

Now I'm stuck. I know that I need to develop a contradiction because $x$ cannot be in $C^c$, but I'm just not seeing it. Any suggestions? If I can see this one, I'll be able to see the similar method I need to develop for case 2: $x\in A \cap C$ where I need to examine whether $x \in B$ or $B^c$.

$\endgroup$
2
$\begingroup$

In case 1: $$x\in A\cap B^c\\x\in A,x\in B^c\\x\in A,x\not\in B\\x\in A,x\not\in B\cap C^c\\x\in A,x\not\in B\backslash C\\x\in A,x\in(B\backslash C)^c\\x\in A\cap(B\backslash C)^c\\x\in A\backslash(B\backslash C)$$

You don't need subcases (in case 1) for $x\in C, x\not\in C$.

(Incidentally, case 2 is as simple: there, you don't need subcases for $x\in B,x\not\in B$.)

$\endgroup$
  • $\begingroup$ I understand that. And there's a much simpler version of this just unpacking definitions. But I'm really trying to get them to see how to use contradictions and to really examine everything. It's for a class of computer science majors. This proof is more about incorporating all the elements of proof writing (except induction) and making sure they know how to use them. $\endgroup$ – Tyler Murphy Feb 20 '14 at 7:33
  • $\begingroup$ I don't see that the steps in this answer are different from the types of steps you took. Would you prefer them written in order? $x\in A\cap B^c$; $x\in A,x\in B^c$; $x\in A,x\not\in B$; $x\in A,x\not\in B\cap C^c$; $x\in A,x\not\in B\backslash C$; $x\in A,x\in(B\backslash C)^c$; $x\in A\cap(B\backslash C)^c$; $x\in A\backslash(B\backslash C)$. $\endgroup$ – msh210 Feb 20 '14 at 7:45
  • $\begingroup$ @TylerMurphy, I've edited. $\endgroup$ – msh210 Feb 20 '14 at 7:51
  • $\begingroup$ Thanks. It makes more sense now that I see the error I made that the other answer pointed out. I should have just slept on it. Thank you very much. $\endgroup$ – Tyler Murphy Feb 20 '14 at 8:00
2
$\begingroup$

There is yet another solution, namely you can rewrite $$A\setminus (B\setminus C) = (A\setminus B) \cup (A\setminus C^c)$$ using $$X - Y = X \cap Y^c$$ into $$A\cap \color{blue}{(B\cap C^c)^c} = (A\cap \color{red}{B^c}) \color{red}{\cup} (A\cap \color{red}{C}).$$ Now it is enough to use De Morgan law for blue part of LHS and the distributive law for red part of RHS: $$A\cap \color{blue}{(B^c\cup C)} = A \cap (\color{red}{B^c \cup C}).$$

I hope this helps $\ddot\smile$

$\endgroup$
  • $\begingroup$ This solution infinitely better than all the others. $\endgroup$ – goblin Feb 20 '14 at 10:07
  • $\begingroup$ @user18921 Thank you $\ddot\smile$ $\endgroup$ – dtldarek Feb 20 '14 at 10:12
1
$\begingroup$

In your proof, there exists an error. Note the following fact :

$x \in A \cap (B^c \cup C)$ iff

$x \in A \cap (B \cap C^c)^c$.

$\endgroup$
  • $\begingroup$ I knew I needed a fresh pair of eyes. That fixed everything. Thank you. $\endgroup$ – Tyler Murphy Feb 20 '14 at 7:54
0
$\begingroup$

it might be enlightening for your students to do this 'algebraically':

If you go to the indicator functions and the set $\mathbf{2}^U=\mathbb{F}_2^U$ then

The symmetric difference of $a$ and $b$ is a+b

The complement of $a$ is $1+a$

The intersection of $a$ and $b$ is $ab$

The union of $a$ and $b$ is $U(a,b)=a+b+ab$

$a$ set-minus $b$ is $a(1+b)$

So the LHS $$ a(1+(b(1+c))=a+ab(1+c)=a+ab+abc $$ and the RHS $$ U(a(1+b),a(1+1+c))=U(a+ab,ac)=a+ab+ac+abc+aac=a+ab+abc $$ (note that $x^2=x$ and $x+x=0$)

$\endgroup$
0
$\begingroup$

Here is how I would present this proof.

The approach I learned is to start with the most complex side, calculate the elements of that set using the definitions, and then simplify, and finally work towards the other side of the equality.

In other words, for all $\;x\;$, \begin{align} & x \in (A \setminus B) \cup (A \setminus C^c) \\ \equiv & \qquad \text{"definition of $\;\cup\;$"} \\ & x \in A \setminus B \;\lor\; x \in A \setminus C^c \\ \equiv & \qquad \text{"definition of $\;\setminus\;$, twice; definition of $\;^c\;$"} \\ & (x \in A \land \lnot(x \in B)) \;\lor\; (x \in A \land \lnot(\lnot(x \in C))) \\ \equiv & \qquad \text{"logic, simplify: double negation, factor out common conjunct"} \\ & x \in A \land (\lnot(x \in B) \lor x \in C) \\ \equiv & \qquad \text{"logic: DeMorgan -- to work towards $\;x \in A \land \lnot \ldots\;$, suggested by goal"} \\ & x \in A \land \lnot (x \in B \land \lnot(x \in C)) \\ \equiv & \qquad \text{"definition of $\;\setminus\;$, twice"} \\ & x \in A \setminus (B \setminus C) \\ \end{align} This proves the equality by set extensionality.

The only things needed for this type of proof are knowledge of the definitions, and of the laws of (propositional/predicate) logic.

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