The books mentioned in other answers (see also this question) might be hard to get and their proofs employ some advanced theory. I think natural = predictable should be illuminated early in stochastic calculus, even before the Doob-Meyer decomposition and stochastic integration. In that light I will try to offer an original proof based on elementary methods. I have drawn heavily from the work of P. Spreij and G. Lowther. The errors are mine alone (I'm a student).
Statement
The following definition is a well known equivalent of the OP's.
$A$ is natural when it is an increasing process that satisifes
\begin{equation}\tag{1}
\forall t \ge 0 : \mathbb E \int_{(0,t]} M_{s} dA_s = \mathbb E \int_{(0,t]} M_{s-} dA_s
\end{equation}
for all bounded right continuous martingales $M$.
The integrals are Lebesgue-Stieltjes.
Predictable processes are those measurable in the predictable $\sigma$-algebra which may be defined as the one generated by the left continuous processes.
Claim.
$A$ is natural if and only if $A$ is predictable.
Natural implies predictable
Let natural $A$ be decomposed as a continuous process plus a countable sum of jumps $\Delta A_T$ at stopping times $T$. Continuous processes are predictable so we need only prove that $\Delta A_T \mathbf 1_{\{t \ge T\}}$ is predictable. Notice that both $T$ and $\Delta A_T$ are strictly positive.
For convenience set $M'_s = M_{s-}$ and $B_T = \Delta A_T \mathbf 1_{\{T < \infty\}}$.
Evaluate $(1)$ for any time $t$:
\begin{equation}\tag{2}
\mathbb E M_T B_T \mathbf 1_{\{t \ge T\}} = \mathbb E M'_T B_T \mathbf 1_{\{t \ge T\}}
\end{equation}
\begin{equation}\tag{3}
\mathbb E \Delta M_T B_T \mathbf 1_{\{t \ge T\}} = 0
\end{equation}
Sketch:
- $T$ is a predictable stopping time.
- $M'_T \in \mathbb E [M_T | \mathcal F_{T-}]$ because $T$ is predictable.
- $B_T \in \mathbb E [B_T | \mathcal F_{T-}]$ by a special choice of $M$.
- $B_T \mathbf 1_{\{t \ge T\}}$ is predictable by $\mathcal F_{T-}$ measurability.
The key parts are really the predictability of $T$ and the $\mathcal F_{T-}$ measurability of $B_T$. The rest is boilerplate finishing with $B_T \mathbf 1_{\{t \ge T\}}$ being predictable because $\sigma(B_T \mathbf 1_{\{t \ge T\}})$ is contained in the predictable $\sigma$-algebra.
$T$ is a predictable stopping time
We appeal to a construction of $M$ related to estimation of $T - t$, in such a way that $\Delta M_T \le 0$. Finding that $\Delta M_T = 0$ using $(3)$, the announcing sequence that defines a predictable stopping time will follow.
First choose a map $f : [0,\infty) \to [0,\infty)$ that is bounded, continuous, and strictly increasing (think of sigmoids or $\tanh$ for example). The process $Y_t = E[f(T) - f(t) | \mathcal F_t]$ estimates (however poorly) the time left until stopping. What matters is that $Y$ is positive when $t < T$ and identically zero when $t=T$. Therefore $\Delta Y_T \le 0$.
Let $M_t \in \mathbb E[f(T) | \mathcal F_t]$ which is a bounded martingale. Given the usual condition of a right continuous filtration let $M_t$ be moreover (a.s.) right continuous. Since $M_t = Y_t + f(t)$ and $f(t)$ is continuous we have $\Delta M_T = \Delta Y_T \le 0$. Finally as $t \to \infty$ in $(3)$ it's clear that $\Delta M_T$ is zero a.e. in $\{T < \infty\}$.
The announcing sequence $T_n$ is now given by $T_n = n \wedge \inf \{t : Y_t \le 1/n\}$. The conditions $T_n < T$ and $T_n \to T$ are satisfied by continuity since (a.s.) $\Delta Y_T = \Delta M_T = 0$. Per these criteria $T$ is predictable.
$M'_T \in \mathbb E [M_T | \mathcal F_{T-}]$
We need this in the next section. It's a standard result of predictable projection theory, but here is a direct proof.
One must show that $\forall G \in \mathcal F_{T-} : \mathbb E \mathbf 1_G M'_T = \mathbb E \mathbf 1_G M_T$. First let $k,n \in \mathbb N$ such that $n > k$ and take $G \in \mathcal F_{T_k}$. Apply optional stopping then dominated convergence.
\begin{align}
\mathbb E \mathbf 1_G M_T
&= \mathbb E \mathbf 1_G \mathbb E \left[ \mathbb E[M_T | \mathcal F_{T_n}] \big| \mathcal F_{T_k} \right] \\
&= \mathbb E \mathbf 1_G \mathbb E [M_T | \mathcal F_{T_n}] \\
&= \mathbb E \mathbf 1_G M_{T_n}\ (\forall n > k) \\
&= \lim_{n \to \infty} \mathbb E \mathbf 1_G M_{T_n} \\
&= \mathbb E \lim_{n \to \infty} \mathbf 1_G M_{T_n} \\
&= \mathbb E \mathbf 1_G M'_T \\
\end{align}
Equality for $G \in \mathcal F_{T-}$ follows from the case $G \in \cup_{k \in \mathbb N} \mathcal F_{T_k}$ because the latter collection is a $\pi$-system and it generates $\mathcal F_{T-}$ (almost by definition). Let $\mathcal D \subseteq 2^\Omega$ comprise all sets $G$ for which the stated equality holds. Then $\mathcal D$ contains the $\pi$-system. By the linearity of the integral and by dominated convergence $\mathcal D$ is a d-system. Hence $\mathcal D = \mathcal F_{T-}$ per Dynkin's lemma.
$B_T$ is $\mathcal F_{T-}$ measurable
Let $\hat B_T = \mathbb E[B_T | \mathcal F_{T-}]$.
Both $M'_T$ and $\mathbf 1_{\{t \ge T\}}$ are $\mathcal F_{T-}$ measurable, thus from $(2)$:
\begin{align}
\mathbb E M_T B_T \mathbf 1_{\{t \ge T\}}
&= \mathbb E M'_T B_T \mathbf 1_{\{t \ge T\}} \\
&= \mathbb E M'_T \hat B_T \mathbf 1_{\{t \ge T\}} \\
&= \mathbb E \left( \mathbb E [M_T | \mathcal F_{T-}] \hat B_T \mathbf 1_{\{t \ge T\}} \right) \\
&= \mathbb E M_T \hat B_T \mathbf 1_{\{t \ge T\}} \\
\end{align}
\begin{equation}\tag{4}
\mathbb E M_T (B_T - \hat B_T)\mathbf 1_{\{t \ge T\}} = 0
\end{equation}
Finally $B_T = \hat B_T$ must hold a.e. because $M$ in $(4)$ may be chosen as follows:
- $Z = \mathbf 1_{\{B_T > \hat B_T\}} - \mathbf 1_{\{B_T < \hat B_T\}}$
- $M_t = \mathbb E [Z | \mathcal F_t]$
- $M_T = Z$
Here the (bounded) martingale $M_t$ is taken (a.s.) right continuous under the usual condition of a right continuous filtration. Thus $(4)$ applies and sending $t \to \infty$ we have $B_T \ne \hat B_T$ on at most a null set within $\{T < \infty\}$. Both vanish on $\{T = \infty\}$ so they are indeed a.e. identical.
$A$ is therefore predictable
It has now been shown that $B_T \mathbf 1_{\{t \ge T\}}$ is a member of a class that generates the predictable $\sigma$-algebra. Recall that by decomposition into such processes the predictability of $A$ follows.
$$\tag*{$\blacksquare$}$$
Predictable implies natural
When $A$ is a continuous process of bounded variation the condition $(1)$ is true. This follows because the measure induced by $A$ is absolutely continuous w.r.to $dt$ and hence the countable discontinuities of the integrands fall in a set of measure zero.
So for $A$ increasing and predictable, like before we need only consider a countable sum of jumps at stopping times $T$ and prove that $\Delta A_T \mathbf 1_{\{t \ge T\}}$ is natural. Again $T$ and $\Delta A_T$ are strictly positive. It should be clear that $\mathbf 1_{\{t \ge T\}}$ by itself is also predictable.
Now it will not be a surprise that $T$ is a predictable stopping time. There is a nice theorem that relies on stochastic integrals. I will give a direct argument.
$T$ is a predictable stopping time
Consider the process $\mathbb E [T-t | \mathcal F_t]$. Pathwise, this must be positive when $t < T$ and zero when $t = T$. If it is moreover (a.s.) continuous from the left when $t = T$ the predictability of $T$ follows immediately (take decreasing hitting times as the announcing sequence). Technically the announcing sequence should also go to infinity if $T=\infty$.
These goals in mind, a weaker claim that's easy to prove is the continuity of $\mathbb E [T \wedge n - t | \mathcal F_t]$ for stopping times $(T \wedge n)_{n \in \mathbb N}$. Let $\{X^n : n \in \mathbb N\}$ and $\{Y^u : u > 0\}$ be the martingales in the next display.
\begin{equation}\tag{5}
X^n_t = \mathbb E [T \wedge n | \mathcal F_t] \le \mathbb E [u \mathbf 1_{\{T \le u\}} + n \mathbf 1_{\{T > u\}} | \mathcal F_t] = Y^u_t
\end{equation}
\begin{equation}\tag{6}
\forall \omega \in \Omega : \forall t > 0 : X^n(t,\omega) \le \inf_{u > 0} Y^u(t,\omega)
\end{equation}
Here $(6)$ merely restates the inequality $(5)$ to make a point. Fix arbitrary $\omega$ and send $t \to T(\omega) \wedge n$ from below. Assume there is a process in $\{Y^u\}$ such that $Y^u(t,\omega) - t \to 0$ continuously. Then by $(6)$ also $X^n(t,\omega) - t \to 0$ continuously.
Indeed the assumption holds for $\{Y^u : u > 0\}$. Fix $u > 0$ and send $t \to u$ from below. $Y^u_u$ must be continous from the left because $\mathbf 1_{\{T \le u\}}$ is predictable.
$$Y^u_u = \mathbb E [Y^u_u | \mathcal F_u] = \mathbb E [Y^u_u | \mathcal F_{u-}] = Y^u_{u-} \ \text{(a.s.)}$$
Moreover if $u = T(\omega) \wedge n$ then $Y^u(u,\omega) = u$ and $Y^u(t,\omega) - t = 0$ when $t=u$.
Now take $(T^n_k)_{k \in \mathbb N} = \inf \{t : X^n_t - t \le 1/k\}$ as the announcing sequence for $T \wedge n$. Clearly $n < m$ implies $X^n_t \le X^m_t$ and $T^n_k \le T^m_k < T$. Hence $(T^n_n)_{n \in \mathbb N}$ announces $T$.
$A$ is therefore natural
Finally, skipping over details elaborated in the last section,
\begin{align}
\forall t > 0 :
\mathbb E M_T \Delta A_T \mathbf 1_{\{t \ge T\}}
&= \mathbb E \left( \mathbb E [M_T \Delta A_T \mathbf 1_{\{t \ge T\}} | \mathcal F_{T-}] \right) \\
&= \mathbb E M'_T \Delta A_T \mathbf 1_{\{t \ge T\}} \\
\end{align}
and condition $(1)$ has been shown.
$$\tag*{$\blacksquare$}$$
