3.2 Workshop 2 (Reading)

3.2.1 Preparatory Exercises (1 hour)

Proving two sets are equal

Task 3.11.

Read the following proof.

1.
Highlight:
1. (a)
  
  The key features of the proof (e.g. the assumptions, the conclusions, the proof technique used).
2. (b)
  
  Any parts of the proof you don’t understand or are not entirely convinced by.
2.

In this proof, Section A and Section B are written in different styles. Which section do you find easiest to follow? What are the pros and cons of each style?
3.

Try to rewrite Section A in the style of Section B and vice versa.

Theorem (De Morgan’s Laws - Part 1).

If $A$ and $B$ are sets, then

(A\cup B)^{c}=A^{c}\cap B^{c}.

Proof.

(The lines of this proof are numbered to aid your discussion in the workshop.)

1.

To prove $(A\cup B)^{c}=A^{c}\cap B^{c}$ , we first show that $(A\cup B)^{c}\subseteq A^{c}\cap B^{c}$ and then $(A\cup B)^{c}\supseteq A^{c}\cap B^{c}$ .
2.

SECTION A:
3.

Let $x\in(A\cup B)^{c}$ then, by definition of the complement, $x\notin A\cup B$ .
4.

As $x$ is not an element of $A$ or $B$ , then we must have that $x\notin A$ and $x\notin B$ .
5.

Equivalently, $x\in A^{c}$ and $x\in B^{c}$ so $x$ belongs to an intersection of two sets: $x\in A^{c}\cap B^{c}$ .
6.

We’ve shown that any element $x\in(A\cup B)^{c}$ is also an element of $A^{c}\cap B^{c}$ so $(A\cup B)^{c}\subseteq A^{c}\cap B^{c}$ .
7.

SECTION B:
8.

To show $(A\cup B)^{c}\supseteq A^{c}\cap B^{c}$ , consider an element $y\in A^{c}\cap B^{c}$ .

Then

	$\displaystyle y\in A^{c}\cap B^{c}\quad$		(3.1)
$\displaystyle\iff$	$\displaystyle y\in A^{c}\text{ and }y\in B^{c}\quad$	by definition of intersection	(3.2)
$\displaystyle\iff$	$\displaystyle y\notin A\text{ and }y\notin B$	by definition of complement	(3.3)
$\displaystyle\iff$	$\displaystyle y\notin A\cup B$	by definition of union	(3.4)
$\displaystyle\iff$	$\displaystyle y\in(A\cup B)^{c}$	$\displaystyle\text{ by definition of complement}.$	(3.5)

10.

We have therefore shown that $A^{c}\cap B^{c}\subseteq(A\cup B)^{c}$ .
11.

As we have also seen that $(A\cup B)^{c}\subseteq A^{c}\cap B^{c}$ , then we must have $(A\cup B)^{c}=A^{c}\cap B^{c}$ .

Proof by Induction

Part of Block 2 is dedicated to another type of proof technique: Proof by Induction.

Definition (The Principle of Mathematical Induction).

Given a list of statements $P(k),P(k+1),...$ , we may conclude that $P(n)$ is true for every integer $n\geqslant k$ provided that

•

we know that $P(k)$ is true (the base case)
•

and we can prove that $P(n)\Rightarrow P(n+1)$ for any integer $n\geqslant k$ (the induction step).

A full written proof by induction has the following four parts clearly separated.

1.

A clear and explicit statement of the induction hypothesis $P(n)$ and a stated intention to prove that $P(n)$ is true for all $n\geqslant k$ by induction.
2.

The base case. Typically we prove a single statement $P(k)$ .
3.

The induction step. This normally involves assuming $P(n)$ is true and then reasoning that $P(n+1)$ must also be true.
4.

A conclusion that steps (2) and (3) mean that $P(n)$ is true for all natural numbers $n\geqslant k$ by the principle of mathematical induction.

Task 3.12.

1.

Read Section 4.7 in the Companion Notes.
2.

Read the following proof and identify the key features of the proof (e.g. the assumptions, the conclusions) and the 4 key parts of a proof by induction.
3.

Highlight any parts of the proof you don’t understand or are not entirely convinced by.

Theorem (Generalised De Morgan’s Laws - Part 1).

Let $A_{1},\cdots,A_{n}$ be $n$ sets where $n\in\mathbb{N}$ . Then

