I am reading the solution of b(ii):
Solution:
I am very confused from the start of the solution. To show isomorphism we want to prove there is a bijective function $\alpha: \mathcal A_2\to \mathcal B_2$ s.t. for all $a_1,a_2\in \mathcal A_2$, $a_1 =_A a_2$ iff $\alpha(a)=_B \alpha(b)$? I am not sure I understand the solution correctly: $f$ is inkective in both structures, and 1 is the unique fixed point. But then, even if $x\in im f$ shouldn't $x, f(x), f(f(x))...$ still be distinct? How is this enough to give an isomorphism? Does this try to construct $\alpha$ by $\alpha(f_A(x))=f_B(x)$ if $x$ is one of $y,f_A(y),f_A(f_A(y))...$ for some fixed $y$? If it is this case, what will happen to $f_A(y')$ for $y'\neq y$?
Thank you very much!
Maybe a picture will help. Here is $A_2$: $$\require{AMScd}\begin{CD} 1 \\ \\ 2 @>{f}>> 4 @>{f}>> 16 @>{f}>> \dots\\\\ 3 @>{f}>> 9 @>{f}>> 81 @>{f}>> \dots\\\\ 5 @>{f}>> 25 @>{f}>> 625 @>{f}>>\dots \\\\ \vdots & & \vdots & & \vdots \end{CD}$$
... and here is $B_2$: $$\begin{CD} 1 \\ \\ 2 @>{f}>> 8 @>{f}>> 512 @>{f}>>\dots\\\\ 3 @>{f}>> 27 @>{f}>> 19683 @>{f}>>\dots\\\\ 4 @>{f}>> 64 @>{f}>> 262144 @>{f}>>\dots\\\\ \vdots & & \vdots & & \vdots \end{CD}$$ Isn't it clear that they're isomorphic?
To write a careful proof, the key point is the parenthetical at the end: any bijection between then points not in the image (those are the leftmost columns, excluding $1$, in my pictures of $A_2$ and $B_2$) extends in a unique way to an isomorphism.
Let $C\subseteq A_2$ be the set of points not in the image of $f$. Note that $C$ is an infinite subset of $\mathbb{N}$ (there are infinitely many non-squares in $\mathbb{N}$), hence $C$ is countably infinite.
Let $D\subseteq B_2$ be the set of points not in the image of $f$. Again, $D$ is an infinite subset of $\mathbb{N}$ (there are infinitely many non-cubes in $\mathbb{N}$), hence $D$ is countably infinite.
Since $C$ and $D$ are both countably infinite, we can fix a bijection $\beta\colon C\to D$.
Now we'd like to extend $\beta$ to an isomorphism. Let $n\in A_2$ with $n\neq 1$. Then $n = f^k(c)$ for some unique $k\in \mathbb{N}$ and $c\in C$. [Try to prove this yourself. In the solution, this is stated as "the points $x$, $f(x)$, $f(f(x))$, $\dots$ are all distinct and sets like this partition $\mathbb{N}$ (apart from the fixed point".] Note that we allow $k = 0$, in the case $n = c\in C$.
If we want $\alpha$ to be an isomorphism and extend $\beta$, $\alpha$ must map the unique fixed point to the unique fixed point ($1\mapsto 1$), and we must set $\alpha(f^k(c)) = f^k(\alpha(c)) = f^k(\beta(c))$. So there is only one possible way to define $\alpha$: $$\alpha(x) = \begin{cases} 1 & \text{if }x = 1\\ f^k(\beta(c)) &\text{if }x = f^k(c)\text{ with }c\in C\end{cases}$$
I'll leave it to you to check that $\alpha$ is an isomorphism.