Cartesian Product

cartesian product

Suppose that

A, B

are set, then we define

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

intersection and cartesian product commute

Given sets

A, B, C, D

, then

(A \times B) \cap (C \times D) = (A \cap C) \times (B \cap D)

We will prove this true by the definition of set equality.

Suppose that $(x, y) \in (A \times B) \cap (C \times D)$ , which is true iff $(x, y) \in (A \times B)$ , so that $x \in A$ and $y \in B$ .

We also know that $(x, y) \in (C \times D)$ which is equivalent to $x \in C$ and $y \in D$

We have $x \in A \cap C$ and $y \in B \cap D$ which is equivalent to $(x, y) \in (A \cap C) \times (B \cap D)$ .

Thus we've proven that $(x, y) \in (A \times B) \cap (C \times D)$ if and only if $(x, y) \in (A \times B) \cap (C \times D)$ as needed.

cartesian product distributes over intersection

Given sets

A, B, C

, then

(A \cap B) \times C = (A \times C) \cap (B \times C)

We will show their equality directly

So suppose that $(x, y) \in (A \cap B) \times C$ , which is true iff $x \in A \cap B$ and $y \in C$ , which is true iff $(x, y) \in A \times C$ and $(x, y) \in B \times C$ , which is true iff $x \in (A \times C) \cap (B \times C)$ .

Therefore $(x, y) \in (A \cap B) \times C$ if and only if $x \in (A \times C) \cap (B \times C)$ , so $(A \cap B) \times C = (A \times C) \cap (B \times C)$ as needed.

Set Power

Suppose that

A

is a set, and that

n \in ℕ_{1}

, then we define

A^{n}

to be the set of all n-tuples of

A

, that is :

A^{n} : = {(a_{1}, a_{2}, . . ., a_{n}) : \forall i \in [n], a_{i} \in A}