Products of Sets

 

We often need to represent information in the form of tuples, in which the elements in each tuple come from known sets. If A and B are sets, then the product of A and B is the set of all 2-tuples with first components from A and second components from B. The product is denoted by A×B. So we can write the definition as follows:

 

A×B = {{a, b} | aA and b  B}.

 

For example, if A = {x, y} and B = {0, 1}, then we have

 

A × B = {(x, 0), (x, l), (y,0), (y, 1)}.

 

The product is sometimes called the cross product or the Cartesian product - after the mathematician Rene Descartes (1596- 1650), who introduced the idea of graphing ordered pairs. The product of two sets is easily extended to any number of sets A1, ..., An by writing

 

A1× A1×…×An = {(x1, …, xn) | xi  Ai}.

 

If all the sets A, in a product are the same set A, then we use the abbreviated notation

 

An = A×. . .×A.

 

With this notation we have the following definitions for the sets A1 and A0:

 

A1 = {(a) | a  A} and A0 = {( )}.

 

So we must conclude that A1 ≠ A and A0 ≠ .

EXAMPLE 3. Let A = {a, b, c}. Then we have the following products:

A0 = {( )},

A1 = { (a), (b), (c)},

A2 = { (a, a), (a, b), {a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)},

A3 is bigger yet, with 27 3-tuples.