SP18:Lecture 3 Induction

From CS2800 wiki


We will introduce a bit more set notation ([math]2^A [/math] and [math]A \times B [/math]). We will discuss more proof techniques, including induction.

Set constructions

Power set


Definition: Power set
The power set of a set [math]A [/math] (written [math]\href{/cs2800/wiki/index.php/2}{2}^A [/math])is the set of all subsets of [math]A [/math]. Formally, [math]\href{/cs2800/wiki/index.php/2}{2}^A \href{/cs2800/wiki/index.php/Definition}{:=} \href{/cs2800/wiki/index.php/Set_comprehension}{\{B \mid} B \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} A\} [/math].

Because the elements of the power set are themselves sets, it is easy to confuse elements and subsets. As with any set comprehension, the elements of [math]\href{/cs2800/wiki/index.php/2}{2}^A [/math] are the subsets of [math]A [/math]. Here are some examples:

Let [math]A := \href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2,3\}} [/math]. Then

  • [math]\href{/cs2800/wiki/index.php/2}{2}^A = \{ \href{/cs2800/wiki/index.php/Empty_set}{\{\}}, \href{/cs2800/wiki/index.php/Enumerated_set}{\{1\}}, \href{/cs2800/wiki/index.php/Enumerated_set}{\{2\}}, \href{/cs2800/wiki/index.php/Enumerated_set}{\{3\}}, \href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2\}}, \href{/cs2800/wiki/index.php/Enumerated_set}{\{1,3\}}, \href{/cs2800/wiki/index.php/Enumerated_set}{\{2,3\}}, \href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2,3\}} \} [/math], by inspection. For example, [math]\{1,2,3\} \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/2}{2}^A [/math] because [math]\{1,2,3\} \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} A [/math].
  • [math]1 \href{/cs2800/wiki/index.php/%5Cnotin}{\notin} \href{/cs2800/wiki/index.php/2}{2}^A [/math], because 1 is a number but [math]\href{/cs2800/wiki/index.php/2}{2}^A [/math] contains only sets. Put differently, [math]1 \href{/cs2800/wiki/index.php?title=%5Cnsubseteq&action=edit&redlink=1}{\nsubseteq} A [/math].
  • Therefore [math]\href{/cs2800/wiki/index.php/Enumerated_set}{\{1\}} \href{/cs2800/wiki/index.php?title=%5Cnsubseteq&action=edit&redlink=1}{\nsubseteq} \href{/cs2800/wiki/index.php/2}{2}^A [/math]
  • But note that [math]\href{/cs2800/wiki/index.php/Enumerated_set}{\{1\}} \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/2}{2}^A [/math].
  • for any set [math]X [/math], we have [math]\href{/cs2800/wiki/index.php/%E2%88%85}{∅} \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/2}{2}^A [/math] and [math]X \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/2}{2}^X [/math], because ∅⊆X and X⊆X.

Cartesian product

Definition: Ordered pair
If [math]x [/math] and [math]y [/math] are things, then [math](x,y) [/math] is the ordered pair of [math]x [/math] and [math]y [/math].


Two ordered pairs [math](x_1,y_1) [/math] and [math](x_2,y_2) [/math] are equal if [math]x_1 = x_2 [/math] and [math]y_1 = y_2 [/math].

In particular, order matters: [math](1,2) \neq (2,1) [/math] because [math]1 \neq 2 [/math].

We can also consider ordered triples, quadruples, etc. The general term is a k-tuple. For example, a pair is a 2-tuple and a triple is a 3-tuple.


Definition: Cartesian product
If [math]A [/math] and [math]B [/math] are sets, then the cartesian product of [math]A [/math] and [math]B [/math] (written [math]A \href{/cs2800/wiki/index.php/%5Ctimes}{\times} B [/math]) is the set of ordered pairs of elements, one from [math]A [/math] and one from [math]B [/math]. Formally, [math]A \href{/cs2800/wiki/index.php/%5Ctimes}{\times} B \href{/cs2800/wiki/index.php/Definition}{:=} \{\href{/cs2800/wiki/index.php/Pair}{(a,b)} \mid a \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A\text{ and }b \href{/cs2800/wiki/index.php/%E2%88%88}{∈} B\} [/math].

For example, [math]\href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2\}} \href{/cs2800/wiki/index.php/%5Ctimes}{\times} \href{/cs2800/wiki/index.php/Enumerated_set}{\{a,b\}} = \{\href{/cs2800/wiki/index.php/Pair}{(1,a)}, \href{/cs2800/wiki/index.php/Pair}{(1,b)}, \href{/cs2800/wiki/index.php/Pair}{(2,a)}, \href{/cs2800/wiki/index.php/Pair}{(2,b)}\} [/math]

Induction by example

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]