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.)

#

#