# Is this proof correct?

• Jul 20th 2010, 04:31 PM
integral
Is this proof correct?
I found a Abstract algebra book in goodwill (Rofl)

I can not get how do prove something. It seems almost impossible in some cases.
This is a question in it:

Prove : $\displaystyle (A\cap B)'= A' \cup B'$

Where $\displaystyle n'=U\setminus n$

and U is the universal set.

Here is my attempted proof:
$\displaystyle (A \cap B)' \Rightarrow$
$\displaystyle x\in (U\setminus (A\cap B) \Rightarrow$
$\displaystyle (x\in U) \wedge (x\notin (A\cap B)) \Rightarrow$
$\displaystyle (x\in U) \wedge (x\notin A \wedge x\notin B) \Rightarrow$
$\displaystyle (x\in U \wedge x\notin A) \vee (x\in U \wedge x\notin B) \Rightarrow$
$\displaystyle (x\in (U \setminus A) \vee x\in(U\setminus B) \Rightarrow$
$\displaystyle x\in (U\setminus A \cup U\setminus B) \Rightarrow$
$\displaystyle x\in A' \cup B'$

$\displaystyle \therefore\,\, A'\cup B' \subseteq (A\cap B)'$

And the reverse is true. Therefore they must be equal.
Is this correct? (Bow)
• Jul 20th 2010, 06:11 PM
Ackbeet
Not all the steps are correct.

Your first step needs to be

$\displaystyle x\in(A \cap B)'\Rightarrow...$

Also,
$\displaystyle x\not\in(A\cap B)$ implies
$\displaystyle (x\not\in A)\vee(x\not\in B)$, not
$\displaystyle (x\not\in A)\land(x\not\in B).$
That's essentially a DeMorgan Law application. You fix this error, incidentally, in the next step.

Also, you should be more careful with your parentheses here:
$\displaystyle x\in (U\setminus A \cup U\setminus B).$
In context, I can tell that you meant
$\displaystyle x\in ((U\setminus A) \cup (U\setminus B)),$
but you don't want to write so that people can understand. Write so that no one can misunderstand!

All your steps are reversible, correct? So just change your implications to double implications, and you can then omit the sentence "And the reverse is true." (You mean converse, by the way.)

As Strunk and White have told us, "Omit needless words!"
• Jul 20th 2010, 07:08 PM
integral
How does $\displaystyle x\notin (A \cap B) \Rightarrow (x\notin A) \vee (x\notin B)$? $\displaystyle A \cap B$ is the intersection so you would say A and B are true, else it is false. Thus logical conjunction :"$\displaystyle \wedge$"
• Jul 21st 2010, 01:51 AM
Ackbeet
Except that you are negating the whole thing. You're essentially saying this:

$\displaystyle \neg(x\in(A\cap B)),$ which is the same as
$\displaystyle \neg((x\in A)\land(x\in B)),$ which is the same as
$\displaystyle (\neg(x\in A))\vee(\neg(x\in B)),$ which is the same as
$\displaystyle (x\not\in A)\vee(x\not\in B).$

Does that make sense?
• Jul 21st 2010, 10:25 AM
usagi_killer
Hi, I will try prove this using pure logic notation.

To prove $\displaystyle (A \cap B)' = A' \cup B'$ we need to show the following to be true:

1. If $\displaystyle x \in A' \cup B'$ then $\displaystyle x \in (A \cap B)'$

and

2. If $\displaystyle x \in (A \cap B)'$ then $\displaystyle x \in A' \cup B'$

Now I will show you how to prove 1. You can try 2. yourself (Smirk)

Let $\displaystyle p: x \in A' \cup B'$ and $\displaystyle q : x \in (A \cap B)'$ now 1. becomes $\displaystyle p \to q$

To prove this conditional proposition is true we will now go through all the possibilities. If p is false, then $\displaystyle p \to q$ is vacuously true. We can ignore this trivial case.

Thus we need to show if p is true and q is true then $\displaystyle p \to q$ is true.

Assume p is true.

$\displaystyle p: x \in A' \cup B' = (x \in A') \lor (x \in B')$

Now p is only true under 3 conditions: (using the 'inclusive-or' definition we have)

a) $\displaystyle (x \in A')$ is true and $\displaystyle (x \in B')$ is false

b) $\displaystyle (x \in A')$ is false and $\displaystyle (x \in B')$ is true

c) $\displaystyle (x \in A')$ is true and $\displaystyle (x \in B')$ is true

Now notice in a) $\displaystyle (x \in A') = \neg (x \in A)$

So if $\displaystyle \neg(x \in A)$ is true then $\displaystyle x \in A$ is false. Similarly $\displaystyle x \in B$ is true.

Likewise from b) you should conclude $\displaystyle x \in A$ is true and $\displaystyle x \in B$ is false.

c) $\displaystyle x \in A$ is false and $\displaystyle x \in B$ is false.

Now consider $\displaystyle q: x \in (A \cap B)' = \neg[x \in (A \cap B)] = \neg[(x \in A) \land (x \in B)]$

Using the results from a), b) and c) we see q is always true. Thus 1. is now proven.

Try 2. with the same principles :)
• Jul 22nd 2010, 03:27 PM
integral
Oh! I get it!.

I was thinking of OR as XOR.

If we use OR then the elements could be in the location AND is.

Proving that ( A intercect B)' is a subset. And once we prove the converse, we prove they are equal.

Right?
• Jul 23rd 2010, 07:04 AM
Ackbeet
I'm not sure I follow this post. Are you referring to usagi_killer's proof in post # 5?