= Solution
Suppose $h:\omega\hookrightarrow X$ is an <injection>. Shift its image by defining
$$
g(h(n))=h(n+1),\qquad g(x)=x\quad(x\notin h[\omega]).
$$
The two pieces have disjoint images, so $g$ is injective, but $h(0)$ is omitted. Thus $g$ is not surjective.
Conversely, let $g:X\to X$ be an <injection> which omits some $a\in X$. The <natural-number recursion theorem> defines $h(0)=a$, $h(n+1)=g(h(n))$. If $h(m)=h(n)$ with $m<n$, repeated injectivity cancels $m$ iterations and gives $a=g^{n-m}(a)$, putting $a$ in the image of $g$, a contradiction. Hence $h$ is injective. Therefore
$$
\boxed{\omega\preceq X\iff X\text{ admits an injective nonsurjective self-map}.}
$$
Choosing one witness $a$ from a single known nonempty set uses no <axiom of choice>. This is the <Dedekind-infinite characterization>.
Back to article page
