# Why are we bothering to define multiplication on cyclic monoids?

I just proved that given any cyclic monoid $(N,+,0)$, that is monoids generated by a single element, it is always possible to construct a commutative, associative multiplication $\times$ that is distributive over $+$ and has $0$ as absorbing element. Hence my question, why are we bothering to define $\times$ as another binary law on $\mathbb{N}$, considering it's nothing else than iterated addition ?

• Maybe convenience? Isn't that why we defined multiplication first anyway? – N. Owad Nov 10 '14 at 16:16
• The point is, this changes the signature of your structure, and thus its underlying category while it shouldn't. – sure Nov 10 '14 at 16:17
• Now the monoid has the structure of a semiring. – Matt Samuel Nov 10 '14 at 16:19
• We do define multiplication, as iterated addition. What is the question? By your apparent logic, we shouldn't define any operation that we can define. – Thomas Andrews Nov 10 '14 at 16:20

I'm not sure I completely understand the question, but multiplication makes a big difference for (first order) logic.

$(\forall n \forall m . p = n \cdot m \Rightarrow (n = 1 \vee m = 1)) \wedge p \neq 1$

Is a way to express that $p$ is prime. This sentence cannot be expressed using addition only.

The expressibility of first order logic with addition isn't great: Godel's trick of arithmetisation doesn't work. In fact the whole theory is decidable

With multiplication however, you can express anything, eg. a proof system.

• It can, and easily actually. Suppose that $p$ is prime and that the number of generators of your cyclic monoid is $L$. Then, $p$ is prime if there exists only $L+1$ way to write it as a sum of identical elements of your monoids. – sure Nov 10 '14 at 16:21
• @sure Write that in first order logic. What does "a sum of identical elements of your monoid" look like in first order logic? – Thomas Andrews Nov 10 '14 at 16:23
• Presburger arithmetics is decidable yes, but I'm working inside set theory here (say, ZF) – sure Nov 10 '14 at 16:23
• Let $A$ be the set of constant value sequences that are zero after a certain rank, that is, of the form $x = (n,n,n,n,n,n,0,0, \ldots)$. Call l(x) the length of the previous sequence, then an equivalence relation can be created on $A$ as $x R y$ <=> $n + \ldots + n$ ($l(y)$ times) $= m + \ldots + m$ ($l(x)$ times). Then $p$ is prime if the cardinal of its equivalent class is $L+1$. I don't know if this can be written in first order logic, can it ? – sure Nov 10 '14 at 16:27