Question

3. Let W = P({1,2,3,4,5}). Consider the following statement and attempted proof: VAE W WB EW (((AUB) C A) + (ACB)) (1) Towards a universal generalization argument, choose arbitrary A € W, BEW. (2) We need to show ((AUB) C A) + (ACB). (3) Towards a proof by contraposition, assume B CA, and we need to show A C (AUB). (4) By definition of subset inclusion, this means we need to show Vc (E A →r (AUB)). (5) Towards a universal generalization,choose arbitrary c; we need to show that XEA →IE (AUB). (6) Towards a direct proof, assume x e A, and we need to show x € (AUB). (7) By definition of set union and set builder notation, we need to show that I E AVI E B. (8) By logical equivalences (Domination Law on page 27 of Rosen textbook), TV3 E B=T, so the assumption x e A in line 6) is enough to guarantee what we needed to show. QED (a) Demonstrate that this attempted proof is invalid by providing and justifying a counterexample (disproving the claim). (b) Demonstrate how this attempted proof is invalid by identifying in which step a definition or proof strategy is used incorrectly, and describing how the definition or proof strategy was misused. (c) (Graded for fair effort completeness) Prove this related statement that is true: VA EWVB EW ((ACB) + ((AUB) = B))

Answer 1

(a) Consider
Вс А
. Then
AUB= A C A but AB
. For a concrete example, take
A= {1,2,3), B = {1,2}
.

(b) The problem lies in step (3). The negation of
Ас В
is
(BCA) V(BRA) = 0
and the second condition has not been taken care of in the proof.

(c) Consider arbitrary
A. BEW
such that
Ас В
. We show this assumption makes the two sets
AUB
and $\small B$ equal. To that end:

.

TEAUBIEAVIEBTEB VreBrEB=AUBCB

On the other hand:

TEBIEAUB=BCAUB

Thus

B CAUBAB 2 AUB) = AUB=B

which completes the proof.