, 2020

The statement holds when $g$ is the inverse function of $2^x + x^2 + 1$ in $\mathbb{R}^+$. The detail will be stated as follows.

Note that $\mathbb{N} \setminus A = \{1, 2, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 16, 18, \dots\} = \{b_n : n \in \mathbb{N}\}$.
After a rearrangement, we can assume $b_n < b_{n+1}$, $n \in \mathbb{N}$. Let us in a position consider
the sequence $\{b_n - n : n \in \mathbb{N}\}$, which is obviously a non-decreasing sequence. It is easy
to see that for each $m \in \mathbb{N} \cup \{0\}$, there exists at least two $n$ such that $b_n - n = m$.
More precisely, for each $m \ge 1$ fixed, the number of all distinct elements in the set
$B_m := \{n : b_n - n = m\}$ is
$$((m+1)^2 + 2^{m+1}) - (m^2 + 2^m) - 1 = 2m + 2^m.$$
Hence, if $n \in B_m$ with $m \ge 1$, then
$$2 + \sum_{l=1}^{m-1} (2l + 2^l) + 1 \le n \le 2 + \sum_{l=1}^{m} (2l + 2^l).$$
implying
$$2^m + m^2 - m + 1 \le n \le 2^{m+1} + m^2 + m, \text{ for } n \in B_m. \quad (1)$$

In particular, we have $2^m < n < 2^{m+2}$ and thus $m < \log_2 n < m + 2$. Along with (1), we get
$$2^m + m^2 + 1 < n + \log_2 n < 2^{m+1} + (m+1)^2 + 1, \text{ for } n \in B_m. \quad (2)$$
Note also that $2^x + x^2 + 1$ is strictly increasing to $x > 0$. Hence, there exists a strictly increasing function $g : \mathbb{R}^+ \to \mathbb{R}^+$ such that its inverse $g^{-1}(x) = 2^x + x^2 + 1$. This along with (2) yields
$$m < g(h_1(n)) < m + 1, \text{ for } n \in B_m. \quad (3)$$
On the other hand, by (2), one has $2^m < n + \log_2 n < 2^{m+2}$, and hence $m < \log_2(n + \log_2 n) < m + 2$. Along with (1), we get $2^m + m^2 + 1 \le n + \log_2(n + \log_2 n) \le 2^{m+1} + (m+1)^2 + 1$, i.e.,
$$m < g(h_2(n)) < m + 1, \text{ for } n \in B_m. \quad (4)$$
Repeating the same argument, we can prove
$$m < g(h_i(n)) < m + 1, \forall i \in \mathbb{N} \text{ and } \forall n \in B_m. \quad (5)$$
Hence, we obtain $[g(h_i(n))] = m, \forall n \in B_m$ and $\forall i \in \mathbb{N}$. As a consequence,
$$b_n = n + [g(h_i(n))] \in \mathbb{N} - A, \forall n \in \mathbb{N}.$$
Furthermore, for $k \in \mathbb{N} \setminus A$, there exists $n := a_{i,k}$ such that $k = a_{i,k} + [g(h_i(a_{i,k}))]$. Since both $g$ and $h_i$ are strictly increasing functions, the uniqueness for $a_{i,k}$ is trivial. This completes the proof of (a) and (b).