Proving Set Theory Equality: How to Use Sentential Calculus Rules

[JoeRocket]

Hi Everyone!

I would really appreciate some help with this set proof.

Homework Statement

Show that, for any sets A, B, ((A ∪ B) ∩ A) = (A ∩ A') ∪ (A ∩ B).
(Hint: Remember that a complement of a complement is just the original set.)

Homework Equations

I can use any sentential calculus rules to prove this equality.

The Attempt at a Solution

I think that the key to this problem is to use the SC distribution rule. But using distribution on the left yields (A ∩ A) ∪ (A ∩ B), and I can't think of anyway to get the left side to (A ∩ A'). There is a hint with the question about complements of complements, but I don't see how to use that. I have tried variations of double negation and still can't get it started. If I can get the left side to ((A` ∪ B) ∩ A) before distribution that would work, but I'm not sure how to get there!

Thanks in advance for the help, I just need help getting this question started!

 

[lanedance]

i'm not totally convinced after a quick look:

((A ∪ B) ∩ A) = (A ∩ A) ∪ (B ∩ A) = (A) ∪ (A ∩ B) =...

(A ∩ A') ∪ (A ∩ B) = (empty) ∪ (A ∩ B) =...

assume you can pick an element a in A, that is not in B. Its in the 1st, but not in the 2nd?

 

[HallsofIvy]

Hi Everyone!

I would really appreciate some help with this set proof.

Homework Statement

Show that, for any sets A, B, ((A ∪ B) ∩ A) = (A ∩ A') ∪ (A ∩ B).
(Hint: Remember that a complement of a complement is just the original set.)

You can't prove it- it's not true!

If A and B are disjoint the A\cap B is empty and, of course, A\cap A' is empty. If A and B are disjoint, then the right side is the empty set. But A is always a subset of A\cup B so (A\cup B)\cap A= A.

As a counter example, let A= {1, 2, 3, 4} and B= {0} in the set of integers. Then A\cap A'= \Phi, and A\cap B= \Phi so (A\cap A')\cup (A\cap B)= \Phi. But on the left, A\cup B= \{0, 1, 2, 3, 4\} so (A\cup B)\cap A= \{0, 1, 2, 3, 4\}\cap \{1, 2, 3, 4\}= \{1, 2, 3, 4\}= A.

Your hint mentions "complement of a complement" but you have no "complement of a complement" in the problem. Perhaps you have miscopied the problem.

Homework Equations

I can use any sentential calculus rules to prove this equality.

The Attempt at a Solution

I think that the key to this problem is to use the SC distribution rule. But using distribution on the left yields (A ∩ A) ∪ (A ∩ B), and I can't think of anyway to get the left side to (A ∩ A'). There is a hint with the question about complements of complements, but I don't see how to use that. I have tried variations of double negation and still can't get it started. If I can get the left side to ((A` ∪ B) ∩ A) before distribution that would work, but I'm not sure how to get there!

Thanks in advance for the help, I just need help getting this question started!

 

[JoeRocket]

You two are my heroes. I started looking into the more because I believed the same thing. I copied the question from my online class system into this forum, but then I found that he had entered the questions online wrong. Else where in our class literature, the question is written as ((A ∪ B) ∩ A) = (A ∩ A'') ∪ (A ∩ B), which I can solve.

I think I learned more from the original, wrong question!

Thanks again for the help.