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,

  • Are the two definitions logically equivalent in any model of $\sf{ZFC}$,$\sf{TG}$ or $\sf{NBG}$?

  • Does there exist any model(s) of Set Theory in which these two definitions are not logically equivalent?

  • Suppose it is known that $S$ is a Descartes-Infinite set. So there exists a bijection between $S$ and $S\times S$. My question is, is there any way to explicitly define the bijection?

  • $\begingroup$ They're certainly equivalent over ZFC. $\endgroup$ – goblin GONE Apr 18 '16 at 8:57
  • $\begingroup$ @goblin: But how can we prove it? $\endgroup$ – user170039 Apr 18 '16 at 9:01
  • $\begingroup$ 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. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ So the two notions of infinite coincide in $\sf{TG}$ and $\sf{NBG}$, right? But what about my third question? $\endgroup$ – user170039 Apr 19 '16 at 12:17
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Apr 19 '16 at 12:25
  • $\begingroup$ 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$. $\endgroup$ – user170039 Apr 19 '16 at 12:36
  • $\begingroup$ @user170039: For well-ordered $X$ there is, but in general I don't think so. $\endgroup$ – Brian M. Scott Apr 19 '16 at 12:45
  • $\begingroup$ Can you mention some reference(s)? $\endgroup$ – user170039 Apr 19 '16 at 13:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy