👁 Preview — Study, Practice and Revise are open; mock tests and the rest of the syllabus unlock on subscription. Unlock all · ₹4,999
← Back to Algebra
Study mode

Cartesian Product

Study Practice Revise 🔒 Test
Learning objective
Define and understand Cartesian products and ordered pairs.

Understanding Cartesian Product

The Cartesian product is a fundamental concept in set theory and algebra, crucial for understanding relations, functions, and many other mathematical structures. It combines elements from two sets to form ordered pairs.

1. Definition of Cartesian Product

Given two sets \( A \) and \( B \), the Cartesian product of \( A \) and \( B \), denoted by \( A \times B \), is the set of all ordered pairs where the first element is from \( A \) and the second is from \( B \). Formally,

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

Here, each element of \( A \times B \) is an ordered pair, meaning the order of elements matters: \( (a, b) \neq (b, a) \) unless \( a = b \).

2. Ordered Pairs and Their Importance

An ordered pair \( (a, b) \) is a pair of elements where the first element is \( a \) and the second is \( b \). This is different from a set \({a, b}\) because in sets, order does not matter, but in ordered pairs, it does.

For example, if \( A = {1, 2} \) and \( B = {x, y} \), then

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

Note that \( (1, x) \neq (x, 1) \), and \( (x, 1) \) is not even an element of \( A \times B \) because \( x \notin A \).

3. Cardinality of Cartesian Product

If \( n(A) \) denotes the number of elements in set \( A \) and \( n(B) \) the number of elements in \( B \), then the number of elements in the Cartesian product \( A \times B \) is given by:

\[n(A \times B) = n(A) \times n(B)\]

This follows because for each element in \( A \), there are \( n(B) \) possible pairs with elements of \( B \).

4. Properties of Cartesian Product

  • Non-commutativity: Generally, \( A \times B \neq B \times A \) because the order of elements in ordered pairs matters.
  • Associativity: Cartesian product is associative up to isomorphism, i.e., \( (A \times B) \times C \) can be identified with \( A \times (B \times C) \), but strictly speaking, they are not equal sets because their elements are ordered pairs vs. ordered pairs of ordered pairs.
  • Empty Set: If either \( A \) or \( B \) is empty, then \( A \times B = \emptyset \).

5. Visualizing Cartesian Product

Consider the sets \( A = {1, 2} \) and \( B = {x, y, z} \). The Cartesian product \( A \times B \) can be visualized as a grid or matrix where rows correspond to elements of \( A \) and columns correspond to elements of \( B \):

xyz
1(1,x)(1,y)(1,z)
2(2,x)(2,y)(2,z)

6. Cartesian Product of a Set with Itself

The Cartesian product \( A \times A \) is the set of all ordered pairs where both elements come from the same set \( A \). For example, if \( A = {1, 2} \), then

\[A \times A = {(1,1), (1,2), (2,1), (2,2)}\]

This is important in defining relations on \( A \), such as equivalence relations or orderings.

7. Connection to Relations and Functions

A relation from set \( A \) to set \( B \) is any subset of \( A \times B \). For example, if \( A = {1, 2} \) and \( B = {x, y} \), then a relation \( R \) could be:

\[R = {(1, x), (2, y)} \subseteq A \times B\]

A function from \( A \) to \( B \) is a relation where each element of \( A \) appears exactly once as the first element in an ordered pair.

8. Power Set and Its Relation to Cartesian Product

The power set \( \mathcal{P}(S) \) of a set \( S \) is the set of all subsets of \( S \). If \( n(S) = k \), then

\[n(\mathcal{P}(S)) = 2^k\]

This is a key concept often tested alongside Cartesian products, especially in problems involving subsets and set operations.

9. Common Mistakes to Avoid

  • Confusing ordered pairs with sets: \( (a, b) \neq {a, b} \).
  • Assuming \( A \times B = B \times A \) without checking the order.
  • Forgetting that if either \( A \) or \( B \) is empty, the Cartesian product is empty.
  • Miscounting the number of elements in \( A \times B \) by not multiplying cardinalities.

10. Summary Table of Key Concepts

ConceptNotationDefinition/Formula
Cartesian Product\( A \times B \)\( {(a,b) : a \in A, b \in B} \)
Cardinality of Cartesian Product\( n(A \times B) \)\( n(A) \times n(B) \)
Power Set\( \mathcal{P}(S) \)Set of all subsets of \( S \), \( n(\mathcal{P}(S)) = 2^{n(S)} \)
Empty Set\( \emptyset \)Subset of every set; \( A \times \emptyset = \emptyset \)

