4.2: Sequences

Last updated
Save as PDF

Page ID: 48312

Eric Lehman, F. Thomson Leighton, & Alberty R. Meyer
Google and Massachusetts Institute of Technology via MIT OpenCourseWare

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Sets provide one way to group a collection of objects. Another way is in a sequence, which is a list of objects called terms or components. Short sequences are commonly described by listing the elements between parentheses; for example, (\(a, b, c\)) is a sequence with three terms.

While both sets and sequences perform a gathering role, there are several differences.

The elements of a set are required to be distinct, but terms in a sequence can be the same. Thus, \((a, b, a)\) is a valid sequence of length three, but \(\{a, b, a\}\) is a set with two elements, not three.
The terms in a sequence have a specified order, but the elements of a set do not. For example, \((a, b, c)\)and \((a, c, b)\) are different sequences, but \(\{a, b, c\}\) and \(\{a, c, b\}\) are the same set.
Texts differ on notation for the empty sequence; we use \(\lambda\) for the empty sequence.

The product operation is one link between sets and sequences. A Cartesian product of sets, \(S_1 \times S_2 \times \cdots \times S_n\), is a new set consisting of all sequences where the first component is drawn from \(S_1\), the second from \(S_2\), and so forth. Length two sequences are called pairs.³ For example, \(\mathbb{N} \times \{a, b\}\) is the set of all pairs whose first element is a nonnegative integer and whose second element is an \(a\) or a \(b\):

\[\nonumber \mathbb{N} \times \{a, b\} = \{(0, a), (0, b), (1, a), (1, b), (2, a), (2, b), \ldots\}\]

A product of \(n\) copies of a set \(S\) is denoted \(S^n\). For example, \(\{0, 1\}^3\) is the set of all 3-bit sequences:

\[\nonumber \{0, 1\}^3 = \{(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)\}\]

³Some texts call them ordered pairs.