Cot 3100h spring Homework #3 Solutions 1 this is what I meant to be question a




Yüklə 25.61 Kb.
tarix20.04.2016
ölçüsü25.61 Kb.
COT 3100H Spring Homework #3 Solutions

1)
THIS IS WHAT I MEANT TO BE QUESTION A...
a) (B  C)  (B – A)  (C – A).
We must prove the following: (B – A)  (C – A).
This means, for an arbitrarily chosen element x, we must show the following:
if x(B – A), then x(C – A).
We will prove this using the direct proof method.
1) Assume x(B – A).

2) By definition of set difference, this means xB and xA.

3) Since B  C and xB, by definition of subset, we know that xC.

4) By definition of set difference since, xC and xA, x(A – C), as desired.


REAL QUESTION A
a) ((A  B)  (B  C))  (A  C).
This statement is true. This means, we must prove that A  C.
We must show that for an arbitrary xA that xC and that there exists some

element y such that yA but yC.


First, let's consider an arbitrary xA. Since A  B, by the definition of proper

subset we can conclude that xB. Similarly, using the given information again,

since B  C, we can conclude that xC. This proves the first part of what we

need to show.


Now, since we know that A  B, in follows that there exists an element y such

that yA but yB. But, if yB, since B  C, it follows that yC. Thus, we have

shown that there exists an element y such that yA but yC as desired.
REAL QUESTION B

b) ((A  B)  (A  C))  ((B  C)  (C  B)).
This statement is false as well. Consider the following counter example:
A = , B = {1}, C={2}
Here clearly, (A  B)  (A  C) since the empty set is a proper subset of all

non-empty sets. But both of (B  C) and (C  B) are false here.


I MEANT FOR THIS TO BE THE QUESTION C...
c) ((A  C)  (B  C))  A  B  C.
This statement is false. Consider the following counter example:
A = {1}, B = {2}, C={1,2}. Clearly we have that (A  C)  (B  C). But, in

this example we have that A  B = C, thus it is false that A  B  C.


REAL QUESTION C AND D - ANSWERS ARE IN QUESTION #3 because I goofed up!!!
2) Let A, B and C be arbitrary sets taken from the set of positive integers.
(a) Show that the sets and are equal, using any method.
(b) Prove or disprove: If C B, then .
(a) In this solutions, set laws will be used to show the equivalence:
, using DeMorgan's Law

, using Law of Double Complement

, using Associative Law
Another solution uses a Membership Table.
(b) We must prove the following:
Thus, We must prove that if an arbitrary element , then .
We split our work into two cases: (1) , and (2) .
Case (1): , by definition of set difference, we have that , and . Since the latter is true, and since C B, it follows that . Hence, , based on the definition of set complement. Also, since , it naturally follows that , by definition of set union. Since and , by definition of set intersection, we conclude that .
Case (2): , by definition of set difference, we have that , and . Hence, , based on the definition of set complement. Also, since , it naturally follows that , by definition of set union. Since and , by definition of set intersection, we conclude that .

3) Let A, B and C be any three sets. Prove or disprove the following propositions:
a) If AB C, then either AB or AC.

b) (AC) (CB) = 

c) Power(A)Power(B)  Power (A B)

d) If AB, then AxCBxC.

e) If AxCBxC, then AB.
a) If AB C, then either AB or AC.
It can be disproved by the following counter example. Take A = {1, 2}, B = {1, 3} and C = {2, 4}. Then ABC = {1, 2, 3, 4}, but A is neither a subset of B , nor a subset of C.

b) (AC) (CB) = 
Proof by contradiction. Assume that (AC) (CB)   to show that it results to contradiction. (AC) (CB)   means that there exists some x  (AC) (CB). By the definition of intersection we can imply, that there exists x for which the following proposition is true: p = (xAC)  (xCB). Using the definition of set difference we can rewrite p as

: p = (xA) (x C)  (xC) (x B). But (x C)  (xC) = False, so



p = (xA) [(x C)  (xC)] (x B) = (xA) False (x B) = False.

So, the assumption that intersection (AC) (CB)   is not empty results to contradiction which proves that this assumption is false, i.e. intersection is empty.


Other solution is to use the membership table.
c) Power(A)Power(B)  Power (A B)
This is false. To disprove take a counterexample: A = {1, 2}, B = {2, 3}, Power(A) = {, {1}, {2}, {1, 2}}, Power(B) = {, {2}, {3}, {2, 3}}, Power(A)  Power(B) = {{1}, {1, 2}}, A B = {1}, Power (A B )={, {1}}. Thus, {1, 2} Power(A)  Power(B), but {1, 2} Power (A B ), so the proposition Power(A)Power(B)  Power (A B) is disproved.
d) If AB, then AxCBxC.
This is true. We must show the following: AxCBxC. This means, for an arbitrarily chosen ordered pair (x,y) we must show the following:
if (x,y) AxC, then (x,y)BxC.
We use direct proof.
1) Assume (x,y) AxC.

2) If this is the case, then we have that xA and yC.

3) We are given that AB and xA. By definition of subset, it follows that xB.

4) By definition of Cartesian Product, we can conclude that (x,y)BxC, as desired.


e) If AxCBxC, then AB.
This is false, let A = {1}, B = {2}, and C = {}. In this case AxC = {}, BxC = {}, but A is NOT a subset of B.


Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azrefs.org 2016
rəhbərliyinə müraciət

    Ana səhifə