Worked Examples

Example 1: Finding the Cartesian Product of Two Finite Sets [Easy]

Find the Cartesian product \( A \times B \) where \( A = {1, 2} \) and \( B = {x, y} \).

Solution:

  1. List all elements of \( A \): 1, 2.
  2. List all elements of \( B \): x, y.
  3. Form ordered pairs by pairing each element of \( A \) with each element of \( B \):
    • \( (1, x), (1, y) \)
    • \( (2, x), (2, y) \)
  4. Therefore,
\[ A \times B = {(1, x), (1, y), (2, x), (2, y)} \]

Example 2: Cardinality of Cartesian Product [Easy]

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

Solution:

By the formula for cardinality of Cartesian product:

\[ n(A \times B) = n(A) \times n(B) = 3 \times 4 = 12 \]

Example 3: Cartesian Product with an Empty Set [Medium]

Let \( A = {1, 2, 3} \) and \( B = \emptyset \). Find \( A \times B \).

Solution:

Since \( B \) is empty, there are no elements to pair with elements of \( A \). Hence,

\[ A \times B = \emptyset \]

Example 4: Intersection of Cartesian Products [Medium]

Given \( A = {1, 2, 5, 6} \) and \( B = {1, 2, 3} \), find \( (A \times B) \cap (B \times A) \).

Solution:

  1. Find \( A \times B = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (5,1), (5,2), (5,3), (6,1), (6,2), (6,3)} \).
  2. Find \( B \times A = {(1,1), (1,2), (1,5), (1,6), (2,1), (2,2), (2,5), (2,6), (3,1), (3,2), (3,5), (3,6)} \).
  3. Find the intersection \( (A \times B) \cap (B \times A) \), i.e., ordered pairs common to both sets.
  4. Common pairs are those where \( (a,b) = (b,a) \), which can only happen if \( a = b \) and \( a,b \in A \cap B \).
  5. Since \( A \cap B = {1, 2} \), the pairs are \( (1,1) \) and \( (2,2) \).
\[ (A \times B) \cap (B \times A) = {(1,1), (2,2)} \]

Example 5: Number of Subsets of a Set [Easy]

Find the number of subsets of the set \( S = {1, 2, y, 2 + y, 2 = 1} \).

Solution:

First, identify the number of distinct elements in \( S \). The elements are \( 1, 2, y, 2 + y, 2 = 1 \).

Note: \( 2 = 1 \) is a statement, not an element; assuming it is a typo or symbol, we consider only distinct elements.

Assuming all five are distinct, \( n(S) = 5 \).

The number of subsets is:

\[ 2^{n(S)} = 2^5 = 32 \]

Example 6: Maximum Number of Elements in Symmetric Difference [Medium]

Given \( n(A) = 5 \) and \( n(B) = 4 \), find the maximum number of elements in \( A \oplus B \) (symmetric difference).

Solution:

The symmetric difference \( A \oplus B = (A - B) \cup (B - A) \).

Maximum occurs when \( A \) and \( B \) are disjoint sets.

Therefore, maximum number of elements in \( A \oplus B = n(A) + n(B) = 5 + 4 = 9 \).

Formula Bank

  • Cartesian Product: \( A \times B = {(a,b) : a \in A, b \in B} \)
  • Cardinality of Cartesian Product: \( n(A \times B) = n(A) \times n(B) \)
  • Power Set Cardinality: If \( n(S) = k \), then \( n(\mathcal{P}(S)) = 2^k \)
  • Symmetric Difference: \( A \oplus B = (A - B) \cup (B - A) \)
  • Subset Property: \( A \subseteq B \implies A \cup B = B \) and \( A \cap B = A \)
  • Empty Set: \( \emptyset \subseteq A \) for any set \( A \)
Curated videos per subtopic
Top YouTube explainers, AI-ranked for your exam and language. Unlocks with subscription.
Unlock

Try Practice next.

Progress tracking is paywalled — subscribe to mark subtopics as understood and save your streak.

Go to practice →
Ask a doubt
Cartesian Product · 10 free messages
Ask me anything about this subtopic. You have 10 free messages this session — chat history isn't saved in preview.