This is from Tao's Analysis I:
So far I managed to show (inductively) that these sets do exist for for every $\mathit{N}\in\mathbb{N}$ but, I'm finding it hard to show they're unique.
One of the things I'm (also) trying to proof is that $\mathit{N}\in\mathit{A_N}$, but I'm stuck on that one too.
I'm not allowed to use the ordering of the natural numbers.
On
Let $A_N, B_N$ be such pair,
Let $m=\min B_N$(which exists because $B_N$ is not empty),
If $B_N≠\{n∈\Bbb N\mid n≥m\}$, then let $k$ be the minimal value that is in the right hand side, but not in the left hand side, this numbers is greater or equal to $m+1$, so $k-1≥m$, by $k$ being minimal it means $k-1∈B_N$ which implies $k∈B_N$, contradiction, so $B_N=\{n∈\Bbb N\mid n≥m\}$.
So $(A_N, B_N)=(\{n∈\Bbb N\mid n<m\},\{n∈\Bbb N\mid n≥m\})$, for some $m∈\Bbb N$.
I claim that $m=N+1$, it is obvious that $0<m≤N+1$, assume $0<m<N+1$, i.e. $0<m≤N$, we have that $m-1<N$ and $m-1∈A_N$, so $m∈A_N$ which implies $m∉B_N$, which is impossible.
Thus $(A_N, B_N)=(\{n∈\Bbb N\mid n<N+1\},\{n∈\Bbb N\mid n≥N+1\})$ is the unique solution
Suppose $(A_N, B_N)$ and $(A_N', B_N')$ are two pairs satisfying the properties (a)-(f).
We prove by induction that for any $n \in \mathbf N$, if $n \in A_N$ then $n \in A_N'$ and if $n \in B_N$ then $n \in B_N'$. This implies that $A_N \subseteq A_N'$ and $B_N \subseteq B_N'$, and by switching the roles of the two pairs we obtain that $A_N = A_N'$ and $B_N = B_N'$.
Base case. Consider $n = 0$. Since $0 \in A_N$ and $0 \in A_N'$ by (c), the statement is true.
Inductive step. Suppose the statement is true for $k$, i.e., if $k \in A_N$ then $k \in A_N'$ and if $k \in B_N$ then $k \in B_N'$. Consider $n = k{++}$. We distinguish three cases:
Since $A_N \cup B_N = \mathbf N$ by (b), this is enough to prove the statement for $k{++}$.