The **Cartesian product** is one of the basic operations in set theory. It is named after Descartes, probably by way of the Cartesian (rectangular) coordinate system.

Basically the idea is, that given two sets *A* and *B*, their Cartesian product *A* × *B* is the set of all pairs where the left element is in *A* and the right element is in *B*. For example, if *A* is the set { a, b, c } and *B* is { 1, 2 } then *A* × *B* is { (a, 1), (b, 1), (c, 1), (a, 2), (b, 2), (c, 2) } .

Implementing the above in a procedure is straightforward:

proc Cartesian_product {A B} { set res {} foreach a $A { foreach b $B { lappend res [list $a $b] } } return $res }

% Cartesian_product {a b c} {1 2} {a 1} {a 2} {b 1} {b 2} {c 1} {c 2}

(It's supposed to be a set, so the order of the pairs is irrelevant.)

**However**, there is a complication in that if the elements of *A* are understood to be *k*-tuples and the elements of *B* are understood to be *l*-tuples, then by convention the elements of *A* × *B* should be (*k*+*l*)-tuples, e.g. ℝ³×ℝ⁴=ℝ⁷. This too is easily implemented as a procedure, which is almost the same as the above:

proc Cartesian_product_tuplesets {A B} { set res {} foreach a $A { foreach b $B { lappend res [concat $a $b] ; # Not [list] } } return $res }

% Cartesian_product_tuplesets {{a b c} {d e f}} {{1 2 3 4} {5 6 7 8}} {a b c 1 2 3 4} {a b c 5 6 7 8} {d e f 1 2 3 4} {d e f 5 6 7 8}

And then there is of course the mixed possibilities, where one factor is a set of tuples and the other is just a set of "plain" elements.

proc Cartesian_product_tupleset_left {A B} { set res {} foreach a $A { foreach b $B { lappend res [linsert $a end $b] ; # Or [concat $a [list $b]] } } return $res } proc Cartesian_product_tupleset_right {A B} { set res {} foreach a $A { foreach b $B { lappend res [linsert $b 0 $a] ; # Or [concat [list $a] $b] } } return $res }

Where do these ever occur, you may ask? Well, if one thinks about a Cartesian product with more than two factors, such as *A* × *B* × *C* × *D* × *E* then the ×'s can't all be **Cartesian_product**, can they? That would produce elements looking like ((((*a*,*b*),*c*),*d*),*e*) — or why not (*a*,(*b*,(*c*,(*d*,*e*)))) or ((*a*,*b*),((*c*,*d*),*e*)) — rather than the expected (*a*,*b*,*c*,*d*,*e*), so some of the ×'s have to be some **Cartesian_product_tupleset***.

More generally, this is an illustration of a phenonemon in mathematics that the same symbol is used for many related operations which one maybe doesn't even think of as being distinct — until one has to stringently formalise them, which happens for example if one tries to implement them!

See also: