Cartesian product

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!