# Thread: Sets, ordered tuples … and lists

1. ## Sets, ordered tuples … and lists

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 equation x3(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 a list. When we list a string of elements a1,a2,…,an it 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 doesn’t matter in what order we list the roots.

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 set S = {s1,…,sk} of k elements (all distinct) and we wish to make a list of n elements (not necessarily all distinct) from it. Define a relation ~ on the class of all ordered n-tuples of elements of S by

$\left(a_1,\ldots,a_n\right)\ \sim\ \left(b_1,\ldots,b_n\right)$

iff there is a permutation π of the integers {1,…,n} such that ai = bπ(i) for each 1 ≤ in.

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.

Definition: We define the list a1,…,an of elements from S to be the equivalence class under ~ containing the ordered n-tuple (a1,…,an).

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.

2. ## Re: Sets, ordered tuples … and lists

There's no point in attempting to popularise a formal definition unless: a) there is some confusion in the informal usage; or b) you have useful results that stem from the formal defi ition.

In other (somewhat direct) words, my question is: why bother?

3. ## Re: Sets, ordered tuples … and lists

Originally Posted by Archie
In other (somewhat direct) words, my question is: why bother?
That was what they said to Hamilton when he came up with quaternions.

4. ## Re: Sets, ordered tuples … and lists

I don't know the story, and I've never studied quaternions to know what they are (something is telling me we are talking number systems), but I'm prepared to bet that he didn't just define them. He probably came up with them to answer a theoretical question and must have gone on to get some results about them, sufficient to show that they have some interest in their own right. The "why bother?" would have been from those who didn't see how they might be useful in existing mathematics or physics. But that's a very different sort of "why bother".

Here we have a definition not seemingly motivated by any need at all, theoretical or otherwise, and it comes with no results whatever.

5. ## Re: Sets, ordered tuples … and lists

There is already a term in mathematics for such set-like objects (where order does not matter but multiplicity of elements does): multisets.

6. ## Re: Sets, ordered tuples … and lists

Originally Posted by Archie
There's no point in attempting to popularise a formal definition unless: a) there is some confusion in the informal usage; or b) you have useful results that stem from the formal defi ition.

In other (somewhat direct) words, my question is: why bother?
In the video below, the guy is actually trying to develop some multiset theory (including some arithmetic with multisets); however he does not formally define what a multiset is. This is where it would actually pay to bother.