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 $C$ is infinite if there is no bijection between $C$ and any set $\mathbb{N}_k$ (as defined above).

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

Are the definitions of (standard) infinite and Dedekind-infinite equivalent?

##

Definition. A set $C$ is countable if and only if there exists a surjective function from $\mathbb{N}$ to $C$. (That is, $\le 1$ arrow out from $\mathbb{N}$, $ge 1$ arrow in to $C$.)

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

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

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

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.

# ##

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

# ##

Induction Summary

\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}

Challenge-Response Protocols

1. Verifier: picks random challenge, $y$.

2. Prover: proves knowledge of $x$ by revealing $f(x, y)$.

3. Verifer: can verify prover knows $x$ from response, but learns nothing (useful) about $x$.

How can you know the website you are sending your password to is what you think it is?

Structural Induction

We can show a property holds for all objects of a data type by:

1. Showing the property holds for all base objects.

2. Showing that all the ways of constructing new objects, preserve the property.

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

#

Pairs

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

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.

List Operations

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

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

Unique Construction property:

\begin{equation} \begin{split} \forall p \in \text{\em List} - { \text{\bf null} } \ldotp \exists q \in \text{\em List}, e \in \text{\em Object} \ldotp p = \text{\em prepend}(e, q) \; \wedge
(\forall r \in \text{\em List}, f \in \text{\em Object} \ldotp p = \text{\em prepend}(f, r) \implies r = q \wedge f = e) \end{split} \end{equation}

Why is this necessary for our length definition?

##

def list_prepend(e, l):
    return make_pair(e, l)

def list_first(l):
    return pair_first(l)

def list_rest(l):
    return pair_last(l)

def list_empty(l):
    return l == None

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

Stable Matching

Definition. $M = { (a_1, b_1), (a_2, b_2), \cdots, (a_n, b_n) }$ is a stable matching between two sets $A = { a_1, \cdots, a_n }$ and $B = { b_1, \cdots, b_n }$ with respective preference orderings $\prec_A$ and $\prec_B$ if there is no pair $(a_i, b_j)$ where $bi \prec{a_i} b_j$ and $aj \prec{b_j} a_i$.

How do we know there is always a stable matching between any two equal-size sets?

##

Gale-Shapley Algorithm

def gale_shapley(A, B):
    pairings = {} # dictionary b: a pairings
    unpaired = set(a for a in A.keys()) # unpaired a's
    proposals = {a: 0 for a in A.keys()} # keep track of who gets next proposal

    while unpaired:
        a = unpaired.pop()
        ap = A[a] # a's preference list
        assert proposals[a] < len(ap)
        choice = ap[proposals[a]]
        proposals[a] += 1
        if choice in pairings: # a's choice already has a match
            amatch = pairings[choice]
            bp = B[choice]
            if bp.index(a) < bp.index(amatch):
                pairings[choice] = a
                unpaired.add(amatch) # lost match
            else:
                unpaired.add(a)
        else:
            pairings[choice] = a
    return [(a, b) for (b, a) in pairings.items()]

A = {"Anna": ["Kristoff", "Olaf"], "Elsa": ["Olaf", "Kristoff"]}
B = {"Kristoff": ["Anna", "Elsa"], "Olaf": ["Elsa", "Anna"]}
gale_shapley(A, B)

Modeling the Gale-Shapley program as a state machine

$S = $

$G = $

$q_0 = $

Prove termination. The Gale-Shapley program, modeled by the state machine, eventually returns.

#

#

Prove correctness. The Gale-Shapley program returns a stable matching of the two input sets and preferences.