5
$\begingroup$

It is general consensus that Cartesian product is distributive over set difference. However, I am unable to identify a flaw in this example.

Let $A$ be a non empty set. Let $X=\prod_{i}^{\infty} A$, i.e. an infinite Cartesian product of A. Let $Y=A$ and $Z=A \times A$.

Then,

$Y - Z=Y$ and $X \times (Y - Z)=X$.

But $X \times Y=X$ and $X \times Z=X$ and their difference is $\emptyset$.

What is the flaw in this counterexample?

$\endgroup$
7
  • 2
    $\begingroup$ $Y-Z$ is not even defined since $Y$ and $Z$ are subsets of different universal sets. $\endgroup$ Commented Jun 16 at 23:00
  • 3
    $\begingroup$ $X \times Y = X$ is incorrect, and so are your other product equalities. The two sets are in bijection, sure, but they are not equal. $\endgroup$
    – Sambo
    Commented Jun 16 at 23:46
  • 1
    $\begingroup$ Explicitly: the elements of $X$ are sequences $(a_i)_{i=1}^\infty$ (of elements in $A$), while the elements of $X \times Y$ are pairs $(s,a)$, where $a \in A$ and $s$ is a sequence of elements of $A$. $\endgroup$
    – Sambo
    Commented Jun 16 at 23:48
  • $\begingroup$ @geetha290krm One could argue that $A - B$ is the set $\{a \in A \mid a \notin B\}$, but the example still doesn't work. $\endgroup$
    – Sambo
    Commented Jun 16 at 23:50
  • 1
    $\begingroup$ You are running into the issue of the difference between a product of a family of sets (such as $X$), and the cartesian product of two sets (such as $Z$, and $X\times Y$). Your assertions that $X$ and $X\times Y$ are equal is not quite correct, since $X$ is the set of functions from $\mathbb{N}$ to $A$, whereas $X\times Y$ consists of ordered pairs $(x,y)$ where $x\in X$ and $y\in Y$. They are not the same thing. $\endgroup$ Commented Jun 16 at 23:53

1 Answer 1

5
$\begingroup$

Recall that for two sets $A$ and $B$, the cartesian product $A\times B$ is defined to be $$A\times B=\{(a,b)\mid a\in A, b\in B\},$$ where $(a,b)$ is a specific set defined in some specific uniform way to ensure the defining property of the ordered product, namely that $(a,b)=(c,d)$ if and only if $a=c$ and $b=d$ (most common definition is the Kuratowski definition).

Given a family of sets $\{A_i\}_{i\in I}$, the product of the family, $\prod_{i\in I}A_i$, by contrast, is defined to be $$\prod_{i\in I}A_i = \left\{\left. f\colon I\to \bigcup_{i\in I}A_i\ \right|\, f(i)\in A_i\text{ for all }i\in I\right\}.$$

Thus, your set $X$ is $$X = \prod_{i\in\omega}A = \{f\colon\omega\to A\cup f(n)\in A\text{ for all }n\in A\},$$ while your other sets are $$\begin{align*} X\times Y &= \{(x,y)\mid x\in X, y\in Y\}\\ &= \left\{ (f,a) \mid f\colon\omega\to A, a\in A\right\}.\\ X\times Z &= \{(x,z) \mid x\in X, z\in Z\}\\ &= \left\{ (f,z)\mid f\colon\omega\to A, z\in A\times A\right\}\\ &=\left\{ \bigl( f,(a_1,a_2)\bigr)\mid f\colon\omega\to A, a_1,a_2\in A\right\}. \end{align*}$$

Thus, we have that it is not true that $X\times Y=X$; there is a natural bijection between them (by sending the pair $(f,a)$ to the function $g\colon\omega\to A$ given by $g(0)=a$ and $g(n+1) = f(n)$), but as sets there is no equality. Likewise, it is not true that $X\times Z=X$; again, there is a natural bijection between them, but they are not equal as sets. And of course there is no equality between $X\times (Y-Z) = X\times Y$ and $X$, either.

Thus, while it is true that we have that $Y-Z = Y$, it is not the case that $X\times (Y-Z)\neq (X\times Y)-(X\times Z)$, since $(X\times Y)\cap (X\times Z) =\varnothing$ (assuming some mild assumptions, e.g. Foundation, that ensure that no nonempty set intersects its cartesian square), we have that $(X\times Y)-(X\times Z) = X\times Y = X\times (Y-Z)$, exactly as expected.


Note that this is subtle. Technically, $A_1\times A_2$ is not even the same set as the product of the family $\{A_i\}_{i=1}^2$, namely $\prod_{i=1}^2 A_i$. Because the latter is the set of all functions $f\colon\{1,2\}\to A_1\cup A_2$ with $f(i)\in A_i$, while the former is the set of all ordered pairs $(a_1,a_2)$ with $a_1\in A_1$ and $a_2\in A_2$.

We usually elide this difference because there is a natural bijection between the two sets. But when we want to work with the sets as sets, which is what you are doing, we need to be careful and correctly distinguish between the two. This is the situation with your assertion that "$X\times Y = X$". They are not equal as sets: the left hand side is a set of ordered pairs, the right hand side is a set of functions with infinite domain. They are "naturally isomorphic", so when we want to use them for their properties we don't usually care about this distinction, but when working with them as sets we must be mindful of the difference.

Your write that are using the "infinite cartesian product". But think through what that could mean.

We usually define the binary cartesian product in terms of ordered pairs. Then we define functions in terms of ordered pairs. Then we define arbitrary products in terms of functions.

There is no set "$A\times B\times C$". We can either define it as $(A\times B)\times C$, or as $A\times(B\times C)$... or we can try to define what an "ordered triple" is. In order to play with this as a set, we have to pick one and do so explicitly. We can do this fairly straighforward for ordered triples, 4-tuples, etc... but then it gets complicated once you try to have an infinite set. What is an $\omega$-tuple as a set, exactly? That's why we avoid this issue entirely by using the definition as a set of functions.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .