**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 xB and xA.
3) Since B C and xB, by definition of subset, we know that xC.
4) By definition of set difference since, xC 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 xA that xC and that there exists some
element y such that yA but yC.
First, let's consider an arbitrary xA. Since A B, by the definition of proper
subset we can conclude that xB. Similarly, using the given information again,
since B C, we can conclude that xC. 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 yA but yB. But, if yB, since B C, it follows that yC. Thus, we have
shown that there exists an element y such that yA but yC 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 *A* *B **C*, then either *A**B *or *A**C*.
b) (*A* *C*) (*C* *B*) =
c) Power(*A*)Power(*B*) Power (*A **B*)
d) If *A**B, *then *AxC*BxC.
e) If *AxC*BxC, then *A**B.*
**a) **If *A* *B **C*, then either *A**B *or *A**C*.
* *It can be disproved by the following counter example. Take *A* = {1, 2}, *B* = {1, 3} and *C* = {2, 4}. Then *A* *B* *C* = {1, 2, 3, 4}, but *A *is neither a subset of *B *, nor a subset of *C*.
**b) **(*A* *C*) (*C* *B*) =
Proof by contradiction. Assume that (*A* *C*) (*C* *B*) to show that it results to contradiction. (*A* *C*) (*C* *B*) means that there exists some *x* (*A* *C*) (*C* *B*). By the definition of intersection we can imply, that there exists *x* for which the following proposition is true: *p *= (*x* *A* *C*)* * (*x* *C* *B*). Using the definition of set difference we can rewrite *p *as
: *p *= (*x* *A*) (*x **C*)* * (*x* *C*) (*x * *B*). But (*x **C*)* * (*x* *C*) = False, so
*p *= (*x* *A*) [(*x **C*)* * (*x* *C*)] (*x * *B*) = (*x* *A*) False (*x * *B*) = False.
So, the assumption that intersection (*A* *C*) (*C* *B*) 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 AB, then AxCBxC.
This is true. We must show the following:* *AxCBxC. 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 xA and yC.
3) We are given that AB and xA. By definition of subset, it follows that xB.
4) By definition of Cartesian Product, we can conclude that (x,y)BxC, as desired.
**e)** If *AxC*BxC, then *A**B.*
This is false, let A = {1}, B = {2}, and C = {}. In this case AxC = {}, BxC = {}, but A is NOT a subset of B. |