Induction overview

From CS2800 wiki


We will prove a variety of claims to demonstrate a new proof technique called induction; we will discuss induction much more later in the semester.

claim 2

We start with a simple version of the claim, which I will refer to as claim 2 (for reasons that will become apparent):

[math]A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B\href{/cs2800/wiki/index.php/%E2%88%AA}{∪}C) \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} (A\href{/cs2800/wiki/index.php/%E2%88%A9}{∩}B) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A\href{/cs2800/wiki/index.php/%E2%88%A9}{∩}C) [/math]
Proof:
Choose arbitrary sets [math]A [/math], [math]B [/math], and [math]C [/math]. We want to show to show that every [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} C) [/math] is also in [math](A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} C) [/math]. Choose an arbitrary [math]x [/math] in the left hand side. Then [math]x ∈ A [/math] and [math]x ∈ B \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} C [/math]. This means either (1) [math]x ∈ B [/math] or (2) [math]x ∈ C [/math]. In case (1), we have [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math] and [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} B [/math], so [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B [/math], and thus [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math]. Case (2) is similar. In either case, [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} RHS [/math], as required.

claim 3

We now graduate to claim 3:

[math]A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_2 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_3) ⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_2) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_3) [/math]
Proof:
By claim 2 (with [math]B = B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_2 [/math] and [math]C = B_3 [/math]), we have [math]A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} ((B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_2) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_3) ⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_2)) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_3) [/math]. Now, we can apply claim 2 to conclude that [math]A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_2) ⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_2) [/math]. In general, if A ⊆ B then A ∩ C ⊆ B ∩ C, so we know that [math](A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_2)) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_3) ⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_2) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_3) [/math]. Putting this together (and using the fact that ⊆ is transitive),

we have


[math]\begin{align*} A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} ((B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_2) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_3) &⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_2)) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_3) \\ &⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_2) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_3) \end{align*} [/math]

as required.

claim 4

Notice that we used claim 2 to prove claim 3. Similarly, we can use claim 3 to prove claim 4:

[math]A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_4) ⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_4) [/math]
Proof: claim 4
By claim 2 (with [math]B = B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_3 [/math] and [math]C = B_4 [/math]), we have [math]A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} ((B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_3) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_4) ⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_3)) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_4) [/math]. Now, we can apply claim 3 (above) to conclude that [math]A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_3) ⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_3) [/math]. In general, if A ⊆ B then A ∩ C ⊆ B ∩ C, so we know that [math](A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_3)) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_4) ⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_3) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_4) [/math]. Putting this together (and using the fact that ⊆ is transitive), we have


[math]\begin{align*} A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} ((B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_3) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_4) &⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_3)) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_4) \\ &⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_3) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_4) \\ &⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_4) \end{align*} [/math]

as required.

claim n

You may have noticed the proofs of claim 3 and claim 4 are almost identical. You might imagine that you could use claim 4 to prove claim 5, and claim 5 to prove claim 6, and so on. Indeed you can, and this is the idea behind induction.

Since we have proved claim 2, and, for any [math]n ≥ 2 [/math], we can use claim [math]n [/math] to prove claim [math]n+1 [/math] (this is called the inductive step), we can conclude claim [math]n [/math] for any [math]n [/math]. Here is the general inductive step:

[math]A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_n) ⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_n) [/math]
Proof: claim n+1
Since A ∩ (B∪C) ⊆ (A∩B) ∪ (A∩C) (proven above), we have [math]A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} ((B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_n) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_{n+1}) ⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_n)) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_{n+1}) [/math]. Now, we can apply claim n (above) to conclude that [math]A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_n) ⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_n) [/math]. In general, if A ⊆ B then A ∩ C ⊆ B ∩ C, so we know that [math](A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_n)) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_{n+1}) ⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_n) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_{n+1}) [/math]. Putting this together (and using the fact that ⊆ is transitive), we have


[math]\begin{align*} A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} ((B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_n) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_{n+1}) &⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_n)) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_{n+1}) \\ &⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_n) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_{n+1}) \\ &⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_{n+1}) \end{align*} [/math]

as required.

Induction

Because this pattern is so common, there is some stylized language. Typically, instead of "claim n", people often write P(n); this is referred to as the inductive hypothesis. The first proof (in our case, the proof of claim 2) is referred to as the base case. The general proof (using P(n) to prove P(n+1)) is called the inductive step. Here is a stylized induction proof:

For any [math]n ≥ 2 [/math], [math]A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_n) \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_n) [/math]


Proof:
By induction. Let [math]P(n) [/math] be the statement "[math]A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_n) \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_n) [/math]."

We must show [math]P(2) [/math] and [math]P(n+1) [/math] assuming [math]P(n) [/math].

In the base case, when [math]n = 2 [/math], we want to show to show that every [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_2) [/math] is also in [math](A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_2) [/math]. Choose an arbitrary [math]x [/math] in the right hand side. Then [math]x ∈ A [/math] and [math]x ∈ B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_2 [/math]. This means either (1) [math]x ∈ B_1 [/math] or (2) [math]x ∈ B_2 [/math]. In case (1), we have [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math] and [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} B_1 [/math], so [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1 [/math], and thus [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math]. B_2ase (2) is similar. In either case, [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} RHS [/math], as required.

For the inductive step, choose an arbitrary [math]n [/math] and assume we have already proved [math]P(n) [/math]. Our goal is to show [math]P(n+1) [/math]. We compute:


[math]\begin{align*} A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_{n+1}) &= A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} ((B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_n) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_{n+1}) \\ &⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_n)) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_{n+1}) && \text{by P(2)} \\ &⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_n) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_{n+1}) && \text{by P(n) and }\href{/cs2800/wiki/index.php/If_A_%E2%8A%86_B_then_A_%E2%88%A9_C_%E2%8A%86_B_%E2%88%A9_C_claim}{ \text{lemma}} \\ &⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_{n+1}) && \text{by definition} \end{align*} [/math]