Friday, April 16, 2010

how to prove it - ch1, sec1.4(operations on sets) ex

This section introduces set operations: Intersection, Union and Difference ($\cap , \cup$ and \)

Most important take away of this section is that, there are two main ways to prove equivalence of two sets
1. By drawing venn diagrams
2. By converting set operations into logic statements(with logic connectives) and then using logical equivalences. Following are the conversion of 3 basic set operations...
x $\in$ $A \cup B$ = $(x \in A) \lor (x \in B)$
x $\in$ $A \cap B$ = $(x \in A) \land (x \in B)$
x $\in$ $A \setminus B$ = $(x \in A) \land \lnot(x \in B)$

Ex-1(a) {3, 12}
Ex-1(b) {1,3,7,12,20,35} \ {x | x is a prime} = {1,12,20,35}
Ex-1(c) {1,3,12,35} $\cup$ ({3,7,12,20} \ {x | x is a prime}) = {1,3,12,35} $\cup$ {12,20} = {1,3,12,20,35}

Ex-2(a) {United States, Germany, China, Australia, France, India, Brazil}
Ex-2(b) {Germany} \ {x | x is a country in Europe} = {}
Ex-2(c) {Germany, France} \ A = {France}

Ex-4 look in the attached pic

x $\in$ $A \setminus (A \cap B)$
= $(x \in A) \land x \notin (A \cap B)$
= $(x \in A) \land \lnot((x \in A) \land (x \in B))$
= $(x \in A) \land (\lnot (x \in A) \lor \lnot (x \in B))$
= $((x \in A) \land \lnot (x \in A)) \lor ((x \in A) \land \lnot (x \in B))$
= $(x \in A) \land \lnot (x \in B)$
= $x \in A \setminus B$

x $\in$ $A \cup (B \cap C)$
= $(x \in A) \lor (x \in (B \cap C))$
= $(x \in A) \lor ((x \in B) \land (x \in C))$
= $((x \in A) \lor (x \in B)) \land ((x \in A) \lor (x \in C))$
= $(x \in A \cup B) \land (x \in A \cup C)$
= $x \in (A \cup B) \cap (A \cup C)$

Ex-6 look in the attached pic


x $\in$ $(A \cup B) \setminus C$
= $(x \in (A \cup B)) \land (x \notin C)$
= $((x \in A) \lor (x \in B)) \land (x \notin C)$
= $((x \in A) \land (x \notin C)) \lor ((x \in B) \land (x \notin C))$
= $(x \in A \setminus C) \lor (x \in B \setminus C)$
= $x \in (A \setminus C) \cup (B \setminus C)$


x $\in$ $A \cup (B \setminus C)$
= $(x \in A) \lor x \in (B \setminus C)$
= $(x \in A) \lor ((x \in B) \land \lnot(x \in C))$
= $((x \in A) \lor (x \in B)) \land ((x \in A) \lor \lnot(x \in C))$
= $(x \in (A \cup B)) \land \lnot((x \in C) \land \lnot(x \in A))$
= $(x \in (A \cup B)) \land \lnot(x \in (C \setminus A))$
= $x \in (A \cup B) \setminus (C \setminus A)$


(a) x $\in$ $(A \setminus B) \setminus C$
= $(x \in (A \setminus B)) \land (x \notin C)$
= $((x \in A) \land (x \notin B)) \land (x \notin C)$
= $(x \in A) \land (x \notin B) \land (x \notin C)$
= $(x \in A) \land \lnot((x \in B) \lor (x \in C))$
= $(x \in A) \land \lnot(x \in (B \cup C))$
= $x \in A \setminus (B \cup C)$

(b) x $\in$ $A \setminus (B \setminus C)$
= $(x \in A) \land \lnot(x \in (B \setminus C))$
= $(x \in A) \land \lnot((x \in B) \land \lnot(x \in C))$
= $(x \in A) \land ((x \notin B) \lor (x \in C))$
= $((x \in A) \land (x \notin B)) \lor ((x \in A) \land (x \in C))$
= $(x \in (A \setminus B)) \lor (x \in (A \cap C))$
= $x \in (A \setminus B) \cup (A \cap C)$

(c) from analysis of b, clearly b and c are same

(d) x $\in$ $(A \setminus B) \cap (A \setminus C)$
= $(x \in (A \setminus B)) \land (x \in (A \setminus C))$
= $((x \in A) \land (x \notin B)) \land ((x \in A) \land (x \notin C))$
= $((x \in A) \land (x \in A)) \land ((x \notin B) \land (x \notin C))$
= $(x \in A) \land \lnot((x \in B) \lor (x \in C))$
= $(x \in A) \land \lnot(x \in (B \cup C))$
= $x \in A \setminus (B \cup C)$

(e) from analysis of a and d, clearly a,d and e are same

A = {1,2,3)
B = {2,4}

$(A \cup B)$ = {1,2,3,4}
$(A \cup B) \setminus B$ = {1,3} , which is not A

Ex-11(a) Look in the attached pic, its clear that $(A \cup B) \setminus C \hspace{2} \subseteq \hspace{2} A \cup (B \setminus C)$

Clearly, for two can be made non-equal by making $A \cap C$ non-empty
A = {1,2,3,4}
B = {3,4,5,6}
C = {0,2,3,4,7}

$(A \cup B) \setminus C$ = {1,5,6}
$A \cup (B \setminus C)$ = {1,2,3,4,5,6}

Rest of the exercises are pretty similar to the ones done, so I'm passing them :)


  1. Thank you for all your posts, they are really helpful.
    Can you please post any of #13 or #14 from section 1.4 just so that I can see how you do proves with symmetrical difference?

  2. Tried to do 13)a) using logical sentences, but it gets too big and I resorted to Venn Diagrams. 13)a) Would be {[(xeA) or (xeB)] and negation of (xe inter)} or (xeC). From there it gets too complicated...

  3. 15) can be done this way: Draw three Venn diags. In the first, the end result. In the second, what the exercise has already given. In the third, draw the areas that: (1) will be removed, that is, belong to the second and third diagrams and (2) the areas that still need to be added. See what set it is and there is your answer.