12
$\begingroup$

Is every subset of a product a product of subsets ?

i.e Let $E$ and $F$ two non empty sets and we define the Cartesian product $E \times F$.

Now given a non empty subset $A$ of $E\times F$, can we write $A$ as the product of two subsets of $E$ and $F$: i.e is there $E_1 \subset E$ and $F_1 \subset F$ such that $$A=E_1 \times F_1$$

My idea is that this statement is false, and some counter-example I thought of is $$\{(x,y) \in \mathbb{R}^2, \,\, x^2+y^2=1\}$$ $$\{(x,1/x), \,\, x\in \mathbb{R}^*\}$$ But I could not find a way to prove we can't write these two sets as product of two subsets of $\mathbb{R}.$

$\endgroup$
1

10 Answers 10

49
$\begingroup$

Keep it simple. A minimal counterexample is the following: $$A=\{a,b\},B=\{d,e\}$$ We have

$$A\times B=\left\{(a, d), (a, e), (b, d), (b, e)\right\}$$ And the subset $$E=\left\{ (a, e), (b, d)\right\}$$ is not the cartesian product of two sets.

$\endgroup$
7
  • 10
    $\begingroup$ So you do not need $c$. $\endgroup$
    – Paul Frost
    Oct 15, 2020 at 16:47
  • 4
    $\begingroup$ $c$ is obviously an unnecessary letter. $\endgroup$ Oct 16, 2020 at 12:56
  • 1
    $\begingroup$ @DarkMalthorp Yes. We kan replase it with s or k or sometimes z, exzept in the konsonant kluster ch, which sounds a bit like j, so maybe we'll write it as jh and then we kan delete c. Jheerio! $\endgroup$
    – user253751
    Oct 16, 2020 at 16:38
  • 16
    $\begingroup$ @DarkMalthorp : I believe you mean "$c$ is obviously an unne$\,$essary letter." $\endgroup$ Oct 16, 2020 at 17:11
  • 6
    $\begingroup$ @gen-ℤreadytoperish: If the input sets are connected in $\mathbb{R}$, then their product is a (filled) rectangle in $\mathbb{R}^2$ - but then you can take a subset of that rectangle which is (say) a disk or annulus, and that shape is certainly not the cartesian product of anything. $\endgroup$
    – Kevin
    Oct 16, 2020 at 17:35
9
$\begingroup$

Assume $\{(x,y): x^2+y^2=1\}=A\times B$ for some $A,B\subseteq\mathbb{R}$. Let $x\in A$. Then for every $y\in B$ we have $x^2+y^2=1$. However, there can be at most two real numbers $y$ which satisfy $x^2+y^2=1$, and hence we conclude that $|B|\leq 2$. Similarly, $|A|\leq 2$. But this is obviously a contradiction, because $\{(x,y): x^2+y^2=1\}$ is an infinite set.

$\endgroup$
1
  • 2
    $\begingroup$ This seems unnecessarily complicated! Simpler to note that $(0,1)$ and $(1,0)$ are both on the given circle, so if the circle was equal to $A \times B$, we’d have to have $0 \in A$ (first co-ordinate of $(0,1)$) and $0 \in B$ (the second co-ordinate of $(1,0)$), and so $(0,0)$ would be in $A \times B$ — but it’s not in the circle. $\endgroup$ Oct 17, 2020 at 22:00
8
$\begingroup$

No. If $A \subset X \times Y$ has the form $A = E_1 \times F_1$, then

$$E_1 = \{ x \in E \mid \exists y \in F : (x,y) \in A\}, F_1 = \{ y \in F \mid \exists x \in E : (x,y) \in A\} .$$

In other words, $E_1$ is the image $\pi_E(A)$ of $A$ under the projection $\pi_E : E \times F \to E$, similarly $F_1 = \pi_F(A)$.

Your first set, the unit circle, has both images $= [-1,+1]$, but $[-1,+1] \times [-1,+1]$ is bigger than your set.

For your second set, the hyperbola with two branches, you get images $\mathbb R^*$ which again does not fit.

$\endgroup$
6
$\begingroup$

An easier counterexample is to let $E=F=\{0,1\}$ and $A=\{\langle 0,0\rangle,\langle 1,1\rangle\}$. If $A=E_1\times F_1$ for some $E_1\subseteq E$ and $F_1\subseteq F$, then clearly $0\in E_1$ and $0\in F_1$, and $1\in E_1$ and $1\in F_1$. But then $E_1=E=F=F_1$, so $$E_1\times F_1=E\times F\ne A\,.$$

Alternatively, you can argue from cardinality: $|A|=2$, and the subsets of $E$ and $F$ have cardinalities $0,1$, and $2$, so if $E_1\times F_1=A$, then one of $E_1$ and $F_1$ must have one element, and the other must have two. But if $|E_1|=1$, the members of $A$ must all have the same first component, while if $|F_1|=1$, they must all have the second component, and neither of these is in fact the case.

This second argument needs only a tiny modification to show that if $E$ and $F$ both have at least two points, then $E\times F$ has a subset that is not a product: if $e_1$ and $e_2$ are distinct points of $E$, and $f_1$ and $f_2$ are distinct points of $F$, the subset $\{\langle e_1,f_1\rangle,\langle e_2,f_2\rangle\}$ of $E\times F$ cannot be a product for the same reason that $A$ above is not a product.

$\endgroup$
6
$\begingroup$

$$ S = \{ (x,y)\in \mathbb{R}\times \mathbb{R} \vert y = x\} $$ is a subset of $\mathbb{R}\times \mathbb{R}$.

But $S$ is not a cartesian product. To see this, notice that: $$(0,0)\in S$$ $$(1,1)\in S$$ But $$(0,1)\notin S.$$

Therefore $S$ is not a cartesian product. $\Box$

FYI, this $S$ is sometimes called the diagonal subset of $\mathbb{R}\times \mathbb{R}$, and I think this name should make some sense to you if you draw the graph of $S$. Some of the other answers that have already been posted also use diagonal subsets (of sets other than $\mathbb{R}$), so this answer is really no different from theirs. But it might be easier to visualize.

$\endgroup$
5
$\begingroup$

For sets $S_1$ and $S_2$ with finite cardinalities $n_1$, $n_2$ respectively, $S_1 \times S_2$ has $2^{n_1n_2}$ subsets. For subsets that can be written as product of subsets, we have $2^{n_1}$ choices of what subset to take of $S_1$, and $2^{n_2}$ for $S_2$, but if one of them is the null set, then it doesn't matter what the other one is. So that gives $(2^{n_1}-1)(2^{n_2}-1)+1$ different subsets.

For infinite cardinalities, the two calculations yield the same cardinal number and thus don't immediately result in a contradiction, but we can still use the argument on finite subsets or a modulus that result in a finite number of classes.

$\endgroup$
3
  • $\begingroup$ Nice, I was about to post something similar. Anyway the subset of $S_1 \times S_2$ is supposed to be non-empty as well, so only $2^{n_1 n_2}-1$ subsets. Also for the second one I think it should be $(2^{n_1}-1)(2^{n_2}-1)$ (without the $+1$), because you multiply possibilities of non-empty subsets (try example with $S_1,S_2$ both having two elements, there are $9$ possible non-empty products of subsets, which corresponds to $(2^2-1)(2^2-1) )$. $\endgroup$
    – Sil
    Oct 27, 2020 at 23:23
  • $\begingroup$ @Sil The term "subset" is generally understood to include the entire set and the null set. To exclude them, we use the term "proper subset". I have the +1 for product of subsets because the null set is the Cartesian product of null sets. $\endgroup$ Oct 27, 2020 at 23:28
  • $\begingroup$ We don't care about empty subsets in this problem at all, so normally we would subtract those in the counting argument and compare $2^{n_1n_2}-1$ with $(2^{n_1}-1)(2^{n_2}-1)$. You are comparing $2^{n_1n_2}$ with $(2^{n_1}-1)(2^{n_2}-1)+1$ which is of course equivalent so it's not a big deal, but it might look confusing to some. $\endgroup$
    – Sil
    Oct 27, 2020 at 23:37
3
$\begingroup$

Visualizing -- or drawing -- a product of sets as a rectangular grid where the rows are labelled by one set and the columns by the other set helps a lot, I think.

Pick a subset of the rows and a subset of the columns, and look at the points that are in both subsets. That's a product of subsets. It always looks kind of rectangular, though possibly with some rows and columns removed from a complete rectangle.

Pick some random collection of points in your original grid. Does this collection of points look like a product of subsets? You should be able to find some collections that don't look rectangular at all. They can't be products of subsets.

I think this visualization is important, but the tricky part is making this reasoning into a precise argument.

One way to do it is to notice that in a product $A \times B$, if you pick $a \in A$ and look at all the elements of $B$ it's paired with, they're always the same ones, no matter which $a$ you pick.

In particular, if you have a set of pairs and $(a,x)$ is in your set and $(b,y)$ is in your set, then for it to be a product of subsets you know the elements that $a$ and $b$ are paired with need to be the same, so $(a,y)$ and $(b,x)$ need to be in there too. (But note that $(a,b)$ doesn't need to be.)

In the visualization, this means if a set of pairs has two opposite corners of a rectangle in it, then in order for it to be a product of subsets it must also have the other two corners of the rectangle. So subsets which contain fragments of rectangles with missing corners can't be written as a product.

$\endgroup$
2
$\begingroup$

Theorem. Let $E$ and $F$ be nonempty sets. If every subset of the product $E\times F$ is a product of sets, then either $E$ or $F$ has a single element.

Proof. Suppose $u,v\in F$, with $u\ne v$. Let $x\in E$; then, for every $x\in E$, we have that $A=\lbrace(a,u),(x,v)\rbrace=E_1\times F_1$. By definition, $a,x\in E_1$ and $u,v\in F_1$, so also $(x,u)\in E_1\times F_1$. Thus $x=a$. QED

$\endgroup$
1
$\begingroup$

Suppose your set $A$ could be written as a product $E_1 \times F_1$. Note then that $$E_1 \times F_1 = \bigcup_{e\in E_1} (e \times F_1)$$ but your candidates are very clearly not of this form.

(Yes, I know one should technically write $\{e\}\times F_1$, but $e\times F_1$ is a very common abuse of notation.)

$\endgroup$
1
  • $\begingroup$ @BenMillwood : Yes, this was out-of-context. That notation is used in similar circumstances as a sloppy abbreviation. I'll remove the note. $\endgroup$
    – MPW
    Oct 17, 2020 at 11:11
0
$\begingroup$

Assuming the product is $A\times A$, the subset of $A\times A$, $B$ is a product of subset of $A$ if $B$ is some form of "rectangle". That is to say, for any $x,y,d,e\in A$, $(d,x)\in B$ and $(e,y)\in B$ implies $(d,y)\in B$ and $(e,x)\in B$.

If the condition above is supposed, then for any pair of elements $C=(x,y)\times (d,e)$, always have the conclusion: $C$ is a subset of $A\times A$ and $C$ is a cartesian product. Also, let $x,y,d,e$ go through all the elements of $B$, so that is proved.

It should also be correct for cartesian of 2 different sets.

$\endgroup$

You must log in to answer this question.

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