Cartesian Product in Discrete Mathematics [ English ]

Languages

• English

1. Introduction

In set theory, the Cartesian product is a fundamental concept used to combine elements of two sets in an ordered manner. It plays a crucial role in:

• Relations
• Functions
• Coordinate systems
• Database structures

Unlike union or intersection, the Cartesian product focuses on forming ordered pairs.

2. Definition of Cartesian Product

The Cartesian product of two sets A and B is the set of all ordered pairs (a, b) such that:

• a ∈ A
• b ∈ B

Formal Definition:

A × B = { (a, b) | a ∈ A and b ∈ B }

3. Ordered Pair

An ordered pair (a, b) means:

• First element comes from set A
• Second element comes from set B

⚠ Important:

(a, b) ≠ (b, a)

Order matters.

4. Example of Cartesian Product

Let:

A = {1, 2}
B = {a, b}

Then:

A × B = { (1, a), (1, b), (2, a), (2, b) }

Reverse Product

B × A = { (a, 1), (a, 2), (b, 1), (b, 2) }

✔ Clearly:

A × B ≠ B × A

5. Number of Elements in Cartesian Product

If:

• n(A) = m
• n(B) = n

Then:

n(A × B) = m × n

Example

A = {1, 2, 3} → n(A) = 3
B = {x, y} → n(B) = 2

n(A × B) = 3 × 2 = 6

6. Cartesian Product with Itself

A × A

Example:

A = {1, 2}

A × A = { (1,1), (1,2), (2,1), (2,2) }

7. Special Cases

(a) Product with Empty Set

A × ∅ = ∅
∅ × A = ∅

✔ No ordered pairs possible

(b) Singleton Set

A = {1}
B = {a, b}

A × B = { (1,a), (1,b) }

8. Applications of Cartesian Product

(a) Relations

• Relations are subsets of A × B

(b) Functions

• Functions are special types of relations

(c) Coordinate System

• Points like (x, y) in graphs

(d) Computer Science

• Database combinations
• Pairing data

9. Key Observations

• Order of elements matters
• Result consists of ordered pairs
• Not commutative (A × B ≠ B × A)
• Size depends on multiplication of cardinalities

10. Summary

• Cartesian product is written as A × B

• Defined as:

  • { (a, b) | a ∈ A and b ∈ B }

• Produces ordered pairs

• Number of elements:

  • n(A × B) = n(A) × n(B)

• Important in relations, functions, and coordinate geometry