Skip to main content
Mathematics LibreTexts

4.5: Some Proofs about Sets

  • Page ID
    23903
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    To find proofs in , you can use all of the strategies that were helpful in : working backwards, working forwards, changing what you are looking at, breaking the proof into cases, and proof by contradiction are all important. The introduction and elimination rules for quantifiers just add some new options when you are working forwards or working backwards. In particular:

    • If you have \(\exists x, \mathcal{A}(x)\), you will probably use \(\exists\)-elimination: assume \(\mathcal{A}(c)\) for some letter \(c\) that is not already in use, and then derive a conclusion that does not contain \(c\).
    • If the desired conclusion is \(\forall x \in X,\mathcal{A}(x)\), then your proof will almost certainly be based on \(\forall\)-introduction, so the first words of your proof will usually be “Given \(x \in X\), …”
    • If you have \(\forall x,\mathcal{A}(x)\), and it might be helpful to know \(\mathcal{A}(c)\) (for some constant \(c\)), then you could use \(\forall\)-elimination.

    For example, now that we have all the rules of First-Order Logic, we can prove the following important fact that was stated on.

    Example \(4.5.1\).

    Assume \(A\) and \(B\) are sets. We have \(A = B\) if and only if \(A \subset B\) and \(B \subset A\).

    Solution

    Proof.

    (\(\Rightarrow\)) Assume \(A = B\). Every set is a subset of itself (see Remark \(3.2.20\)), so we have \[A=B \subset B \quad \text { and } \quad B=A \subset A ,\] as desired.

    (\(\Leftarrow\)) Assume \(A \subset B\) and \(B \subset A\). We wish to show \(A = B\); in other words, we wish to show \[\forall x, (x \in A \eiff x \in B) .\]

    Let \(x\) be arbitrary.

    (\(\Rightarrow\)) Suppose \(x \in A\). Since \(A \subset B\), this implies \(x \in B\).

    (\(\Leftarrow\)) Suppose \(x \in B\). Since \(B \subset A\), this implies \(x \in A\).

    Therefore, \(x \in A \eiff x \in B\). Since \(x\) is arbitrary, this implies \(\forall x, (x \in A \eiff x \in B)\), as desired.

    Example \(4.5.2\).

    Suppose \(A\), \(B\), and \(C\) are sets (and \(\univ\) is the universal set, as usual). Then:

    1. \(A \cap B \subset A\).
    2. \(A \subset A \cup B\).
    3. \(A \cap \mathcal{U} =A\).
    4. \(\text { If } A \subset B \text { and } B \subset C, \text { then } A \subset C \text {. }\)
    5. \(A \cap B \subset A \cup B\).
    6. \(\text { If } A \subset B \text { and } A \subset C, \text { then } A \subset B \cap C \text {. }\)

    Solution

    Proof.

    1. We wish to show that every element of \(A \cap B\) is an element of \(A\). Given \(x \in A \cap B\), we know, from the definition of \(A \cap B\), that \(x \in A\) and \(x \in B\). In particular, \(x \in A\), as desired.
    2. We wish to show that every element of \(A\) is an element of \(A \cup B\). Given \(x \in A\), it is obviously true that either \(x \in A\) or \(x \in B\) (since, in fact, we know \(x \in A\)). Therefore \(x \in A \cup B\), as desired.
    3. From 1., we know that \(A \cap \mathcal{U} \subset A\), so it suffices to show that \(A \subset A \cap \mathcal{U}\). Given \(a \in A\), we obviously have \(a \in A\). Furthermore, since the universal set \(\mathcal{U}\) contains every element that is under consideration, we also have \(a \in \mathcal{U}\). Hence \(a \in A \cap \mathcal{U}\), as desired.
    4. Let \(a\) be an arbitrary element of \(A\). Since \(A \subset B\), we know \(a \in B\). Then, because \(B \subset C\), we know \(a \in C\). Since \(a\) is an arbitrary element of \(A\), this implies \(A \subset C\).
    5. Given \(x \in A \cap B\), we know \(x \in A\) and \(x \in B\). In particular, we have \(x \in A\), so it is certainly true that either \(x \in A\) or \(x \in B\). Therefore \(x \in A \cup B\). Since \(x\) is an arbitrary element of \(A \cap B\), this implies \(A \cap B \subset A \cup B\), as desired.
      Alternate proof of 5.. From parts and , we know \(A \cap B \subset A\) and \(A \subset A \cup B\). So 4. implies that \(A \cap B \subset A \cup B\), as desired.
    6. Let \(a\) be an arbitrary element of \(A\). Since \(A \subset B\), we have \(a \in B\). Similarly, since \(A \subset C\), we also have \(a \in C\). Having established that \(a \in B\) and \(a \in C\), we conclude that \(a \in B \cap C\). Since \(a\) is an arbitrary element of \(A\), this implies \(A \subset B \cap C\).

    Exercise \(4.5.3\).

    Assume \(A\), \(B\), and \(C\) are sets.

    1. Show that if \(A \subset B\), then \(A \cap B = A\).
    2. Show if \(A \subset B\), then \(A \cup B = B\).
    3. Show that if \(B \subset C\), then \(A \cap B \subset A \cap C\).
    4. Show that if \(A \subset C\) and \(B \subset C\), then \(A \cup B \subset C\).
    5. Show \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\).
    6. Show \(A \backslash B = A \backslash (A \cap B)\).
    7. Let \(X = A \cap B\), and show \(A \cup B = (A \backslash X) \cup (B \backslash X) \cup X\).
    8. Show that if \(\mathcal{P}(A \cup B) = \mathcal{P}(A) \cup \mathcal{P}(B)\), then either \(A \subset B\) or \(B \subset A\).

    Exercise \(4.5.4\).

    Suppose \(A\) and \(B\) are sets.

    1. Show \(A \backslash B = A \cap \bar{B}\).
    2. Show \(A = (A \backslash B) \cup (A \cap B)\).
    3. Prove De Morgan’s Laws:
      1. \(\overline{\bar{A}}=A\).
      2. \(\overline{A \cap B}=\bar{A} \cup \bar{B}\).
      3. \(\overline{A \cup B}=\bar{A} \cap \bar{B}\).
    4. Show that if \(\bar{A}=\bar{B}\), then \(A = B\).
      [Hint: Follows immediately from one of DeMorgan's Laws.]

    Exercise \(4.5.5\).

    Suppose \(A\), \(B\), and \(C\) are sets.

    1. Show that \(A\) is disjoint from \(B\) if and only if \(A \subset \bar{B}\).
    2. Show \(A \backslash B\) is disjoint from \(B\).
    3. Show that if \(A\) is disjoint from \(B\), and \(C\) is a subset of \(B\), then \(A\) is disjoint from \(C\).
    4. Show that \(A \backslash B\) is disjoint from \(A \cap B\).
    5. Show that \(A\) is disjoint from \(B \cup C\) iff \(A\) is disjoint from both \(B\) and \(C\).

    Exercise \(4.5.6\).

    1. Show \(A \cup B = (A \backslash B) \cup (B \backslash A) \cup (A \cap B)\).
    2. Show the three sets \(A \backslash B\), \(B \backslash A\), and \(A \cap B\) are all disjoint from each other.

    Recall from that sets \(A_{1},A_{2},\ldots,A_{n}\) are pairwise-disjoint iff \(A_{i}\) is disjoint from \(A_{j}\) whenever \(i \neq j\).

    Exercise \(4.5.7\).

    Suppose the sets \(A_{1},A_{2},\ldots,A_{n}\) are pairwise-disjoint. Show:

    1. The sets \(A_{1},A_{2},\ldots,A_{n-1}\) are pairwise-disjoint, if \(n > 1\).
    2. \(A_{n}\) is disjoint from \(A_{1} \cup A_{2} \cup \cdots \cup A_{n-1}\), if \(n > 1\).

    This page titled 4.5: Some Proofs about Sets is shared under a CC BY-NC-SA 2.0 license and was authored, remixed, and/or curated by Dave Witte Morris & Joy Morris.

    • Was this article helpful?