Infinite Dedekind Finite sets

I realized that i have used argument below many times before and I'm not sure if it is true.

Let $A=\{n\in \omega|\Phi(n)\}$.

Then $A\preceq \aleph_0$.

(i)Suppose $A$ is dedekind-infinite and find a contradiction (Dedekind-infinite here refers to a set when there exists a injective function $f:\omega_0 \rightarrow A$)

(ii)Thus $A\prec \aleph_0$.

Here, after the step(ii), could $A$ possibly be an infinite-dedekind finite set? That is $A$ may not have a maximal element? (Not a von-neumann ordinal?)

• You probably meant to write $A=\{\varphi(n)\mid n\in\omega\}$, otherwise $A$ is just a subset of $\omega$ and has to be countable or finite. – Asaf Karagila Nov 12 '12 at 13:41

If $A$ can be written as an image of $\omega$ then $A$ is either finite or countably infinite. If we assume that it is infinite then it has to be Dedekind-infinite.

The reason is that surjections from well-ordered sets can be inversed.

Note also that $A=\{n\in\omega\mid\varphi(n)\}$ is a subset of $\omega$ and therefore can only be Dedekind-finite if it is finite.

Let us make some clarifications too, while we're at it:

1. Dedekind-finite means that there is no injection from $\omega$ into $A$.
2. If $A\subseteq\omega$ then $A$ is Dedekind-finite if and only if $A$ is finite.
3. If $A\subseteq\omega$ then $A$ has a maximal element if and only if $A$ is finite.
4. If $A\subseteq\omega$ then $A$ is a von Neumann ordinal if and only if $A$ is an initial segment of $\omega$.
5. If $\alpha$ is a von Neumann ordinal then $\alpha$ is Dedekind-finite if and only if it is finite.

If you show that $A\subseteq\omega$ is bounded then it is finite. If you show that it is not Dedekind-infinite then it is finite, and bounded. If you have shown that there is some $k<m$ such that $k\notin A$ and $m\in A$ then $A$ is not an ordinal itself.