Construct a sentence involving a model's function's injective character implicating the model's universe's infinity

Question

I am sorry for the lengthy title. I am having some trouble solving section (iv) of exercise 10 in section 4.2 of van Dalen's Logic and Structure. I will now reproduce it:

10. Let $\mathcal L$ have one unary function symbol.
(i) Write down a sentence $\phi$ such that $\mathcal M \models \phi \iff f^\mathcal M$ is a surjection.
(ii) Idem for an injection.
(iii) Idem for a bijection (permutation).
(iv) Use (ii) to formulate a sentence $\sigma$ such that (a) $\mathcal M \models \sigma \implies \mathcal M$ is infinite, (b) each infinite set can be expanded to a model of $\sigma$ (Dedekind).

Now the first three sections I have resolved so:
(i) $\phi_1 = \forall x \ \exists y \ (x = f(y))$.
(ii) $\phi_2 = \forall x \ \exists! y \ (x = f(y))$. Alternatively, $\phi_2 = \forall xx' \ (f(x)=f(x') \longrightarrow x=x')$.
(iii) $\phi_3 = \phi_1 \land \phi_2$.
(iv) Here is where the issue arises.
I do not really know what is expected of me here. In particular, I think the issue comes down to figuring out how to effectively rule out the existence of total 'circuits' within the model's universe (consider its elements as vertices and their functional relations $x \longmapsto f(x)$ as edges).
As an example, exercise 8 exhibited a sentence that performed what I refer to:
8. Let $\mathcal L$ have the binary predicate symbol $P$. $\sigma = \forall x \ \neg P(x, x) \land \forall xyz \ (P(x, y) \land P(y, z) \longrightarrow P(x, z)) \land \forall x \ \exists y \ P(x, y)$. Show that $\mathrm{Mod}(\sigma)$ contains only infinite models.
I have resolved this exercise already, and one can see in it that the relation's antireflexivity, coupled with its transitivity and the existence of a related term for all elements effectively prohibits the sort of 'closed circuits' that would inevitably form given a finite number $n$ of elements.
What I have been looking for (to no avail) is something analogous for this fourth section. However, it may very well be that this is not the way to do it at all, so any such clarification or help would be extremely appreciated.
I thought maybe adding to $\phi_2$ some sentence of the sort $\exists x \ \nexists y \ (x = f(y))$, effectively affirming the existence of some element outside any circuit could help. It seemed especially promising when I considered what such an element's image would be, noticing that it could not 'point' to any element contained within our problematic circuits and so would need to point to a 'new' element within our universe. However, such a promising start readily falls apart when considering the image's image, as such would have no issue pointing to itself and thus reproducing the circuit problematic wholly anew.
Thus, I stand here, with no ideas yet... I would really appreciate any help in solving this problem, and I thank any such help in advance.

Answer 1

The key is to use the idea of being Dedekind-infinite, hence the "(Dedekind)" at the end of the exercise.

A set $X$ is Dedekind-infinite if there exists a non-surjective injection $f: X \to X$.

I think you are focusing too much on the issue of "closed cycles", because you have actually already mentioned the correct solution. Namely taking $\sigma$ to be the conjunction of "$f$ is injective" (i.e. your $\phi_2$) and "$f$ is not surjective" (i.e. the formula $\exists x \not \exists y(x = f(y))$ you wrote later). That way $\sigma$ expresses that $\mathcal{M}$ is Dedekind-infinite. So can you now prove that this is the same as being infinite, using the two hints below?

Show that any injective function $f: X \to X$, where $X$ is finite, must be surjective. Conclude that Dedekind-infinite sets are infinite.

This takes care of the first part of (iv). Now for the "(b)" part of (iv).

Let $X$ be an infinite set. Construct an injection $f: X \to X$ that is not surjective. Conclude that infinite sets are Dedekind-infinite.

This last hint requires the axiom of choice. If you do not know what that is, or get stuck on how to use it, you can instead just assume what is under the spoiler below.

It follows from the axiom of choice that any infinite set $X$ contains a subset that is in bijection with $\mathbb{N}$. That is, we can find a subset $\{ x_0, x_1, \ldots \} \subseteq X$ that is enumerated by the natural numbers.

---

If you really want to find your infinite chain of elements $x, f(x), f(f(x)), \ldots$, here is how you can do that. We need the assumption that $f$ is injective and not surjective. Let $x$ be such that it is not in the image of $f$. Then I claim that for all $n, m \in \mathbb{N}$ with $n \neq m$ we have $f^n(x) \neq f^m(x)$, where $f^n(x)$ denotes $f$ applied $n$ times to $x$ (and $f^0(x) = x$). In other words, we would get an infinite chain $x, f(x), f(f(x)), \ldots$. Indeed, assume for a contradiction that $f^n(x) = f^m(x)$ for some $n \neq m$ and assume without loss of generality that $n < m$. Applying injectivity $n$ times we get $x = f^{m-n}(x)$, and as $m > n$ this contradicts the assumption that $x$ is not in the image of $f$.