Shewing that every proper elementary extension of a structure is uncountable Let $\alpha$ be a bijection between the set of finite sequences of $0$s and $1$s and ${\bf N}$ and for $f : {\bf N} \to \{0,1\}$ let $f^* : {\bf N} \to {\bf N}$ be given by $f^*(n) = \alpha(f\mid\{0,\dots, n-1\})$
Can there be a proper countable elementary extension of the first order structure $({\bf N}, (f^*)_{f: {\bf N} \to \{0,1\})}$?
 A: This is an example of a general very useful heuristic, which comes up a lot in nonstandard models of arithmetic: the binary tree $T_\alpha$ of height $\alpha$, for $\alpha$ a nonstandard natural number, is uncountable, and paths through the usual binary tree $2^{<\mathbb{N}}$ are represented by nodes of $T_\alpha$. Other applications of this basic idea include the result in computability theory that the standard system of any nonstandard model of arithmetic is a Scott set.
First, let's look at a slightly easier problem: we throw "$<$" into the language, and the structure we're thinking about is $\mathcal{N}=(\mathbb{N}; (f^*)_{f:\mathbb{N}\rightarrow 2}, <)$.
Now suppose $\mathcal{A}$ is a proper elementary extension of your structure, and $C$ is a "nonstandard natural number" - that is, an element of the domain of $\mathcal{A}$ which is not in $\mathbb{N}$. What can you say about $f^*(C)$ versus $g^*(C)$ for $f, g:\mathbb{N}\rightarrow\{0, 1\}$ distinct? HINT: if they're distinct, then $f(k)\not=g(k)$ for some $k\in\mathbb{N}$; think about what $\mathcal{N}$ thinks about $f^*(n)$ versus $g^*(n)$ for $n>k$. Now, what can you say about the nonstandard element $C$, compared with $k$? 

This argument used the presence of the ordering; now, do you see how to get rid of that? HINT: can you express "Unless $n\le k$", for $k$ fixed, without referring to the ordering on $\mathbb{N}$?
