Strong Induction Principle

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

• $P(0)$ is true, and
• $(\forall m \in \mathbb{N}, m \le n . P(n)) \implies P(n + 1)$ for all $n \in \mathbb{N}$,

then

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

As an inference rule:

$$ \infer{\forall m \in \mathbb{N} . P(m)}{P(0), \forall n \in \mathbb{N} . (P(0) \vee P(1) \wedge \cdots \wedge P(n)) \implies P(n + 1)} $$

With arbitrary basis, $b \in \mathbb{N}$:

$$ \infer{\forall m \in { b, b+1, b+2, \ldots } . P(m)}{P(b), \forall n \in \mathbb{N} . (P(b) \vee P(b + 1) \wedge \cdots \wedge P(n)) \implies P(n + 1)} $$

Show that strong induction is not actually stronger than regular induction. (Hint: if the predicate for strong induction is $P(m)$, explain how to construct a predicate, $P’(m)$, that works with regular induction.)

##

Example Strong Induction Proof

Theorem: Every number, $n \in \mathbb{N}, n \geq 4$ can be written as $\alpha \cdot 2 + \beta \cdot 5$ where $\alpha, \beta \in \mathbb{N}$.

Proof by Strong Induction:

1. First we need to define the predicate: $$P(n) := \exists \alpha, \beta \in \mathbb{N} . n = \alpha \cdot 2 + \beta \cdot 5$$.

2. Basis: we are proving for all $n > 3$:

   $P(4)$: $\alpha = 2, \beta = 0$ gives $4 = 2 \cdot 2 + 0 \cdot 5$. $P(5)$: $\alpha = 0, \beta = 1$ gives $5 = 0 \cdot 2 + 1 \cdot 5$.

3. Induction step: $\forall n \in {6, \ldots }$

   By strong induction, assume $P(m)$ is true for all $m \in { 4, 5, 6, \ldots, m}$.

   Show $P(m + 1)$: Since $P(m - 1)$ is true (by the \emph{strong} induction hypothesis), we know $\exists \alpha, \beta \in \mathbb{N} . m - 1 = \alpha \cdot 2 + \beta \cdot 5$. We can show $P(m + 1)$ since $m + 1 = (\alpha + 1) \cdot 2 + \beta \cdot 5$.

Proof by Contra-Positive (Review)

Recall: $P \implies Q$ is equivalent to $\neg Q \implies \neg P$. (If you are shaky on this, prove it to yourself using a truth table.)

