In mathematics, a set or more specifically a finite set is an enumeration of elements in which repetitions and order do not matter. For example, {1,2,3}, {1,2,2,3}, and {3,2,1} all define the same set, namely the set of the first three positive integers.

If we want both repetitions and order to matter, we use tuples that is to say, ordered tuples. In this case (1,2,3), (1,2,2,3), and (3,2,1) are all distinct enumerations of the first three positive integers. The first and last are ordered 3-tuples, or ordered triples, and the middle one is an ordered 4-tuple.

But what if we want an enumeration in which repetitions matter but not order? For example, consider the prime factors of 12 = 2Χ2Χ3. If we consider the set {2,2,3}, this is the same as {2,3} but obviously 12 is not 2Χ3. On the other hand if we use the ordered triple (2,2,3), we would be unnecessarily imposing an order on the way the numbers appear: (2,2,3) is distinct not only from (2,3) but also from (2,3,2) and (3,2,2) whereas we want (2,2,3), (2,3,2), and (3,2,2) to be, in a sense, the same.

As another example, consider the real solutions of the equationx^{3}(x−1)^{2}(x+1) = 0. The set {0,0,0,1,1,−1} = {0,1,−1} does not tell the whole story as there are 6 roots, not 3. And why should we use ordered 6-tuples since the order in which we wish to enumerate the roots is immaterial?

In these situations we normally use alist. When we list a string of elementsa_{1},a_{2}, ,ait is conventionally assumed that repetitions are important but not the order in which the elements appear. Thus we can list the factors of 12 as 2,2,3, which is the same as 2,3,2 and 3,2,2, but different from 2,3. Similarly the list of the real solutions of the equation above can be 0,0,0,1,1,−1; it is different from the list 0,1,−1 and yet it doesnt matter in what order we list the roots._{n}

Unfortunately the term list does not have a formal mathematical definition. It is merely a convention that we use time after time without giving it any rigorous thought. I think we can easily rectify this.

Suppose we have a setS= {s_{1}, ,s} of_{k}kelements (all distinct) and we wish to make a list ofnelements (not necessarily all distinct) from it. Define a relation ~ on the class of all orderedn-tuples of elements ofSby

iff there is a permutationπof the integers {1, ,n} such thata=_{i}b_{π(i)}for each 1 ≤i≤n.

Then ~ is an equivalence relation. This is easily proved using the identity permutation for reflexivity, inverse permutation for symmetry, and composition of permutations for transitivity.

We define the listDefinition:a_{1}, ,aof elements from_{n}Sto be the equivalence class under ~ containing the orderedn-tuple (a_{1}, ,a)._{n}

For instance, the set of prime factors of 12 is {2,3} while the list of prime factors 2,2,3 is the equivalence class {(2,2,3),(2,3,2),(3,2,2)} under ~. (The other equivalence classes are {(2,2,2)}, {(3,3,3)}, and {(2,3,3),(3,2,3),(3,3,2)}, which are the lists 2,2,2, 3,3,3, and 2,3,3 respectively.)

And there we have it. Lists are more versatile than sets and less cumbersome than ordered tuples and we can now use them in a proper mathematical way with a proper mathematical definition.