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 ?

  • $\begingroup$ Maybe convenience? Isn't that why we defined multiplication first anyway? $\endgroup$ – N. Owad Nov 10 '14 at 16:16
  • 1
    $\begingroup$ The point is, this changes the signature of your structure, and thus its underlying category while it shouldn't. $\endgroup$ – sure Nov 10 '14 at 16:17
  • 2
    $\begingroup$ Now the monoid has the structure of a semiring. $\endgroup$ – Matt Samuel Nov 10 '14 at 16:19
  • $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – sure Nov 10 '14 at 16:21
  • $\begingroup$ @sure Write that in first order logic. What does "a sum of identical elements of your monoid" look like in first order logic? $\endgroup$ – Thomas Andrews Nov 10 '14 at 16:23
  • $\begingroup$ Presburger arithmetics is decidable yes, but I'm working inside set theory here (say, ZF) $\endgroup$ – sure Nov 10 '14 at 16:23
  • $\begingroup$ 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 ? $\endgroup$ – sure Nov 10 '14 at 16:27

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.