# Is there a finite list of identites in the language of $(\mathbb{N},0,1,+,\times,\mathrm{gcd},\mathrm{lcm})$ that generates all the others?

Let $\Phi$ denote the set of all identities satisfied by $(\mathbb{N},0,1,+,\times,\mathrm{gcd},\mathrm{lcm}).$

Question. Is $\Phi$ finitely axiomatizable? If so, I'd like to see a list of identities.

Noteworthy elements of $\Phi$:

• $(\mathbb{N},0,1,+,\times)$ is a commutative semiring
• $(\mathbb{N},1,0,\mathrm{gcd},\mathrm{lcm})$ is a bounded distributive lattice (with bottom $1$ and top $0$)
• $\mathrm{gcd}(a,b+a) = \mathrm{gcd}(a,b)$
• $\gcd(a+b,\operatorname{lcm}(a,b))=\gcd(a,b)$
• $\mathrm{gcd}(a,b)\mathrm{lcm}(a,b) = ab$

The second last identity above actually follows from the preceeding one's; see Bill's answer here.

• "$(\mathbb{N}, 1, 0, \gcd,$lcm$)$ is a bounded distributive lattice (with least element 1)". And, by the way, greatest element is $0$. – amrsa Jul 11 '16 at 11:46
• @amrsa, of course it is. I just couldn't fit that onto one line :) – goblin Jul 11 '16 at 11:53
• You can fit it in if you say "with top $0$ and bottom $1$". – user21820 Jul 11 '16 at 13:25
• If this is possible it will be just barely. If you add merely a $\min$ operator to the language, then the set of identities is definitely not recursively enumerable, due to Matiyasevich's theorem. – hmakholm left over Monica Jul 11 '16 at 13:44
• ... combined with $$\min(1+\gcd(a+1,b+1),\operatorname{lcm}(a+1,b+1))=1+\gcd(a+1,b+1) \iff a\ne b$$ – hmakholm left over Monica Jul 11 '16 at 14:09