\displaystyle\left(\bigcup_{i=1}^{n}A_{i}\right)^{c}=\bigcap_{i=1}^{n}A_{i}^{c}

Proof.

(The lines of this proof are numbered to aid your discussion in the workshop.)

1.

We proceed via induction on $n\in\mathbb{N}$ .
2.

Let $P(n)$ be the statement $\displaystyle\left(\bigcup_{i=1}^{n}A_{i}\right)^{c}=\bigcap_{i=1}^{n}A_{i}^{c}$ .
3.

For the base case, first consider $P(1)$ $:\left(\bigcup_{i=1}^{1}A_{i}\right)^{c}=\bigcap_{i=1}^{1}A_{i}^{c}$ .
4.

The union or intersection of one set is the set itself so the left hand side of this equation is $(A_{1})^{c}$ while the right hand side is $A_{1}^{c}$ .
5.

The brackets make no difference here so we have proven the base case $P(1)$ to be true.
6.

For the induction step, to prove $P(k)$ implies $P(k+1)$ , we suppose that $P(k):\left(\bigcup_{i=1}^{k}A_{i}\right)^{c}=\bigcap_{i=1}^{k}A_{i}^{c}$ holds for some $k\in\mathbb{N}$ .

Let $B=\bigcup_{i=1}^{k}A_{i}$ . Then,

$\displaystyle\left(\bigcup_{i=1}^{k+1}A_{i}\right)^{c}$	$\displaystyle=\left(B\cup A_{k+1}\right)^{c}\quad$	by definition of union	(3.6)
	$\displaystyle=B^{c}\cap A_{k+1}^{c}$	by de Morgan’s Laws	(3.7)
	$\displaystyle=\left(\bigcup_{i=1}^{k}A_{i}\right)^{c}\cap A_{k+1}^{c}$	by definition of $B$	(3.8)
	$\displaystyle=\left(\bigcap_{i=1}^{k}A_{i}^{c}\right)\cap A_{k+1}^{c}$	by inductive assumption $P(k)$	(3.9)
	$\displaystyle=\bigcap_{i=1}^{k+1}A_{i}^{c}$	by definition of intersection.	(3.10)

8.

This shows that $P(k+1)$ holds if $P(k)$ holds so, by the principle of mathematical induction, we have shown $P(n)$ holds for all $n\in\mathbb{N}$ .

3.2.2 B2 Reading Workshop Supplementary Material

For Task B2.2.1:

Consider the following sets

	$\displaystyle S$	$\displaystyle=\{n\in\mathbb{Z}:n=a^{2}-b^{2},\text{ for some }a,b\in\mathbb{Z}\},$
	$\displaystyle O$	$\displaystyle=\{n\in\mathbb{Z}:n\text{ is odd}\},$
	$\displaystyle F$	$\displaystyle=\{n\in\mathbb{Z}:n\text{ is divisible by }4\}.$

Claim.

$S=O\cup F$ .

3.1.

If $a-b$ is even then there is some $k\in\mathbb{Z}$ such that $a-b=2k$ . Moreover, $a+b=(a-b)+2b=2k+2b=2(k+b)$ is also even and $n=(a-b)(a+b)=(2k)(2(k+b))=4k(k+b)$ . This means $n$ is divisible by 4 so $n\in F$ and, more generally, $n\in O\cup F$ .

3.2.

Overall, we have shown both $O\cup F\subseteq S$ and $S\subseteq O\cup F$ so can conclude that $S=O\cup F$ .

3.3.

If $m\in O$ , then $m=2k+1$ for some $k\in\mathbb{Z}$ and we can write this as a difference of two squares: $2k+1=(k+1)^{2}-k^{2}$ . Therefore $m\in S$ .

3.4.

Let $m$ be any element of $O\cup F$ .

3.5.

In either case, $n\in O\cup F$ meaning $S\subseteq O\cup F$ .

3.6.

In either case, $m\in S$ meaning $O\cup F\subseteq S$ .

3.7.

If $a-b$ is odd, then for some $k\in\mathbb{N}$ , $a-b=2k+1$ and $a+b=2(k+b)+1$ . The product of two odd numbers is itself odd so we have $n\in O$ and $n\in O\cup F$ .

3.8.

We show $S\subseteq O\cup F$ .

3.9.

