This page does not represent the most current semester of this course; it is present merely as an archive.
The following includes all of the text from MCS 4.2 with some clarifications and some additional definitions that MCS assumes without defining.
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 an incorrect way of writing a set, and if taken as a set is most likely 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; others use \epsilon, \varepsilon, or ().
Length two sequences are called pairs1. Length one sequences are commonly treated as being identical to their single term, with no special action needed to convert between a length-one sequence and a non-sequence value.
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. 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:
\mathbb N \times \{a,b\} = \{(0,a), (0,b), (1,a), (1,b), (2,a), (2,b), \dots\}
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:
\{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)\}
The special notation S^{*} means the set \big\{x \;\big\|\; \exists n \in \mathbb N \;.\; x \in S^n \big\}. The superscript asterisk is called a Kleene star.
\{0,1\}^{*} = \{\lambda, (0), (1), (0,0), (0,1), (1,0), (1,1), (0,0,0), (0,0,1), \dots\}
Sequences of sequences are sometimes flattened and sometimes preserved, generally with no explicit indication which will be done. Thus ((1,2),3) might be considered identical to (1,2,3) in some contexts and distinct from it in other contexts. As a rule of thumb (with many exceptions in practice), if (a) the terms in a sequence are all of the same type and (b) the exact position of a term is less important than the overall sequence, then they will be implicitly flattened.
A symbol is a mathematical entity whose only meaning is its identity. Symbols are often written in a fixed-width font or as code; for example, 1 is a number and 1 is the symbol used to represent that number. A sequence of symbols is called a string and is often written without the parentheses and commas, sometimes between quotes and other times not. For example, the following all refer to the same string: (1, 1, 0), 110,
.110
Some texts call them ordered pairs.↩︎