Sequences

A sequence $S$ is a partial function from the natural numbers $\mathbb{N}$ to a set $\Sigma$.

\[\mathbb{N} = \{0, 1, 2, 3, \ldots\}\] \[\Sigma = \{\text{e, i, o, u, æ, ɑ, ɔ, ə, ɛ, ɪ, ʊ, ɹ, d, t}\}\] \[S = \begin{Bmatrix} 0 & \rightarrow & \text{d}\\ 1 & \rightarrow & \text{u}\\ 2 & \rightarrow & \text{d}\\ \end{Bmatrix}\]

This definition admits of sequences with gaps in the natural numbers.

\[\begin{Bmatrix} 0 & \rightarrow & \text{d}\\ 1 & \rightarrow & \text{u}\\ 205 & \rightarrow & \text{d}\\ \end{Bmatrix}\]

We will generally assume that a finite sequence maps the first $|S^{-1}(\Sigma)|$ natural numbers to $\Sigma$. But why can we close the gaps without losing the original order? Every finite “gappy” sequence has an order-preserving reindexing with domain $\{0,\ldots,|S^{-1}(\Sigma)|-1\}$.

To construct this reindexing, start with a finite sequence $S$ and list its domain in increasing order:

\[S^{-1}(\Sigma)=\{n_0<n_1<\cdots<n_{k-1}\}.\]

Define the gap-closing map $r:\{0,\ldots,k-1\}\to S^{-1}(\Sigma)$ by $r(i)=n_i$, and define $S'=S\circ r$. The map $r$ is injective because two positions in the increasing list cannot name the same natural number. It is surjective because every member of the domain occurs somewhere in that list. Thus, $r$ is a bijection. And for every $i<k$, $S'(i)=S(n_i)$, so $S'$ retains the values of $S$ in their original order.

For the gappy sequence above, $r(0)=0$, $r(1)=1$, and $r(2)=205$. The reindexed sequence is thus $\langle\text{d},\text{u},\text{d}\rangle$. This construction justifies the no-gaps convention for finite sequences. But there are cases—one discussed below—where we don’t necessarily want our sequences to start at 0.

Functions can be represented as sets of pairs, and thus sequences can be too.

\[S = \{\langle 0, \text{d} \rangle, \langle 1, \text{u} \rangle, \langle 2, \text{d} \rangle\} \subseteq \mathbb{N}\times \Sigma\]

We often denote the $i^{th}$ element of a sequence using a subscript rather than function notation.

\[s_i \equiv S(i)\]

This notation should remind you of the notation we use for indexing tuples. This is no coincidence. So how do we turn a finite sequence $S$ into a $|S^{-1}(\Sigma)|$-tuple $\mathbf{s}$ without losing any information? We map finite sequences to elements of $\Sigma^{|S^{-1}(\Sigma)|}$.

For a gapless sequence with domain $\{0,\ldots,k-1\}$, define

\[ \operatorname{func2tuple}(S,i,k)= \begin{cases} \langle\rangle & \text{if }i=k,\\ \langle S(i)\rangle & \text{if }i=k-1,\\ \langle S(i),\operatorname{func2tuple}(S,i+1,k)\rangle & \text{if }i<k-1. \end{cases} \]

The conversion is $\operatorname{func2tuple}(S,0,k)$. In particular, when $k=0$, it returns the empty tuple without attempting to evaluate the undefined value $S(0)$.

And as we saw, we can always flatten these elements of $\Sigma^{|S^{-1}(\Sigma)|}$ to $|S^{-1}(\Sigma)|$-tuples. Because of this, we (often) implement sequences in Python using lists and tuples, though we can implement them using dicts as well.

The information-preservation claim has two directions. First, fix an arbitrary gapless sequence $S$ with domain $\{0,\ldots,k-1\}$. The tuple $\langle S(0),\ldots,S(k-1)\rangle$ records the value of $S$ at every point in its domain, so two distinct sequences cannot produce the same tuple. This also covers $k=0$: there is one empty function and it maps to the one empty tuple. Second, fix an arbitrary tuple $\mathbf{s}=\langle s_0,\ldots,s_{k-1}\rangle\in\Sigma^k$. Define $S_{\mathbf{s}}(i)=s_i$ for each $i<k$. This is a sequence with the required domain, and converting it back to a tuple returns $\mathbf{s}$. Thus, the conversion is both injective and surjective. Finite gapless sequences on $\Sigma$ and tuples in $\Sigma^k$ are two representations of the same ordered information.

x = ["d", "u", "d"]
y = ("d", "u", "d")
z = {0: "d",
     1: "u",
     2: "d"}

