Proof of Construction of the Integers: Pairs of Natural Numbers up to Equal Differences, with Sum, Product, Negation and Order

Membership. $\mathbb{N}$ is a set by The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion §sets, so $P$ is a set by Membership in a Cartesian Product, and the Cartesian Product of Two Sets Is a Set §set. By The Cartesian Product of Two Classes §product and Membership in a Cartesian Product, and the Cartesian Product of Two Sets Is a Set §membership, the elements of $P$ are exactly the ordered pairs $(a,b)$ with $a,b\in\mathbb{N}$. By The Components of an Ordered Pair §components, the components of such a pair $p=(a,b)$ are $p_1=a$ and $p_2=b$; in particular $p_1,p_2\in\mathbb{N}$ for every $p\in P$. 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. Hence the formulas and expressions below, built from components of elements of $P$ by sums, products and the order of natural numbers, quantify over sets only and use every defined set symbol properly for arguments in $P$, and every pair of such sums and products lies in $P$.

The relations $\sim$ and $\preceq$. Write $p\sim q$ for $(p,q)\in{\sim}$, as in Relations, Domain, Range, Inverse and Composition §relation. By Maps and Relations Given by Formulas §relation, applied to the set $P$ and the formula $p_1+q_2=p_2+q_1$, there is exactly one relation on $P$ with $p\sim q$ if and only if $p_1+q_2=p_2+q_1$, for all $p,q\in P$; as every element of $P$ is a pair $(a,b)$ with components $a$ and $b$, this is the relation $\sim$ of the statement, and for $a,b,c,d\in\mathbb{N}$,

$$(a,b)\sim(c,d)\quad\text{if and only if}\quad a+d=b+c.\qquad(\ast)$$

In the same way, Maps and Relations Given by Formulas §relation, applied to $P$ and the formula $p_1+q_2\le p_2+q_1$, gives a relation $\preceq$ on $P$ such that, for $a,b,c,d\in\mathbb{N}$,

$$(a,b)\preceq(c,d)\quad\text{if and only if}\quad a+d\le b+c.\qquad(\ast\ast)$$

The clause equivalence above. Let $(a,b),(c,d),(e,f)\in P$.

Reflexive: $a+b=b+a$ by Arithmetic and Order of the Natural Numbers §commutative, so $(a,b)\sim(a,b)$ by $(\ast)$. Thus $\sim$ is reflexive.

Symmetric: if $(a,b)\sim(c,d)$, then $a+d=b+c$ by $(\ast)$, so $c+b=d+a$ by Arithmetic and Order of the Natural Numbers §commutative, that is, $(c,d)\sim(a,b)$. Thus $\sim$ is symmetric.

Transitive: if $(a,b)\sim(c,d)$ and $(c,d)\sim(e,f)$, then $a+d=b+c$ and $c+f=d+e$ by $(\ast)$. Adding, $(a+d)+(c+f)=(b+c)+(d+e)$; rearranging by Arithmetic and Order of the Natural Numbers §commutative and Arithmetic and Order of the Natural Numbers §associative,

$$(a+f)+(c+d)=(b+e)+(c+d),$$

so $a+f=b+e$ by Arithmetic and Order of the Natural Numbers §cancellation, that is, $(a,b)\sim(e,f)$. Thus $\sim$ is transitive.

Hence $\sim$ is an equivalence relation on the set $P$ by Equivalence Relations on a Set §equivalence.

The clause equal above. As $\sim$ is an equivalence relation on the set $P$, the quotient $P/{\sim}$ is a set by Equivalence Classes Partition the Set: Cover, Disjointness and Representatives; the Quotient Is a Set and the Canonical Projection Is a Surjection §quotient-set. By The Quotient of a Set by an Equivalence Relation and the Canonical Projection §quotient, the elements of $P/{\sim}$ are exactly the classes $[p]$ with $p\in P$; as the elements of $P$ are exactly the pairs $(a,b)$ with $a,b\in\mathbb{N}$, these are exactly the classes $[a,b]$ with $a,b\in\mathbb{N}$. For $a,b,c,d\in\mathbb{N}$, $[a,b]=[c,d]$ if and only if $(a,b)\sim(c,d)$, by Equivalence Classes Partition the Set: Cover, Disjointness and Representatives; the Quotient Is a Set and the Canonical Projection Is a Surjection §equal, that is, by $(\ast)$, if and only if $a+d=b+c$.

The clause operations above. Operations on $P$. The expressions $(p_1+q_1,\,p_2+q_2)$ and $(p_1q_1+p_2q_2,\,p_1q_2+p_2q_1)$ lie in $P$ for all $p,q\in P$, so Maps and Relations Given by Formulas §binary, with domain $P\times P$ and values in $P$, gives maps $\oplus,\otimes:P\times P\to P$, that is, binary operations on $P$, with, in the notation of Binary Operations on a Set §notation,

$$(a,b)\oplus(c,d)=(a+c,\,b+d),\qquad(a,b)\otimes(c,d)=(ac+bd,\,ad+bc)\qquad(a,b,c,d\in\mathbb{N}).$$

Likewise Maps and Relations Given by Formulas §map, applied to $(p_2,p_1)$, gives a map $\ominus:P\to P$ with $\ominus((a,b))=(b,a)$.

