Is it possible that $A\subseteq A\times B$ for some non empty sets $A,B$?

I was wondering if there exist two non empty sets $A,B$ such that $$A\subseteq A\times B.$$ I know that always exists a subset of $A\times B$ with the same cardinality of $A$, but i'm requesting here that $A$ is a subset of $A\times B$ without using any identification map. At first i thought that this was not possible because $A$ and $B\times A$ are two sets containing different kind of elements: the second contains pairs like $(a,b)$ with $a\in A, b\in B$; the first just single elements $a\in A$. Moreover, suppose $A\subseteq A\times B$ holds and take $a \in A$. Then $a=(a_1,b_1)$ for some $a_1 \in A, b_1\in B$. For the same reason $a_1=(a_2,b_2)$ and so $a=((a_2,b_2),b_1)$. Following this argument I got some sort of recursive infinite definition for $a$ that made me suspect something is wrong. However if I take $$A=\mathbb{N}^{\mathbb{N}} ;B=\mathbb{N}$$ is it true that $A=A\times B$ or I'm missing something? Moreover, if $A\subseteq A\times B$ can be true, are there other examples?

edit: I add another strange example: take $A=\bigcup_{i=1}^{\infty} \mathbb{N}^i$ and $B=\mathbb{N}$, then $A \times B \subset A$. This makes me think that maybe exists also an example for the other inclusion.

• It doesn't make sense to say $A\subseteq A\times B$ because $A$ would live in a smaller dimension than $A\times B$. – Gregory Grant Nov 6 '15 at 20:19
• You can identify $A$ with a subset of $A\times B$, like for example you can fix $b\in B$ and then do $a\mapsto (a,b)$, but without any such association $A$ cannot be a subset of $A\times B$. – Gregory Grant Nov 6 '15 at 20:21
• @GregoryGrant I'm not convinced that either of those intuitions works for infinite products. – Chappers Nov 6 '15 at 20:23
• @Gregory: That has nothing to do with anything here. – Asaf Karagila Nov 6 '15 at 20:32
• @Gregory: Yes, there is. $A\times B$ is a set of ordered pairs. $A$ is a set. It makes perfect sense to ask whether or not $A\subseteq A\times B$. It makes no sense if you think about $A$ being a set of real numbers or whatever. But sets are not limits to being sets of real numbers. – Asaf Karagila Nov 6 '15 at 20:36

2 Answers

The existence of sets $A$ and $B$ with $A\subseteq A\times B$ contradicts the axiom of regularity (or the axiom of foundation.) The precise proof depends on which construction of $A\times B$ you prefer. We will use the most common formulation, in which we represent the ordered pair $(a,b)$ by the set $\{\{a\},\{a,b\}\}$, but the proof easily adapts to other constructions.

Suppose $A\subseteq A\times B$. Since the sets are nonempty, we can pick $a_0\in A$. By assumption, we can write $a_0=(a_1,b_1)$ with $a_1\in A$ and $b_1\in B$, and continuing on we can write $a_i=(a_{i+1},b_{i+1})$. Under our formulation of the cartesian product, this means $a_{i+1}\in \{a_{i+1}\}\in a_i$.

This gives an infinite descending sequence $$\cdots \in a_{i+1}\in \{a_{i+1}\}\in a_i \in \{a_i\}\in a_{i-1}\cdots \in a_0,$$ contradicting the axiom of foundation.

An element of $\Bbb N^{\Bbb N}$ is an infinite sequence of natural numbers. Buy what do we mean by a sequence. $n_0,n_1,\ldots n_k,\ldots$ is really nothing more than a function $f:\Bbb N\to\Bbb N$. For example, $f(k)=n_k$.

So, $\Bbb N^{\Bbb N}=\{f:\Bbb N\to\Bbb N\}$. So, what is an element of $A\times\Bbb N$? It is a pair $(f,n)$. The are not elements of $A$.

• I see wich is the problem. So is $A \subseteq A \times B$ always false? If so, how can one prove it? – mrprottolo Nov 6 '15 at 20:33
• It's neither true nor false, the question itself does not make sense. – Gregory Grant Nov 6 '15 at 20:35
• @GregoryGrant Given any two sets $A$ and $B$, we can always ask if $A\subseteq B$. – Tim Raczkowski Nov 6 '15 at 20:36
• Well okay then it's trivially false, and not very interesting. – Gregory Grant Nov 6 '15 at 20:41
• @GregoryGrant Well it is inuitively obvious, but proving it rigorously is not so easy. – Tim Raczkowski Nov 6 '15 at 20:47