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

**el_llavero** · Jun13-09, 12:54 PM

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

I'm assuming that by stating ({x1 , x2} $LaTeX Code: \\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

**CompuChip** · Jun14-09, 03:50 AM

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
$LaTeX Code: 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 S₂(A)).

**el_llavero** · Jun14-09, 09:59 AM

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?

**CRGreathouse** · Jun14-09, 12:29 PM

Originally Posted by el_llavero

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?

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.

**el_llavero** · Jun14-09, 02:43 PM

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}

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

**CompuChip** · Jun15-09, 04:22 AM

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
$LaTeX Code: S(A) = \\{ (x_1, x_2) \\mid x_1, x_2 \\in A \\text{ and } x_1 < x_2 \\}$
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}.