2.3. Sequences¶

A finite sequence can be represented as a list of objects, each of which are of the same set or type (see Section 2.2). For example, the sequence \(a = [a_1, a_2, \dots, a_n]\) is written as

\[a = [a_1, a_2, \dots, a_n] = [a_i]_{i \in \{1, 2, \dots, n\}} = [a_i]_{i \in \mathcal{I}_a}\]

where each \(a_i \in A\), and \(\mathcal{I}_a = \{1, 2, \dots, n\}\) is the index set whose elements are used to identify objects within the sequence \(a\).

In general, an index set does not impose an order on the sequence elements—the sequence \(a\) could thus be equivalently expressed as:

\[a = [a_1, a_2, \dots, a_n] = [a_n, \dots, a_2, a_1]\]

or any of the \(n!\) orderings possible. The index set simply provides a mapping from an index to the data object itself.

The length of the sequence \(a\) above is denoted by \(|a|\), and it equals the cardinality of the index set: \(|a| = |\mathcal{I}_a| = n\). In this document, we will have need of a list of length 0, or the empty list, which is a sequence whose elements are indexed by the empty set:

\[[\ ] = [a_i]_{i \in \emptyset} \ .\]