Is this proof correct?

**integral** · July 20th 2010, 04:31 PM

I found a Abstract algebra book in goodwill

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

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

Where $n'=U\setminus n$

and U is the universal set.

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

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

And the reverse is true. Therefore they must be equal.
Is this correct?

**Ackbeet** · July 20th 2010, 06:11 PM

Not all the steps are correct.

Your first step needs to be

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

Also,
$x\not\in(A\cap B)$ implies
$(x\not\in A)\vee(x\not\in B)$ , not
$(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:
$x\in (U\setminus A \cup U\setminus B).$
In context, I can tell that you meant
$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!"

**integral** · July 20th 2010, 07:08 PM

How does $x\notin (A \cap B) \Rightarrow (x\notin A) \vee (x\notin B)$ ? $A \cap B$ is the intersection so you would say A and B are true, else it is false. Thus logical conjunction :" $\wedge$ "

**Ackbeet** · July 21st 2010, 01:51 AM

Except that you are negating the whole thing. You're essentially saying this:

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

Does that make sense?

**usagi_killer** · July 21st 2010, 10:25 AM

Hi, I will try prove this using pure logic notation.

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

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

and

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

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

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

To prove this conditional proposition is true we will now go through all the possibilities. If p is false, then $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 $p \to q$ is true.

Assume p is true.

$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) $(x \in A')$ is true and $(x \in B')$ is false

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

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

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

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

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

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

Now consider $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

**integral** · July 22nd 2010, 03:27 PM

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?

**Ackbeet** · July 23rd 2010, 07:04 AM

I'm not sure I follow this post. Are you referring to usagi_killer's proof in post # 5?

Thread: Is this proof correct?

LinkBack

Thread Tools

Display