Elementary Discrete Mathematics 2

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 arbitrary set, 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 it itself is empty!

So, we want to prove that every element of \(\varnothing\) is an element of \(A\text{,}\) because this is the definition of a subset. In a later section we will make this next step clear, 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 above 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. You will have to un-“knowl” it like you 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 people have trouble writing them at first!)

In the following example we will calculate the power set of \(\{a,b,c\}\text{.}\) Before you open 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 you might forget (hint: reread the preceding theorems).

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.

This theorem contains the phrase “if and only if,” which we will learn about in detail shortly. Here, it means that \(A=B\) implies that \(A\) and \(B\) contain one another as subsets; and, that if \(A\) and \(B\) contain each other, then \(A=B\text{.}\) This conditional 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.

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