Proof of The Integers Form an Ordered Ring Containing the Natural Numbers as Its Positive Elements

Preliminaries. Sums and products of natural numbers are natural numbers by The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion §operations, so every bracket $[k,l]$ below has $k,l\in\mathbb{N}$ and is an integer by The Integers §integers. By Construction of the Integers: Pairs of Natural Numbers up to Equal Differences, with Sum, Product, Negation and Order §equal, every integer is $[k,l]$ for some $k,l\in\mathbb{N}$, and for all $k,l,m,n\in\mathbb{N}$,

$$[k,l]=[m,n]\quad\text{if and only if}\quad k+n=l+m.\qquad(\mathrm{E})$$

In particular $[k,k]=[1,1]=0_{\mathbb{Z}}$ for every $k\in\mathbb{N}$, since $k+1=k+1$; call this (Z0). The formulas for $+$, $\cdot$, $-$ and $\le$ of Construction of the Integers: Pairs of Natural Numbers up to Equal Differences, with Sum, Product, Negation and Order §operations (which are the operations of The Integers §operations), the constants $0_{\mathbb{Z}}=[1,1]$ and $1_{\mathbb{Z}}=[2,1]$ of The Integers §constants, where $2=1+1$ by Arithmetic and Order of the Natural Numbers §digits, and $\iota(n)=[n+1,1]$ from The Integers §embedding are used without further mention. By the order formula, $0_{\mathbb{Z}}=[1,1]\le[k,l]$ if and only if $1+l\le1+k$, that is, by Arithmetic and Order of the Natural Numbers §commutative and Arithmetic and Order of the Natural Numbers §order, if and only if

$$l\le k.\qquad(\mathrm{P})$$

In the proofs of the clauses ring, ordered-ring and negation, $x=[u_1,u_2]$, $y=[v_1,v_2]$ and $z=[w_1,w_2]$ with $u_1,u_2,v_1,v_2,w_1,w_2\in\mathbb{N}$.

The clause ring above. $\mathbb{Z}$ is a set, $+$ and $\cdot$ are binary operations on it and $0_{\mathbb{Z}},1_{\mathbb{Z}}\in\mathbb{Z}$, by The Integers §integers, Construction of the Integers: Pairs of Natural Numbers up to Equal Differences, with Sum, Product, Negation and Order §operations and The Integers §constants. We check the conditions of Commutative Rings §ring.

Sums: $(x+y)+z=[(u_1+v_1)+w_1,(u_2+v_2)+w_2]$ and $x+(y+z)=[u_1+(v_1+w_1),u_2+(v_2+w_2)]$ coincide by Arithmetic and Order of the Natural Numbers §associative; $x+y=[u_1+v_1,u_2+v_2]$ and $y+x=[v_1+u_1,v_2+u_2]$ coincide by Arithmetic and Order of the Natural Numbers §commutative. Next, $x+0_{\mathbb{Z}}=[u_1+1,u_2+1]$, which is $[u_1,u_2]=x$ by (E), since $(u_1+1)+u_2=(u_2+1)+u_1$ by Arithmetic and Order of the Natural Numbers §commutative and Arithmetic and Order of the Natural Numbers §associative. Finally $x+(-x)=[u_1,u_2]+[u_2,u_1]=[u_1+u_2,u_2+u_1]=[u_1+u_2,u_1+u_2]=0_{\mathbb{Z}}$ by Arithmetic and Order of the Natural Numbers §commutative and (Z0); so $-x$ is an additive inverse of $x$, and the identity $x+(-x)=0_{\mathbb{Z}}$ of the clause holds.

Products: $x\cdot y=[u_1v_1+u_2v_2,\,u_1v_2+u_2v_1]$ and $y\cdot x=[v_1u_1+v_2u_2,\,v_1u_2+v_2u_1]$ coincide by Arithmetic and Order of the Natural Numbers §commutative. Further,

$$(x\cdot y)\cdot z=[(u_1v_1+u_2v_2)w_1+(u_1v_2+u_2v_1)w_2,\,(u_1v_1+u_2v_2)w_2+(u_1v_2+u_2v_1)w_1],$$ $$x\cdot(y\cdot z)=[u_1(v_1w_1+v_2w_2)+u_2(v_1w_2+v_2w_1),\,u_1(v_1w_2+v_2w_1)+u_2(v_1w_1+v_2w_2)],$$

and by Arithmetic and Order of the Natural Numbers §distributive, Arithmetic and Order of the Natural Numbers §commutative and Arithmetic and Order of the Natural Numbers §associative both first entries equal $u_1v_1w_1+u_1v_2w_2+u_2v_1w_2+u_2v_2w_1$ and both second entries equal $u_1v_1w_2+u_1v_2w_1+u_2v_1w_1+u_2v_2w_2$. Next, $x\cdot1_{\mathbb{Z}}=[u_1(1+1)+u_2 1,\,u_1 1+u_2(1+1)]=[(u_1+u_1)+u_2,\,u_1+(u_2+u_2)]$ by Arithmetic and Order of the Natural Numbers §distributive and Arithmetic and Order of the Natural Numbers §one, which is $[u_1,u_2]=x$ by (E), since $((u_1+u_1)+u_2)+u_2=(u_1+(u_2+u_2))+u_1$ by Arithmetic and Order of the Natural Numbers §commutative and Arithmetic and Order of the Natural Numbers §associative. Finally,

$$x\cdot(y+z)=[u_1(v_1+w_1)+u_2(v_2+w_2),\,u_1(v_2+w_2)+u_2(v_1+w_1)],$$ $$x\cdot y+x\cdot z=[(u_1v_1+u_2v_2)+(u_1w_1+u_2w_2),\,(u_1v_2+u_2v_1)+(u_1w_2+u_2w_1)],$$

and by the same three clauses both first entries equal $u_1v_1+u_1w_1+u_2v_2+u_2w_2$ and both second entries equal $u_1v_2+u_1w_2+u_2v_1+u_2w_1$. Hence $\mathbb{Z}$, with $+$, $\cdot$, $0_{\mathbb{Z}}$ and $1_{\mathbb{Z}}$, is a commutative ring by Commutative Rings §ring.

A consequence used below: for $g,h\in\mathbb{Z}$, if $g-h=0_{\mathbb{Z}}$, then, by the clause ring above,

$$g=g+0_{\mathbb{Z}}=g+((-h)+h)=(g+(-h))+h=0_{\mathbb{Z}}+h=h+0_{\mathbb{Z}}=h.\qquad(\mathrm{D})$$

The clause ordered-ring above. By Construction of the Integers: Pairs of Natural Numbers up to Equal Differences, with Sum, Product, Negation and Order §operations, $\le$ is a relation on $\mathbb{Z}$.

Reflexivity: $x\le x$ means $u_1+u_2\le u_2+u_1$, which holds by Arithmetic and Order of the Natural Numbers §commutative and Arithmetic and Order of the Natural Numbers §partial-order. Antisymmetry: if $x\le y$ and $y\le x$, then $u_1+v_2\le u_2+v_1$ and $v_1+u_2\le v_2+u_1$, that is, $u_2+v_1\le u_1+v_2$ by Arithmetic and Order of the Natural Numbers §commutative; so $u_1+v_2=u_2+v_1$ by Arithmetic and Order of the Natural Numbers §partial-order, and $x=y$ by (E). Transitivity: if $x\le y$ and $y\le z$, then $u_1+v_2\le u_2+v_1$ and $v_1+w_2\le v_2+w_1$, so $(u_1+v_2)+w_2\le(u_2+v_1)+w_2$ and $(v_1+w_2)+u_2\le(v_2+w_1)+u_2$ by Arithmetic and Order of the Natural Numbers §order; as $(u_2+v_1)+w_2=(v_1+w_2)+u_2$ by Arithmetic and Order of the Natural Numbers §commutative and Arithmetic and Order of the Natural Numbers §associative, Arithmetic and Order of the Natural Numbers §partial-order gives $(u_1+v_2)+w_2\le(v_2+w_1)+u_2$, that is, $(u_1+w_2)+v_2\le(u_2+w_1)+v_2$, so $u_1+w_2\le u_2+w_1$ by Arithmetic and Order of the Natural Numbers §order, which is $x\le z$. Thus $\le$ is reflexive, antisymmetric and transitive, hence a partial order on $\mathbb{Z}$. Totality: by Arithmetic and Order of the Natural Numbers §trichotomy and Arithmetic and Order of the Natural Numbers §partial-order, $u_1+v_2\le u_2+v_1$ or $u_2+v_1\le u_1+v_2$; the former is $x\le y$, and the latter, being $v_1+u_2\le v_2+u_1$, is $y\le x$. So $\le$ is a total order on $\mathbb{Z}$ by Partial and Total Orders on a Set and the Associated Strict Relation §total.

Strict relation: by Partial and Total Orders on a Set and the Associated Strict Relation §strict, every element of the strict relation associated with $\le$ is a pair $(g,h)$ with $g\le h$, so with $g,h\in\mathbb{Z}$, as $\le$ is a relation on $\mathbb{Z}$; and by Uniqueness of Least and Greatest Elements, Properties of the Strict Order, and Trichotomy for Total Orders §strict-characterization, for $g,h\in\mathbb{Z}$ the pair $(g,h)$ belongs to it if and only if $g\le h$ and $g\neq h$, which by The Integers §operations is exactly $g<h$. So $<$ is the strict relation associated with $\le$.

Compatibility with sums: if $x\le y$, that is, $u_1+v_2\le u_2+v_1$, then $(u_1+v_2)+(w_1+w_2)\le(u_2+v_1)+(w_1+w_2)$ by Arithmetic and Order of the Natural Numbers §order, that is, $(u_1+w_1)+(v_2+w_2)\le(u_2+w_2)+(v_1+w_1)$ by Arithmetic and Order of the Natural Numbers §commutative and Arithmetic and Order of the Natural Numbers §associative; this is $[u_1+w_1,u_2+w_2]\le[v_1+w_1,v_2+w_2]$, that is, $x+z\le y+z$.

Compatibility with products: let $0_{\mathbb{Z}}\le x$ and $0_{\mathbb{Z}}\le y$, so $u_2\le u_1$ and $v_2\le v_1$ by (P); recall $x\cdot y=[u_1v_1+u_2v_2,\,u_1v_2+u_2v_1]$. If $u_1=u_2$, the entries are $u_1v_1+u_1v_2$ and $u_1v_2+u_1v_1$; if $v_1=v_2$, they are $u_1v_1+u_2v_1$ and $u_1v_1+u_2v_1$; in both cases $x\cdot y=0_{\mathbb{Z}}$ by Arithmetic and Order of the Natural Numbers §commutative and (Z0), and $0_{\mathbb{Z}}\le x\cdot y$ by reflexivity. Otherwise $u_2<u_1$ and $v_2<v_1$ by Arithmetic and Order of the Natural Numbers §partial-order, and by Arithmetic and Order of the Natural Numbers §difference there are $s,t\in\mathbb{N}$ with $u_1=u_2+s$ and $v_1=v_2+t$. By Arithmetic and Order of the Natural Numbers §distributive, Arithmetic and Order of the Natural Numbers §commutative and Arithmetic and Order of the Natural Numbers §associative,

$$u_1v_2+u_2v_1=(u_2+s)v_2+u_2(v_2+t)=u_2v_2+sv_2+u_2v_2+u_2t,$$ $$u_1v_1+u_2v_2=(u_2+s)(v_2+t)+u_2v_2=(u_2v_2+sv_2+u_2v_2+u_2t)+st=(u_1v_2+u_2v_1)+st,$$

