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


Ex-5(a)
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$

Ex-5(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


Ex-7(a)

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)$

Ex-7(b)

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)$


Ex-8

(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


Ex-9
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)$

Ex-11(b)
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 :)


4 comments:

  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?

    ReplyDelete
  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...

    ReplyDelete
  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.

    ReplyDelete
  4. It seems I'm not the only person who finds the huge identity verification exercises at the end of this section uninstructive. I was able to get the first one (exercise 15 in the newest version of the book), but I have spent more hours of my life than I would have liked to picking at them and just getting lost in the morass of set notation. They really aren't worth it, and I feel genuine disappointment at Velleman for putting problems that basically amount to busywork into, otherwise, such a good text. Since all he says is to verify it somehow, Venn diagrams are fine.

    ReplyDelete