10
$\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

47
$\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
  • 9
    $\begingroup$ So you do not need $c$. $\endgroup$ – Paul Frost Oct 15 '20 at 16:47
  • 3
    $\begingroup$ $c$ is obviously an unnecessary letter. $\endgroup$ – Dark Malthorp Oct 16 '20 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 '20 at 16:38
  • 16
    $\begingroup$ @DarkMalthorp : I believe you mean "$c$ is obviously an unne$\,$essary letter." $\endgroup$ – Eric Towers Oct 16 '20 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 '20 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$ – Peter LeFanu Lumsdaine Oct 17 '20 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 '20 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$ – Acccumulation Oct 27 '20 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 '20 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 '20 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.