Sets and sequences

Sets and multisets

1. In a set, each element occurs at most once, that is, no duplications of elements within a set.
2. In contrast, in a multiset, an element may occur more than once. The multiplicity of an element in a multiset is the number of its occurrences in that multiset.

Remark: In computer science, as opposed to math, sets and multisets are usually dynamic, that is, elements may be inserted and removed.

Maximal and minimal sets

Let [math]\displaystyle{ \mathcal{S} }[/math] be a set of (multi)sets.

1. A set [math]\displaystyle{ S\in\mathcal{S} }[/math] is inclusion-minimal (resp., inclusion-maximal) if [math]\displaystyle{ S'\subsetneq S }[/math] (resp., [math]\displaystyle{ S'\supsetneq S }[/math]) for no [math]\displaystyle{ S'\in\mathcal{S}\setminus\{S\} }[/math].
2. A set [math]\displaystyle{ S\in\mathcal{S} }[/math] is cardinality-minimal (resp., cardinality-maximal) if [math]\displaystyle{ |S'|\lt [S[ }[/math] (resp., [math]\displaystyle{ |S'|\gt |S| }[/math]) for no [math]\displaystyle{ S'\in\mathcal{S}\setminus\{S\} }[/math].

Remark: Typically, [math]\displaystyle{ \mathcal{S} }[/math] is given as all subsets of a ground set that fulfill a certain property.

Ordered and sorted sequences

An ordered sequence (or sequence, for short) is given by

1. a number [math]\displaystyle{ n \in \N_{0} }[/math], its length,
2. some component type [math]\displaystyle{ C }[/math], and
3. a mapping [math]\displaystyle{ \pi : \{1,...,n\} \rightarrow C }[/math].

We say that [math]\displaystyle{ 1,...,n }[/math] are the positions in the sequence (a.k.a. the indexes). The element [math]\displaystyle{ \pi (i) }[/math] of sequence [math]\displaystyle{ S }[/math] at position [math]\displaystyle{ i }[/math] is denoted by [math]\displaystyle{ S[i] }[/math].

Consider a comparison [math]\displaystyle{ c }[/math] on [math]\displaystyle{ C }[/math], as introduced above. Then a sequence [math]\displaystyle{ S }[/math] of length [math]\displaystyle{ n }[/math] is sorted with respect to [math]\displaystyle{ c }[/math], if [math]\displaystyle{ S[i] \le S[i+1] }[/math] for all [math]\displaystyle{ i \in \{1,...,n-1\} }[/math].

Remarks:

1. Note that the first position is [math]\displaystyle{ 1 }[/math], not [math]\displaystyle{ 0 }[/math], as opposed to array indexes in many popular programming languages such as C, C++, and Java.
2. Like sets and multisets, sequences are dynamic.

Maps

A map is given by

1. a number [math]\displaystyle{ n \in \N_{0} }[/math], its size
2. a key type [math]\displaystyle{ \mathcal{K} }[/math] and a value type [math]\displaystyle{ \mathcal{V} }[/math],
3. a finite subset [math]\displaystyle{ K \subseteq \mathcal{K} }[/math], the map's keys, and
4. a mapping [math]\displaystyle{ K \rightarrow \mathcal{V} }[/math], which assigns a value to each key in the map.

Remark

A sequence may also be a map, namely if its component type is [math]\displaystyle{ \mathcal{K} \times \mathcal{V} }[/math] and each value of [math]\displaystyle{ \mathcal{K} }[/math] occurs at most once.

Like sets, multisets and sequences, maps are dynamic.