CS 173
Spring 2021

## Sets 2

Let's do two proofs of subset inclusion.

## Proof of subset inclusion

First, let's remember the claim from the previous video. We had two sets

$$A = \{\lambda(2,3) + (1 - \lambda)(7,4) \ \mid\ \lambda \in [0,1] \}$$

$$B = \{(x,y) \ \mid \ x,y \in \mathbb{R}, x \ge 0, \text{ and }, y \ge 0 \}$$

Claim: $$A \subseteq B$$

The standard outline for a subset inclusion proof is to pick a representative element from the smaller set and show that it's also in the larger set. So, in this case:

Proof: Let p be an element of A.
....
So p is an element of B.
Since every element of A is also an element of B, $$A \subseteq B$$.

We now use the definitions of the two sets to convert our claim about set membership to an algebra problem. Remember from the previous video that A contains pairs of real numbers. So p is going to look like (x,y).

Proof: Let p be an element of A.
Then $$p = \lambda(2,3) + (1 - \lambda)(7,4)$$ where $$\lambda \in [0,1]$$.
....
So $$x \ge 0$$ and $$y \ge 0$$. Since x and y are clearly real numbers, $$p= (x,y)$$ is an element of B.
Since every element of A is also an element of B, $$A \subseteq B$$.

The word "clearly" (or "obviously") is infamously used when a mathematician doesn't feel like explaining something. In this case, it probably is obvious to all of us that everything in the problem is a real number. And we wouldn't be picky about this point when grading your proofs. But sometimes you'll see these words used when the fact isn't as obvious as they are pretending.

Notice that we're starting with a single vector equation for p and have to end up with separate equations for the coordinates x and y. So let's work out what p is equal to, with a view to splitting up the vector equation.

Proof: Let p be an element of A.
Then $$p = \lambda(2,3) + (1 - \lambda)(7,4)$$ where $$\lambda \in [0,1]$$.

So $$p = (2\lambda,3\lambda) + (7 - 7\lambda, 4 - 4\lambda) = (7 - 5 \lambda, 4 - \lambda)$$.
Let $$p = (x,y)$$. Then $$x = 7 - 5 \lambda$$ and $$y = 4 - \lambda$$.
....

So $$x \ge 0$$ and $$y \ge 0$$. Since x and y are clearly real numbers, $$p= (x,y)$$ is an element of B.
Since every element of A is also an element of B, $$A \subseteq B$$.

Ok, now what? A good strategy when stuck is to look back at the early part of the proof to see if there is part of the given information that you haven't used yet. In our case, we haven't used the fact that $$\lambda$$ comes from [0,1]. It turns out that we need only part of this information, that is that $$\lambda \le 1$$.

Proof: Let p be an element of A.
Then $$p = \lambda(2,3) + (1 - \lambda)(7,4)$$ where $$\lambda \in [0,1]$$.

So $$p = (2\lambda,3\lambda) + (7 - 7\lambda, 4 - 4\lambda) = (7 - 5 \lambda, 4 - \lambda)$$.
Let $$p = (x,y)$$. Then $$x = 7 - 5 \lambda$$ and $$y = 4 - \lambda$$.
Since $$\lambda \in [0,1]$$, $$\lambda \le 1$$. So $$5\lambda \le 5 \le 7$$ and $$\lambda \le 4$$.
And therefore $$x = 7 - 5 \lambda \ge 0$$ and $$y = 4 - \lambda \ge 0$$.

So $$x \ge 0$$ and $$y \ge 0$$. Since x and y are clearly real numbers, $$p= (x,y)$$ is an element of B.
Since every element of A is also an element of B, $$A \subseteq B$$.

## Abstract subset proof

Now, let's look at a more abstract claim about sets:

Claim: For any sets A, B, and C, if $$A \times B \subseteq A\times C$$ and $$A \not = \emptyset$$, then $$B \subseteq C$$

In this case, the top-level structure of our claim is an if/then statement. So our main outline is a standard direct proof outline:

Proof: Let A, B, and C be sets. Suppose that $$A \times B \subseteq A\times C$$ and $$A \not = \emptyset$$.
...
So $$B \subseteq C$$. That is what we needed to prove.

In order to show that $$B \subseteq C$$, use the standard subset inclusion outline: we pick a representative element from B and show that it's in C. So let's splice that bit of outline into our proof:

Proof: Let A, B, and C be sets. Suppose that $$A \times B \subseteq A\times C$$ and $$A \not = \emptyset$$.
Let $$x \in B$$.
...
$$x \in C$$

Since every element in B is also in C, $$B \subseteq C$$. That is what we needed to prove.

If we're trying to get from B to C, the most relevant piece of given information is $$A \times B \subseteq A\times C$$. But that fact is about pairs of values. To use it, we'll need to make ourselves a pair. Notice that it's important that A isn't the empty set, otherwise there might not be an element in A to use in making our pair.

Proof: Let A, B, and C be sets. Suppose that $$A \times B \subseteq A\times C$$ and $$A \not = \emptyset$$.
Let $$x \in B$$.

Since $$A \not = \emptyset$$, we can choose an element t from A. Then (t,x) is an element of $$A \times B$$. Since $$A \times B \subseteq A\times C$$, this means that (t,x) is also in $$A \times C$$. So $$x \in C$$.

Since every element in B is also in C, $$B \subseteq C$$. That is what we needed to prove.

These abstract proofs are a bit harder to work out, but they use the same basic outlines.

Notice that the claim isn't true if A is the empty set. Then $$A \times B$$ and $$A \times C$$ are also the empty set. So our starting information doesn't tell us enough to show that $$B \subseteq C$$.