Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Describing all unique 2-tuples from a set using Set Notation

  1. Jun 13, 2009 #1
    Describing certain 2-tuples from a set using Set Notation

    How do you describe, using set notation, a certain set of n-tuples generated from a set satisfying the following conditions

    Condition 1: non of the components of an individual n-tuple can equal each other

    Condition 2: if (a,b) is an element of the set then (b,a) can not be an element of the set as well, I believe this is called not being symmetric

    I believe the above conditions are analogous to generating all unique n-element subsets from a set, except I need to convert to n-tuple form

    For instance, I have a set A = {S1, S2, S3, S4, DS1, DS2}, I would like to describe the set consisting of all the following 2-tuples generated from A, using set notation.
    That is, describe the set below using set notation
    S = {(S1,S2), (S1, S3), (S1, S4),(S1, DS1), (S1, DS2), (S2, S3), (S2, S4),
    (S2, DS1), (S2, DS2), (S3, S4), (S3, DS1), (S3, DS2), (S4,DS1), (S4, DS2), (DS1, DS2)}

    This is my best attempt

    S= {(x1 , x2): {x1 , x2} [tex]\subseteq[/tex] A}

    I'm assuming that by stating ({x1 , x2} [tex]\subseteq[/tex] A) that alone guarantees generation of all unique subsets which satisfy the conditions above, where the x1 , x2 of each generated subset are assigned to the x1 , x2 values of the 2-tuple
    Last edited: Jun 13, 2009
  2. jcsd
  3. Jun 14, 2009 #2


    User Avatar
    Science Advisor
    Homework Helper

    Actually, you now have both (x1, x2) and (x2, x1) which are distinct 2-tuples, because {x1, x2} and {x2, x1} are both subsets of A.
    And depending whether you want to consider {x, x} as a stupid way of writing {x}, your other condition may not be satisfied either.

    The best I can think of at the moment is to introduce a linear order < on A, and write something like
    [tex]S_n(A) = \{ (x_1, x_2, \cdots, x_n) \mid x_i \in A \text{ and } x_1 < x_2 < \cdots < x_n \}[/tex]
    (I generalized your notation, what was S is now S2(A)).
  4. Jun 14, 2009 #3
    I see how that works. However, could you enlighten me on the applicability of ordering, that is, when you can introduce ordering on a set where the elements have no numberical value.

    for instance

    A = {square, pizza, egg, dog}, and |A|= 4

    It's obvious square != pizza but does the applicability of ordering come from the fact that
    A is a countable set and/or that the elements in A are distinct and/or some other reason?
    Last edited: Jun 14, 2009
  5. Jun 14, 2009 #4


    User Avatar
    Science Advisor
    Homework Helper

    A finite set can obviously be ordered.

    The natural numbers can also be ordered: 1 < 2 < 3 < .... A set is countable if there is a one-to-one mapping into the natural numbers. You can use this mapping to make an order on any countable set.
  6. Jun 14, 2009 #5
    Thank you for your insight, I am familiar with the concepts of a set being finite and therefore being countable since there is a one-to-one mapping into the natural numbers which I've used in a proof once, I believe it's termed dove tailing, so my only exposure to this is when I have explicitly had to show it.

    Now I just need clarification on the conventions of proper set builder notation to describe these relationships and this set.

    My question now is:


    For instance in my original problem would describing set A and Set B as done below satisfy all conditions? Or do i explicity have to show the mapping from the elements in A into the natural numbers? Does describing A as a finite set as done below encompass all information to later use it in S and order it a certain way.

    A = {S1, S2, S3, S4, DS1, DS2}

    [tex]S_n(A) = \{ (x_1, x_2) \mid x_i \in A \text{ and } x_1 < x_2 \}[/tex]
  7. Jun 15, 2009 #6


    User Avatar
    Science Advisor
    Homework Helper

    I would say that making the statement more general by replacing
    Let A be {S1, S2, S3, S4, DS1, DS2}​
    in your definition by
    Let (A, <) be an ordered set​
    is an elegant way to do it.
    Then the statement a < b makes sense and you can define
    [tex]S(A) = \{ (x_1, x_2) \mid x_1, x_2 \in A \text{ and } x_1 < x_2 \}[/tex]
    without anything else. That this is always possible when A is a finite set is then a corollary: it immediately follows from the fact that there exists a bijection between any finite set with n elements and the numbers {1, 2, ..., n} which can be used to introduce an ordering. The formal proof would be something like:
    Let A be a finite set with n elements. Then there is a bijection f between A and {1, 2, ..., n}. Now introduce an order < on A by
    a < b iff f(a) < f(b) ​
    where the "<" symbol on the right denotes the familiar "less than" relation on {1, 2, ..., n}. ​
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook