CSC165H1, Winter 2022 CSC165H1: Worksheet 9—Induction on Sets (Partial Solutions)
Learning Objectives
By the end of this worksheet, you will:
• Prove statements about sets using induction.
Copyright By PowCoder代写 加微信 powcoder
So far, we have only used induction to prove statements about numbers. In CSC236, you’ll see many more appli- cations of the principle of induction beyond just numbers, but in this problem session you’ll get a taste of what’s to come by learning how to use induction on another familiar entity: sets.
1. A first example. Consider the following statement: “Every finite set S has exactly |S|(|S| − 1) subsets of size 2.”1 2
This is a universally-quantified statement, but given an arbitrary set S, it isn’t obvious how to make an argument for its number of subsets. It isn’t obvious how to use induction either! After all, we only know (right now) how to apply induction to prove statements about the natural numbers.
Here’s the big insight into how to apply induction to (finite) sets: every set has a simple corresponding natural number, its size. We can rewrite the initial statement to emphasize the size of the sets, as
Foreveryn∈N,everysetofsizenhas n(n−1) subsetsofsize2. 2
If we define the predicate P (n) : “every set S of size n has n(n − 1) subsets of size 2,” then this statement is exactly
the kind of statement we can prove using induction!
(a) Check your understanding: write down, in English, what P (0) means. (This is the base case of the induction proof.)
(b) Prove P(0). We have started the proof for you.
Proof. Base case: Let n = 0. Let S be an arbitrary set, and assume S has size 0.
(c) Now we’ll prove the induction step, in a series of parts. Please read through the following and complete the proof.
Proof. Induction step. Let k ∈ N, and assume P (k). That is, assume that: [Write down, in English, the induction hypothesis (what P(k) means).]
We want to prove P (k + 1), that is,
[Write down, in English, what you want to prove (what P (k + 1) means).]
1For example, a set containing 4 elements has 4 · 3 = 6 subsets of size 2. 2
Every set S of size 0 has 0 subsets of size 2.
We want to prove that S has 0 subsets of size 2.
Since S has no elements, it doesn’t have any subsets of size 2 (in fact, its only subset is itself, which has size 0).
Every set S of size k has exactly k(k − 1) subsets of size 2. 2
CSC165H1, Winter 2022 CSC165H1: Worksheet 9—Induction on Sets (Partial Solutions)
Every set S of size k + 1 has exactly (k + 1)k subsets of size 2. 2
Let S be an arbitrary set, assume S has size k+1, and let the elements in the set be {s1,s2,…,sk,sk+1}. The key idea of most proofs by induction on sets is that you can take a set of size k + 1, and split it up into a single element and another set of size k.2 Let S′ = {s1,s2,…,sk}, so that S = S′ ∪ {sk+1}. Note that S′ has size k. Now, we’ll treat sk+1 as “special,” and use it to divide up the possible subsets of S in a really nice way!
Part 1: counting subsets of S of size 2 that contain sk+1.
Part 2: counting subsets of S of size 2 that don’t contain sk+1.
[Use the induction hypothesis to determine the number of subsets of S of size 2 that don’t contain sk+1.]3
Part 3: putting the counts together.
[Finish off this proof by adding up your results from Parts 1 and 2.]
2. Extending your work. Use the technique presented in the previous question to prove the following statement:
“Every finite set S has exactly |S|(|S| − 1)(|S| − 2) subsets of size 3.” You can (and should) use the statement you 6
used in the previous question as an external fact in your proof.
We’ll prove that the number of subsets of S of size 2 that contain sk+1 is exactly k.
Every subset of S of size 2 that contains sk+1 must contain exactly one element from S′; there are k choices of elements from S′ (since |S′| = k), and so k subsets of S of size 2 that contain sk+1.
Every subset of S of size 2 that doesn’t contain sk+1 must contain 2 elements from {s1, . . . , sk}. That is, these subsets are exactly the subsets of S′ of size 2. Since S′ has size k, the induction hypothesis tells us
that S′ has exactly k(k − 1) subsets of size 2. 2
By combining the two counts from Parts 1 and 2, the total number of subsets of size 2 of S is
k+ k(k−1) = 2k+k(k−1) = k(k+1) 222
The only difference between this proof and the previous one is that here, the subsets of size 3 that contain the “last” element sk+1 correspond to the subsets of size 2 from a set of size k. That’s why you need to use what you proved in the previous question to count the number of subsets of size 3 in this part.
2This is the exact same idea as taking a summation with range 1 to (k + 1), and splitting it up into a summation with range 1 to k, plus the (k + 1)-st term.
3Note that the induction hypothesis only applies to sets of size k; do you have a set of size k in this proof to work with?
CSC165H1, Winter 2022 CSC165H1: Worksheet 9—Induction on Sets (Partial Solutions)
3. Counting all subsets. We’ll wrap up this worksheet by counting one more quantity: all the subsets of a given set. Recall that for a set S, the power set of S, denoted P(S), is the set of all subsets of S.4 For example,
P ({1, 2}) = {}, {1}, {2}, {1, 2}
Your goal for this question is to prove the following statement: “For every natural number n, every set S of size n
satisfies |P(S)| = 2n.”
(a) (Warm-up) Before trying to prove this directly, let’s try out a small example to gain some intuition about why this statement is true. Consider a set S = {1, 2, 3}, with size 3. The above statement predicts that S will have eight subsets.
In the space below, write down the subsets of S in two groups:
• The subsets of S that contain the element 3.
• The subsets of S that do not contain the element 3. (Can you find a relationship between the two groups?)
(b) Prove the above statement using induction. Clearly define the predicate P (n) that is relevant to this statement (this is to help you make sure you understand exactly what it is you’re proving).
Contain 3: {3}, {1, 3}, {2, 3}, {1, 2, 3}. Do not contain 3: {}, {1}, {2}, {1, 2}.
The proof is actually quite similar to the previous two proofs, with the major difference being that the number of subsets that contain the last element sk+1 is 2k, and the number of subsets that do not contain the last element is also 2k (and 2k + 2k = 2k+1).
Please consult the Course Notes, page 73-74, for a complete proof.
4Remember that the empty set is a subset of every set, and every set is also a subset of itself.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com