Elementary Discrete Mathematics

Section 1.2 Containment

One of the most important ideas when dealing with sets is that of a subset.

There is a prickly little set that arises very quickly when discussing subsets, which leads to all sorts of interesting examples.

In the preceding section we discussed definitions, examples, theorems, and proofs. You saw the first two in that section; now, we will see our first theorem and its proof.

A proof is simply an argument that convinces its reader of the truth of a mathematical fact. Valid proofs must only use definitions and the hypotheses of the theorem; it is not correct to assume more than you are given. So the ingredients in the proof of this theorem are simply going to the empty set, the second set (which must be arbitrary) and the definition of a subset.

Let's give a name to the second set, say, \(A\text{.}\) We may not assume anything else about it—not even finiteness or whether \(A\) itself is empty!

To prove that \(\varnothing \subseteq A\text{,}\) we will rely on the definition of a subset, which you just wrote down (right?): \(\varnothing \subseteq A\) if every element of \(\varnothing\) is an element of \(A\text{.}\) In a later section we will clarify this next step somewhat, but it turns out that saying “Everything in \(\varnothing\) is in \(A\)” is the same as saying “There is nothing in \(\varnothing\) that is not in \(A\text{.}\)” This is true, because there is nothing in \(\varnothing\text{!}\) To get an idea of why this weird conversion works, look back to the previous example. The reason \(\{a,c\} \not\subseteq \{b\}\) is because we can find an element (\(a\text{,}\) for instance) that is not in \(\{b\}\text{.}\) Had the set been empty, we could not have found that element.

Now that we have thought through our proof, we can write it down. We want to include enough details that the intended audience can understand it, but trim unnecessary verbage. The proof is below. Readers of the web version will have to un-“knowl” it like they do the examples.

Notice that the proof began with the assumptions (\(A\) is a set) and ended on a restatement of the desired theorem.

Here is another theorem. As an exercise, see if you can come up with the proof before you read it. You may not get it right, but it's important to at least try to think about why a theorem is true before reading the proof.

Notice that this proof contains two cases: the case that \(A\) is empty and the case that \(A\) is nonempty. A proof must address every possible situation, or else the theorem should be restricted to only the appropriate cases.

Wait—our elements are sets? Yes, and this is perfectly fine! As we've said, elements can be anything: other sets included. When we have a "set of sets" we typically refer to it as a family or a collection of sets to avoid using the same word and over and over.

The symbol \(\mathscr{P}\) is a curly “P”. It's fun to practice writing, but don't worry if you don't get it perfect; any curly capital “P” will do. (Same goes for the curly braces \(\{\) and \(\}\text{.}\) Lots of students have trouble writing them at first!)

In the following example we will calculate the power set of \(\{a,b,c\}\text{.}\) Before you read the example, try to write it down for yourself. What are all the possible groups of elements from that set? Remember there are two special ones that students commonly forget at first (hint: reread the preceding theorems).

Be careful that you do not use a capital letter to refer to a set that has not been given a name. Above, we declared that \(A=\{a,b,c\}\text{.}\) Had we not done so, it would have been incorrect to use \(A\) to stand in for \(\{a,b,c\}\text{.}\)

Finally, we are often interested in knowing whether two sets are equal. This is often how we prove that being one type of object is the same as being another type of object. What does it mean for two sets to be equal? Then, we will prove a useful theorem that shows two sets are equal if they contain each other.

The following principle of mutual inclusion is often very useful in proving two sets are equal.

This theorem contains the phrase “if and only if,” which we will learn about in detail shortly. Here, it means that if \(A=B\text{,}\) then \(A\) and \(B\) contain one another as subsets; and vice-versa, that if \(A\) and \(B\) contain each other, then \(A=B\text{.}\) This conditional statement works both ways. Generally, conditional statements do not work both ways (this will be important later!)

So, we will prove this statement in two parts. First, we will prove that if \(A=B\text{,}\) then \(A \subseteq B\) and \(B \subseteq A\text{.}\) Next, we will prove that if \(A \subseteq B\) and \(B \subseteq A\text{,}\) then \(A=B\text{.}\) Truly adventurous readers may try to sketch the proof themselves, or think about how it may go, before reading the proof that follows.

The word conversely means “We are turning the conditional statement around.” It is a very handy word for writing proofs with two directions.