9
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ It doesn't make sense to say $A\subseteq A\times B$ because $A$ would live in a smaller dimension than $A\times B$. $\endgroup$ – Gregory Grant Nov 6 '15 at 20:19
  • $\begingroup$ 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$. $\endgroup$ – Gregory Grant Nov 6 '15 at 20:21
  • $\begingroup$ @GregoryGrant I'm not convinced that either of those intuitions works for infinite products. $\endgroup$ – Chappers Nov 6 '15 at 20:23
  • 2
    $\begingroup$ @Gregory: That has nothing to do with anything here. $\endgroup$ – Asaf Karagila Nov 6 '15 at 20:32
  • 6
    $\begingroup$ @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. $\endgroup$ – Asaf Karagila Nov 6 '15 at 20:36
6
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

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

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.