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}.$
 A: 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.
A: 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.
A: 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.
A: $$
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.
A: 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.
A: 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.
A: 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.
A: 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
A: 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.)
A: 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.
