Discrete Mathematics

# 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

1. State, “We prove by induction.”
2. 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}$.
3. Prove $P(0)$ is true. (base case or basis step.)
4. Prove that $P(n) \implies P(n + 1)$ for every $n \in \mathbb{N}$. (induction step)
5. 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.)

#

#