# Thread: Proving equality of sets, is my working correct?

1. ## Proving equality of sets, is my working correct?

Can someone check if my working is correct for the following proof?

Prove $X \cup (Y-X) = X \cup Y$ for all sets $X$ and $Y$.

Let $P(x)$ be the proposition function '$x \in X \cup (Y-X)$' and $Q(x)$ be the proposition function '$x \in X \cup Y$'

Let the domain of discourse of both these proposition functions be $\mathbb{U}$, the universal set.

Now to prove the statement to be true we must show the following 2 universally quantified statements to be true:

1. $\forall x \in \mathbb{U} \left(P(x) \to Q(x)\right)$

2. $\forall x \in \mathbb{U} \left(Q(x) \to P(x)\right)$

To show case 1 to be true, first we know that if $P(x)$ is false then the case is vacuously true, so we will ignore this trivial case.

We will assume $P(x)$ to be true and if we can show that $Q(x)$ is also true then case 1 is true.

Now $P(x): \left(x \in X\right) \lor \left(x \in (Y-X)\right)$ and $Q(x): \left(x \in X\right) \lor \left(x \in Y\right)$

Since $P(x)$ is true then either

a. $x \in X$ is true and $x \in (Y-X)$ is false

b. $x \in X$ is false and $x \in (Y-X)$ is true

[Note: these 2 propositions can not be both true since they are mutually exclusive]

If we use case a. Since $x \in X$ is true $\implies \left(x \in X\right) \lor \left(x \in Y\right)$ is true $\implies Q(x)$ is true.

Now using case b. Since $x \in (Y-X)$ is true $\implies x \in Y$ is true $\implies \left(x \in X\right) \lor \left(x \in Y\right)$ is true $\implies Q(x)$ is true.

Thus we have shown case 1. to be true.

To show case 2 to be true, first we know that if $Q(x)$ is false then the case is vacuously true, so again we will ignore this trivial case.

We will assume Q(x) to be true and Q(x) is true if either of the following 3 conditions are satisfied.

i. $x \in X$ is true and $x \in Y$ is false

ii. $x \in X$ is false and $x \in Y$ is true

iii. $x \in X$ is true and $x \in Y$ is true

Now using case i. Since $x \in X$ is true $\implies \left(x \in X\right) \lor \left(x \in (Y-X)\right)$ is true $\implies P(x)$ is true.

Using case ii. Since $x \in Y$ is true $\implies x \in (Y-X)$ is true$\implies \left(x \in X\right) \lor \left(x \in (Y-X)\right)$ is true $\implies P(x)$ is true.

Now using case iii. Since $x \in X$ is true and $x \in Y$ is true $\implies \left(x \in X\right) \lor \left(x \in (Y-X)\right)$ is true $\implies P(x)$ is true.

Case 2 is now proven to be true.

We have completed our proof to show that the original statement is true.

Thanks!

2. Suggestion: Just write your proof in a single post rather than asking people to click on a different URL for every single line in your proof.

3. Sorry what do you mean "click on a different URL for every single line of my proof"? Can you somehow not see the LaTeX?

4. Your OP looks good to me, if a little bit overkill.

5. I don't see Latex in your post. In other poster's posts I see Latex, but for your post, my browser shows virtually only English words plus URLs.

But another poster does see your Latex, so I guess it's an anomaly between your post and my broswer.

6. Anyway, it's very simple.

Show X u (Y\X) = X u Y:

Suppose z in X u (Y\X).

So z in X or z in Y\X.

If z in X, then z in X u Y.

If z in Y\X, then z in X u Y.

Suppose z in X u Y.

So z in X or z in Y.

Suppose z in X.

So z in X u (Y\X).

Suppose z in Y.

If z in X, then see above.

If z not in X, then Z in Y\X, so z in X u Y\X.

So z in X u (Y\X) iff X u Y.

So, since z is arbitary, we have X u (Y\X) = X u Y.

/

Even more brief:

z in X u Y
iff
z in X or z in Y
iff
z in X or ((z in Y but z not in X) or (z in Y and z in X))
iff
z in X or (Z in Y but z not in X)
iff
z in X or z in Y\X
iff
z in X u Y\X

/

Even more brief:

z in X u Y
iff
z in X or z in Y
iff
z in X or (z in Y but z not in X)
iff
z in X u Y\X

/

Even more brief:

z in X u Y
iff
z in X or (z in Y but z not in X)
iff
z in X u Y\X

/

Even more brief:

Follows by obvious sentential logic and universal generalization.