Some thougts on cartesian products

Christoph Zwerschke cito at
Tue Jan 24 12:39:58 EST 2006

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 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 
tuple as the set of its values which is done by casting to 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, 1), (1, 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. 
Since functions are sets in Mathematics, once you have a Cartesian 
product on sets, there is a natural (canonical) way to define a 
Cartesian product on functions as well. So there is also a canonical way 
to define a Cartesian product on tuples, if you interpret tuples as 
functions via (A). And there is a canonical way to understand the 
resulting sets as tuples again (by the lexicographical order of the 
index set).

So the cartesian product of a string, tuple, or list is well-defined 
including its order.

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

More information about the Python-list mailing list