Types of collections
Mathematics has several kinds of “a bunch of things,” which differ in whether order and repetition matter. A set ignores order and repetition. A multiset keeps repetition. A sequence keeps order and repetition. “Collection” is informal, and “group” is a technical term for a set with an operation.
Definitions
A collection is a group of objects considered together.
Collection is an informal word, used as a synonym for “set,” to produced for variety (e.g., “a collection of subsets”) or for classes that are too large to be sets (“the collection of all sets”).
Examples
-
$\setdef{1, 2, 2}$
$\setdef{1, 2, 2}$ is a collection, and as a set it equals $\setdef{1, 2}$, with two elements.
-
The class of all sets
The class of all sets is a collection.
A set is a collection of different objects, called its elements. Order and repetition do not matter: $\setdef{1, 2}$, $\setdef{2, 1}$, and $\setdef{1, 1, 2}$ are the same set.
A set is an object of a set theory such as ZFC. By the axiom of extensionality, a set is determined entirely by its elements.
Examples
Non-examples
-
The roots of $(x - 1)^2$ counted with multiplicity
The roots of $(x - 1)^2$ counted with multiplicity does not form a set, which cannot count an element twice.
- $(1, 2, 2)$
-
The class of all sets
The class of all sets is not a set, because treating it as one leads to Russell’s paradox.
Properties
- Not every collection is a set: the collection of all sets is not a set (Russell’s paradox).
A sequence is a list of things in a particular order.
A sequence is an ordered list of terms $a_1, a_2, a_3, \dots$ Both order and repetition matter: $(1, 2)$, $(2, 1)$, and $(1, 1, 2)$ are different sequences.
A sequence is a function from $\nats$ (an infinite sequence) or from $\setdef{1, \dots, n}$ (a finite sequence, or $n$-tuple) to a set.
Examples
- The sequence $1, 2, 3, \dots$
-
$(1, 2, 2)$
$(1, 2, 2)$ is a sequence of length three, and so an indexed family, which is different from $(2, 1, 2)$ and from $(1, 2)$.
Non-examples
-
$\setdef{1, 2, 3}$
A set has no order. A sequence lists its terms in order.
Consider a set, in which each element appears only once. A multiset is like a set, except that an element can appear more than once.
A multiset is a collection in which order does not matter but repetition does. Formally, a function from a set to the positive integers that gives the multiplicity of each element.
Examples
-
$\setdef{1, 2, 2}$
As a multiset, it differs from $\setdef{1, 2}$.
-
The roots of $(x - 1)^2$ counted with multiplicity
The roots of $(x - 1)^2$ counted with multiplicity form a multiset, in which the root $1$ appears twice.
Non-examples
Consider a set $G$ with a binary operation $\ast$. The set $G$ is a group if
- $\ast$ is associative: $(a \ast b) \ast c = a \ast (b \ast c)$ for all $a, b, c \in G$,
- $G$ has an identity element $e$ such that $e \ast g = g \ast e = g$ for all $g \in G$, and
- every element $g \in G$ has an inverse $g^{-1}$ such that $g \ast g^{-1} = g^{-1} \ast g = e$.
Examples
-
$\mathbb{Z}$ with addition
Adding $0$ changes nothing, and adding $-3$ undoes adding $3$.
Non-examples
-
$\nats$ with addition
$\nats$ with addition is not a group, because no positive integer has an additive inverse in $\nats$.
Properties
- The identity element of a group is unique, and so is the inverse of each element.
Consider an index set $I$ and a set of values. An indexed family is a function $i \mapsto x_i$ from $I$ to the set, written \((x_i)_{i \in I}\). Unlike a set, an indexed family can repeat elements. A sequence is an indexed family with $I = \nats$.
Examples
Examples
| Example | collection | set | sequence | multiset | group | indexed family | Why |
|---|---|---|---|---|---|---|---|
| $\setdef{1, 2, 2}$ | ✓ | ✓ | – | ✓ | – | – | |
| $(1, 2, 2)$ | – | ✗ | ✓ | ✗ | – | ✓ | |
| The roots of $(x - 1)^2$ counted with multiplicity | – | ✗ | – | ✓ | – | – | |
| $\mathbb{Z}$ with addition | – | – | – | – | ✓ | – | |
| $\nats$ with addition | – | – | – | – | ✗ | – | |
| The class of all sets | ✓ | ✗ | – | – | – | – |