--- title: Sequences jupyter: python3 --- A *sequence* $S$ is a partial function from the natural numbers $\mathbb{N}$ to a set $\Sigma$. $$\mathbb{N} = \{0, 1, 2, 3, \ldots\}$$ $$\Sigma = \{\text{e, i, o, u, æ, ɑ, ɔ, ə, ɛ, ɪ, ʊ, ɹ, d, t}\}$$ $$S = \begin{Bmatrix} 0 & \rightarrow & \text{d}\\ 1 & \rightarrow & \text{u}\\ 2 & \rightarrow & \text{d}\\ \end{Bmatrix}$$ This definition admits of sequences with gaps in the natural numbers. $$\begin{Bmatrix} 0 & \rightarrow & \text{d}\\ 1 & \rightarrow & \text{u}\\ 205 & \rightarrow & \text{d}\\ \end{Bmatrix}$$ We will generally assume that a finite sequence maps the first $|S^{-1}(\Sigma)|$ natural numbers to $\Sigma$. But why can we close the gaps without losing the original order? Every finite "gappy" sequence has an order-preserving reindexing with domain $\{0,\ldots,|S^{-1}(\Sigma)|-1\}$. To construct this reindexing, start with a finite sequence $S$ and list its domain in increasing order: $$S^{-1}(\Sigma)=\{n_0<n_1<\cdots<n_{k-1}\}.$$ Define the **gap-closing map** $r:\{0,\ldots,k-1\}\to S^{-1}(\Sigma)$ by $r(i)=n_i$, and define $S'=S\circ r$. The map $r$ is injective because two positions in the increasing list cannot name the same natural number. It is surjective because every member of the domain occurs somewhere in that list. Thus, $r$ is a bijection. And for every $i<k$, $S'(i)=S(n_i)$, so $S'$ retains the values of $S$ in their original order. For the gappy sequence above, $r(0)=0$, $r(1)=1$, and $r(2)=205$. The reindexed sequence is thus $\langle\text{d},\text{u},\text{d}\rangle$. This construction justifies the no-gaps convention for finite sequences. But there are cases—one discussed below—where we don't necessarily want our sequences to start at 0. Functions can be represented as sets of pairs, and thus sequences can be too. $$S = \{\langle 0, \text{d} \rangle, \langle 1, \text{u} \rangle, \langle 2, \text{d} \rangle\} \subseteq \mathbb{N}\times \Sigma$$ We often denote the $i^{th}$ element of a sequence using a subscript rather than function notation. $$s_i \equiv S(i)$$ This notation should remind you of the notation we use for indexing tuples. This is no coincidence. So how do we turn a finite sequence $S$ into a $|S^{-1}(\Sigma)|$-tuple $\mathbf{s}$ without losing any information? We map finite sequences to elements of $\Sigma^{|S^{-1}(\Sigma)|}$. For a gapless sequence with domain $\{0,\ldots,k-1\}$, define $$ \operatorname{func2tuple}(S,i,k)= \begin{cases} \langle\rangle & \text{if }i=k,\\ \langle S(i)\rangle & \text{if }i=k-1,\\ \langle S(i),\operatorname{func2tuple}(S,i+1,k)\rangle & \text{if }i<k-1. \end{cases} $$ The conversion is $\operatorname{func2tuple}(S,0,k)$. In particular, when $k=0$, it returns the empty tuple without attempting to evaluate the undefined value $S(0)$. And as we saw, we can always flatten these elements of $\Sigma^{|S^{-1}(\Sigma)|}$ to $|S^{-1}(\Sigma)|$-tuples. Because of this, we (often) implement sequences in Python using `list`s and `tuple`s, though we can implement them using `dict`s as well. The information-preservation claim has two directions. First, fix an arbitrary gapless sequence $S$ with domain $\{0,\ldots,k-1\}$. The tuple $\langle S(0),\ldots,S(k-1)\rangle$ records the value of $S$ at every point in its domain, so two distinct sequences cannot produce the same tuple. This also covers $k=0$: there is one empty function and it maps to the one empty tuple. Second, fix an arbitrary tuple $\mathbf{s}=\langle s_0,\ldots,s_{k-1}\rangle\in\Sigma^k$. Define $S_{\mathbf{s}}(i)=s_i$ for each $i<k$. This is a sequence with the required domain, and converting it back to a tuple returns $\mathbf{s}$. Thus, the conversion is both injective and surjective. Finite gapless sequences on $\Sigma$ and tuples in $\Sigma^k$ are two representations of the same ordered information. ```{python} x = ["d", "u", "d"] y = ("d", "u", "d") z = {0: "d", 1: "u", 2: "d"} ```