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?)

  • 1
    $\begingroup$ 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. $\endgroup$ – 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.

| cite | improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.