I think I understand how this begins now. The key definition is that:
an $\omega$-model for the language $(R_1, \ldots R_n)$ is a model $M$ such that $(|M|,R_1)$ is isomorphic to $(\omega, x +1=y)$
or for these purposes
an $\omega$-model for the language $(R,S)$ is a model $M$ such that $(|M|,R)$ is isomorphic to $(\omega, x +1=y)$
This is hidden inside the definition of a particular set, in the middle of theorem 7.10, at the top of page 415; furthermore, the language is not specified in the paper. But once I figured that out, I could make sense of the rest of the argument.
Consider the sentence $\theta$: $$\exists m,n\, (2n=2m+1)$$ This is the negation of the first sentence in the above question. In relational form this is $$\exists m,n,u,v\, (Smmu \wedge Snnv \wedge Ruv)$$ where $Sabc$ is the relation for $a+b=c$ and $Ruv$ is the relation for $u+1=v$.
To find out whether $\theta$ is true arithmetically, we can incorporate clauses for the Peano definition of addition and the uniqueness of addition, and then ask whether there is an $\omega$-model for the sentence:
\begin{align} \forall a,b,c,d,e &(Sa0a\\ &\wedge\, (Rbc \wedge Rde \wedge Sabc \rightarrow Sade) \\ &\wedge\,(Sabc \wedge Sabd \rightarrow c=d))\\ \wedge\, \exists m,n,u,v\, &(Smmu \wedge Snnv \wedge Ruv) \end{align}
The paper does not specify this use of these clauses, but in an $\omega$-model they are enough to determine the addition relation completely. In particular, in an $\omega$-model, the first two clauses are enough to determine that any two elements can be added.
So the difference in the treatment of the two original sentences is that the procedure for the first only needs to incorporate the Peano definition of addition, and the procedure for the second needs to incorporate the Peano definitions of both addition and multiplication.
To continue with the procedure for $\theta$, we transform it further into prenex form for $G_1(\theta)$. (The paper also says to put the quantifier-free portion into $\bigvee_i \bigwedge_j$ form, but that does not seem necessary.) Then we can presumably apply the rest of the procedure to calculate $G_2(\theta)$, $G_3(\theta)$, and finally the desired $G(\theta)$ in the language of the monadic theory of order. I haven't done so yet.
I also see a few noteworthy items in the rest of the procedure:
- Step (1) seems to have a typo, where $l<0$ should read $l>0$.
- Steps (1), (3), (4) refer to $\psi$, which is defined on p. 413 using the definition of $\theta$ on p. 411.
- Step (3) seems to have a typo, where $\bigwedge_i \bigvee_j$ should read $\bigvee_i \bigwedge_j$ as in the definition of $G_1$.
- Step (4) seems to be defining $\chi^*$ as $\alpha \wedge \beta \wedge \gamma \wedge \delta \wedge \epsilon$, even though the clauses of the conjunction are interrupted by a sentence with another definition.
- Step (5) refers to quantifying over $X_0, \ldots, Q_l^i, \ldots$, which does not mean quantifying over $X_0, X_1, X_2, \ldots$; it means quantifying over $X_0, Q_1^1, \ldots, Q_l^i, \ldots, Q_{n(2)}^{m(n(2))}$.
The density of confusing exposition in this section is remarkable.