Compatibility. Let $p=(a,b)$, $p'=(a',b')$, $q=(c,d)$ and $q'=(c',d')$ be elements of $P$ with $p\sim p'$ and $q\sim q'$, that is, by $(\ast)$,

$$a+b'=b+a'\qquad\text{and}\qquad c+d'=d+c'.\qquad(\dagger)$$

Sum: $p\oplus q=(a+c,b+d)$ and $p'\oplus q'=(a'+c',b'+d')$. Rearranging by Arithmetic and Order of the Natural Numbers §commutative and Arithmetic and Order of the Natural Numbers §associative and using $(\dagger)$,

$$(a+c)+(b'+d')=(a+b')+(c+d')=(b+a')+(d+c')=(b+d)+(a'+c'),$$

so $p\oplus q\sim p'\oplus q'$ by $(\ast)$.

Product: $p\otimes q=(ac+bd,ad+bc)$, $p'\otimes q=(a'c+b'd,a'd+b'c)$ and $p'\otimes q'=(a'c'+b'd',a'd'+b'c')$. First, $p\otimes q\sim p'\otimes q$: multiplying the first equation of $(\dagger)$ by $c$, and its reverse $b+a'=a+b'$ by $d$, and expanding by Arithmetic and Order of the Natural Numbers §distributive and Arithmetic and Order of the Natural Numbers §commutative,

$$ac+b'c=bc+a'c\qquad\text{and}\qquad bd+a'd=ad+b'd;$$

adding these and rearranging by Arithmetic and Order of the Natural Numbers §commutative and Arithmetic and Order of the Natural Numbers §associative,

$$(ac+bd)+(a'd+b'c)=(ad+bc)+(a'c+b'd),$$

which is $p\otimes q\sim p'\otimes q$ by $(\ast)$. Second, $p'\otimes q\sim p'\otimes q'$: multiplying the second equation of $(\dagger)$ by $a'$, and its reverse $d+c'=c+d'$ by $b'$, and expanding in the same way,

$$a'c+a'd'=a'd+a'c'\qquad\text{and}\qquad b'd+b'c'=b'c+b'd';$$

adding these and rearranging,

$$(a'c+b'd)+(a'd'+b'c')=(a'd+b'c)+(a'c'+b'd'),$$

which is $p'\otimes q\sim p'\otimes q'$ by $(\ast)$. As $\sim$ is transitive, $p\otimes q\sim p'\otimes q'$.

Negation: $\ominus(p)=(b,a)$ and $\ominus(p')=(b',a')$, and by $(\ast)$, $\ominus(p)\sim\ominus(p')$ means $b+a'=a+b'$, the first equation of $(\dagger)$ reversed.

Order: by $(\ast\ast)$, $p\preceq q$ means $a+d\le b+c$, and $p'\preceq q'$ means $a'+d'\le b'+c'$. By Arithmetic and Order of the Natural Numbers §order, $a+d\le b+c$ if and only if $(a+d)+(b'+c')\le(b+c)+(b'+c')$. Rearranging by Arithmetic and Order of the Natural Numbers §commutative and Arithmetic and Order of the Natural Numbers §associative and using $(\dagger)$ (in the form $c'+d=c+d'$),

$$(a+d)+(b'+c')=(a+b')+(c'+d)=(b+a')+(c+d')=(a'+d')+(b+c),$$

and $(b+c)+(b'+c')=(b'+c')+(b+c)$. So $a+d\le b+c$ if and only if $(a'+d')+(b+c)\le(b'+c')+(b+c)$, which by Arithmetic and Order of the Natural Numbers §order holds if and only if $a'+d'\le b'+c'$. Hence $p\preceq q$ if and only if $p'\preceq q'$.

Passing to the quotient. By the compatibility of $\oplus$ and Compatible Operations, Maps and Relations Pass to the Quotient §operation, there is exactly one binary operation $+$ on $P/{\sim}$ with $[p]+[q]=[p\oplus q]$ for all $p,q\in P$. As $p$ and $q$ run through $P$, $(p,q)$ runs through the pairs $((a,b),(c,d))$ with $a,b,c,d\in\mathbb{N}$, and $(a,b)\oplus(c,d)=(a+c,b+d)$; so this condition says exactly that $[a,b]+[c,d]=[a+c,b+d]$ for all $a,b,c,d\in\mathbb{N}$. Hence $+$ exists and is unique. In the same way, Compatible Operations, Maps and Relations Pass to the Quotient §operation applied to $\otimes$ gives the unique $\cdot$ with $[a,b]\cdot[c,d]=[ac+bd,ad+bc]$, and Compatible Operations, Maps and Relations Pass to the Quotient §map applied to $\ominus$ gives the unique map $x\mapsto-x$ with $-[a,b]=[b,a]$. Finally, Compatible Operations, Maps and Relations Pass to the Quotient §relation applied to $\preceq$ gives a relation $\le$ on $P/{\sim}$ with $([p],[q])\in{\le}$ if and only if $(p,q)\in{\preceq}$ for all $p,q\in P$, that is, by $(\ast\ast)$, with $[a,b]\le[c,d]$ if and only if $a+d\le b+c$ for all $a,b,c,d\in\mathbb{N}$; and it is unique, since by $(\ast\ast)$ every relation on $P/{\sim}$ with the latter property has the former, and the relation with the former property is unique by Compatible Operations, Maps and Relations Pass to the Quotient §relation.