Set Products

Why

Does a set exist which contains all ordered pairs of elements from two sets?

Discussion

The answer is easily seen to be yes. Ordered pairs are just sets, containing two sets. One set has one object, and so is a singleton. The other has two objects, and so is a pair. So to construct the set of all ordered pairs, we need only specify certain members of some set containing all singletons and pairs. The power set of the union of the two sets will suffice.

To see this, suppose $A$ and $B$ are two sets. If $a \in A$, then $a \in A \cup B$. Likewise if $b \in B$, then $b \in A \cup B$. Hence $\set{a} \subset A$ and $\set{b} \subset B$, so that $\set{a}, \set{b} \in \powerset{A \cup B}$. In other words, the singletons are members of the power set. Similarly, $\set{a, b} \in \powerset{A \cup B}$. In other words, the pairs are elements of the power set. Thus the set of sets containing singletons and pairs is a power set of the power set of $A \cup B$. In symbols, $\set{\set{a}, \set{a, b}} \in \powerset{\powerset{A \cup B}}$.

Definition

We define the set of “all ordered pairs” from $A$ and $B$ by specifying the appropriate pairs of this set.¹

\[ \Set{(a, b) \in \powerset{\powerset{A \cup B}}}{a \in A \land b \in B} \]

We name this set the product of the set denoted by $A$ and the set denoted by $B$ is the set of all ordered pairs. This set is also called the set product (or cartesian product² ). If $A \neq B$, the ordering causes the product of $A$ and $B$ to differ from the product of $B$ with $A$. If $A = B$, however, the symmetry holds.

Notation

We denote the product of $A$ with $B$ by $A \times B$, read aloud as “A cross B.” In this notation, if $A \neq B$, then $A \times B \neq B \times A$.³

Empty set

It turns out the product of the empty set with any other set is always empty.

Suppose $A$ is a set. Then $A \times \varnothing = \varnothing \times A = \varnothing$.

This follows from the definition of the set product, since there is no element in the emepty set, and so the statement used in the specification always evaluates to false.

The specific statement used here requires some translation. A discussion of this and the full statement will appear in a future edition. ↩︎
This second term is universal, but avoided in accordance with the project policy on naming. ↩︎
Future editions may include a table figure visualizing the product. ↩︎