13
$\begingroup$

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.

$\endgroup$
14
  • $\begingroup$ "$(\mathbb{N}, 1, 0, \gcd, $lcm$)$ is a bounded distributive lattice (with least element 1)". And, by the way, greatest element is $0$. $\endgroup$ – amrsa Jul 11 '16 at 11:46
  • 1
    $\begingroup$ @amrsa, of course it is. I just couldn't fit that onto one line :) $\endgroup$ – goblin GONE Jul 11 '16 at 11:53
  • $\begingroup$ You can fit it in if you say "with top $0$ and bottom $1$". $\endgroup$ – user21820 Jul 11 '16 at 13:25
  • 2
    $\begingroup$ 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. $\endgroup$ – hmakholm left over Monica Jul 11 '16 at 13:44
  • $\begingroup$ ... 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$$ $\endgroup$ – hmakholm left over Monica Jul 11 '16 at 14:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.