Franklin's Notes


IDF and amorphous sets

An infinite-Dedekind-finite set, or an IDF set for short, is a set which is infinite but Dedekind-finite . No such sets exist if the Axiom of Choice or any of its equivalents is true - however (according to Sierpinski), the failure of AC does not imply the existence of such sets.

An amorphous set is a set which is infinite but cannot be partitioned into two infinite subsets. That is, $A$ is amorphous if and only if there do not exist subsets $A_1,A_2\subset A$ such that

1. $A_1\cap A_2 = \varnothing$
2. $A_1\cup A_2 = A$
3. $A_1$ and $A_2$ are both infinite

The amorphous sets comprise a subclass of the IDF sets.

Theorem 1. Every amorphous set is IDF.

Proof. Suppose the set $A$ is infinite but not Dedekind-finite, so that it contains a countable subset $A_1$. If we let $A_2=A\backslash A_1$, then $A_1=A_1\cup A_2$ with $A_1\cap A_2 = \varnothing$. If $A_2$ is finite, then $A=A_1\cup A_2$ has the cardinality of $\mathbb N$, and is therefore not amorphous. On the other hand, if $A_2$ is infinite, $A=A_1\cup A_2$ is a partition of $A$ into two infinite sets, meaning that $A$ fails to be amorphous in this case as well. Hence, a Dedekind-infinite set $A$ cannot be amorphous, meaning that all amorphous sets are Dedekind-finite and therefore IDF. $\blacksquare$

IDF sets also have the strange property that their cardinality is incomparable with the countable cardinality $\aleph_0=|\mathbb N|$. This means that the existence of IDF sets contradicts Trichotomy .

Theorem 2. If $A$ is IDF, then $|A|\not\leq |\mathbb N|$ and $|\mathbb N|\not\leq|A|$.

Proof. If $A$ is IDF, then clearly $|\mathbb N|\not\leq |A|$, because otherwise $A$ would be Dedekind-infinite by definition. Suppose, on the other hand, that $|A|\leq |\mathbb N|$, so that there exists an injection $f:A\to\mathbb N$. Since $\mathbb{N}$ is well-ordered , we may define a sequence of natural numbers recursively by letting $x_1=f(a)$, where $a\in A$ is arbitrarily chosen, and letting $x_{n+1}$ be the smallest element of $\mathbb N$ greater than $x_n$ that is the image under $f$ of some element of $A$. Then the function $g:\mathbb N\to A$ defined by $g(n)=f^{-1}(x_n)$ would be an injection, meaning that $A$ would be Dedekind-infinite, which is a contradiction. Hence, $|A|\not\leq|\mathbb N|$, as claimed. $\blacksquare$

Question. Does there exist any total order on an IDF set? If so, what can be said about such an order?

set-theory

cardinality

infinitude

nonstandard-model

back to home page