Cartesian Product and Introduction to Relations | NIMCET

Quick answer: The Cartesian product $A \times B$ is the set of all ordered pairs $(a, b)$ with $a \in A$ and $b \in B$, so $n(A \times B) = n(A) \cdot n(B)$. A relation from A to B is any subset of $A \times B$. If $n(A) = m$ and $n(B) = n$, there are $2^{mn}$ relations from A to B.

Ordered pairs

An ordered pair $(a, b)$ has a first and a second element, so order matters: $(1, 2) \ne (2, 1)$.

Two ordered pairs are equal only when corresponding elements are equal: $(a, b) = (c, d)$ means $a = c$ and $b = d$.

Cartesian product

$A \times B = \{(a, b) : a \in A, b \in B\}$

Example: If $A = \{1, 2\}$ and $B = \{x, y, z\}$, then

$A \times B = \{(1, x), (1, y), (1, z), (2, x), (2, y), (2, z)\}$

which has $2 \times 3 = 6$ elements.

Properties

$A \times A$ is often written $A^2$, and $\mathbb{R} \times \mathbb{R}$ is the coordinate plane.

Relations

A relation R from A to B is a subset of $A \times B$. We write $a\,R\,b$ when $(a, b) \in R$.

Example: Let $A = \{1, 2, 3, 4\}$ and $R = \{(a, b) : b = a + 1\}$ on A. Then $R = \{(1, 2), (2, 3), (3, 4)\}$, the domain is $\{1, 2, 3\}$ and the range is $\{2, 3, 4\}$.

Inverse relation

$R^{-1} = \{(b, a) : (a, b) \in R\}$

The domain of $R^{-1}$ is the range of R, and vice versa.

Counting results

Why $2^{mn}$: a relation is any subset of $A \times B$, and a set of $mn$ elements has $2^{mn}$ subsets (see power sets).

Worked examples

Example 1: equal ordered pairs

If $(x + 1, y - 2) = (3, 1)$, find x and y.

$x + 1 = 3$ and $y - 2 = 1$, so $x = 2$ and $y = 3$.

Example 2: counting relations

If $n(A) = 2$ and $n(B) = 3$, how many relations are there from A to B?

$2^{2 \cdot 3} = 2^6 = 64$.

Example 3: recovering sets from a product

If $A \times B = \{(a, 1), (a, 2), (b, 1), (b, 2)\}$, then $A = \{a, b\}$ and $B = \{1, 2\}$.

Example 4: common elements

If $n(A) = 3$, $n(B) = 4$ and $n(A \cap B) = 2$, find $n((A \times B) \cap (B \times A))$.

Using the mixed property, it equals $n((A \cap B) \times (B \cap A)) = 2 \times 2 = 4$.

Summary table

Exam tips

• For "how many relations" questions, find $n(A \times B)$ first, then raise 2 to that power.
• Use the mixed property for intersections of two Cartesian products.
• Do not confuse the range of a relation with its co-domain.

Next, study types of relations and equivalence relations or browse the NIMCET Set Theory chapter.

Common mistakes

• Treating $(a, b)$ and $(b, a)$ as the same pair.
• Writing the number of relations as $mn$ instead of $2^{mn}$.
• Assuming $A \times B = B \times A$.
• Forgetting that the empty relation is also a relation.

Frequently Asked Questions

What is the Cartesian product of two sets?

A × B is the set of all ordered pairs (a, b) with a in A and b in B.

How many relations are there from A to B?

If n(A) = m and n(B) = n, there are 2^(mn) relations from A to B.

Is A × B equal to B × A?

Not in general. They are equal only when A = B or when one of the sets is empty.

What is a relation in set theory?

A relation from A to B is any subset of the Cartesian product A × B.

What is the inverse of a relation?

The inverse R⁻¹ contains every pair of R with its elements swapped.