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