No zero divisors in $\mathbb{Z}$

Let $\mathbb{N}$ be natural number with injective successor function $s.$

Define addition $+:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$: $\forall a,b\in\mathbb{N}.\;a+ 0 =0+a= a\;\wedge\;a+ s(b) = s(a+b)$

Define multiplication $\cdot:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$: $\forall a,b\in\mathbb{N}.\;a\cdot 0 = a\;\wedge\;a\cdot s(b) = a\cdot b+a$
Abbreviate $a\cdot b$ with $ab$.

Define $\sim$ on $\mathbb{N}\times\mathbb{N}: (a,b)\sim(c,d)\iff a+d = b+c$

Define $\mathbb{Z} = \mathbb{N}\times\mathbb{N}\backslash \sim$

Define $+_Z:\mathbb{Z}\times\mathbb{Z}\to\mathbb{Z}$: $[(a_1,a_2)]+_Z[(b_1,b_2)] = [(a_1+b_1,a_2+b_2)]$

Define $*:\mathbb{Z}\times\mathbb{Z}\to\mathbb{Z}$: $[(a_1,a_2)]*[(b_1,b_2)] = [(a_1 b_1+a_2b_2,a_1b_2+a_2b_1)]$

In my homework I have shown that $(\mathbb{N},+)$ is a commutative monoid with cancellation law and $\cdot$ distributive over $+$. And that $+_Z$ and $*$ are well defined, $(\mathbb{Z},+_Z)$ is an abelian group with identity $\overline{0} = [(0,0)] = [(a,a)]$. Also I showed that $*$ is commutative, associative and distributive over $+_Z$ and has identity $\overline{1} = [(1,0)]\ne\overline{0}$.

Now in order to prove $\mathbb{Z}$ is an integral domain, I need to show $$\forall \overline{a},\overline{b}\in\mathbb{Z}.\;\overline{a}\ne \overline{0}\;\wedge\;\overline{b}\ne \overline{0}\;\Longrightarrow\;\overline{a}*\overline{b}\ne \overline{0}$$
which I am not able to. I read many proofs but they either define order on $\mathbb{Z}$ which I don't want to do yet or they use cancellation law of $*$ which is equivalent to what I am trying to prove now.

Thank you very much.

-

Not the best proof, but since you probably already proved that the multiplication is well defined then if $a=s(a')$ and $b=s(b')$ then

$$[(a,b)]*[(x,y)]=[(0,0)] \Leftrightarrow [(a',b')]*[(x,y)]=[(0,0)]$$

Using this trick you can assume that you have zero divisors

$$[(a,b)]*[(c,d)]=[(0,0)]$$

such that $[a=1 \vee b=1 ] \wedge [c=1 \vee d=1]$.

Alternately: I think you can prove the following statement:

$$ac+bd=ad+bc \wedge a\neq b \Rightarrow c=d \,.$$

Indeed if $c=1$ (or $d=1$) you have

$$a+bd=ad+b$$ and then $d$ cannot be the successor of something since $d=s(d')$ implies

$$bd'=ad'$$

the cancellation law in $\mathbb N$ is easy to prove by induction on $d'$.

Now, if $c=s(c')$ then we already know by the above that $d\neq 1$ then $d=s(d')$ and you just reduce the problem to

$$ac'+bd'=ad'+bc'$$

-
yea, but there are no negatives here, there is no order yet. – mez Feb 16 '13 at 18:44
@mezhang Sorry I missed that you don't have an order yet... Does this work? – N. S. Feb 16 '13 at 21:29