Infinite Sets

Finite Cardinality. The cardinality of the set $$ \mathbb{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. (Class 9)

Does this definition tell us the cardinality of $\mathbb{N}$?

###

Definition. A set $S$ is infinite if there is no bijection between $S$ and any set $\mathbb{N}_k$ (as defined above).

Show that $\mathbb{Z}$ is infinite.

Cardinality of Infinite Sets

Equal Carinalities. We say $|A|\; = |B|$ for arbitrary sets $A,B$ (and say that they have the same cardinality), if there is a bijection between $A$ and $B$.

Comparing Cardinalities. We say $|B|\; \leq |A|$ for arbitrary sets $A,B$ (and say that $B$’s cardinality is less than or equal to the cardinality of $A$), if there is a surjective function from $A$ to $B$.

Show that $|A|\; = |B|$ implies $|B|\; \leq |A|$ and $|A|\; \leq |B|$. Be careful as these sets might not be finite, in which case we cannot simply use natural numbers to denote their cardinalities.

##

Schr\wrap{\“{o}}der-Bernstein Theorem: If $|A|\; \leq |B|$ and $|B|\; \leq |A|$, then there is a bijection between $A$ and $B$, namely $|A|\; = |B|$. (Not proven in cs2102; this is somewhat tricky to prove! For a full proof, see the linked lecture notes.)

Other Definitions for Infinite Sets

Dedekind-Infinite. A set $A$ is Dedekind-infinite if and only if there exists a strict subset of $A$ with the same cardinality as $A$. That is, $$\exists B \subset A \ldotp \exists R \ldotp R\ \text{is a bijection between}\ A\ \text{and}\ B.$$

Recall the definition of strict subset: $$B \subset A \iff B \subseteq A \wedge \exists x \in A\; .\; x \notin B.$$

Third Definition. A set $S$ is third-definition infinite if $|S|\; \geq |\mathbb{N}|$ (as defined on the previous page). Namely, there is a surjective function from $S$ to $\mathbb{N}$.

Are the above three definitions of (standard) infinite and Dedekind-infinite and third-definition infinite equivalent definitions?

##

Definition. A set $S$ is countable if and only if there exists a surjective function from $\mathbb{N}$ to $S$. (That is, $\le 1$ arrow out from $\mathbb{N}$, $\ge 1$ arrow in to $S$.) Using our notation defined above, this means $|S|\; \leq |\mathbb{N}|$.

Prove that these sets are countable: $\mathbb{Z}$, $\mathbb{N} \times \mathbb{N}$, $\mathbb{Q}$ (rationals), $\emptyset$, $\mathbb{N} \cup (\mathbb{N} \times \mathbb{N}) \cup (\mathbb{N} \times \mathbb{N} \times \mathbb{N})$, all finite sequences of elements of $\mathbb{N}$.

#

Definition. A set $S$ is countably infinite if and only if it is countable and it is infinite (according to standard definition).

Must a countable set that is Dedekind-infinite be countably infinite?

#

Using the definition of countable, and third definition of infinite, show that $S$ is countably infinite if and only if there is a bijection between $S$ and $\mathbb{N}$. (We might as well use this definition in the future.)

Lists

Definition. A list is an ordered sequence of objects. A list is either the empty list ($\lambda$), or the result of $\text{prepend}(e, l)$ for some object $e$ and list $l$.

\begin{equation} \begin{split} \text{\em first}(\text{prepend}(e, l)) &= e
\text{\em rest}(\text{prepend}(e, l)) &= l
\text{\em empty}(\text{prepend}(e, l)) &= \text{\bf False}
\text{\em empty}(\text{\bf null}) &= \text{\bf True}
\end{split} \end{equation}

Definition. The length of a list, $p$, is: \begin{equation} \begin{split} \begin{cases} 0 & \text{if}\ p\ \text{is \bf null}
\text{\em length}(q) + 1 & \text{otherwise}\ p = \text{\em prepend}(e, q)\ \text{for some object}\ e\ \text{and some list}\ q
\end{cases} \end{split} \end{equation}

def list_length(l):
    if list_empty(l):
        return 0
    else:
        return 1 + list_length(list_rest(l))

Prove: for all lists, $p$, list_length(p) returns the length of the list $p$.

Concatenation

Definition. The concatenation of two lists, $p = (p_1, p_2, \cdots, p_n)$ and $q = (q_1, q_2, \cdots, q_m)$ is $$(p_1, p_2, \cdots, p_n, q_1, q_2, \cdots, q_m).$$

Provide a constructuve definition of concatenation.

Note that $\text{prepend}(p,q)$ is not a good idea for two reasons. If we use this definition, then the first element of the constructed list will be the object (list) $p$ (as a whole) rather than the first element $p_1$ of the list $p$. Also, if we want to only define lists of specific objects, for example integers, we can still use the same recursive/constructive definition of lists by substituting “object” with “integer”, but in that case $\text{prepend}(p,q)$ will not even well defined, as it can only accept integers as first input.

#

Structural Induction

To prove proposition $P(x)$ for element $x \in D$ where $D$ is a recursively-constructed data type, we do two things:

1. Show $P(x)$ is true for all $x \in D$ that are defined using base cases.
2. Show that if $P(y)$ is true for element $y$ and $x$ is constructed from $y$ using any “construct case” rules, then $P(x)$ is true as well.

Comparing Various forms of Induction

\begin{center} \begin{tabular}{lccc} & {\bf Regular Induction} & {\bf Invariant Principle} & {\bf Structural Induction} \ \hline Works on: & natural numbers & state machines & data types
To prove $P(\cdot)$ & {\em for all natural numbers} & {\em for all reachable states} & {\em for all data type objects}
Prove {\bf base case(s)} & $P(0)$ & $P(q_0)$ & $P(\text{base object(s)})$
and {\bf inductive step} & $\forall m \in \mathbb{N} \ldotp$ & $\forall (q, r) \in G \ldotp $ & $\forall s \in \text{\em Type} \ldotp$
& $P(m) \implies P(m+1)$ & $P(q) \implies P®$ & $P(s) \implies P(t)$
& & & $\quad \forall t\ \text{constructable from}\ s$ \ \end{tabular} \end{center}

# ##

Prove. For any two lists, $p$ and $q$, $\text{length}(p + q) = \text{length}(p) + \text{length}(q)$.

#

Proving Correctness

def slow_power(a, b):
   y = 1
   z = b
   while z > 0:
      y = y * a
      z = z - 1
   return y

We model the Python program with a state machine:

$S ::= \mathbb{N} \times \mathbb{N}$
$G ::= { (y, z) \rightarrow (y \cdot a, z - 1) \, | \, \forall y, z \in \mathbb{N}^{+}}$
$q_0 ::= (1, b)$

It is important to remember this is a model. It does not capture many important aspects of execution of a real Python program. In particular, it only models inputs in $\mathbb{N}$, when the actual inputs could be other types in PYthon. It also assume all math opderations work mathematically, not Pythonically.

To prove partial correctness, we show $P(q = (y, z)) := y = a^{b-z}$ is a preserved invariant. Then, we show that it holds in state $q_0$. Finally, we show that in all final states, $y = a^b$.

Invariant is Preserved: We need to show that $\forall q \in S . \forall t \in S . (q, t) \in G \implies P(q) \implies P(t)$.

1. $q = (y, z)$. $P(q = (y, z))$: $y = a^{b-z}$.
2. If there is an edge from $q$ to $t$, that means $t = (y \cdot a, z-1)$ and $z \ge 1$ since this is the only edge from $q$ in $G$.
3. We show $P(t = (y \cdot a, z-1))$ holds by multiplying both sides of $P(q)$ by $a$: $$ya = (a^{b -z}) \cdot a = a^{b - z + 1} = a ^{b - (z - 1)}.$$

Invariant holds in $q_0$: $q_0 = (1, b)$. So, we need to show $P(q_0 = (1, b))$: $1 = a^{b - b}$. This holds since $a^{0} = 1$.

Final states: All states where $z \ge 1$ have an outgoing edge, but no states where $z = 0$ do. So, the final states are all of the form $(\alpha, 0)$. If a final state is reachable from $q_0$, the invariant must hold since we proved it is preserve. Hence, in the final state $(\alpha, 0)$ we know $\alpha = a^{b}$.

This proves partial correctness: if the program terminates, it terminates in a state where the property ($y = a^b$ is satisfied). To prove total correctness we also need to know the execution eventually reaches a final state.

We prove this by showing that from any initial state $q_0 = (1, b)$, the machine will reach a final state $q_f = (y, 0)$ in $b$ steps. The proof in class used the Well Ordering Principle. You could also prove this using regular Induction.

Pairs

What is the difference between scalar data and compound data structures?

Definition. A $\text{\em Pair}$ is a datatype that supports these three operations:
\begin{quote} $\text{\em make_pair}: \text{\em Object} \times \text{\em Object} \rightarrow \text{\em Pair}$
$\text{\em pair_first}: \text{\em Pair} \rightarrow \text{\em Object}$\
$\text{\em pair_last}: \text{\em Pair} \rightarrow \text{\em Object}$\
\end{quote} where, for any objects $a$ and $b$, $\text{\em pair_first}(\text{\em make_pair}(a, b)) = a$ and $\text{\em pair_last}(\text{\em make_pair}(a, b)) = b$.

def make_pair(a, b):
    def selector(which):
        if which:
            return a
        else:
            return b
    return selector

def pair_first(p):
    return p(True)

def pair_last(p):
    return p(False)

Lists

Definition (1). A List is either (1) a Pair where the second part of the pair is a List, or (2) the empty list.

Definition (2). A List is a ordered sequence of objects.

State Machines (review from Class 13)

A state machine, $M = (S, G: S \times S, q_0 \in S)$, is a binary relation (called a transition relation) on a set (both the domain and codomain are the same set). One state, denoted $q_0$, is designated as the start state.

An execution of a state machine $M = (S, G \subseteq S \times S, q_0 \in S)$ is a (possibly infinite) sequence of states, $(x_0, x_1, \cdots, x_n)$ where (1) $x_0 = q_0$ (it begins with the start state), and (2) $\forall i \in {0, 1, \ldots, n - 1} \ldotp (xi, x{i + 1}) \in G$ (if $q$ and $r$ are consecutive states in the sequence, then there is an edge $q \rightarrow r$ in $G$).

A state $q$ is reachable if it appears in some execution.

A preserved invariant of a state machine $M = (S, G \subseteq S \times S, q_0 \in S)$ is a predicate, $P$, on states, such that whenever $P(q)$ is true of a state $q$, and $q \rightarrow r \in G$, then $P®$ is true.

Bishop State Machine

$S = { (\fillin ) \, | \, r, c \in \mathbb{N} }$ $G = { (r, c) \rightarrow (r’, c’) \, | \, r, c \in \mathbb{N} \wedge (\exists d \in \mathbb{N}^{+} \textrm{ such that } r’ = r \fillin d \wedge r’ \ge 0 \wedge c’ = c \fillin d \wedge c’ \ge 0 }$ $q_0 = (0, 2)$

What states are reachable?

#

``Progress” Machine

$S = { (x, d) \, | \, x \in \mathbb{Z}, d \in { \mathrm{\bf F}, \mathrm{\bf B}} }$ $G = { (x, \mathrm{\bf F}) \rightarrow (x + 1, \mathrm{\bf B}) \, | \, x \in \mathbb{Z} } \cup { (x, \mathrm{\bf B}) \rightarrow (x - 2, \mathrm{\bf F}) \, | \, x \in \mathbb{Z} }$ $q_0 = (0, \mathrm{\bf F})$

Which states are reachable?

Preserved Invariants

A predicate $P(q)$ is a preserved invariant of machine $M = (S, G \subseteq S \times S, q_0 \in S)$ if: $$ \forall q \in S \ldotp (P(q) \wedge (q \rightarrow r) \in G) \implies P® $$

What are some preserved invariants for the (original) Bishop State Machine?

Invariant Principle. If a preserved invariant of a state machine is true for the start state, it is true for all reachable states.

To show $P(q)$ for machine $M = (S, G \subseteq S \times S, q_0 \in S)$ all $q \in S$, show:

1. Base case: $P(\fillin)$
2. $\forall s \in S \ldotp \fillin \implies \fillin$

Prove that the original Bishop State Machine never reaches a square where $r + c$ is odd.

Slow Exponentiation

def slow_power(a, b):
   y = 1
   z = b
   while z > 0:
      y = y * a
      z = z - 1
   return y

$S ::= \mathbb{N} \times \mathbb{N}$ $G ::= { (y, z) \rightarrow (y \cdot a, z - 1) \, | \, \forall y, z \in \mathbb{N}^{+}}$ $q_0 ::= (1, b)$

Prove slow_power(a, b) = $a^b$.

#

Fast Exponentiation

This is the algorithm from Section 6.3.1 written as Python code:

def power(a, b):
   x = a
   y = 1
   z = b
   while z > 0:
      r = z % 2 # remainder of z / 2
      z = z // 2 # quotient of z / 2
      if r == 1:
         y = x * y
      x = x * x
   return y

State Machines

A state machine is a binary relation (called a transition relation) on a set (both the domain and codomain are the same set). One state is designated as the start state.

$$M = (S, G: S \times S, q_0 \in S)$$

What does it mean if $G$ is total?

##

What does it mean if $G$ is not a function?

##

Parity Counter. Describe a state machine that determines if the number of steps is even.

#

Unbounded Counter. Describe a state machine that counts the number of steps.

#

How well do state machines model real computers? What kind of transition relation does the state machine modeling your computer have?

State Machine Execution

An execution of a state machine $M = (S, G \subseteq S \times S, q_0 \in S)$ is a (possibly infinite) sequence of states, $(x_0, x_1, \cdots, x_n)$ where:

1. $x_0 = q_0$ (it begins with the start state), and
2. $\forall i \in {0, 1, \ldots, n - 1} \ldotp (xi, x{i + 1}) \in G$ (if $q$ and $r$ are consecutive states in the sequence, then there is an edge $q \rightarrow r$ in $G$)

A state $q$ is reachable if it appears in some execution. (That is, there is a sequence of transitions starting from $q_0$, following edges in $G$, that ends with $q$.)

$$ M_1 = (S = \mathbb{N}, G = {(x, y) | y = x^2 }, q_0 = 1) $$ $$ M_2 = (S = \mathbb{N}, G = {(x, y) | \exists k \in \mathbb{N} \ldotp y = kx }, q_0 = 1) $$

Which states are reachable for $M_1$ and $M_2$?

#