There are a few possibilities, but here is the one approach. Even the starting point—the set of natural numbers $\mathbb{N}$—can be defined in several ways, but the standard definition takes $\mathbb{N}$ to be the set of finite von Neumann ordinals. Let us assume that we do have a set $\mathbb{N}$, a constant $0$, a unary operation $s$, and binary operations $+$ and $\cdot$ satisfying the axioms of second-order Peano arithmetic.
First, we need to construct the set of integers $\mathbb{Z}$. This we can do canonically as follows: we define $\mathbb{Z}$ to be the quotient of $\mathbb{N} \times \mathbb{N}$ by the equivalence relation
$$\langle a, b \rangle \sim \langle c, d \rangle \text{ if and only if } a + d = b + c$$
The intended interpretation is that the equivalence class of $\langle a, b \rangle$ represents the integer $a - b$. Arithmetic operations can be defined on $\mathbb{Z}$ in the obvious fashion:
$$\langle a, b \rangle + \langle c, d \rangle = \langle a + c, b + d \rangle$$
$$\langle a, b \rangle \cdot \langle c, d \rangle = \langle a c + b d, a d + b c \rangle$$
(Check that these respect the equivalence relation.)
Again, this is not the only way to construct $\mathbb{Z}$; we can give a second-order axiomatisation of the integers which is categorical (i.e. any two models are isomorphic). For example, we may replace the set $\mathbb{Z}$ by $\mathbb{N}$, since the two sets are in bijection; the only thing we have to be careful about is to distinguish between the arithmetic operations for $\mathbb{Z}$ and for $\mathbb{N}$. (In other words, $\mathbb{Z}$ is more than just the set of its elements; it is also equipped with operations making it into a ring.)
Next, we need to construct the set of rational numbers $\mathbb{Q}$. This we may do using equivalence relations as well: we can define $\mathbb{Q}$ to be the quotient of $\mathbb{Z} \times (\mathbb{Z} \setminus \{ 0 \})$ by the equivalence relation
$$\langle a, b \rangle \sim \langle c, d \rangle \text{ if and only if } a d = b c$$
The intended interpretation is that the equivalence class of $\langle a, b \rangle$ represents the fraction $a / b$. Arithmetic operations are defined by
$$\langle a, b \rangle + \langle c, d \rangle = \langle a d + b c, b d \rangle$$
$$\langle a, b \rangle \cdot \langle c, d \rangle = \langle a c, b d \rangle$$
And as before, we can give an axiomatisation of the rational numbers which is categorical.
Now we can construct the set of real numbers $\mathbb{R}$. I describe the construction of Dedekind cuts, which is probably the simplest. A Dedekind cut is a pair of sets of rational numbers $\langle L, R \rangle$, satisfying the following axioms:
- If $x < y$, and $y \in L$, then $x \in L$. ($L$ is a lower set.)
- If $x < y$, and $x \in R$, then $y \in R$. ($R$ is an upper set.)
- If $x \in L$, then there is a $y$ in $L$ greater than $x$. ($L$ is open above.)
- If $y \in R$, then there is an $x$ in $R$ less than $y$. ($R$ is open below.)
- If $x < y$, then either $x \in L$ or $y \in R$. (The pair $\langle L, R \rangle$ is located.)
- For all $x$, we do not have both $x \in L$ and $x \in R$. ($L$ and $R$ are disjoint.)
- Neither $L$ nor $R$ are empty. (So $L$ is bounded above by everything in $R$ and $R$ is bounded below by everything in $L$.)
The intended interpretation is that $\langle L, R \rangle$ is the real number $z$ such that $L = \{ x \in \mathbb{Q} : x < z \}$ and $R = \{ y \in \mathbb{Q} : z < y \}$. The set of real numbers is defined to be the set of all Dedekind cuts. (No quotients by equivalence relations!) Arithmetic operations are defined as follows:
- If $\langle L, R \rangle$ and $\langle L', R' \rangle$ are Dedekind cuts, their sum is defined to be $\langle L + L', R + R' \rangle$, where $L + L' = \{ x + x' : x \in L, x' \in L' \}$ and similarly for $R + R'$.
- The negative of $\langle L, R \rangle$ is defined to be $\langle -R, -L \rangle$, where $-L = \{ -x : x \in L \}$ and similarly for $-R$.
- If $\langle L, R \rangle$ and $\langle L', R' \rangle$ are Dedekind cuts, and $0 \notin R$ and $0 \notin R'$ (i.e. they both represent positive numbers), then their product is $\langle L \cdot L' , R \cdot R' \rangle$, where $L \cdot L' = \{ x \cdot x' : x \in L, x' \in L', x \ge 0, x' \ge 0 \} \cup \{ x \in \mathbb{Q} : x < 0 \}$ and $R \cdot R' = \{ y \cdot y' : y \in R, y \in R' \}$. We extend this to negative numbers by the usual laws: $(-z) \cdot z' = -(z \cdot z') = z \cdot -z'$ and $z \cdot z' = (-z) \cdot -z'$.
John Conway gives an alternative approach generalising the Dedekind cuts described above in his book On Numbers and Games. This eventually yields Conway's surreal numbers.
The idea in the last paragraph is that in this sequence we many name the same element twice. This can happen if some $x$ is in two of the $E_k$ sets. Hence the author points out that the function that sends every natural number $n$ to the $n$th element of that sequence is not bijective. To make it bijective, we have to restrict its domain to some subset of the natural numbers (such that not two natural numbers are sent to the same element). Hence, $S$ is equinumerous with a subset of natural numbers.
Now we know (and I assume this is theorem 2.8) that every subset of the natural numbers is either countably infinite or finite. Therefore up until now we have only shown that $S$ is either countably infinite or finite. But, we already know that it contains at least countably infinite elements, the elements of $E_1$. Hence it cannot be finite. This implies that it is countable.
Best Answer
HINT: If $A$ and $B$ are countably infinite, there are bijections $a:A\to\Bbb N$ and $b:B\to\Bbb N$. Now modify these to get a map $a'$ that maps $A$ bijectively onto the even natural numbers and a map $b\,'$ that maps $B$ bijectively onto the odd natural numbers. Then combine $a'$ and $b\,'$ into a single bijection from $A\cup B$ to $\Bbb N$.