---
title: "Define Cartesian product"
subject: "Theory of Computation"
chapter: 1
key: "semester_3/theory_of_computation:cartesian-product-define"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/cartesian-product-define
site: BCT Engineering
---

# Define Cartesian product

Theory of Computation · Chapter 1: Introduction

- Asked in: 2072 Chaitra
- Video: [2.1 Cartesian Product of Two Sets AXB](https://www.youtube.com/watch?v=gs0dQF3pGqM) — KnowledgeGATE by Sanchit Sir
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/cartesian-product-define
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-1

## Question

Define Cartesian product.

## Short answer

A × B = {(a,b) | a∈A, b∈B}. Ordered pairs, |A×B| = |A|·|B|. It is not generally commutative. Cartesian products underlie relations and functions: a relation from A to B is a subset of A×B.

## Answer

The **Cartesian product** of two sets A and B, written A × B, is the set of all ordered pairs whose first element is from A and second from B:

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

**Example.** A = {1, 2}, B = {x, y, z}:

A × B = {(1,x), (1,y), (1,z), (2,x), (2,y), (2,z)}

**Properties**
- Pairs are ordered: (a, b) ≠ (b, a) unless a = b.
- |A × B| = |A|·|B| for finite sets (here 2·3 = 6).
- In general A × B ≠ B × A (it is equal only if A = B or one of them is empty).
- A × ∅ = ∅.
- It extends to n sets: A₁ × A₂ × ... × Aₙ is the set of ordered n-tuples. Aⁿ = A × A × ... × A (n times).

**Use in this subject.** A relation from A to B is a subset of A × B. A function f : A → B is a special kind of relation, so it is also a subset of A × B. The transition function of a DFA is δ : Q × Σ → Q, whose domain is a Cartesian product.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What is A × B?
   A. The set of all ordered pairs (a, b) with a in A and b in B
   B. The set of elements common to A and B
   C. The set of all unordered pairs from A and B
   D. The set of elements in A or B
   Answer: A. The Cartesian product consists of ordered pairs with first element from A and second from B. (Key point: Definition)

2. If |A| = 2 and |B| = 3, what is |A × B|?
   A. 8
   B. 9
   C. 5
   D. 6
   Answer: D. |A × B| = |A|·|B| = 6 for finite sets. (Key point: Size)

3. Is A × B = B × A in general?
   A. No, pairs are ordered, so it holds only if A = B or one is empty
   B. Yes, only when |A| = |B|
   C. Yes, always
   D. No, never, even if A = B
   Answer: A. (a, b) ≠ (b, a) in general, so equality needs A = B or an empty set. (Key point: Commutativity)

4. Where is the Cartesian product used in a DFA?
   A. The set of final states F
   B. The alphabet Σ
   C. The domain of the transition function δ : Q × Σ → Q
   D. The start state q0
   Answer: C. δ takes a pair (state, symbol), which is an element of Q × Σ. (Key point: Use in automata)