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 \(\left\{ {2,3} \right\}\) and \(\left\{ {3,2} \right\}\) 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 \(\left({2,3}\right)\) and \(\left({3,2}\right)\) 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 \text{ = }}\kern0pt{\left\{ {\left( {1,x} \right),\left( {2,x} \right),\left( {3,x} \right),}\right.}\kern0pt{\left.{\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 \text{ = }}\kern0pt{\left\{ {\left( {x,1} \right),\left( {y,1} \right),\left( {x,2} \right),}\right.}\kern0pt{\left.{\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. \(\require{AMSsymbols}{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 cardinality or cardinal number of a set is defined as the number of elements of the set. The cardinality of a Cartesian product of two sets is equal to the product of the cardinalities of the sets:

\[{n\left( {A \times B} \right) }={ n\left( {B \times A} \right) }={ n\left( A \right) \times n\left( B \right).}\]

Similarly

\[{n\left( {{A_1} \times \ldots \times {A_n}} \right) }={ n\left( {{A_1}} \right) \times \ldots \times n\left( {{A_n}} \right).}\]


Solved Problems

Click or tap a problem to see the solution.

Example 1

Given \(A = \{1,2,5\}\) and \(B = \{1,2\}.\) Find the following sets:
  1. \({A \times B}\)
  2. \({B \times A}\)
  3. \({A^2}\)
  4. \({B^2}\)

Example 2

Given \(A = \{a,b,c\}\) and \(B = \{b,c\}.\) Find the following sets:
  1. \(\left( {A \times B} \right) \cap \left( {B \times A} \right)\)
  2. \(\left( {A \times B} \right) \cup \left( {B \times A} \right)\)

Example 3

Suppose \(A = \{x,y\},\) \(B = \{1,2\}\) and \(C = \{2,3\}.\) Determine the sets:
  1. \(A \times \left( {B \cup C} \right)\)
  2. \(\left( {A \times B} \right) \cup \left( {A \times C} \right)\)

Example 4

Suppose \(A = \{a,b\},\) \(B = \{4,6\}\) and \(C = \{5,6\}.\) Determine the sets:
  1. \(A \times \left( {B \cap C} \right)\)
  2. \(\left( {A \times B} \right) \cap \left( {A \times C} \right)\)

Example 5

Find the Cartesian product \(A \times \mathcal{P}\left( A \right)\) if \(A = \left\{ {0,1} \right\}.\)

Example 6

Find the Cartesian product \(\left\{ {1,2,3} \right\} \times \mathcal{P}\left( {\left\{ a \right\}} \right).\)

Example 7

Let \(A = \left\{ {{a_1}, \ldots ,{a_n}} \right\}.\) Compute the cardinality of the set \(\mathcal{P}\left( {{A^m}} \right).\)

Example 8

Let \(X = \left\{ {x,y} \right\}.\) Compute the cardinality of the set \(\mathcal{P}\left( {\mathcal{P}\left( X \right)} \right) \times \mathcal{P}\left( X \right).\)

Example 1.

Given \(A = \{1,2,5\}\) and \(B = \{1,2\}.\) Find the following sets:
  1. \({A \times B}\)
  2. \({B \times A}\)
  3. \({A^2}\)
  4. \({B^2}\)

Solution.

  1. By definition, the Cartesian product \({A \times B}\) contains all possible ordered pairs \(\left({a,b}\right)\) such that \(a \in A\) and \(b \in B.\) Therefore, we can write
  2. \[{A \times B }={ \left\{ {1,2,5} \right\} \times \left\{ {1,2} \right\} }={ \left\{ {\left( {1,1} \right),\left( {1,2} \right),\left( {2,1} \right),}\right.}\kern0pt{\left.{\left( {2,2} \right),\left( {5,1} \right),\left( {5,2} \right)} \right\}.}\]
  3. Similarly we find the Cartesian product \({B \times A}:\)
  4. \[{B \times A }={ \left\{ {1,2} \right\} \times \left\{ {1,2,5} \right\} }={ \left\{ {\left( {1,1} \right),\left( {1,2} \right),\left( {1,5} \right),}\right.}\kern0pt{\left.{\left( {2,1} \right),\left( {2,2} \right),\left( {2,5} \right)} \right\}.}\]
  5. The Cartesian square \(A^2\) is defined as \({A \times A}.\) So, we have
  6. \[{{A^2} = A \times A }={ \left\{ {1,2,5} \right\} \times \left\{ {1,2,5} \right\} }={ \left\{ {\left( {1,1} \right),\left( {1,2} \right),\left( {1,5} \right),}\right.}\kern0pt{\left.{\left( {2,1} \right),\left( {2,2} \right),\left( {2,5} \right),}\right.}\kern0pt{\left.{\left( {5,1} \right),\left( {5,2} \right),\left( {5,5} \right)} \right\}.}\]
  7. The Cartesian square \(B^2\) is given by
  8. \[{{B^2} = B \times B }={ \left\{ {1,2} \right\} \times \left\{ {1,2} \right\} }={ \left\{ {\left( {1,1} \right),\left( {1,2} \right),}\right.}\kern0pt{\left.{\left( {2,1} \right),\left( {2,2} \right)} \right\}.}\]

Example 2.

Given \(A = \{a,b,c\}\) and \(B = \{b,c\}.\) Find the following sets:
  1. \(\left( {A \times B} \right) \cap \left( {B \times A} \right)\)
  2. \(\left( {A \times B} \right) \cup \left( {B \times A} \right)\)

Solution.

  1. We calculate the Cartesian products \({A \times B}\) and \({B \times A}\) and then determine their intersection:
  2. \[{A \times B }={ \left\{ {a,b,c} \right\} \times \left\{ {b,c} \right\} }={ \left\{ {\left( {a,b} \right),\left( {a,c} \right),\left( {b,b} \right),}\right.}\kern0pt{\left.{\left( {b,c} \right),\left( {c,b} \right),\left( {c,c} \right)} \right\}}\] \[{B \times A }={ \left\{ {b,c} \right\} \times \left\{ {a,b,c} \right\} }={ \left\{ {\left( {b,a} \right),\left( {b,b} \right),\left( {b,c} \right),}\right.}\kern0pt{\left.{\left( {c,a} \right),\left( {c,b} \right),\left( {c,c} \right)} \right\}}\] \[{\left( {A \times B} \right) \cap \left( {B \times A} \right) }={ \left\{ {\left( {b,b} \right),\left( {b,c} \right),}\right.}\kern0pt{\left.{\left( {c,b} \right),\left( {c,c} \right)} \right\}.}\]
  3. The union of the Cartesian products \({A \times B}\) and \({B \times A}\) is given by:
  4. \[{\left( {A \times B} \right) \cup \left( {B \times A} \right) }={ \left\{ {\left( {a,b} \right),\left( {b,a} \right),\left( {a,c} \right),}\right.}\kern0pt{\left.{\left( {c,a} \right),\left( {b,b} \right),\left( {b,c} \right),}\right.}\kern0pt{\left.{\left( {c,b} \right),\left( {c,c} \right)} \right\}.}\]

Example 3.

Suppose \(A = \{x,y\},\) \(B = \{1,2\}\) and \(C = \{2,3\}.\) Determine the sets:
  1. \(A \times \left( {B \cup C} \right)\)
  2. \(\left( {A \times B} \right) \cup \left( {A \times C} \right)\)

Solution.

  1. First we find the union of the sets \(B\) and \(C:\) \[{B \cup C }={ \left\{ {1,2} \right\} \cup \left\{ {2,3} \right\} }={ \left\{ {1,2,3} \right\}.}\] Then the Cartesian product of \(A\) and \(B \cup C\) is given by \[{A \times \left( {B \cup C} \right) }={ \left\{ {x,y} \right\} \times \left\{ {1,2,3} \right\} }={ \left\{ {\left( {x,1} \right),\left( {x,2} \right),\left( {x,3} \right),}\right.}\kern0pt{\left.{\left( {y,1} \right),\left( {y,2} \right),\left( {y,3} \right)} \right\}.}\]
  2. Compute the Cartesian products of given sets: \[{A \times B }={ \left\{ {x,y} \right\} \times \left\{ {1,2} \right\} }={ \left\{ {\left( {x,1} \right),\left( {x,2} \right),}\right.}\kern0pt{\left.{\left( {y,1} \right),\left( {y,2} \right)} \right\}.}\] \[{A \times C }={ \left\{ {x,y} \right\} \times \left\{ {2,3} \right\} }={ \left\{ {\left( {x,2} \right),\left( {x,3} \right),}\right.}\kern0pt{\left.{\left( {y,2} \right),\left( {y,3} \right)} \right\}.}\] Now we can find the union of the sets \(A \times B\) and \(A \times C:\) \[{\left( {A \times B} \right) \cup \left( {A \times C} \right) }={ \left\{ {\left( {x,1} \right),\left( {x,2} \right),\left( {x,3} \right),}\right.}\kern0pt{\left.{\left( {y,1} \right),\left( {y,2} \right),\left( {y,3} \right)} \right\}.}\] We see that \[{A \times \left( {B \cup C} \right) }={ \left( {A \times B} \right) \cup \left( {A \times C} \right)}.\] This identity confirms the distributive property of Cartesian product over set union.

Example 4.

Suppose \(A = \{a,b\},\) \(B = \{4,6\}\) and \(C = \{5,6\}.\) Determine the sets:
  1. \(A \times \left( {B \cap C} \right)\)
  2. \(\left( {A \times B} \right) \cap \left( {A \times C} \right)\)

Solution.

  1. Find the intersection of the sets \(B\) and \(C:\) \[{B \cap C }={ \left\{ {4,6} \right\} \cap \left\{ {5,6} \right\} }={ \left\{ 6 \right\}.}\] The Cartesian product of \(A\) and \(B \cap C\) is written as \[{A \times \left( {B \cap C} \right) }={ \left\{ {a,b} \right\} \times \left\{ 6 \right\} }={ \left\{ {\left( {a,6} \right),\left( {b,6} \right)} \right\}.}\]
  2. Compute the Cartesian products: \[{A \times B }={ \left\{ {a,b} \right\} \times \left\{ {4,6} \right\} }={ \left\{ {\left( {a,4} \right),\left( {a,6} \right),}\right.}\kern0pt{\left.{\left( {b,4} \right),\left( {b,6} \right)} \right\}.}\] \[{A \times C }={ \left\{ {a,b} \right\} \times \left\{ {5,6} \right\} }={ \left\{ {\left( {a,5} \right),\left( {a,6} \right),}\right.}\kern0pt{\left.{\left( {b,5} \right),\left( {b,6} \right)} \right\}.}\] The intersection of the two sets is given by \[{\left( {A \times B} \right) \cap \left( {A \times C} \right) }={ \left\{ {\left( {a,6} \right),\left( {b,6} \right)} \right\}.}\] So, we have validated the distributive property of Cartesian product over set intersection: \[{A \times \left( {B \cap C} \right) }={ \left( {A \times B} \right) \cap \left( {A \times C} \right).}\]

Example 5.

Find the Cartesian product \(A \times \mathcal{P}\left( A \right)\) if \(A = \left\{ {0,1} \right\}.\)

Solution.

The power set of \(A\) is written in the form

\[{\mathcal{P}\left( A \right) = \mathcal{P}\left( {\left\{ {0,1} \right\}} \right) }={ \left\{ {\varnothing,\left\{ 0 \right\},\left\{ 1 \right\},\left\{ {0,1} \right\}} \right\}.}\]

Hence, the Cartesian product \(A \times \mathcal{P}\left( A \right)\) is given by

\[{A \times \mathcal{P}\left( A \right) }={ \left\{ {0,1} \right\} \times \left\{ {0,\left\{ 0 \right\},\left\{ 1 \right\},\left\{ {0,1} \right\}} \right\} }={ \left\{ {\left( {0,\varnothing} \right),\left( {0,\left\{ 0 \right\}} \right),}\right.}\kern0pt{\left.{\left( {0,\left\{ 1 \right\}} \right),\left( {0,\left\{ {0,1} \right\}} \right),}\right.}\kern0pt{\left.{\left( {1,\varnothing} \right),\left( {1,\left\{ 0 \right\}} \right),}\right.}\kern0pt{\left.{\left( {1,\left\{ 1 \right\}} \right),\left( {1,\left\{ {0,1} \right\}} \right)} \right\}.}\]

Example 6.

Find the Cartesian product \(\left\{ {1,2,3} \right\} \times \mathcal{P}\left( {\left\{ a \right\}} \right).\)

Solution.

The power set \(\mathcal{P}\left( {\left\{ a \right\}} \right)\) consists of one element and contains two subsets:

\[\mathcal{P}\left( {\left\{ a \right\}} \right) = \left\{ {\varnothing,\left\{ a \right\}} \right\}.\]

The Cartesian product of the sets \(\left\{ {1,2,3} \right\}\) and \(\mathcal{P}\left( {\left\{ a \right\}} \right)\) is given by

\[{\left\{ {1,2,3} \right\} \times \mathcal{P}\left( {\left\{ a \right\}} \right) }={ \left\{ {1,2,3} \right\} \times \left\{ {\varnothing,\left\{ a \right\}} \right\} }={ \left\{ {\left( {1,\varnothing} \right),\left( {1,\left\{ a \right\}} \right),}\right.}\kern0pt{\left.{\left( {2,\varnothing} \right),\left( {2,\left\{ a \right\}} \right),}\right.}\kern0pt{\left.{\left( {3,\varnothing} \right),\left( {3,\left\{ a \right\}} \right)} \right\}.}\]

Example 7.

Let \(A = \left\{ {{a_1}, \ldots ,{a_n}} \right\}.\) Compute the cardinality of the set \(\mathcal{P}\left( {{A^m}} \right).\)

Solution.

If the set \(A\) has \(n\) elements, then the \(m\text{th}\) Cartesian power of \(A\) will contain \(nm\) elements:

\[{n\left( {{A^m}} \right) }={ n\left( {\underbrace {A \times \ldots \times A}_m} \right) }={ \underbrace {n\left( A \right) \times \ldots \times n\left( A \right)}_m }={ \underbrace {n \times \ldots \times n}_m }={ nm.}\]

Then the cardinality of the power set of \(A^m\) is

\[n\left( {\mathcal{P}\left( {{A^m}} \right)} \right) = {2^{nm}}.\]

Example 8.

Let \(X = \left\{ {x,y} \right\}.\) Compute the cardinality of the set \(\mathcal{P}\left( {\mathcal{P}\left( X \right)} \right) \times \mathcal{P}\left( X \right).\)

Solution.

First we find the power set of \(X:\)

\[{\mathcal{P}\left( X \right) = \mathcal{P}\left( {\left\{ {x,y} \right\}} \right) }={ \left\{ {\varnothing,\left\{ x \right\},\left\{ y \right\},\left\{ {x,y} \right\}} \right\}.}\]

As it can be seen, \(\mathcal{P}\left( X \right)\) contains \(4\) elements:

\[{n\left( {\mathcal{P}\left( X \right)} \right) }={ n\left( {\mathcal{P}\left( {\left\{ {x,y} \right\}} \right)} \right) }={ {2^2} }={ 4.}\]

It is clear that the power set of \(\mathcal{P}\left( X \right)\) will have \(16\) elements:

\[{n\left( {\mathcal{P}\left( {\mathcal{P}\left( X \right)} \right)} \right) }={ {2^4} }={ 16.}\]

Consider now the Cartesian product:

\[{n\left( {\mathcal{P}\left( {\mathcal{P}\left( X \right)} \right) \times \mathcal{P}\left( X \right)} \right) }={ n\left( {\mathcal{P}\left( {\mathcal{P}\left( X \right)} \right)} \right) \times n\left( {\mathcal{P}\left( X \right)} \right) }={ 16 \times 4 }={ 64,}\]

so the cardinality of the given set is equal to \(64.\)