Proving equality of sets, is my working correct?

**usagi_killer** · July 15th 2010, 07:29 AM

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!

**MoeBlee** · July 15th 2010, 08:15 AM

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.

**usagi_killer** · July 15th 2010, 08:40 AM

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

**Ackbeet** · July 15th 2010, 09:14 AM

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

**MoeBlee** · July 15th 2010, 09:16 AM

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.

**MoeBlee** · July 15th 2010, 09:33 AM

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.

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

LinkBack

Thread Tools

Display

Proving equality of sets, is my working correct?

Similar Math Help Forum Discussions

Logic and Sets - Equality

[SOLVED] Please correct my working for: Factorise z^3 +1 over C.

2's complement additions(is my working correct)

Equality of sets

Equality of Sets

Search Tags