Subject: HW8: 200909_102694_CH
From: "William J. Rapaport"
Date: Wed, 4 Nov 2009 20:28:30 -0500 (EST)
Concerning HW 8, problem 12:
First, some notation:
I'll use "u" for union,
"n" for intersection,
"e" for set-membership,
and "<=" for the subset relation
(which, don't forget, looks like a less-than-or-equal sign).
Several of you have emailed me with sample proofs of:
A u (A n B) = A.
I haven't yet seen any that are completely correct.
So let me give you some suggestions.
*One* way to prove that two sets are equal is to prove that each is a subset of the other, because, for any sets S,T: S=T <-> (S<=T ^ T<=S).
So you could consider 2 cases:
case 1: Au(AnB) <= A
case 2: A <= Au(AnB)
To prove case 1, show that an arbitrary x e Au(AnB) is also such that
x e A (see suggestion in next paragraph).
To show case 2, show the converse of that.
To show the first subset relationship, convert the
"x e Au(AnB)" proposition into its propositional-logic definition;
then you can use the rules of propositional logic to show that x e A.
*Another* way to prove that two sets are equal is to use the other
method that I showed in lecture, namely, start with the definition of
Au(AnB) = {x | x e Au(AnB)}
= [here, replace the set by its propositional logic definition,
and keep transforming it till you get to...]
= {x | x e A} = A.