On the clarification of Manin's remark about Gödel’s incompleteness theorems

In his paper Georg Cantor and his heritage Yuri I. Manin writes (see page 7, 3rd paragraph),

Baffling discoveries such as Gödel’s incompleteness of arithmetics lose some of their mystery once one comes to understand their content as a statement that a certain algebraic structure simply is not finitely generated with respect to the allowed composition laws.

My questions are the following,

1. What exactly is the algebraic structure that Manin is talking about? I am aware that a logic may be define as a tuple $(L,\vdash)$ where $L$ is the set of all well-formed formulas and $\vdash$ is the consequence relation. Is Manin talking about the same thing?

2. What is the definition of a "finitely generated structure" (I only know about finitely generated groups and modules)? What composition laws is Manin talking about?

Edit: While going through all the papers listed in Manin's ar$\chi$iv page, I found that in the paper Foundations as Superstructure. (Reflections of a practicing mathematician), he writes (see page 1, 3rd paragraph),

In metamathematics, Gödel’s theorem is a discovery that a certain class of finitely generated structures (statements in a formal language) contains substructures that are not finitely generated (those statements that are true in a standard interpretation).

According to the simplest interpretation of Manin's comment, the algebraic structures here are theories (really, just sets of sentences), with the operations corresponding to proofs. This fits into an existing tradition ("algebraic logic") of trying to give algebraic interpretations of logical systems.

Historical note: The original success of algebraic logic was the relationship between Boolean algebras and propositional logic, and this was further augmented on the topological side via Stone duality. The picture with stronger logics gets much more complicated, unfortunately; see e.g. the notion of cylindric algebras, which arise when we "algebraify" first-order logic.

Let's look at a weak incompleteness principle first:

$(*)\quad$ The set $Th(\mathbb{N})$ of true sentences in the language of arithmetic is not finitely axiomatizable.

This is a corollary of the full first incompleteness theorem ("No complete consistent extension of PA (or even much less!) is recursively axiomatizable").

Now let's "algebraify" the principle $(*)$, to say that a certain algebraic structure $\mathcal{A}$ isn't finitely generated:

• The elements of $\mathcal{A}$ are exactly the sentences in $Th(\mathbb{N})$.

• The operations of $\mathcal{A}$ are just the inference rules of first-order logic. (We have to be a bit careful here, and cook up a set of "unique application" inference rules since otherwise our "operations" are multi-valued. Alternatively, we could take as our operations individual proofs: if $p$ is a proof of $\varphi$ from $\psi_1,...,\psi_n$, then the operation $f_p$ associated to $p$ is the $n$-ary operation defined by $f_p(x_1,...,x_n)=\varphi$ if $x_i=\psi_i$ for $1\le i\le n$ and $f_p(x_1,...,x_n)=x_1$ otherwise.)

Before going forward, let's talk about where $\mathcal{A}$ "lives" (especially since the definition of $\mathcal{A}$ itself already referred to $Th(\mathbb{N})$, so it seems kind of ad hoc). $\mathcal{A}$ is a substructure of the larger structure $\mathcal{B}$ with the same operations but domain consisting of all sentences. $\mathcal{B}$ is computably presentable: its domain can be thought of as the set of valid Godel numbers of sentences (which is computable), and each operation of the algebra is computable when so interpreted (exercise). So it makes sense to consider $\mathcal{B}$ as "given at the outset," and all of our work being aimed at understanding complicated substructures of $\mathcal{B}$.

The principle $(*)$ is then exactly equivalent to "$\mathcal{A}$ is not finitely generated." Because if it were generated by $\{a_1,...,a_n\}$, the theory $\{a_1,..., a_n\}$ would be complete and prove exactly $Th(\mathbb{N})$, and this contradicts $(*)$.

A stronger form of the first incompleteness theorem says:

$(**)\quad$ No complete consistent theory in the language of arithmetic extending $PA$ (or again, much less) is finitely axiomatizable.

Now the algebraic situation is the following: I have a distinguished substructure $\mathcal{S}$ of $\mathcal{B}$, consisting of the theorems of PA; and I have a distinguished class $\mathfrak{C}$ of substructures of $\mathcal{B}$, namely those corresponding to complete consistent theories. Then $(**)$ is equivalent to the statement "If $\mathcal{A}\in\mathfrak{C}$ and $\mathcal{S}\subseteq\mathcal{A}$ then $\mathcal{A}$ is not finitely generated."

Finally, the full first incompleteness theorem,

$(*$$*$$*)\quad$ No complete consistent extension of PA (or indeed muchless) is recursively axiomatizable,

is then equivalent to the statement that no $\mathcal{A}\in\mathfrak{C}$ containing $\mathcal{S}$ is recursively generated. This is a bit of an odd situation, since (unlike the finite generation situation) whether or not a structure is recursively generated is not isomorphism-invariant (finite sets remain finite no matter how you name them, but recursiveness isn't so invariant). This explains (I believe) why Manin talks about finite generability, even though we get a stronger result from the incompleteness theorem: the stronger result, being non-isomorphism-invariant on the face of things, is not "algebraically natural."