How to define multiplication in addition terms in monadic second order logic? meaning, having natural numbers variables, N sub-groups variables, successor function, negations, "for every", "there exists" and "+" operation, I need to create a formula that will describe the multiplication operation. For example, given square, "+" and "/", multiplication can be described as: a*b={(a+b)^2-a^2-b^2}/2


  • $\begingroup$ Please add your question to the body of the post, and while you are at it, let us know your thoughts and efforts on the task. $\endgroup$ – Namaste Jun 15 '14 at 21:57
  • $\begingroup$ hope it's good enough, Thank you $\endgroup$ – Alfred Jun 15 '14 at 22:10
  • $\begingroup$ What you wrote does not define multiplicaton in terms of addition in first order logic (which actually does not mean anything). You need to be more precise: Are you working in the context of PA? So, do you mean first order PA or second order PA? What operations are given to you? What precisely does it mean to define an operation? (Does it mean to give a set of axioms that uniquely characterize the function, does it mean to exhibit a formula giving us the graph of the function? Does it mean something else?) $\endgroup$ – Andrés E. Caicedo Jun 15 '14 at 22:11
  • $\begingroup$ Well, how about now? $\endgroup$ – Alfred Jun 15 '14 at 22:28
  • $\begingroup$ It's not clear to me that this is possible. Because we can only quantify over sets (and not over functions), we would normally need a pairing function in order to define a function by recursion. But, without multiplication, it's not clear that we have a pairing function. $\endgroup$ – Carl Mummert Jun 16 '14 at 11:47

A bit informally...

$x$ divides $y$ iff $y$ belongs to all sets which contain $0$ and are closed under addition-by-$x$.

$x=y^2$ iff $x+y$ is the least common multiple of $y$ and $y+1$.

$x=yz$ iff $(y+z)^2=y^2+z^2+2x$.

  • $\begingroup$ How would you define that x+y is the least common multiple of y and y+1? Don't you need to define multiplication for that? $\endgroup$ – Roi Divon Jun 18 '14 at 16:32
  • 1
    $\begingroup$ hint: $x$ is a multiple of $y$ iff $y$ divides $x$. $\endgroup$ – mmw Jun 18 '14 at 16:42

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.