Let $n$ be an arbitrary element of $S$ so $n=a^{2}-b^{2}=(a+b)(a-b)$ for some $a,b\in\mathbb{Z}$ .

3.10.

If $m\in F$ , then $m$ is a multiple of 4 so $m=4k$ for some $k\in\mathbb{Z}$ . Consider $(k+1)^{2}-(k-1)^{2}=4k=m$ . As we can write $m$ as the difference of two squares, then we again have $m\in S$ .

3.11.

We prove the inclusion $O\cup F\subseteq S$ .

For Task B2.2.2:

Claim.

For every $n\in\mathbb{N}$ , the sum of the first $n$ positive odd integers equals $n^{2}$ .

Proof.

We prove by induction on $n$ . Let $P(n)$ be the statement “ $\sum_{k=1}^{n}\ldots=n^{2}$ ”. The sum of the first odd number, $1$ , equals …so that $\sum_{k=1}^{1}\ldots$ and so $P(1)$ is true. Assume that $P(n)$ is true for some $n\in\mathbb{N}$ . Then

\displaystyle\sum_{k=1}^{n+1}\ldots=\ldots=(n+1)^{2}.

Hence $P(n+1)$ is also true. Since $P(1)$ holds and $P(n)\Rightarrow P(n+1)$ , it follows that $P(n)$ is true for all $n\in\mathbb{N}$ by the principal of mathematical induction.

For Task B2.2.3:

Theorem.

Every integer $n\geq 2$ can be written as a product of primes $n=p_{1}\cdots p_{k}$ .

Proof.

Let $P(n)$ be the statement $n=p_{1}\cdots p_{m}$ where $p_{i}$ are all prime numbers.

First consider the base case $P(2)$ which immediately holds as a prime number can be considered to be a product of one number.

For the induction step, suppose the theorem holds for all positive integers $2\leqslant k<n$ .

If $n$ is prime, then, as in the base case, $P(n)$ holds immediately.

Otherwise, if $n$ is not prime, then $n=a\cdot b$ for some positive integers $a$ and $b$ greater than $1$ and smaller than $n$ . Both $a$ and $b$ can be decomposed by the inductive hypothesis, thus so can $n=ab$ .

Therefore, we have shown both the base case and the inductive step hold so we can conclude that $P(n)$ holds for all $n\geq 2$ .

For Task B2.2.4:

Faulty Proof 1: Let $P(n)$ be the statement that “ $1.1!+2.2!+3.3!+\cdots+n.n!=(n+1)!$ ”.

Assume $P(k)$ holds for some $k\in\mathbb{N}$ , then

$\displaystyle 1\cdot 1!+\cdots+k\cdot k!+(k+1)(k+1)!$	$\displaystyle=(k+1)!+(k+1)(k+1)!\quad$	by assumption
	$\displaystyle=(k+1)!(k+2)$	by rearranging
	$\displaystyle=(k+2)!$	by definition of $n!$

Therefore, we can conclude $P(n)$ holds for all $n\in\mathbb{N}$ .

Faulty Proof 2: Define $S(n)$ to be the statement “For any collection of $n$ lines in the plane, if no two are parallel then all lines intersect at one point”.

The base case $S(1)$ holds immediately.

Assume $S(k)$ for some $k\in\mathbb{N}$ so that any collection of $k$ lines (no two of which are parallel) intersect at a single point. Then consider having $k+1$ lines, where no two are parallel. The first $k$ lines must intersect at a single point $P$ by the inductive hypothesis. Moreover, the last $k$ lines also intersect at a single point $Q$ . Two non-parallel lines intersect at a single point so $P=Q$ .

Therefore $S(n)$ holds for all $n\in\mathbb{N}$ .

Faulty Proof 3: Let $P(n)$ be the statement “ $a^{n}=1$ for every non-zero $a\in\mathbb{R}$ ”.

As $a^{0}=1$ , $P(0)$ is true.

Assume $P(k)$ holds. Then

a^{k+1}=\frac{a^{k}\cdot a^{k}}{a^{k-1}}=\frac{1\cdot 1}{1}=1.

Hence $P(k+1)$ is true.

Therefore, $P(n)$ holds for all values $n\in\mathbb{N}$ .

3.2.3 Workshop Tasks

Task 3.13 (10 mins).

[Warm Up]

