# Proof by contradiction involving set theory

Using a contradiction, prove the following:

If $S\cap T = \emptyset$ and $S\cup T = T$, then $S = \emptyset$.

So far, I've written the definitions of the intersection and union, and I've assumed that $S\neq\emptyset$, but I'm not sure how to derive the contradiction.

Any advice would be greatly appreciated.

• I am pretty sure that I saw this very question here sometime in the past few days. – Asaf Karagila Sep 30 '14 at 19:05
• could you show me where you found it? – Marcus Sep 30 '14 at 19:08
• You can see here – Mauro ALLEGRANZA Sep 30 '14 at 19:25
• @Mauro: Thanks! – Asaf Karagila Sep 30 '14 at 19:26

Assume $S\neq\emptyset$. Then there has to exist at least one object $x$ that is in $S$. Because $S$ must be a subset of $S\cup T$ (proof not included) and $S\cup T = T$, it must then be true that $x\in S\subseteq T$, and so $x\in T$. But then what is $S\cap T$?

Without contradiction: $$S=S\cap(S\cup T)=S\cap T=\emptyset$$ The first equality follows from $S\subseteq S\cup T$.

If you really need a proof by contradiction, then the path is almost obvious: negating $S=\emptyset$ means there exists $x\in S$. Since $T=S\cup T$ and $x\in S$, we get $x\in T$. But then $x\in S\cap T$: contradiction.

If $S\cup T=T$ therefore $S\subset T$. Moreover $S\cap T=\emptyset$, then $S=\emptyset$

Assume that $s\in S$.

Then also $s\in S\cup T=T$ so that $s\in S\cap T$.

This however contradicts that $S\cap T=\emptyset$.

We conclude that no $s$ exists with $s\in S$, or equivalently that $S=\emptyset$.