Construct a sequence of choice functions such that their defined well-orders are not isomorphic to each other

Question

As a homework exercise I got the following definitions:

We call $f$ a choice function from $\wp(\Bbb{N}) \setminus \{\varnothing\}$ to $\Bbb{N}$ if for every $A \in \wp(\Bbb{N}) \setminus \{\varnothing\}$, we have that $f(A)\in A$.
If $f$ is such a choice function for $\wp(\Bbb{N}) \setminus \{\varnothing\}$, then there exists exactly one well-order $(\Bbb{N}, <_f)$ such that for every $n \in \Bbb{N}$ we have that $n = f(\Bbb{N} \setminus \{m \in \Bbb{N} | m <_f n\})$.

The question that followed is:

Find a sequence $f_0, f_1, \dots$ of choice functions for $\wp(\Bbb{N}) \setminus \{\varnothing\}$ such that for every $i < j$, $(\Bbb{N}, <_{f_i})$ is not isomorphic to $(\Bbb{N}, <_{f_j})$

I am having trouble with how I need to start such a construction of a sequence since every function defines a different well-order.

Can someone give me a hint in the right direction so that I know what I need to do so that I can construct such a sequence?

Answer 1

Do the problem in reverse: start with the well-orders and use them to get the choice functions.

Suppose that $\preceq$ is a well-order on $\Bbb N$. For non-empty $A\subseteq\Bbb N$ let $\min_\preceq A$ be the unique $a_0\in A$ such that $a_0\preceq a$ for each $a\in A$. Then $\min_\preceq$ is a choice function on $\wp(\Bbb N)\setminus\{\varnothing\}$, and $$n=\min_\preceq(\Bbb N\setminus\{m\in\Bbb N:m\prec n\})$$ for each $n\in\Bbb N$. Thus, you can start by finding a sequence $\preceq_0,\preceq_1,\ldots$ of pairwise non-isomorphic well-orders of $\Bbb N$ and use them to define the desired choice functions $\min_{\preceq_0},\min_{\preceq_1},\ldots\;$.

In the comments spaceisdarkgreen suggested one way to generate non-isomorphic well-orders on $\Bbb N$. I’m spoiler-protecting another below.

Fix an integer $m\ge 2$. Each $n\in\Bbb N$ can be written uniquely as $n=q_nm+r_n$, where $q_n,r_n\in\Bbb N$ and $r_n<m$. (For instance, if $m=5$, then $q_{13}=2$ and $r_{13}=3$, since $13=2\cdot5+3$. (It’s just quotient and remainder.) Define an order $\preceq_m$ on $\Bbb N$ as follows: $k\preceq_mn$ if and only if $r_k<r_n$, or $r_k=r_n$ and $q_k\le q_n$. Then $\preceq_m$ is a well-order, and $\langle\Bbb N,\preceq_\ell\rangle$ is isomorphic to $\langle\Bbb N\preceq_m\rangle$ if and only if $\ell=m$. (You’d have to verify these assertions, of course.)