cs2102: Discrete Math

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

#

Fall Break Office Hours (Sun, 1 Oct 2017)

The office hours schedule for next week will be different from normal because of “Fall Break” and the Exam (as usual, all will be in Rice 436 except the professors’ as noted):

#### Monday (2 Oct)

Mohammad Mahmoody (Rice 511), 10:45-11:45am

Sarah Meng, 4:30-6:00pm

#### Tuesday (3 Oct)

Nate Olsen, 10-11:30am

Michael Woon, 11am-12:30pm

Henry Spece, 3:30-5pm

#### Wednesday (4 Oct)

Colin Harfst, 9:30am-12:30pm

Anna Wu, noon-1:30pm

Michael Woon, 12:30-2:00pm

David Evans (Rice 507), 2:30-3:30pm

Bhuvanesh Murali, 3-5pm

Helen Simecek, 3:30-5pm

Yasasvini Puligundle, 5-6pm

Xueying Bai, 6-7pm

Fan Feng, 7-8:30pm

Nate Olsen, 7:30-9:00pm

#### Thursday (5 Oct)

Amar Singh, 9am-10:30

Xiao Zhang, 10-11am

Prashant Gorthi, 11am-noon

No office hours Thursday afternnon and evening. The normal office hours schedule will resume on Monday, 9 October.

Problem Set 5 Comments (Sun, 1 Oct 2017)

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