1. Identify the sequence and the condition:
The set $S = \{ n^k \mid n, k \in \mathbb{Z}, k \ge 2 \}$ consists of all perfect integer powers. We arrange these elements in increasing order to form the sequence $\{a_i\}$. We need to show that there are infinitely many $n$ such that $9999 \mid a_{n+1} - a_n$.

2. Consider the case of consecutive squares:
Let's consider the elements $a_n = k^2$ and $a_{n+1} = (k+1)^2$. The difference between these consecutive squares is:
$$a_{n+1} - a_n = (k+1)^2 - k^2 = k^2 + 2k + 1 - k^2 = 2k + 1$$
We need $9999 \mid 2k + 1$. This implies:
$$2k + 1 \equiv 0 \pmod{9999} \implies 2k \equiv -1 \pmod{9999} \implies k \equiv 4999 \pmod{9999}$$

3. **Count the number of such $k$:**
The number of elements in $S$ that are at most $n$ is $O(\sqrt{n})$ because the largest square less than or equal to $n$ is $(\lfloor \sqrt{n} \rfloor)^2$.

4. **Count the number of $k$ satisfying $k \equiv 4999 \pmod{9999}$:**
The number of $k$ such that $k^2 \leq n$ and $k \equiv 4999 \pmod{9999}$ is approximately:
$$O\left(\frac{\sqrt{n}}{9999}\right) = O(\sqrt{n})$$

5. Consider non-square elements:
The number of non-square elements in $S$ that are at most $n$ is $O(\sqrt[3]{n})$ because the largest cube less than or equal to $n$ is $(\lfloor \sqrt[3]{n} \rfloor)^3$.

6. Combine the counts:
The number of elements in $S$ which are squares $k^2 \leq n$ such that $k \equiv 4999 \pmod{9999}$, and whose subsequent element is also a square, is:
$$O(\sqrt{n} - \sqrt[3]{n}) = O(\sqrt{n})$$
since there can be at most $O(\sqrt[3]{n})$ elements $\leq n$ which aren't squares.

7. Conclusion:
Since $O(\sqrt{n})$ functions grow arbitrarily large as $n \to \infty$, there are infinitely many $n$ such that $9999 \mid a_{n+1} - a_n$.

$\blacksquare$