1.6: A.6- Another Example
- Page ID
- 121752
\( \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}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)If \(A \subseteq C\), then \(A \cup (C \setminus A) = C\).
Proof. Suppose that \(A \subseteq C\). We want to show that \(A \cup (C \setminus A) = C\).
We begin by observing that this is a conditional statement. It is tacitly universally quantified: the proposition holds for all sets \(A\) and \(C\). So \(A\) and \(C\) are variables for arbitrary sets. To prove such a statement, we assume the antecedent and prove the consequent.
We continue by using the assumption that \(A \subseteq C\). Let’s unpack the definition of \(\subseteq\): the assumption means that all elements of \(A\) are also elements of \(C\). Let’s write this down—it’s an important fact that we’ll use throughout the proof.
By the definition of \(\subseteq\), since \(A \subseteq C\), for all \(z\), if \(z \in A\), then \(z \in C\).
We’ve unpacked all the definitions that are given to us in the assumption. Now we can move onto the conclusion. We want to show that \(A \cup (C \setminus A) = C\), and so we set up a proof similarly to the last example: we show that every element of \(A \cup (C \setminus A)\) is also an element of \(C\) and, conversely, every element of \(C\) is an element of \(A \cup (C \setminus A)\). We can shorten this to: \(A \cup (C \setminus A) \subseteq C\) and \(C \subseteq A \cup (C \setminus A)\). (Here we’re doing the opposite of unpacking a definition, but it makes the proof a bit easier to read.) Since this is a conjunction, we have to prove both parts. To show the first part, i.e., that every element of \(A \cup (C \setminus A)\) is also an element of \(C\), we assume that \(z \in A \cup (C \setminus A)\) for an arbitrary \(z\) and show that \(z \in C\). By the definition of \(\cup\), we can conclude that \(z \in A\) or \(z \in C \setminus A\) from \(z \in A \cup (C \setminus A)\). You should now be getting the hang of this.
\(A \cup (C \setminus A) = C\) iff \(A \cup (C \setminus A) \subseteq C\) and \(C \subseteq (A \cup (C \setminus A)\). First we prove that \(A \cup (C \setminus A) \subseteq C\). Let \(z \in A \cup (C \setminus A)\). So, either \(z \in A\) or \(z \in (C \setminus A)\).
We’ve arrived at a disjunction, and from it we want to prove that \(z \in C\). We do this using proof by cases.
Case 1: \(z \in A\). Since for all \(z\), if \(z \in A\), \(z \in C\), we have that \(z \in C\).
Here we’ve used the fact recorded earlier which followed from the hypothesis of the proposition that \(A \subseteq C\). The first case is complete, and we turn to the second case, \(z \in (C \setminus A)\). Recall that \(C \setminus A\) denotes the difference of the two sets, i.e., the set of all elements of \(C\) which are not elements of \(A\). But any element of \(C\) not in \(A\) is in particular an element of \(C\).
Case 2: \(z \in (C \setminus A)\). This means that \(z \in C\) and \(z \notin A\). So, in particular, \(z \in C\).
Great, we’ve proved the first direction. Now for the second direction. Here we prove that \(C \subseteq A \cup (C \setminus A)\). So we assume that \(z \in C\) and prove that \(z \in A \cup (C \setminus A)\).
Now let \(z \in C\). We want to show that \(z \in A\) or \(z \in C \setminus A\).
Since all elements of \(A\) are also elements of \(C\), and \(C \setminus A\) is the set of all things that are elements of \(C\) but not \(A\), it follows that \(z\) is either in \(A\) or in \(C \setminus A\). This may be a bit unclear if you don’t already know why the result is true. It would be better to prove it step-by-step. It will help to use a simple fact which we can state without proof: \(z \in A\) or \(z \notin A\). This is called the “principle of excluded middle:” for any statement \(p\), either \(p\) is true or its negation is true. (Here, \(p\) is the statement that \(z \in A\).) Since this is a disjunction, we can again use proof-by-cases.
Either \(z \in A\) or \(z \notin A\). In the former case, \(z \in A \cup (C \setminus A)\). In the latter case, \(z \in C\) and \(z \notin A\), so \(z \in C \setminus A\). But then \(z \in A \cup (C \setminus A)\).
Our proof is complete: we have shown that \(A \cup (C \setminus A) = C\).
◻