so $u_1v_2+u_2v_1<u_1v_1+u_2v_2$ by Arithmetic and Order of the Natural Numbers §difference, hence $u_1v_2+u_2v_1\le u_1v_1+u_2v_2$ by Arithmetic and Order of the Natural Numbers §partial-order, and $0_{\mathbb{Z}}\le x\cdot y$ by (P). With the clause ring above, $\mathbb{Z}$, with $+$, $\cdot$, $0_{\mathbb{Z}}$, $1_{\mathbb{Z}}$ and $\le$, is an ordered ring by Ordered Rings §ordered-ring.

The clause negation above. $-(-x)=-[u_2,u_1]=[u_1,u_2]=x$. Next, $0_{\mathbb{Z}}\cdot x=[1u_1+1u_2,\,1u_2+1u_1]=[u_1+u_2,u_2+u_1]$ by Arithmetic and Order of the Natural Numbers §one, which is $[u_1+u_2,u_1+u_2]=0_{\mathbb{Z}}$ by Arithmetic and Order of the Natural Numbers §commutative and (Z0). Finally $(-x)\cdot y=[u_2,u_1]\cdot[v_1,v_2]=[u_2v_1+u_1v_2,\,u_2v_2+u_1v_1]$ and $-(x\cdot y)=-[u_1v_1+u_2v_2,\,u_1v_2+u_2v_1]=[u_1v_2+u_2v_1,\,u_1v_1+u_2v_2]$, the same class by Arithmetic and Order of the Natural Numbers §commutative.

The clause embedding above. By The Integers §embedding, $\iota:\mathbb{N}\to\mathbb{Z}$ is a map. Let $m,n\in\mathbb{N}$. If $\iota(m)=\iota(n)$, then $[m+1,1]=[n+1,1]$, so $(m+1)+1=1+(n+1)=(n+1)+1$ by (E) and Arithmetic and Order of the Natural Numbers §commutative, and two applications of Arithmetic and Order of the Natural Numbers §cancellation give $m=n$; so $\iota$ is injective by Injective, Surjective and Bijective Functions between Classes §injective. Next, $\iota(1)=[1+1,1]=[2,1]=1_{\mathbb{Z}}$. For $a,b\in\mathbb{N}$, $\iota(a)+\iota(b)=[(a+1)+(b+1),1+1]$, which equals $\iota(a+b)=[(a+b)+1,1]$ by (E), since $((a+b)+1)+(1+1)=1+((a+1)+(b+1))$ by Arithmetic and Order of the Natural Numbers §commutative and Arithmetic and Order of the Natural Numbers §associative. Further, by Arithmetic and Order of the Natural Numbers §distributive, Arithmetic and Order of the Natural Numbers §one, Arithmetic and Order of the Natural Numbers §commutative and Arithmetic and Order of the Natural Numbers §associative,

$$\iota(a)\cdot\iota(b)=[(a+1)(b+1)+1\cdot1,\,(a+1)1+1(b+1)]=[(ab+a+b+1)+1,\,(a+1)+(b+1)],$$

which equals $\iota(ab)=[ab+1,1]$ by (E), since $(ab+1)+((a+1)+(b+1))$ and $1+((ab+a+b+1)+1)$ both equal $ab+a+b+1+1+1$ by the same clauses. Finally, $\iota(a)\le\iota(b)$ means $(a+1)+1\le1+(b+1)$, that is, $(a+1)+1\le(b+1)+1$ by Arithmetic and Order of the Natural Numbers §commutative, which by two applications of Arithmetic and Order of the Natural Numbers §order holds if and only if $a\le b$; and $\iota(a)\neq\iota(b)$ if and only if $a\neq b$, by injectivity. By The Integers §operations, $\iota(a)<\iota(b)$ if and only if $a\le b$ and $a\neq b$, which by Arithmetic and Order of the Natural Numbers §partial-order and Arithmetic and Order of the Natural Numbers §trichotomy holds if and only if $a<b$.

