Let n(A) = m, and n(B) = n. Then the total number of non-empty relations that can be defined from A to B is (A

NCERT Exemplar · Q24

n(A) = m

Sikkim CbseMCQ· 1mImportance★★★★★est

82% · 82/100 Questions

🔒 Locked · start free trial →

You're viewing a preview — the full solution, concept, methods & PYQ mapping are locked.

Start your 14-day free trial to unlock the full solution →

Concept understanding — Cartesian Product

Cartesian Product: From Intuition to Definition

Imagine you're ordering a pizza. You have two choices to make: the size (Small, Medium, Large) and the topping (Cheese, Pepperoni, Veggie). How many different pizzas can you order?

You can pair each size with each topping:

Small + Cheese, Small + Pepperoni, Small + Veggie
Medium + Cheese, Medium + Pepperoni, Medium + Veggie
Large + Cheese, Large + Pepperoni, Large + Veggie

That's $3 \times 3 = 9$ possible pizzas. What you just did — systematically pairing every element of one set with every element of another — is the Cartesian product in action.

The Intuition

The Cartesian product is a way to combine two sets to create a new set of ordered pairs. The order matters: (Small, Cheese) is different from (Cheese, Small) — one is a pizza order, the other is nonsense.

Think of it like a multiplication table for sets. If set $A$ has $m$ items and set $B$ has $n$ items, their Cartesian product has $m \times n$ items.

Note

The name comes from René Descartes, who used this idea to create the coordinate plane — every point $(x, y)$ on a graph is an element of the Cartesian product of the x-axis and y-axis.

The Precise Definition

Let $A$ and $B$ be two sets. The Cartesian product of $A$ and $B$ , written $A \times B$ , is the set of all ordered pairs $(a, b)$ where $a$ is from $A$ and $b$ is from $B$ .

A \times B = \{(a, b) \mid a \in A \text{ and } b \in B\}

The vertical bar means "such that." So read it as: "The set of all ordered pairs (a, b) such that a belongs to A and b belongs to B."

Key Properties to Remember

Order matters: $A \times B$ is generally not the same as $B \times A$ . For example, if $A = \{1, 2\}$ and $B = \{x, y\}$ :
- $A \times B = \{(1, x), (1, y), (2, x), (2, y)\}$
- $B \times A = \{(x, 1), (x, 2), (y, 1), (y, 2)\}$
These are different sets because the pairs are ordered differently.
Size formula: If $|A| = m$ and $|B| = n$ , then $|A \times B| = m \times n$ . This holds even if one set is empty — then the product is empty.
Empty set: $A \times \emptyset = \emptyset$ and $\emptyset \times B = \emptyset$ . You can't form any pairs if one set has nothing to contribute.

Watch out

A common mistake: thinking $A \times B$ contains all possible combinations of elements from $A$ and $B$ without caring about order. But $(a, b)$ and $(b, a)$ are different pairs unless $a = b$ . Always treat ordered pairs as distinct based on position.

Examples to Cement the Idea

Example 1: $A = \{1, 2\}$ , $B = \{3, 4\}$

A \times B = \{(1, 3), (1, 4), (2, 3), (2, 4)\}

Four pairs, as expected ( $2 \times 2 = 4$ ).

Example 2: $A = \{a\}$ , $B = \{1, 2, 3\}$

A \times B = \{(a, 1), (a, 2), (a, 3)\}

Three pairs — every element of $B$ gets paired with the single element of $A$ .

Example 3: $A = \{0, 1\}$ , $B = \{0, 1\}$

A \times B = \{(0, 0), (0, 1), (1, 0), (1, 1)\}

This is the set of all possible 2-bit binary strings — a foundation for computer science.

Why This Matters

The Cartesian product is the mathematical backbone of: …

Start your 14-day free trial to unlock the full solution →

A relation from set $A$ to set $B$ is any subset of their Cartesian product $A \times B$ . If $n(A)=m$ and $n(B)=n$ , then $n(A \times B) = mn$ , leading to $2^{mn}$ total relations. Excluding the single empty relation, the number of non-empty relations is $\boxed{2^{mn} - 1}$ .

Let's break down the concept of relations and how to count them. The core idea is that a relation between two sets is fundamentally defined by which pairs of elements are "related." This naturally leads us to consider the Cartesian product of the sets.

A relation $R$ from set $A$ to set $B$ is simply a collection of ordered pairs $(a, b)$ where $a \in A$ and $b \in B$ . For example, if $A = \{1, 2\}$ and $B = \{x, y\}$ , a relation could be $R = \{(1, x), (2, y)\}$ . Another relation could be $R' = \{(1, y)\}$ . Notice that these relations are nothing more than subsets of all possible ordered pairs you can form between elements of $A$ and $B$ . This set of all possible ordered pairs is called the Cartesian product, $A \times B$ .

1. Determine the size of the Cartesian Product $A \times B$

The Cartesian product $A \times B$ is the set of all possible ordered pairs $(a, b)$ where $a \in A$ and $b \in B$ .

Given:

The number of elements in set $A$ is $n(A) = m$ .
The number of elements in set $B$ is $n(B) = n$ .

To form an ordered pair $(a, b)$ , we choose one element from $A$ (there are $m$ choices) and one element from $B$ (there are $n$ choices). By the fundamental principle of counting, the total number of such distinct ordered pairs is the product of the number of choices for each position.

Therefore, the number of elements in the Cartesian product $A \times B$ is:

$n(A \times B) = n(A) \times n(B) = m \times n = mn$ .

For example, if $A = \{1, 2\}$ ( $m=2$ ) and $B = \{x, y, z\}$ ( $n=3$ ), then $A \times B = \{(1, x), (1, y), (1, z), (2, x), (2, y), (2, z)\}$ . Here, $n(A \times B) = 2 \times 3 = 6$ .

2. Calculate the total number of possible relations

A relation from $A$ to $B$ is defined as any subset of $A \times B$ .

Let $S = A \times B$ . We found that $n(S) = mn$ .

k

Since a relation is a subset of $A \times B$ , and $A \times B$ has $mn$ elements, the total number of possible relations that can be defined from $A$ to $B$ is $2^{mn}$ .

This count includes all possible subsets, from the empty set to the set $A \times B$ itself. …

Start your 14-day free trial to unlock the full solution →

←Previous questionQ23 — If f(x) = y = (ax - b)/(cx - a), then prove that f(y) = x.→Next questionQ25 — If [x]² - 5[x] + 6 = 0, where [.] denote the greatest integer function…

Q.Let n(A)=mn(A) = mn(A)=m, and n(B)=nn(B) = nn(B)=n. Then the total number of non-empty relations that can be defined from AAA to BBB is (A) mnm^nmn (B) nm−1n^m - 1nm−1 (C) mn−1mn - 1mn−1 (D) 2mn−12^{mn} - 12mn−1

1. Determine the size of the Cartesian Product A×BA \times BA×B

2. Calculate the total number of possible relations

🎓Unlock everything free for 14 days

Q.Let $n(A) = m$ , and $n(B) = n$ . Then the total number of non-empty relations that can be defined from $A$ to $B$ is
(A) $m^n$
(B) $n^m - 1$
(C) $mn - 1$
(D) $2^{mn} - 1$

1. Determine the size of the Cartesian Product $A \times B$

Unlock everything free for 14 days