Some thougts on cartesian products

[Christoph Zwerschke]

Bryan Olson wrote:
 > The claim "everything is a set" falls into the category of
 > 'not even wrong'.

No, it falls into the category of the most fundamental Mathematical 
concepts. You actually *define* tuples as sets, or functions as sets or 
relations as sets, or even all kinds of numbers and other things, which 
exist only in the heads of Mathematicians, as sets.

 > Watch things not be sets:
 >
 >    x = [1, 1, 2]
 >    y = [1, 2]
 >    print x == y
 >    print set(x) == set(y)

Python tuples and lists are of course not the same as Python sets. But 
mathematically, you can understand them as sets anyway and associate 
every Python tuple with a Python set. The naive approach to understand a 
list as the set of its values which is done by casting with set() does 
not work, as you rightly noticed. The associated set to a Python tuple 
or list x would be set(enumerate(x)), not set(x).

Generally, two approaches are common for constructing tuples as sets:

(A) Think of an n-tuple as a function on the index set, range(n). Then 
remember a function is a special relation is a set.

   (1, 2, 2) would correspond to the set {(0, 1), (1, 2), (2, 2)}
   (1, 2) would correspond to the set {(0, 1), (1, 2)}

In Python, the tuple or list x would correspond to set(enumerate(x)).

As a sidemark, another common approach is this:

(B) Define the set corresponding to (1, 2) as {{1}, 2}. Define the set 
corresponding to (1, 2, 2) as {{{1}, 2}, 2}, the set corresponding to 
(1, 2, 2, 4) as {{{{1}, 2}, 2}, 4} and so on.

 > I really did try to raise the real issues. I cannot make you answer,
 > but the question remains: are duplicate and order significant in
 > what you call "Cartesian product" or they not? Can you show that
 > your proposed language extensions are  useful and consistent in
 > some reasonable sense?

I already tried to answer. It is not what "I call" Cartesian product. If 
there is a canonical set representation of something like a function or 
a tuple you immediately have a well-defined Cartesian product on these 
things, and this would be also called Cartesian product. A Cartesian 
product of functions and tuples is a well-defined mathematical concept. 
The Cartesian product of functions is even a function again, and (via 
lexicographical order of the index set) you can also interpret the 
Cartesian product of tuples as a tuple again (this was probably the 
point where you had doubts, but I already tried to explain).

The only ambiguity is whether the result should be a generator or a 
tuple, and in the case of strings whether the elements in the result 
should be returned as tuples,
"ab"*"cd" = ("a", c"), ("a", "d"), ("b", "c"), ("b", "d")
or concatenated as strings:
"ab"*"cd" = "ac", "ad", "bc", "bd"

In any way, there is no dispute about duplicates or ordering. This is 
all canonical and well-defined.

Concerning the use, I admit there is no really frequent use, but in some 
occasions it may be useful and I already gave some examples.

-- Christoph