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.

Solution 1:

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.

Solution 2:

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