The clause difference above. $\iota(a)-\iota(b)=[a+1,1]+(-[b+1,1])=[a+1,1]+[1,b+1]=[(a+1)+1,\,1+(b+1)]$, which equals $[a,b]$ by (E), since $((a+1)+1)+b=(1+(b+1))+a$ by Arithmetic and Order of the Natural Numbers §commutative and Arithmetic and Order of the Natural Numbers §associative.

The clause trichotomy above. Choose $k,l\in\mathbb{N}$ with $x=[k,l]$. By Arithmetic and Order of the Natural Numbers §trichotomy, $l<k$, $k=l$ or $k<l$. If $l<k$, then $k=l+n$ for some $n\in\mathbb{N}$ by Arithmetic and Order of the Natural Numbers §difference, and $x=[l+n,l]=[n+1,1]=\iota(n)$ by (E), since $(l+n)+1=l+(n+1)$ by Arithmetic and Order of the Natural Numbers §associative. If $k=l$, then $x=0_{\mathbb{Z}}$ by (Z0). If $k<l$, then $l=k+n$ for some $n\in\mathbb{N}$, and $-\iota(n)=-[n+1,1]=[1,n+1]$, which equals $x=[k,k+n]$ by (E), since $k+(n+1)=(k+n)+1$ by Arithmetic and Order of the Natural Numbers §associative. So at least one alternative holds. For exclusivity let $m,n\in\mathbb{N}$. If $\iota(n)=0_{\mathbb{Z}}$, then $(n+1)+1=1+1$ by (E), so $n+1=1$ by Arithmetic and Order of the Natural Numbers §cancellation, contradicting Arithmetic and Order of the Natural Numbers §successor. If $-\iota(m)=[1,m+1]=0_{\mathbb{Z}}$, then $1+1=(m+1)+1$ by (E), so $m+1=1$, the same contradiction. If $\iota(n)=-\iota(m)$, then $(n+1)+(m+1)=1+1$ by (E); the left side is $((n+m)+1)+1$ by Arithmetic and Order of the Natural Numbers §commutative and Arithmetic and Order of the Natural Numbers §associative, so $(n+m)+1=1$ by Arithmetic and Order of the Natural Numbers §cancellation, contradicting Arithmetic and Order of the Natural Numbers §successor. Hence exactly one alternative holds.

The clause positive above. For $n\in\mathbb{N}$, $0_{\mathbb{Z}}\le\iota(n)=[n+1,1]$ by (P), since $1\le n+1$ by Arithmetic and Order of the Natural Numbers §least, and $\iota(n)\neq0_{\mathbb{Z}}$ by the clause trichotomy above; so $0_{\mathbb{Z}}<\iota(n)$ by The Integers §operations. Conversely let $0_{\mathbb{Z}}<x$, so $0_{\mathbb{Z}}\le x$ and $x\neq0_{\mathbb{Z}}$ by The Integers §operations. If $x=-\iota(m)=[1,m+1]$ for some $m\in\mathbb{N}$, then $0_{\mathbb{Z}}\le x$ gives $m+1\le1$ by (P), while $1\le m+1$ by Arithmetic and Order of the Natural Numbers §least, so $m+1=1$ by Arithmetic and Order of the Natural Numbers §partial-order, contradicting Arithmetic and Order of the Natural Numbers §successor. By the clause trichotomy above, $x=\iota(n)$ for some $n\in\mathbb{N}$.

The clause no-zero-divisors above. Suppose $x\neq0_{\mathbb{Z}}$ and $y\neq0_{\mathbb{Z}}$. By the clause trichotomy above, $x$ is $\iota(m)$ or $-\iota(m)$ and $y$ is $\iota(n)$ or $-\iota(n)$, for some $m,n\in\mathbb{N}$. By the clauses ring, negation and embedding above,

