# How do I solve this with a direct proof?

• Nov 8th 2012, 05:39 AM
blueaura94
How do I solve this with a direct proof?
Prove that for all sets X and Y, (X ∩ Y) ∪(Y-X)=Y

I'm stuck and I'm not fully sure how to solve this.
• Nov 8th 2012, 08:12 AM
Deveno
Re: How do I solve this with a direct proof?
suppose that a is an element of (X∩Y) U (Y-X).

this means one of two things:

a is in X∩Y, or
a is in Y-X

suppose a is in X∩Y. this means that a is in BOTH X and Y, so is certainly in Y.

alternatively, if a is in Y-X, this means a is in Y, but not in X. who cares if its not in X, at least it's in Y!

so in all possible cases, we see that a is in Y.

this means that (X∩Y) U (Y-X) is a subset of Y.

now suppose b is in Y.

well we have two possibilities:

b is in X
b is NOT in X (in or out, that's the way it is with sets. you cannot be "sort of" in a set).

if b is in X, then b is in X AND Y, so b is in X∩Y.
if b is not in X, then b is in Y, but not in X, so b is in Y-X.

if we put these two sets together, b is certain to be in one of them. hence b is in (X∩Y) U (Y-X).

thus Y is a subset of (X∩Y) U (Y-X).

but, if for 2 sets A,B: if A⊆B and B⊆A, then A and B have exactly the same elements, that is: A = B.

so (X∩Y) U (Y-X) = Y.

(intuitively what we are doing is splitting Y into 2 parts: the part that overlaps with X, and the part that doesn't).
• Nov 8th 2012, 12:07 PM
Soroban
Re: How do I solve this with a direct proof?
Hello, blueaura94!

Quote:

$\displaystyle \text{Prove: }\:(X \cap Y) \cup (Y - X) \:=\:Y$

$\displaystyle \begin{array}{ccccc}1. & (X \cap Y) \cup (Y - X) && 1. & \text{Given} \\ 2. & (X \cap Y) \cup (Y \cap \overline{X}) && 2. & \text{Def. Subtr'n} \\ 3. & (X\cap Y) \cup (\overline{X} \cap Y) && 3. & \text{Commutative} \\ 4. & (X \cup \overline{X}) \cap Y && 4. & \text{Distributive} \\ 5. & U \cap Y && 5. & A \cup \overline{A} \,=\,\mathbb{U} \\ 6. & Y && 6. & \mathbb{U} \cap A \,=\,A \end{array}$
• Nov 8th 2012, 12:32 PM
Plato
Re: How do I solve this with a direct proof?
Quote:

Originally Posted by blueaura94
Prove that for all sets X and Y, (X ∩ Y) ∪(Y-X)=Y

Here is another way.
$\displaystyle X\cap Y\subseteq Y~\&~Y\setminus X\subseteq Y$ so there is just need to prove one way.

If $\displaystyle t\in Y$ then either $\displaystyle t\in X$ or $\displaystyle t\notin X$.

And we are done.