# Some thougts on cartesian products

Christoph Zwerschke cito at online.de
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