$$\iota(m)\cdot\iota(n)=\iota(mn),\quad(-\iota(m))\cdot\iota(n)=-(\iota(m)\cdot\iota(n))=-\iota(mn),\quad\iota(m)\cdot(-\iota(n))=(-\iota(n))\cdot\iota(m)=-\iota(nm),$$ $$(-\iota(m))\cdot(-\iota(n))=-(\iota(m)\cdot(-\iota(n)))=-(-\iota(nm))=\iota(nm).$$

So $x\cdot y$ is $\iota(k)$ or $-\iota(k)$ with $k\in\mathbb{N}$, and $x\cdot y\neq0_{\mathbb{Z}}$ by the clause trichotomy above. This is the contrapositive of the claim.

The clause cancellation above. Let $z\neq0_{\mathbb{Z}}$ and $x\cdot z=y\cdot z$. By the clauses ring and negation above,

$$(x-y)\cdot z=z\cdot(x+(-y))=z\cdot x+z\cdot(-y)=x\cdot z+(-y)\cdot z=x\cdot z+(-(y\cdot z))=y\cdot z+(-(y\cdot z))=0_{\mathbb{Z}}.$$

By the clause no-zero-divisors above, $x-y=0_{\mathbb{Z}}$, and $x=y$ by (D).

The clause order-product above. Let $x<y$ and $0_{\mathbb{Z}}<z$, so $x\le y$ and $x\neq y$ by The Integers §operations, and put $r=y-x$. By the clause ring and the compatibility of $\le$ with sums in the clause ordered-ring above, $0_{\mathbb{Z}}=x+(-x)\le y+(-x)=r$; and $r\neq0_{\mathbb{Z}}$, since otherwise $y=x$ by (D). So $0_{\mathbb{Z}}<r$ by The Integers §operations, and by the clause positive above $r=\iota(m)$ and $z=\iota(n)$ for some $m,n\in\mathbb{N}$; then $r\cdot z=\iota(mn)$ by the clause embedding above, so $0_{\mathbb{Z}}<r\cdot z$ by the clause positive above, that is, $0_{\mathbb{Z}}\le r\cdot z$ and $r\cdot z\neq0_{\mathbb{Z}}$.

By the clauses ring and negation above,

$$r\cdot z=z\cdot(y+(-x))=z\cdot y+z\cdot(-x)=y\cdot z+(-x)\cdot z=y\cdot z-x\cdot z.$$

By compatibility with sums, $0_{\mathbb{Z}}+x\cdot z\le(y\cdot z-x\cdot z)+x\cdot z$, that is, $x\cdot z\le y\cdot z$, since the left side is $x\cdot z$ and the right side is $y\cdot z+((-(x\cdot z))+x\cdot z)=y\cdot z+0_{\mathbb{Z}}=y\cdot z$ by the clause ring above. If $x\cdot z=y\cdot z$, then $r\cdot z=y\cdot z-x\cdot z=0_{\mathbb{Z}}$ by the clause ring above, a contradiction. Hence $x\cdot z<y\cdot z$ by The Integers §operations.

The clause positive-factor above. Let $0_{\mathbb{Z}}<z$. Suppose $x\le y$. If $x=y$, then $x\cdot z=y\cdot z$, and $x\cdot z\le y\cdot z$ by reflexivity of $\le$ (clause ordered-ring above). Otherwise $x<y$ by The Integers §operations, so $x\cdot z<y\cdot z$ by the clause order-product above, and $x\cdot z\le y\cdot z$ by The Integers §operations. Conversely suppose $x\cdot z\le y\cdot z$ and that $x\le y$ fails. As $\le$ is total (clause ordered-ring above), $y\le x$, and $y\neq x$, since $x\le x$; so $y<x$ by The Integers §operations. By the clause order-product above, $y\cdot z<x\cdot z$, so $y\cdot z\le x\cdot z$ and $y\cdot z\neq x\cdot z$ by The Integers §operations; but $x\cdot z\le y\cdot z$ and antisymmetry of $\le$ give $x\cdot z=y\cdot z$, a contradiction. Hence $x\le y$.