cs2102: Discrete Math

Problem Set 8 (Sat, 28 Oct 2017)

**Problem Set 8** [PDF] is now posted and
is due **Friday, 3 Nov at 6:29:00pm**. Please read the
collaboration policy carefully.

Class 18: Spooky Infinities (Thu, 26 Oct 2017)

### Schedule

**Problem Set 7** is due **Friday (27 Oct) at 6:29pm**.

**Exam 2** is two weeks from today (November 9, in class). We will
post more information about Exam 2 soon.

## Links

*Logicomix: An epic search for truth*, comic book by Apostolos Doxiadis and Christos H. Papadimitrou.

Last year, there was a Problem Set ω - you can see some examples of student’s work. (Note that having a PS ω does not imply any limit on the number of regular problem sets, since there are infinitely many natural numbers before ω!)

## Countable and Uncountable Sets

**Definition.** A set $S$ is *countably infinite* if and only if there
exists a bijection between $S$ and $\mathbb{N}$.

**Definition.** A set $S$ is *uncountable*, if there exists no bijection
between $S$ and $\mathbb{N}$.

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

For all **finite** sets $S$, $|pow(S)| = 2^{|S|}$.

# #

For **all** sets $S$, $|pow(S)| > |S|$.

#

Prove $pow(\mathbb{N})$ is uncountable.

#

$\text{bitstrings} = \forall n \in \mathbb{N} . {0, 1}^n$.

#

## Ordinal and Cardinal Numbers

$\omega$ is the *smallest infinite ordinal*. The first ordinal after
$0, 1, 2, \cdots$.

What is the difference between an *ordinal* and *cardinal* number?

##

What should $2\omega$ mean?

##

Is $\text{InfiniteBitStrings} = {0, 1}^\omega$ countable?

#

Prove the number of real numbers in the interval $[0, 1]$ is uncountable.

Problem Set 6 Comments (Wed, 25 Oct 2017)

The Problem Set 6 solutions and comments are now posted in collab: PDF

Class 17: Infinite Sets (Tue, 24 Oct 2017)

### Schedule

Before Thursday, everyone should have finished reading MCS Chapter 8.

**Problem Set 7** is due **Friday (27 Oct) at 6:29pm**.

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

Problem Set 7 (Fri, 20 Oct 2017)

**Problem Set 7** [PDF] is now posted and
is due **Friday, 27 Oct at 6:29:00pm**. Please read the
collaboration policy carefully.

Class 16: Structural Induction (Thu, 19 Oct 2017)

### Schedule

**Problem Set 6** is due **tomorrow at 6:29pm**. Make sure to read the corrected version of Problem 7.

# 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:

- Show $P(x)$ is true for all $x \in D$ that are defined using base cases.
- 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)$.

#

Class 15: Recursive Data Types (Tue, 17 Oct 2017)

### Schedule

You should read MCS Chapter 7 this week.

**Problem Set 6** is due **20 October (Friday) at 6:29pm**.

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

- $q = (y, z)$. $P(q = (y, z))$: $y = a^{b-z}$.
- 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$.
- 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.

Class 14: Invariant Principle (Thu, 12 Oct 2017)

### Schedule

**Problem Set 6** is due **20 October (Friday) at 6:29pm**.

Exam 1 was returned Tuesday. If you did not pick yours up yet, you can get it after class today. We will start charging exponentially-increasing storage fees for inexcusably unclaimed exams starting after Prof. Mahmoody’s office hours Monday.

## 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 (x*i, 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:

- Base case: $P(\fillin)$
- $\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
```

Problem Set 6 (Thu, 12 Oct 2017)

**Problem Set 6** [PDF] is now posted and
is due **Friday, 20 Oct at 6:29:00pm**. Please read the
collaboration policy carefully.

Class 13: State Machines (Tue, 10 Oct 2017)

### Schedule

There is no Problem Set due this week. **Problem Set 6** will be posted soon and due next **Friday (October 20) at 6:29pm**.

Exam 1 was returned in class today. Please read the solutions posted in collab: Exam 1 Comments. If you didn’t pick up Exam 1 in class today, you can get it at Dave’s office hours tomorrow, or before or after class on Thursday.

## 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:

- $x_0 = q_0$ (it begins with the start state), and
- $\forall i \in {0, 1, \ldots, n - 1} \ldotp (x
*i, 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$?

#