10
$\begingroup$

We call a set $X$

  • Dedekind-infinite if there is an injective map $f:X\to X$ that is not surjective,
  • addititvely infinite if $X \neq\emptyset$ and there is an injective map $f:\big((X\times\{1\})\cup(X\times\{2\})\big) \to X$, and
  • multiplicatively infinite if $X$ contains $2$ different points and there is an injective map $f:X\times X \to X$.

In ${\sf (ZF)}$, multiplicative infiniteness implies additive infiniteness, which in turn implies Dedekind infiniteness.

Are some or all of these definitions equivalent in ${\sf (ZF)}$?

$\endgroup$
3
  • 3
    $\begingroup$ For additively and multiplicatively, one might as well say there is a bijective map, since we have injections the other direction. So you are saying $X=X\cdot 2$ and $X^2=X$, respectively. $\endgroup$ Commented May 28 at 13:55
  • 2
    $\begingroup$ Have you checked the Wikipedia article on finiteness? There is a reference to Levy [1958] there. $\endgroup$ Commented May 28 at 16:02
  • 1
    $\begingroup$ @JoelDavidHamkins I also considered adding : $X$ is "+1-infinite" if there is a bijection between $X$ and $X\cup\{X\}$, so $X= X+1$ - but this is the same as Dedekind-infiniteness, I suppose $\endgroup$ Commented May 28 at 19:02

2 Answers 2

10
$\begingroup$

A theorem of Tarski says that the statement "all infinite sets are multiplicatively infinite" implies the axiom of choice (AC). But a theorem of Sageev says that "all infinite sets are additively infinite" doesn't imply AC. So multiplicative and additive infinity are not provably equivalent in ZF.

As for Dedekind vs. additive infinity, consider first the basic Fraenkel model, which has an amorphous set $A$ of atoms. Then the disjoint union $\omega\cup A$ is Dedekind infinite because of the $\omega$ part. But it is not additively infinite because there are very few maps out of an amorphous set. More precisely, given two copies of $\omega\cup A$, any map of either copy of $A$ into the other $A$ or into either $\omega$ is either constant or a bijection except at finitely many points.

Finally, to get the result for ZF, i.e., without atoms, it suffices to apply the Jech-Sochor metatheorem, because the result is just a single example, hence of bounded rank.

$\endgroup$
7
$\begingroup$

But a theorem of Sageev says that $\ldots$

I don't want to alter Andreas's answer, but I want to add a reference to one of the results he mentions.

Sageev, Gershon
An independence result concerning the axiom of choice.
Ann. Math. Logic 8 (1975), 1-184.

Here are the first few lines of the Math Review (written by Andreas Blass) for this 184-page paper:

In 1924, A. Tarski [Fund. Math. 5 (1924), 147–154; Jbuch 50, 135] asked whether the idemmultiple hypothesis, $2m=m$ for all infinite cardinals $m$, implies the axiom of choice. The author answers this question negatively by constructing a model of Zermelo-Fraenkel set theory in which the idemmultiple hypothesis, the ordering principle (every set can be linearly ordered), and the axiom of $\aleph_0$-multiple choice (for any family of nonempty sets, there is a function assigning to each set in the family a countable subset) hold but there is a countable family of sets of reals with no choice function.

The model constructed in Sageev's paper is called $N$. On page 148, Sageev proves

9.30. Lemma. Every $z \in N$ is orderable in $N$; and if $z$ is infinite, then $z$ is idemmultiple in $N$.

A function $I$ is defined in Notation 10.00 on page 164. Then, on pages 181-182, Sageev states and proves:

10.60. Lemma. There is no choice function in $N$ for the set $\{I(i)\;|\; i < \omega\}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .