# Is every subset of a product a product of subsets?

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}.$$

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.

• So you do not need $c$. – Paul Frost Oct 15 '20 at 16:47
• $c$ is obviously an unnecessary letter. – Dark Malthorp Oct 16 '20 at 12:56
• @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! – user253751 Oct 16 '20 at 16:38
• @DarkMalthorp : I believe you mean "$c$ is obviously an unne$\,$essary letter." – Eric Towers Oct 16 '20 at 17:11
• @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. – Kevin Oct 16 '20 at 17:35

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.

• 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. – Peter LeFanu Lumsdaine Oct 17 '20 at 22:00

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.

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.

$$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.

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.

• 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) )$. – Sil Oct 27 '20 at 23:23
• @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. – Acccumulation Oct 27 '20 at 23:28
• 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. – Sil Oct 27 '20 at 23:37

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.

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

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.)

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

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.