Sets, multisets, families, lists, sequences

Our goal is to compare these familiar, basic structures.

All of these, except for set, are simple examples of functions.

For ready comparison, we place these structures in a table.

In the title of this post, the structures were listed starting with the simplest.

In the table, we place the simplest at the bottom of the table.

\[ \boxed { \begin{array} { l | ccl | c | c } & \text{source} && \text{target} & {\textstyle\text{repetitions}} \atop {\textstyle\text{allowed}} & \text{ordered} \\ \\ \hline \\ \text{infinite sequence} & \N & \to & S & \text{Y} & \text{Y} \\ \text{finite sequence, list, $n$-tuple} & [n] & \to & S & \text{Y} & \text{Y} \\ \text{family, indexed collection, general function} & I & \to & S & \text{Y} & \text{N} \\ \text{multiset} & S & \to & \N & \text{Y} & \text{N} \\ \text{predicate} & S & \to & \bftwo = \{\bot\lt\top\} & \text{Y} & \text{N} \\ \text{set} & & & S & \text{N} & \text{N} \\ \end{array} } \]

$S$ and $I$ are arbitrary sets.

The list structure, by that name, is used extensively in Sheldon Axler's popular text "Linear Algebra Done Right."