# Are the following two definitions of infinite sets logically equivalent?

Dedekind-Infinite Set. A set $$S$$ is called a Dedekind-Infinite Set if there exists a bijection $$f:S\to T$$ where $$\emptyset \subset T\subset S$$.

I was wondering if the following definition is logically equivalent to the above definition.

Descartes-Infinite Set. A set $$S$$ is called an Descartes-Infinite Set if $$S$$ is not a singleton set and there exists a bijection $$f:S\to S\times S$$.

My questions are the following,

• They're certainly equivalent over ZFC. – goblin GONE Apr 18 '16 at 8:57
• @goblin: But how can we prove it? – user170039 Apr 18 '16 at 9:01
• I think $\kappa^2=\kappa⟺\kappa = 0 \vee \kappa = 1 \vee \kappa \geq \aleph_0$ is probably a standard exercise, so have a look at your favorite introduction to set theory or cardinal numbers and you'll probably find a proof. I'm guessing the standard proof probably involves first proving $ℵ^2_α=ℵ_α$ over ZF, and then using the axiom of choice to get the full result. – goblin GONE Apr 18 '16 at 11:45

It’s true in $\mathsf{ZF}$ that every Descartes-infinite set is Dedekind-infinite. Suppose that $S$ is Descartes-infinite; then there is a bijection $f:S\times S\to S$, and

$$g:S\to S:x\mapsto f(\langle x,x\rangle)$$

is an injection such that $g[S]\subsetneqq S$, so $S$ is Dedekind-infinite.

In this answer Asaf Karagila shows that it’s a theorem of $\mathsf{ZF}$ that the axiom of choice is equivalent to the statement that each infinite set is Descartes-infinite. (By infinite here I mean that there is no bijection between the set and any finite ordinal.) Thus, in $\mathsf{ZFC}$ the notions of infinite, Dedekind-infinite, and Descartes-infinite coincide.

In the absence of $\mathsf{AC}$, however, there can be sets that are Dedekind-infinite but Descartes-finite. Let $X$ be an infinite, Dedekind-finite set, and let $S$ be the disjoint union $X\sqcup\omega$; clearly $S$ is Dedekind-infinite. Suppose that $f:S\to S\times S$ is a bijection.

Let $N=\omega\cap f^{-1}[X\times X]$, and suppose that $N$ is infinite. If $N_x=\{n\in N:f(n)\in\{x\}\times X\}$ is infinite for some $x\in X$, it’s easy to construct an injection from $N_x$ and hence from $\omega$ into $X$, contradicting the Dedekind-finiteness of $X$, so $N_x$ is finite for each $x\in X$. Thus, if we set $Y=\{x\in X:N_x\ne\varnothing\}$, then $\{N_x:x\in Y\}$ is a partition of $N$, and therefore the map

$$g:Y\to\omega:x\mapsto\min N_x$$

is an injection. Moreover, $Y$ is infinite, so $g^{-1}$ is an injection of the infinite set $g[Y]\subseteq\omega$ into $X$, so there is an injection of $\omega$ into $X$, again contradicting the Dedekind-finiteness of $X$. It follows that $N$ must be finite and hence that $N_x=\varnothing$ for some $x\in X$. Then the function

$$h:X\to X:y\mapsto f^{-1}(\langle x,y\rangle)$$

is an injection from $X$ to a proper subset of $X$, which is impossible. Thus, there is no bijection $f:S\times S\to S$, and $S$ is Descartes-finite.

• So the two notions of infinite coincide in $\sf{TG}$ and $\sf{NBG}$, right? But what about my third question? – user170039 Apr 19 '16 at 12:17
• @user170039: Yes, equivalence in $\mathsf{ZFC}$ implies equivalence in the other two theories. I very much doubt that the answer to your third question is yes, but I don't know for sure. – Brian M. Scott Apr 19 '16 at 12:25
• Actually the motivation for the third question came when I was trying to find a bijection between $\mathbb{N}$ and $\mathbb{N}\times \mathbb{N}$. So, I was wondering if there is really any general way to define bijection from $X$ to $X\times X$. – user170039 Apr 19 '16 at 12:36
• @user170039: For well-ordered $X$ there is, but in general I don't think so. – Brian M. Scott Apr 19 '16 at 12:45
• Can you mention some reference(s)? – user170039 Apr 19 '16 at 13:07