Theory of a first order structure

Question

The book I am earning from states that the theory of a $\mathcal{V}$-structure, $M$, is the set of all $\mathcal{V}$-sentences that are modeled by $M$. Then it goes on to say that that any theory of a $\mathcal{V}$-structure is complete. So lets look at the structure $NT= (\mathbb{N} | +, \cdot,1)$.

My book says that the axioms of NT are:

$\forall x \lnot(x+1=1)$

$\forall x \forall y (x+1 = y+1 \implies x=y)$

$\forall x \forall y (x+y = y+x)$

$\forall x \forall y (x + (y+1)=(x+y)+1)$

$\forall x \forall y (x \cdot y = y \cdot x)$

$\forall x (x \cdot 1 = x)$

$\forall x \forall y (x \cdot (y+1) = (x \cdot y)+x)$

$\forall^1 S(S(1) \land \forall x(S(x) \implies S(x+1)))\implies \forall x S(x)$

This last axiom is technically a second-order sentence, but I have read that it can be written in a first order language as an axiom schema. So these sentences, by our choice, are in $Th(NT)$. But Godel showed that, only assuming these axioms, there are some true sentences which cannot be derived. So won't these sentences and their negations be missing from $Th(NT)$? I don't understand how my book can claim that $Th(NT)$ is complete.

Answer 1

The line

it can be written in a first order language as an axiom schema

is extremely misleading. There is an analogue of the second-order induction sentence in first-order logic, consisting of a scheme of axioms as you say. However, this analogue is strictly weaker than second-order induction. This is why your $NT$ can be complete while its first-order version which I'll call "$NT_1$" is not (per Godel): they are not equally strong theories.

In particular, we do have $NT=Th(\mathbb{N}; +,\cdot, 1)$, but $NT_1\subsetneq Th(\mathbb{N}; +,\cdot,1)$.

Answer 2

The theory of $(\mathbb{N}, +, \cdot)$ is certainly complete. But the axioms you've given, when you translate the induction axiom to a first order schema, do not axiomatize the theory: there are statements which are true in $\mathbb{N}$ that are not provable from those axioms.

The issue is with translating the induction axiom to a "first order schema". The induction axiom you quote (the "second order" axiom) loosely states that "The only subset of $\mathbb{N}$ which contains 1 and is closed under successors is $\mathbb{N}$ itself." The "first order schema" would be all formulas of the form:

$$[\phi(1) \wedge \forall x (\phi(x) \rightarrow \phi(x+1))] \rightarrow \forall x \phi(x)$$

where $\phi(x)$ is any unary formula in the language. What we've done is translate the statement "The only subset of $\mathbb{N}$ ..." into "The only definable subset of $\mathbb{N}$..." Without full second order quantification, we cannot talk about arbitrary subsets of $\mathbb{N}$, only the definable ones.