Cartesian product ($X\times Y$)

The Cartesian product $X\times Y$ is the set of ordered pairs $(x,y)$ with $x\in X$ and $y\in Y$.

An infinite Cartesian product of finite sets need not admit any complete list enumeration. For the repeated binary factor, suppose the output lists all sequences as $z_0,z_1,\dots$. Define a sequence by $b_i=1-z_i(i)$. It is a valid binary sequence but differs from the $i$-th output at coordinate $i$, a contradiction. This is Cantor's diagonal argument. Consequently fair binary products can recursively enumerate the choices from finitely many possibly infinite lists, but cannot solve the unrestricted infinite-family specification. A finite-family algorithm's restriction must be explicit.

For $A\subseteq {\mathbb{R}}^2$ and a nonzero direction $\mathbf{b}$, its affine section is the inverse image of $A$ under the line parametrization $t\mapsto \mathbf{a}+t\mathbf{b}$. The resulting set is a subset of the parameter line, so changing a parametrization can change the section by translation or scaling. The four real parameters can be encoded by a single real using real-number pairing by separated digits. Thus no fixed planar set can realize every real subset as a section, by Cantor's theorem.

Use coding of real sequences by ternary digits to give each real sequence a distinct column coordinate $c(s)\in [0,1/2]$. Put every term of that sequence in its column. The vertical affine section of a planar set at $c(s)$ is exactly the sequence range. Every nonempty countable set has such an enumeration, with repetitions allowed, while any column outside the code interval gives the empty set. This realizes every countable real subset; the other sections are unrestricted.

Given functions $f_i:Y\to X_i$, there is a unique function $g:Y\to X_1\times X_2$ whose coordinate projection maps are $f_1,f_2$. It is the displayed pointwise pairing. Equality of ordered pairs is equality of both coordinates, which proves uniqueness and makes the Cartesian product a categorical product in the Category of sets.

The pairing map to a Cartesian product is injective exactly when its coordinate functions are jointly injective in the displayed sense. Either coordinate being injective is sufficient, but neither need be injective individually. For example, pairing three points with $(0,0),(0,1),(1,0)$ distinguishes all points even though each coordinate separately identifies two of them.

A finite tuple is an ordered list of finitely many entries; coordinates can repeat, and their positions matter. A tuple of length $n$ from a set $M$ is an element of the Cartesian product $M^n$. The empty tuple has length zero. Finite tuples support Scott formulas in a back-and-forth method construction, where matching tuples determine a partial isomorphism of structures.

An ordered triple is a finite tuple with three ordered coordinates. Repeated coordinates are allowed; equality requires equality at each of the three positions.

Using distinct fixed tags $t_1,\dots ,t_n$, encode a tuple $(a_1,\dots ,a_n)$ by the set $\{⟨t_i,a_i⟩:1\le i\le n\}$. Injectivity of the ordered-pair construction makes the unique member with first coordinate $t_i$ recover $a_i$. Thus a set can retain the order of a finite tuple when its entries are tagged, even if some coordinates coincide.