Discrete Mathematics

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:

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

#

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.

Python code from class and list definitions: pairs.py

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.

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 (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


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:

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

#

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)

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