Q: Show that $(\mathbb{Z},|,+,0,1)$ defines multiplication in $\mathbb{Z}$.

I know how to do this in $\mathbb{N}$, but I'm stuck trying to do this is $\mathbb{Z}$. The idea I have is to define lowest common multiple ($lcm$) and using property of coprimes to define $x^2$. From there $(x+y)^2$ will allow me to define $x\cdot y$.

So I first define $$z = lcm(x,y) \iff x\mid z \land y \mid z \land \forall m(x \mid m \land y\mid m \rightarrow z \mid m).$$ Then I define $$2x^2 = x(x+1) + x(x-1) = lcm(x,x+1) + lcm(x,x-1).$$ However, I realised that my definition of $lcm(x,y)=z$ could give $z$ as either a negative or positive integer. Without the ordering relation ($<$), I am having difficulty finding a way to define $lcm$ such that I only get the positive $z$. How can I overcome this?

  • 2
    $\begingroup$ thank you for pointing the error out. I'll edit immediately. $\endgroup$ – jh4 Apr 27 '15 at 17:05
  • $\begingroup$ Apparently you have equality, subtraction, and the number 1 defined as well. If this is the case, then you could define the positive numbers recursively: Let $x$ be positive iff $x = 0$ or $x-1$ is positive. We could define $\ge$ in this manner for any number (not just 0). However, notice that defining $(x+y)^2$ will not get you to $x*y$. What happens when $x=2$ and $y=-2$? $\endgroup$ – Jonny Apr 27 '15 at 18:06
  • $\begingroup$ Yes I have addition. I am able to define subtraction from addition so I used subtraction freely. How do I write a formula for recursive definition of the positive integers? Say $P(a)$ iff $a$ is positive, am I right in writing $P(a) \iff P(a-1) \lor a=0$? $\endgroup$ – jh4 Apr 27 '15 at 18:10
  • $\begingroup$ You could even say $x \ge y \iff x-1 \ge y \lor x = y$. I am very curious how you define subtraction, and the number 1, however. It makes it difficult to answer your question without a complete set of definitions. $\endgroup$ – Jonny Apr 27 '15 at 19:04
  • $\begingroup$ @Jonny I've added in the question above. I was given 0,1 in the language. Also I realised how I defined subtraction is wrong. However, I modified my argument to only require the predecessor of $x$, which can be defined by $Pred(x)=y \iff y+1=x$. $\endgroup$ – jh4 Apr 27 '15 at 19:10

It seems I was wrong in my comment and these induction schemes are not really necessary. See this essentially duplication question: Can multiplication be defined in terms of divisibility?

A synopsis: $$ z = x*y \iff \\ \exists u,v,w (\text{Square}(x,u) \land \text{Square}(y,v) \land \text{Square}(x+y, w) \land w = u + v + z + z) $$

However, they don't quite address the problem that the lcm defined in terms of divisibility is not unique. A thought: simply define your LCM as a set, and $$\text{Square(s,t)} \iff \exists u \in \text{LCM}(s,s+1): s+t = u $$

Notice that when $s$ is negative, eg $s=-3$, then $\text{LCM}(-3,-2) = \{6,-6\}$ and $-3 + 9 = 6$. However, this definition also makes $t=-3$ a possibility, which ruins everything.

Thus we still need to inductively define the positive numbers $P(x) \iff x = 0 \lor P(x-1)$ and assert the LCM is positive.

  • 2
    $\begingroup$ There's little to no link rot danger with highly voted posts within the site. If the link has gone sour, it's probable to assume that this page is not very accessible either. $\endgroup$ – Asaf Karagila Apr 27 '15 at 20:21
  • $\begingroup$ Thank you for this. I was thinking about using your suggestion on recursively defining the set of non-negative integers, but this seems more straight forward. $\endgroup$ – jh4 Apr 27 '15 at 20:48
  • $\begingroup$ Actually, what if $s$ is negative? $\endgroup$ – jh4 Apr 27 '15 at 21:17
  • $\begingroup$ I think it is ok if $s$ is negative, but I just realized this definition gives two possible values of $t$ for each $s$, but only one is good. $\endgroup$ – Jonny Apr 27 '15 at 21:50
  • $\begingroup$ What about this approach: Square$(s,t) \iff \exists h,k: t+t = h+k \land h\in$LCM$(s,s+1) \land k\in$LCM$(s,s-1)$? $\endgroup$ – jh4 Apr 27 '15 at 22:22

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.