Typical use: where the negation of the proposition is easier to reason about than the original proposition (e.g., irrational is a complex property to describe, but rational (NOT irrational) is a simple one. So to prove that ``If $r$ is irrational then $\sqrt{r}$ is also irrational” we can prove the contrapositive which is “if $\sqrt{r}$” is rational, then $r$ is also rational$ which is quite straightforward.

Proof by Contradiction (Review)

To prove $P$, show $\neg P \implies False$.

Example: Proving the $\mathbb{Z}$ is not well ordered.

Goal: proving the proposition $G$ saying ``$\mathbb{Z}$ has no minimum”.

1. To prove by contradiction, assume $\neg G$ (that is, $\mathbb{Z}$ does have a minimum).

2. Then, $\exists m \in \mathbb{Z}$ that is the minimum of $\mathbb{Z}$.

3. But, this leads to a contradiction: $m - 1 \in \mathbb{Z}$ and $m - 1 < m$. So, even though the number $m$ was said to be the minimum of $\mathbb{Z}$, it is in fact not the minimum.

4. Thus, we have a contradiction, so something must be wrong. All our logical inferences after step 1 are correct, so the assumption we made in step 1 must be invalid. If $\neg G$ is invalid, $G$ must be true.

Typical use: when the statment we want to prove has universal quantifier. for example, $\forall x \in \mathbb{Z}. P(x)$. Note that the statment that $\mathbb{Z}$ has \emph{no} minimum, when written formally, uses a universal quantifier (make sure to double check it). Then, instead of arguing that for all $x \in A$, $P(x)$ holds, we assume (for sake of contradiction) that there exists one $x$ for which $\neg(P(x))$ (note that this is indeed the negated statement) from which we get a contradiction.

Binary Relation Properties

When we draw the graph of binary relations, the Domain (input" set) has outgoing edges. Codomain (output” set) has incoming edges. So when we use the compact notation referring to different properties of binary relations, keep in mind that the words ``in-out” refer to the edge (not the input/output sets). The properties about outgoing edges are function ($\le 1 out$) and total ($\ge 1$ out). Adding elements to the codomain cannot effect these properties. The properties about incoming edges are surjection ($\ge 1$ in) and injection ($\le 1$ in). Adding elements to the domain cannot effect these properties.

When we say the any relation with property $X$ (e.g., $\ge 1$ out) about the relations \emph{must} also have propety $Y$. It means that property $X$ implies $Y$ logically (about relations). In case the answer is “no” (i.e. that property $X$ does not imply $Y$) all we have to find is one relation $R$ that satisfies property $X$ but not property $Y$. If the answer is `yes’ we need to show that for all $R$, if property $X$ holds, so does $Y$. So doing so might need more work.

If an edge is added to the graph of a relation, which properties might be impacted?

If an edge is removed to the graph of a relation, which properties might be impacted?

If an element is removed from the domain of a relation, which properties might be impacted?

If an element is removed from the codomain of a relation, which properties might be impacted?

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}$.

Prove: For all sets $A$, $|pow(A)| = 2^|A|$.

Prove: The sum of the first $n$ positive integers is $\frac{n(n+1)}{2}$.

Generalizing to Well-Ordered Sets

We can use Induction for any well-ordered set, where there is an operation (like ‘+ 1’) and a starting point (like ‘0’) that covers the whole set.

Prove. All non-empty finite subsets of $\mathbb{N}$ have a minimum element.

Induction Practice

Take-Away Game: start with $n$ sticks; at each turn a player must remove 1, 2 or 3 sticks; player who takes the last stick wins.

• Prove: for a Take-Away game with any initial number of sticks, $n$, either Player 1 has a winning strategy or Player 2 does.

• Prove: Player 1 has a winning strategy for a Take-Away game with $n$ sticks, if \bigfillin. Otherwise, Player 2 has a winning strategy.

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

#

#

Total and Partial Functions

A function is a mathematical datatype that associates elements from one set, called the domain, with elements from another set, called a codomain.

$$ f: \textrm{\em domain} \rightarrow \textrm{\em codomain} $$

If the function is total, every element of the domain has one associated codomain element; if the function is partial, there may be elements of the domain that do not have an associated codomain element.

Relation Relationships

Definition review: binary relation, $R$, consists of a domain set, $A$, and a codomain set, $B$, and a subset of $A \times B$ called the graph of $R$.

For each statement below, give the name and at least one example.

• A binary relation where no element of $A$ has more than one outgoing edge:

##

• A binary relation where every element of $A$ has exactly one outgoing edge:

##

• A binary relation where every element of $B$ has exactly one incoming edge:

##

• A binary relation where every element of $A$ has exactly one outgoing edge and every element of $B$ has exactly one incoming edge:

##

If there exists a bijective relation between $S$ and $T$ defined by the graph $G$ which of these must be true:

a. there exists some injective relation between $S$ and $T$. b. there exists some bijective relation between $T$ and $S$. c. there exists a total function, $f: S \rightarrow T$. d. $S - T = \emptyset$. e. the number of elements of $S$ is equal to the number of elements of $T$. f. $G - (S \times T) = \emptyset$. g. $(S \times T) - G = \emptyset$. h. $(S \times T) - G \neq \emptyset$.

Relation Practice

The inverse of a relation $R: A \rightarrow B, G \subseteq A \times B$ is defined by reversing all the arrows: $$ R^{-1}: B \rightarrow A, G^{-1} \subseteq B \times A $$

$$ (b, a) \in G^{-1} \iff \fillin\fillin\fillin\fillin $$

What does it mean if $R \equiv R^{-1}$?

Set Cardinality

Finite Cardinality. The book’s definition is: ``If $A$ is a finite set, the cardinality of $A$, written $|A|$, is the number of elements in $A$.”

Does this definition require adding a new fundamental set operation, or is it meaningful with just the set operations we have defined?

Alternate definition: The cardinality of the set $$ N_k = { n | n \in \mathbb{N} \wedge n < k } $$ is $k$. (Next class, we’ll use this to define the cardinality of any set. You should be able to figure out how to do this on your own with what you know now.)

Sequences

A sequence is a mathematical datatype that bears similarities to sets. A sequence $S$ also contains some elements, but we usually refer to them as components. There are two major differences between sets and sequences:

1. Components of a sequence are ordered. There is either $0$, or $1$ or $2$, or … $n$ components, when the sequence if finite or it could be an infinite sequence that has an $i$‘th component for any non-zero natural number $i$.

2. Different components of a sequence could be equal. For example $(a,b,a)$ has $a$ repeating, and this is a different sequence compared to $(a,b,b)$ even though they both have 3 componetns. If we interprete them as sets, then they will be equal sets with $2$ elements each.

Cartesian Product

We can use set products to get new sets whose elements are sequences. Cartesian product is a very useful way of doing it.

Set Products. A Cartesian product of sets $S_1, S_2, \cdots, S_n$ is a set consisting of all possible sequences of $n$ elements where the $i$\textsuperscript{th} element is chosen from $S_i$.

$$ S_1 \times S_2 \times \cdots \times S_n = { (s_1, s_2, \cdots, s_n) | s_i \in S_i } $$

How many elements are in $A \times B$?

Relations and Binary Relations

A relation between some elements from set $A$ and some elements from set $B$ could be represented by putting all such pairs $(a,b)$ in a set $P$. As you can see, this way, $P$ would be a subset of the cartesian product $A \times B$, namely $P \subseteq A \times B$. More formally we have the following definition.

A binary relation, $P$, is defined with respect to a domain set, $A$, and a codomain set, $B$, and it holds that $P$ is $P \subseteq A \times B$. When we draw $P$ by connecting elements of $A$ to $B$ based on their membership in $P$, we call this the graph of $R$.

The notion of relations could be generalized to having relations between elements coming from multiple sets $A,B,C$, and we can also talk about relations of the form $P \subseteq A \times B \times C$, but the binary relation remains a very important data type as it allows us to define functions.

Functions

The concept of a function $F$ models is a special form of a binary relation $R$ between $A$ and $B$ where for every element $a \in A$ there is at most one element in $b \in B$ that is in relation with $a$ (i.e. $(a,b) \in R$). More formally, we use a direct new notation just reserved for working with functions.

A function is a mathematical datatype that associates elements from one set, called the domain, with elements from another set, called a codomain.

$$ f: \textrm{\em domain} \rightarrow \textrm{\em codomain} $$

Defining a function. To define a function, we need to describe how elements in the domain are associated with elements in the codomain.

#

What are the (sensible) domains and codomains of each function below:

$$ f(n) ::= |n| \qquad \qquad f(x) ::= x^2 \qquad\qquad f(n) ::= n + 1 \qquad\qquad f(a, b) ::= a / b $$

$$ f(x) ::= \sqrt{x} \qquad \qquad \qquad f(S) ::= \textrm{minimum}_{<}(S) $$