Skip to main content

Section 2.2 A Direct Proof Involving Sets

One of the most basic types of proofs involving sets is to prove that one set is a subset of another set. If \(S\) and \(T\) are both subsets of some univesal set \(U\text{,}\) to prove that \(S\) is a subset of \(T\text{,}\) we need to prove that

For each element in \(U\text{,}\) if \(x \in S\text{,}\) then \(x \in T\text{.}\)
When we have to prove something that involves a universal quantifier, we frequently use a method that can be called the choose-an-element method. The key is that we have to prove something about all elements in \(\Z\text{.}\) We can then add something to the forward process by choosing an arbitrary element from the set \(S\text{.}\) This does not mean that we can choose a specific element of \(S\text{.}\) Rather, we must give the arbitrary element a name and use only the properties it has by being a member of the set \(S\text{.}\)

The truth of the next proposition may be clear, but it is included to illustrate the process of proving one set is a subset of another set. In this proposition, the set \(S\) is the set of all integers that are a multiple of 6. So when we ā€œchooseā€ an element from \(S\text{,}\) we are not selecting a specific element in \(S\) (such as 12 or 24), but rather we are selecting an arbitrary element of \(S\) and so the only thing we can assume is that the element is a multiple of 6.

Proof.

Let \(S\) be the set of all integers that are multiples of 6, and let \(T\) be the set of all even integers. We will show that \(S\) is a subset of \(T\) by showing that if an integer \(x\) is an element of \(S\text{,}\) then it is also an element of \(T\text{.}\)

Let \(x \in S\text{.}\) (Note: The use of the word ā€œletā€ is often an indication that the we are choosing an arbitrary element.) This means that \(x\) is a multiple of 6. Therefore, there exists an integer \(m\) such that

\begin{equation*} x = 6m \end{equation*}

Since \(6 = 2 \cdot 3\text{,}\) this equation can be written in the form

\begin{equation*} x = 2 (3m) \end{equation*}

By closure properties of the integers, \(3m\) is an integer. Hence, this last equation proves that \(x\) must be even. Therefore, we have shown that if x is an element of \(S\text{,}\) then \(x\) is an element of \(T\) , and hence that \(S \subseteq T\) .