Class 10: Set Cardinality, Induction

### Schedule

This week you should finish reading MCS Chapter 4 (section 4.5) and Section 5.1. We will discuss Induction (Section 5.1) next class.

**Problem Set 4** is due **Friday at 6:29pm**. The
original version of Problem Set 4, Question 6, asked for a *function*,
when we really meant to ask for a *total function* (as we defined it
in class today, and the book defines it). The problem set is updated
now to specify this. If you already answered the original question,
you do not need to update your answer, just indicate clearly for which
questions the function you defined is partial. Sorry for the
confusion!

**Problem Set 5** (not yet posted) will be due Friday, 29 September.

**Exam 1** will be in-class on Thursday, 5 October. It will cover
Classes 1 - 11, Problem Sets 1 - 5, and MCS Chapters 1 - 5.

**Alternate definition:** The *cardinality* of the set
$$
N_k = { n | n \in \mathbb{N} \wedge n < k }
$$
is $k$. If there is a *bijection* between two sets, they have the same
cardinality.

#

If there is a *surjective relation* between $A$ and $B$ what do we know
about their cardinalities?

##

If there is a *surjective function* between $A$ and $B$ what do we know
about their cardinalities?

##

If there is a *total surjective function* between $A$ and $B$ what do we know
about their cardinalities?

##

If there is a *total surjective injective function* between $A$ and $B$
what do we know about their cardinalities?

##

What is the cardinality of $A \cup B$?

#

# Induction Principle

Let $P$ be a predicated on $\mathbb{N}$. If

- $P(0)$ is true, and
- $P(n) \implies P(n + 1)$ for all $n \in \mathbb{N}$,

then

- $P(m)$ is true for all $m \in \mathbb{N}$.

## Template for Induction Proofs

- State, “We prove by induction.”
- Define a predicate, $P(n)$. This is the
*induction hypothesis*. Our goal is to show that $P(n)$ is true for all $n \in \mathbb{N}$. - Prove $P(0)$ is true. (
*base case*or*basis step*.) - Prove that $P(n) \implies P(n + 1)$ for every $n \in \mathbb{N}$. (
*induction step*) - Conclude that $P(n)$ is true for all $n \in \mathbb{N}$ by induction.

How is the method of *proof by induction principle* similar to and different from *proof by well-ordering principle*?

# Power Sets

The **power set** of $A$ ($\textrm{pow}(A)$)is the set of all subsets of $A$:
$$
B \in \textrm{pow}(A) \iff B \subseteq A.
$$

Prove that the size of the power set of a set $S$ with $|S| = N$ is $2^N$ using induction. (We’ll do this in Class 11, but see how far you can get on your own.)

#

#