Results 1 to 6 of 6
Like Tree2Thanks
  • 1 Post By Archie
  • 1 Post By GLaw

Thread: Sets, ordered tuples … and lists

  1. #1
    Member GLaw's Avatar
    Joined
    Jul 2015
    From
    Ilford
    Posts
    217
    Thanks
    113

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Dec 2013
    From
    Colombia
    Posts
    1,821
    Thanks
    592

    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?
    Thanks from Plato
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member GLaw's Avatar
    Joined
    Jul 2015
    From
    Ilford
    Posts
    217
    Thanks
    113

    Re: Sets, ordered tuples … and lists

    Quote Originally Posted by Archie View Post
    In other (somewhat direct) words, my question is: why bother?
    That was what they said to Hamilton when he came up with quaternions.
    Thanks from Olinguito
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Dec 2013
    From
    Colombia
    Posts
    1,821
    Thanks
    592

    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie Olinguito's Avatar
    Joined
    Aug 2016
    From
    Earth
    Posts
    8

    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie Olinguito's Avatar
    Joined
    Aug 2016
    From
    Earth
    Posts
    8

    Re: Sets, ordered tuples … and lists

    Quote Originally Posted by Archie View Post
    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.

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Sets of ordered pairs
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Sep 24th 2012, 01:08 PM
  2. Well-ordered sets.
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: Mar 21st 2011, 04:46 PM
  3. Immediate successors in Well-ordered sets
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Mar 9th 2010, 05:57 AM
  4. Tuples defined as sets
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: Feb 14th 2010, 04:27 AM
  5. Counting ordered k-tuples of subsets...
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 1st 2008, 08:50 PM

Search Tags


/mathhelpforum @mathhelpforum