1.
The next questions refer to the first proof in your preparatory exercises (De Morgan’s Laws - Part 1):
1. (a)
  
  In your groups, discuss this proof. Do you agree on its key features? Which parts did you not understand? Can you unpick them as a group?
2. (b)
  
  We prove that $(A\cup B)^{c}\subseteq A^{c}\cap B^{c}$ and $(A\cup B)^{c}\supseteq A^{c}\cap B^{c}$ . Why does this prove that the two sets are equal?
3. (c)
  
  Which style of proof (Section A or Section B) did you prefer and why? Discuss this with your group.

Task 3.14 (15 mins).

[B2.2.1 - Proving two sets are equal]

1.
In your supplementary material for this workshop, you have been given a claim that sets $S$ and $O\cup F$ are equal. But the proof has been cut up into pieces and arranged in the wrong order.
1. (a)
  
  As a group, arrange the blocks into a correct logical order. Is there more than one valid order they can be in?
2. (b)
  
  Identify categories that you can sort the blocks into based on the role that they serve in the proof. Sort the blocks into your categories.
3. (c)
  
  Are there some blocks that only have one possible correct position in the proof? Are there other blocks that can hold a variety of positions in the proof?
4. (d)
  
  Are there any parts in the complete proof which you don’t find fully convincing or are unsure about? Can you resolve them with your group?
2.

EXTENSION: Split the proofs from the preparatory exercises into the categories you’ve identified. Are there any blocks in those proofs that can be reordered?

Consider the following sets

	$\displaystyle S$	$\displaystyle=\{n\in\mathbb{Z}:n=a^{2}-b^{2},\text{ for some }a,b\in\mathbb{Z}\},$
	$\displaystyle O$	$\displaystyle=\{n\in\mathbb{Z}:n\text{ is odd}\},$
	$\displaystyle F$	$\displaystyle=\{n\in\mathbb{Z}:n\text{ is divisible by }4\}.$

Claim: $S=O\cup F$ .

3.12.

3.13.

Overall, we have shown both $O\cup F\subseteq S$ and $S\subseteq O\cup F$ so can conclude that $S=O\cup F$ .

3.14.

If $m\in O$ , then $m=2k+1$ for some $k\in\mathbb{Z}$ and we can write this as a difference of two squares: $2k+1=(k-1)^{2}-k^{2}$ . Therefore $m\in S$ .

3.15.

Let $m$ be any element of $O\cup F$ .

3.16.

In either case, $n\in O\cup F$ meaning $S\subseteq O\cup F$ .

3.17.

In either case, $m\in S$ meaning $O\cup F\subseteq S$ .

3.18.

If $a-b$ is odd, then for some $k\in\mathbb{N}$ , $a-b=2k+1$ and $a+b=2(k+b)+1$ . The product of two odd numbers is itself odd so we have $n\in O$ and $n\in O\cup F$ .

3.19.

We show $S\subseteq O\cup F$ .

3.20.

Let $n$ be an arbitrary element of $S$ so $n=a^{2}-b^{2}=(a+b)(a-b)$ for some $a,b\in\mathbb{Z}$ .

3.21.

3.22.

We prove the inclusion $O\cup F\subseteq S$ .

Task 3.15 (5 mins).

[Induction Warm Up] The next questions refer to the second proof in your preparatory exercises (Generalised De Morgan’s Laws - Part 1):

1.

In your groups, discuss this proof. Do you agree on its key features? Which parts did you not understand? Can you unpick them as a group?
2.

This is a proof by induction. What kind of statements have you seen before that were proved by induction, if any?
3.

When we prove a claim, we know we shouldn’t assume what we’re trying to prove. So why is it valid in the induction step for us to assume that $P(k)$ holds?

Definition (The Principle of Mathematical Induction).

Given a list of statements $P(k),P(k+1),...$ , we may conclude that $P(n)$ is true for every integer $n\geqslant k$ provided that

•

we know that $P(k)$ is true (the base case)
•

and we can prove that $P(n)\Rightarrow P(n+1)$ for any integer $n\geqslant k$ (the induction step).

A full written proof by induction has the following four parts clearly separated.

1.

A clear and explicit statement of the induction hypothesis $P(n)$ and a stated intention to prove that $P(n)$ is true for all $n\geqslant k$ by induction.
2.

The base case. Typically we prove a single statement $P(k)$ .
3.

The induction step. This normally involves assuming $P(n)$ is true and then reasoning that $P(n+1)$ must also be true.
4.

A conclusion that steps (2) and (3) mean that $P(n)$ is true for all natural numbers $n\geqslant k$ by the principle of mathematical induction.

Task 3.16 (10 mins).

[B2.2.2] In your supplementary material, you have been given an induction proof that the sum of the first $n$ positive odd integers equals $n^{2}$ but the proof has gaps.

1.

Identify the 4 key steps of proof by induction in this proof.
2.

Work together to fill in the gaps.
3.

EXTENSION: Can you think of any diagrams that would illustrate this proof? Do they help your understanding of the argument?

Claim: For every $n\in\mathbb{N}$ , the sum of the first $n$ positive odd integers equals $n^{2}$ .

Proof: We prove by induction on $n$ . Let $P(n)$ be the statement “ $\sum_{k=1}^{n}\ldots=n^{2}$ ”. The sum of the first odd number, $1$ , equals …so that $\sum_{k=1}^{1}\ldots$ and so $P(1)$ is true. Assume that $P(n)$ is true for some $n\in\mathbb{N}$ . Then

\displaystyle\sum_{k=1}^{n+1}\ldots=\ldots=(n+1)^{2}.

Hence $P(n+1)$ is also true. Since $P(1)$ holds and $P(n)\Rightarrow P(n+1)$ , it follows that $P(n)$ is true for all $n\in\mathbb{N}$ by the principal of mathematical induction. $\square$

Task 3.17 (15 mins).

[B2.2.3] In your supplementary material, you have a different proof that every integer $n\geqslant 2$ can be written as a product of primes.

1.

Read the proof. Are there any parts that you are unconvinced of? Try and resolve these with your group.
2.

What is different about the structure here compared to a standard induction proof? Why is it important in this case?
3.

Try to re-write this proof using a standard induction argument. Where does it go wrong?

Theorem.

Every integer $n\geq 2$ can be written as a product of primes $n=p_{1}\cdots p_{k}$ .

Proof.

Let $P(n)$ be the statement $n=p_{1}\cdots p_{m}$ where $p_{i}$ are all prime numbers.

First consider the base case $P(2)$ which immediately holds as a prime number can be consider to be a product of one number.

For the induction step, suppose the theorem holds for all positive integers $2\leqslant k<n$ .

If $n$ is prime, then, as in the base case, $P(n)$ holds immediately.

Therefore, we have shown both the base case and the inductive step hold so we can conclude that $P(n)$ holds for all $n\geq 2$ .

Task 3.18 (15 mins).

[B2.2.4] In your supplementary material for this workshop, you have been given 3 faulty induction proofs.

1.

Try to identify the statement that each argument is attempting to prove.
2.

Identify what is wrong with each proof.
3.

‘Fix’ the statements that these arguments are trying to prove, either by changing the conclusion or assumptions.
4.

EXTENSION: Prove your fixed statements.

Faulty Proof 1: Let $P(n)$ be the statement that “ $1.1!+2.2!+3.3!+\cdots+n.n!=(n+1)!$ ”.

Assume $P(k)$ holds for some $k\in\mathbb{N}$ , then

$\displaystyle 1\cdot 1!+\cdots+k\cdot k!+(k+1)(k+1)!$	$\displaystyle=(k+1)!+(k+1)(k+1)!\quad$	by assumption
	$\displaystyle=(k+1)!(k+2)$	by rearranging
	$\displaystyle=(k+2)!$	by definition of $n!$

Therefore, we can conclude $P(n)$ holds for all $n\in\mathbb{N}$ .

Faulty Proof 2: Define $S(n)$ to be the statement “For any collection of $n$ lines in the plane, if no two are parallel then all lines intersect at one point”.

The base case $S(1)$ holds immediately.

Therefore $S(n)$ holds for all $n\in\mathbb{N}$ .

Faulty Proof 3: Let $P(n)$ be the statement “ $a^{n}=1$ for every non-zero $a\in\mathbb{R}$ ”.

As $a^{0}=1$ , $P(0)$ is true.

Assume $P(k)$ holds. Then

a^{k+1}=\frac{a^{k}\cdot a^{k}}{a^{k-1}}=\frac{1\cdot 1}{1}=1.

Hence $P(k+1)$ is true.

Therefore, $P(n)$ holds for all values $n\in\mathbb{N}$ .