# SP18:Lecture 3 Induction

We will introduce a bit more set notation ( and ). We will discuss more proof techniques, including induction.

# Set constructions

## Power set

Definition: Power set
The power set of a set (written )is the set of all subsets of . Formally, .

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 are the subsets of . Here are some examples:

Let . Then

• , by inspection. For example, because .
• , because 1 is a number but contains only sets. Put differently, .
• Therefore
• But note that .
• for any set , we have and , because ∅⊆X and X⊆X.

## Cartesian product

Definition: Ordered pair
If and are things, then is the ordered pair of and .

Two ordered pairs and are equal if and .

In particular, order matters: because .

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 and are sets, then the cartesian product of and (written ) is the set of ordered pairs of elements, one from and one from . Formally, .

For example,

# 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):

Proof:
Choose arbitrary sets , , and . We want to show to show that every is also in . Choose an arbitrary in the left hand side. Then and . This means either (1) or (2) . In case (1), we have and , so , and thus . Case (2) is similar. In either case, , as required.

#### claim 3

We now graduate to claim 3:

Proof:
By claim 2 (with and ), we have . Now, we can apply claim 2 to conclude that . In general, if A ⊆ B then A ∩ C ⊆ B ∩ C, so we know that . Putting this together (and using the fact that ⊆ is transitive),

we have

as required.

#### claim 4

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

Proof: claim 4
By claim 2 (with and ), we have . Now, we can apply claim 3 (above) to conclude that . In general, if A ⊆ B then A ∩ C ⊆ B ∩ C, so we know that . Putting this together (and using the fact that ⊆ is transitive), we have

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 , we can use claim to prove claim (this is called the inductive step), we can conclude claim for any . Here is the general inductive step:

Proof: claim n+1
Since A ∩ (B∪C) ⊆ (A∩B) ∪ (A∩C) (proven above), we have . Now, we can apply claim n (above) to conclude that . In general, if A ⊆ B then A ∩ C ⊆ B ∩ C, so we know that . Putting this together (and using the fact that ⊆ is transitive), we have

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 ,

Proof:
By induction. Let be the statement "."

We must show and assuming .

In the base case, when , we want to show to show that every is also in . Choose an arbitrary in the right hand side. Then and . This means either (1) or (2) . In case (1), we have and , so , and thus . B_2ase (2) is similar. In either case, , as required.

For the inductive step, choose an arbitrary and assume we have already proved . Our goal is to show . We compute: