Calculus

Set Theory

Set Theory Logo

Cartesian Product of Sets

Ordered Pairs

In sets, the order of elements is not important. For example, the sets {2, 3} and {3, 2} are equal to each other. However, there are many instances in mathematics where the order of elements is essential. So, for example, the pairs of numbers with coordinates (2, 3) and (3, 2) represent different points on the plane. This leads to the concept of ordered pairs.

An ordered pair is defined as a set of two objects together with an order associated with them. Ordered pairs are usually written in parentheses (as opposed to curly braces, which are used for writing sets).

In the ordered pair \(\left( {a,b} \right),\) the element \(a\) is called the first entry or first component, and \(b\) is called the second entry or second component of the pair.

Two ordered pairs \(\left( {a,b} \right)\) and \(\left( {c,d} \right)\) are equal if and only if \(a = c\) and \(b = d.\) In general,

\[\left( {a,b} \right) \ne \left( {b,a} \right).\]

The equality \(\left( {a,b} \right) = \left( {b,a} \right)\) is possible only if \(a = b.\)

Tuples

The concept of ordered pair can be extended to more than two elements. An ordered \(n-\)tuple is a set of \(n\) objects together with an order associated with them. Tuples are usually denoted by \(\left( {{a_1},{a_2}, \ldots, {a_n}} \right).\) The element \({a_i}\) \(\left({i = 1,2, \ldots, n}\right)\) is called the \(i\text{th}\) entry or component, and \(n\) is called the length of the tuple.

Similarly to ordered pairs, the order in which elements appear in a tuple is important. Two tuples of the same length \(\left( {{a_1},{a_2}, \ldots, {a_n}} \right)\) and \(\left( {{b_1},{b_2}, \ldots, {b_n}} \right)\) are said to be equal if and only if \({a_i} = {b_i}\) for all \({i = 1,2, \ldots, n}.\) So the following tuples are not equal to each other:

\[\left( {1,2,3,4,5} \right) \ne \left( {3,2,1,5,4} \right).\]

Unlike sets, tuples may contain a certain element more than once:

\[\left( {1,2,3,2,1,1,1} \right).\]

Ordered pairs are sometimes referred as \(2-\)tuples.

Cartesian Product of Two Sets

Suppose that \(A\) and \(B\) are non-empty sets. The Cartesian product of two sets \(A\) and \(B,\) denoted \(A \times B,\) is the set of all possible ordered pairs \(\left( {a,b} \right),\) where \(a \in A\) and \(b \in B:\)

\[A \times B = \left\{ {\left( {a,b} \right) \mid a \in A \text{ and } b \in B} \right\}.\]

The Cartesian product is also known as the cross product.

The figure below shows the Cartesian product of the sets \(A = \left\{ {1,2,3} \right\}\) and \(B = \left\{ {x,y} \right\}.\)

Cartesian product of two sets A={1,2,3} and B={x,y}.
Figure 1.

It consists of \(6\) ordered pairs:

\[A \times B = \left\{ {\left( {1,x} \right),\left( {2,x} \right),\left( {3,x} \right),\left( {1,y} \right),\left( {2,y} \right),\left( {3,y} \right)} \right\}.\]

Similarly, we can find the Cartesian product \(B \times A:\)

\[B \times A = \left\{ {\left( {x,1} \right),\left( {y,1} \right),\left( {x,2} \right),\left( {y,2} \right),\left( {x,3} \right),\left( {y,3} \right)} \right\}.\]

As you can see from this example, the Cartesian products \(A \times B\) and \(B \times A\) do not contain exactly the same ordered pairs. So, in general, \(A \times B \ne B \times A.\)

If \(A = B,\) then \(A \times B\) is called the Cartesian square of the set \(A\) and is denoted by \(A^2:\)

\[{A^2} = \left\{ {\left( {a,b} \right) \mid a \in A \text{ and } b \in A} \right\}.\]

Cartesian Product of Several Sets

Cartesian products may also be defined on more than two sets.

Let \({A_1}, \ldots ,{A_n}\) be \(n\) non-empty sets. The Cartesian product \({A_1} \times \ldots \times {A_n}\) is defined as the set of all possible ordered \(n-\)tuples \(\left({{a_1}, \ldots ,{a_n}}\right),\) where \({a_i} \in {A_i}\) and \({i = 1,\ldots, n}.\)

If \({A_1} = \ldots = {A_n} = A,\) then \({A_1} \times \ldots \times {A_n}\) is called the \(n\text{th}\) Cartesian power of the set \(A\) and is denoted by \({A^n}.\)

Some Properties of Cartesian Product

  1. The Cartesian product is non-commutative:
    \[A \times B \ne B \times A\]
  2. \(A \times B = B \times A,\) if only \(A = B.\)
  3. \({A \times B = \varnothing},\) if either \(A = \varnothing\) or \(B = \varnothing.\)
  4. The Cartesian product is non-associative:
    \[\left( {A \times B} \right) \times C \ne A \times \left( {B \times C} \right)\]
  5. Distributive property over set intersection:
    \[A \times \left( {B \cap C} \right) = \left( {A \times B} \right) \cap \left( {A \times C} \right)\]
  6. Distributive property over set union:
    \[A \times \left( {B \cup C} \right) = \left( {A \times B} \right) \cup \left( {A \times C} \right)\]
  7. Distributive property over set difference:
    \[A \times \left( {B \backslash C} \right) = \left( {A \times B} \right) \backslash \left( {A \times C} \right)\]
  8. If \(A \subseteq B,\) then \(A \times C \subseteq B \times C\) for any set \(C.\)

Cardinality of Cartesian Product

The сardinality of a Cartesian product of two sets is equal to the product of the cardinalities of the sets:

\[\left| {A \times B} \right| = \left| {B \times A} \right| = \left| A \right| \times \left| B \right|.\]

Similarly,

\[\left| {{A_1} \times \ldots \times {A_n}} \right| = \left| {{A_1}} \right| \times \ldots \times \left| {{A_n}} \right|.\]

See solved problems on Page 2.

Page 1 Page 2