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

1. Jun 13, 2009

### el_llavero

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} $$\subseteq$$ A}

I'm assuming that by stating ({x1 , x2} $$\subseteq$$ 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. Jun 14, 2009

### CompuChip

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
$$S_n(A) = \{ (x_1, x_2, \cdots, x_n) \mid x_i \in A \text{ and } x_1 < x_2 < \cdots < x_n \}$$
(I generalized your notation, what was S is now S2(A)).

3. Jun 14, 2009

### el_llavero

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
4. Jun 14, 2009

### CRGreathouse

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.

5. Jun 14, 2009

### el_llavero

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:

WHAT IS IMPLIED AND WHAT DO I HAVE TO ACTUALLY STATE?

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}

$$S_n(A) = \{ (x_1, x_2) \mid x_i \in A \text{ and } x_1 < x_2 \}$$

6. Jun 15, 2009

### CompuChip

I would say that making the statement more general by replacing
Let A be {S1, S2, S3, S4, DS1, DS2}​
$$S(A) = \{ (x_1, x_2) \mid x_1, x_2 \in A \text{ and } x_1 < x_2 \}$$