Exercise 626Logic, sets and proofs › Sets and mapsL1Added 4 Nov 2026

Inclusion and complement

#inclusion#complement#direct proof#contradiction

Statement

Let $A$ and $B$ be subsets of a set $E$ , and let $\bar A$ and $\bar B$ be their complements in $E$ . Prove:
$A\subseteq B\implies\bar B\subseteq\bar A.$
Give two proofs: (a) by direct reasoning; (b) by contradiction.

Hint

For the direct proof, take $x\in\bar B$ and use $A\subseteq B$ . For contradiction, suppose $\bar B\not\subseteq\bar A$ .

Show solutionHide solution

Solution

(a) Direct proof. Let $x\in\bar B$ , i.e. $x\notin B$ . Since $A\subseteq B$ , every element of $A$ belongs to $B$ ; as $x\notin B$ , we get $x\notin A$ , i.e. $x\in\bar A$ . Hence $\bar B\subseteq\bar A$ .

(b) Proof by contradiction. Suppose $\bar B\not\subseteq\bar A$ . Then there exists $x\in\bar B$ with $x\notin\bar A$ , i.e. $x\notin B$ and $x\in A$ . But $A\subseteq B$ gives $x\in B$ , contradiction.

Conclusion. $A\subseteq B\implies\bar B\subseteq\bar A$ .

Inclusion and complement

Statement

Solution

More problems in Sets and maps