The integers
An Introduction to Real Analysis
2025-11-02
Conceptually, the integers \(\symbb{Z}\) are an extension of the natural numbers \(\symbb{N}\) through the addition of additive inverses \(-1, -2, -3, \dots\) and an additive identity \(0\). Therefore as in Katznelson and Katznelson (2024, 6) one would like to define \[ \symbb{Z}\coloneq \symbb{N}\uplus \{ 0 \} \uplus \{ -a \colon a \in \symbb{N}\}. \]
However, as occurred with the natural numbers in the Section 1.1 notes for Katznelson and Katznelson (2024), the integers can be constructed from a more fundamental object, in this case the natural numbers themselves.
The set-theoretic construction of \(\symbb{Z}\) from \(\symbb{N}\) is carried out in these Section 1.2 notes for Katznelson and Katznelson (2024). Arithmetic in \(\symbb{Z}\) is developed in the Section 1.2.1 notes. The order on \(\symbb{Z}\) is developed in the Section 1.2.2 notes. Euclidean division, which is not covered by Katznelson and Katznelson (2024) but deserves to be included as the basis for modular arithmetic, and hence as a key example in algebra, is given its own set of notes in Section 1.2.3. Radix-\(b\) representations of integers are given their own set of notes in Section 1.2.4.
Concepts of positive and negative numbers
Intuitively, natural numbers are abstract concepts that are employed for counting diverse objects. A villager notices that his children, his hands, and his oxen share a common property that might be called “twoness”. The abstract notion of quantity may have already been understood, for example when going into battle against a larger or smaller enemy tribe, but formalizing the notion of quantity by giving the name “two” to the concept of twoness makes possible not only an understanding of “more” and “fewer” but also a more precise recording and discussion of quantity.
In order to discuss changes in quantity, some notion of combining quantities must be introduced. If the villager is holding two apples and then picks another apple from the tree, one apple is added to two apples. If two apples are given to his children, then two apples are taken away, or subtracted, from three apples. If the last apple is given to his wife then he has no apples.
This informal arithmetic is limiting because it only allows the subtraction of smaller natural numbers from larger natural numbers. It appears nonsensical to consider picking three apples and then giving away four apples.
However, in some situations it is useful to entertain the concept of a quantity less than zero. If the villager lends an ox to his ox-less neighbor and the ox is then stolen, the villager’s neighbor is now in a worse circumstance than he was before borrowing the ox. He has no ox, like before, but unlike before he has a debt of one ox because he is expected to give an ox to his neighbor.
If the villager’s neighbor buys another ox to give to the villager, the villager’s neighbor has an asset of one ox, and upon giving the new ox to the villager, the asset and the debt cancel and the neighbor is back where he started, having zero oxen. A debt of one ox may thus be considered to be the opposite of an asset of one ox.
The abstraction from subtraction as removing a positive quantity, to the addition of a negative quantity, generalizes subtraction and allows for greater flexibility in modeling phenomena. Having three apples and giving away two can be understood as subtracting two apples from three apples; it can also be understood as adding the opposite of two apples to three apples. The opposite of two is a quantity that, when added to another quantity, results in a decrease of two, rather than an increase of two.
Construction of \(\symbb{Z}\) from \(\symbb{N}\)
It was determined in the Section 1.1.2 notes for Katznelson and Katznelson (2024) that if \(a, b \in \symbb{N}\) and \(a < b\), then there exists a unique \(k \in \symbb{N}\) such that \(b = a + k\). In order to go from \(a\) to \(b\), interpreted as apples or oxen or any other quantity, it’s necessary to add \(k\) to \(a\). However, in order to go in the other direction, from \(b\) to \(a\), it’s necessary to add “opposite \(k\)”, or negative \(k\), to \(b\).
Because \(k\) is uniquely determined by \(a\) and \(b\), the alternative notation \(b - a \coloneq k\) was introduced in the Section 1.1.4 notes for Katznelson and Katznelson (2024). In order to encode negative \(k\), one might try defining \(-k \coloneq a - b\), so that negative \(k\) is the reverse of \(k\). The catch is that \(a\) and \(b\) are not the only natural numbers that implicitly define \(k\). If \(b = a + k\), then for any \(c \in \symbb{N}\), \(b + c = (a + k) + c = (a + c) + k\), so \(k = b - a = (b + c) - (a + c)\). Then \(-k\) could be written as \(a - b\) or \((a + c) - (b + c)\). As a concrete if informal example, if \(5\) and \(3\) written as \(5 - 3\) were used to refer to \(2\), and \(3\) and \(5\) written as \(3 - 5\) were used to refer to \(-2\), then \(6\) and \(4\) would also refer to \(2\) and \(4\) and \(6\) would also refer to \(-2\).
Because the only tools available to construct \(\symbb{Z}\) from \(\symbb{N}\) are set theory and \(\symbb{N}\) itself (along with the associated structure of \(\symbb{N}\)), the fact that the informal reasoning laid out above involves the consideration of ordered pairs of elements of \(\symbb{N}\) strongly suggests beginning the construction of \(\symbb{Z}\) with \(\symbb{N}\times \symbb{N}\), the set of ordered pairs of elements of \(\symbb{N}\). Since certain pairs of elements of \(\symbb{N}\times \symbb{N}\), for example \(5\) and \(3\) and \(6\) and \(4\), are indistinguishable for the purpose of defining integers it is natural to look for an equivalence relation \(\sim\) to put on \(\symbb{N}\times \symbb{N}\) and then define \(\symbb{Z}\) as the quotient \((\symbb{N}\times \symbb{N}) / {\sim}\).
Working informally, if \(3 - 5 \overset{!}{=}7 - 9\) then this suggests that \((5, 3) \sim (9, 7)\) for the desired equivalence relation \(\sim\) on \(\symbb{N}\times \symbb{N}\). In order to frame this equivalence relation in terms of the tools available it suffices to move the negative terms to the other side of the equation so that the equation only involves the addition of natural numbers: \[\begin{align*} 3 - 5 &\overset{!}{=}7 - 9\\[0.75em] \implies 3 + 9 &\overset{!}{=}7 + 5. \end{align*}\] The equivalence relation must define positive integers as well, i.e., what are expected to be the natural numbers \(\symbb{N}\) within the the set of integers \(\symbb{Z}\). Therefore it should also be expected that \((3, 5) \sim (7, 9)\) because \(5 - 3 \overset{!}{=}9 - 7\), or in terms of addition of natural numbers, \(5 + 7 \overset{!}{=}9 + 3\).
More generally, if \((a, b), (c, d) \in \symbb{N}\times \symbb{N}\) then the idea that \(b - a \overset{!}{=}d - c\) can be encoded by the equation \(a + d \overset{!}{=}c + b\). Theorem 1 demonstrates that this indeed defines an equivalence relation \(\sim\) on \(\symbb{N}\times \symbb{N}\).
Theorem 1 Let the binary relation \(\sim\) on \(\symbb{N}\times \symbb{N}\) be defined by \((a, b) \sim (c, d)\) if and only if \(a + d = c + b\). Then \(\sim\) is an equivalence relation.
Proof. Since \(a + b = a + b\), it follows that \((a, b) \sim (a, b)\), so \(\sim\) is reflexive.
Next assume that \((a, b) \sim (c, d)\), so \(a + d = c + b\). Then \(c + b = a + d\), so \((c, d) \sim (a, b)\) and therefore \(\sim\) is symmetric.
Lastly suppose \((a, b) \sim (c, d)\) and \((c, d) \sim (e, f)\), so \(a + d = c + b\) and \(c + f = e + d\). Then using standard properties of addition in \(\symbb{N}\), \[\begin{align*} (a + d) + e &= (c + b) + e\\[0.75em] \implies a + (d + e) &= c + (b + e)\\[0.75em] \implies a + \underbrace{(e + d)}_{= c + f} &= c + (e + b)\\[0.75em] \implies a + (c + f) &= (e + b) + c\\[0.75em] \implies a + (f + c) &= (e + b) + c\\[0.75em] \implies (a + f) + c &= (e + b) + c. \end{align*}\] Using the cancellation law of addition from the Section 1.1.2 notes for Katznelson and Katznelson (2024), it follows that \(a + f = e + b\). Therefore \((a, b) \sim (e, f)\), whence \(\sim\) is transitive. \(\blacksquare\)
Because \(\sim\) is an equivalence relation on \(\symbb{N}\times \symbb{N}\), this set can be partitioned into the equivalence classes of the equivalence relation. The integers are defined to be this set of equivalence classes: \(\symbb{Z}\coloneq (\symbb{N}\times \symbb{N}) / {\sim}\). Therefore an integer \([(a, b)] \in \symbb{Z}\) is the equivalence class containing \((a, b) \in \symbb{N}\times \symbb{N}\), that is \[ [(a, b)] \coloneq \{ (c, d) \in \symbb{N}\times \symbb{N}\colon (c, d) \sim (a, b) \}. \]
A subset of \(\symbb{Z}\) isomorphic to \(\symbb{N}\)
An essential sanity check for the construction of \(\symbb{Z}\) is confirming that \(\symbb{Z}\) contains \(\symbb{N}\). It is conventional to write \(\symbb{N}\subseteq \symbb{Z}\) but given that \(\symbb{Z}= (\symbb{N}\times \symbb{N}) / {\sim}\), writing \(\symbb{N}\subseteq (\symbb{N}\times \symbb{N}) / {\sim}\) makes no sense. What is needed instead is to locate a subset of \(\symbb{Z}\) that behaves exactly like \(\symbb{N}\). In particular, it is necessary to locate a subset \(\tilde{\symbb{N}}\subseteq \symbb{Z}\), a successor function \(\tilde{\sigma}\colon \tilde{\symbb{N}}\to \tilde{\symbb{N}}\) and a distinguished element \(\tilde{1}\in \tilde{\symbb{N}}\) such that \((\tilde{\symbb{N}}, \tilde{\sigma}, \tilde{1})\) is a Peano system.
Because the intuition for the equivalence relation \(\sim\) on \(\symbb{N}\times \symbb{N}\) is that \((a, b) \sim (c, d)\) if and only if \(b - a \overset{!}{=}d - c\), one can guess that when looking for the right subset of \(\symbb{Z}\), \[\begin{align} 1 &\overset{!}{=}[(1, \sigma(1))] \label{eq:inform1} \\[0.75em] \sigma(1) &\overset{!}{=}[(1, \sigma(\sigma(1)))] \label{eq:inform2} \\[0.75em] \sigma(\sigma(1)) &\overset{!}{=}[(1, \sigma(\sigma(\sigma(1))))] \label{eq:inform3} \\[0.75em] & \vdotswithin{=} \notag \end{align}\] so \[ \symbb{N}\overset{!}{=}\underbrace{\{ [(1, \sigma(a))] \colon a \in \symbb{N}\}}_{\eqcolon \tilde{\symbb{N}}} \subseteq \symbb{Z}. \]
From this, one can also guess that \(\tilde{\sigma}\colon \tilde{\symbb{N}}\to \tilde{\symbb{N}}\) should be defined by \([(1, \sigma(a))] \mapsto [(1, \sigma(\sigma(a)))]\) and that the distinguished element should be \([(1, \sigma(1))] \eqcolon \tilde{1}\). Therefore one should be looking to establish something like the equation \[ (\symbb{N}, \sigma, 1) \overset{!}{=}(\tilde{\symbb{N}}, \tilde{\sigma}, \tilde{1}). \] However, as mentioned, literal equality does not make sense; instead what is needed is the notion of isomorphism.
An isomorphism is a function \(\iota \colon \symbb{N}\to \tilde{\symbb{N}}\) whose existence demonstrates that \((\symbb{N}, \sigma, 1)\) and \((\tilde{\symbb{N}}, \tilde{\sigma}, \tilde{1})\) have the same behavior in every meaningful way. In particular, an isomorphism will be used to demonstrate that \((\tilde{\symbb{N}}, \tilde{\sigma}, \tilde{1})\) is a Peano system.
If \((\symbb{N}, \sigma, 1)\) and \((\tilde{\symbb{N}}, \tilde{\sigma}, \tilde{1})\) are to be shown to have the same behavior in every meaningful way, then \(\iota\) should be a bijection. In addition the specification of \(\iota\) should involve \(\sigma\), \(\tilde{\sigma}\), \(1\) and \(\tilde{1}\) as well.
It would be reasonable to require that \(\iota(1) = \tilde{1}\) and also that \(\iota(\sigma(a)) = \tilde{\sigma}(\iota(a))\) for all \(a \in \symbb{N}\). In this way the distinguished elements of \(\symbb{N}\) and \(\tilde{\symbb{N}}\) are in correspondence and \(\iota\) plays nicely with the successor functions \(\sigma\) and \(\tilde{\sigma}\).
Definition 1 An isomorphism between triplets \((\symbb{N}, \sigma, 1)\) and \((\tilde{\symbb{N}}, \tilde{\sigma}, \tilde{1})\) is a bijection \(\iota \colon \symbb{N}\to \tilde{\symbb{N}}\) such that \[\begin{align} \iota(1) &= \tilde{1}\label{eq:defiso-1} \\[0.75em] \iota(\sigma(a)) &= \tilde{\sigma}(\iota(a)) \qquad \forall a \in \symbb{N}. \label{eq:defiso-2} \end{align}\] \(\blacksquare\)
Proposition 1 If \(\iota \colon \symbb{N}\to \tilde{\symbb{N}}\) is an isomorphism between triplets \((\symbb{N}, \sigma, 1)\) and \((\tilde{\symbb{N}}, \tilde{\sigma}, \tilde{1})\) as in Definition 1, then \[\begin{alignat}{2} \iota^{-1}(\tilde{\sigma}(\tilde{a})) &= \sigma(\iota^{-1}(\tilde{a})) \qquad &&\forall \tilde{a} \in \tilde{\symbb{N}}\label{eq:equiviso-2} . \end{alignat}\]
Proof. Consider \(\tilde{a} \in \tilde{\symbb{N}}\). Because \(\iota\) is a bijection, there exists a unique \(a \in \symbb{N}\) such that \(\iota(a) = \tilde{a}\). By Definition 1, \(\tilde{\sigma}(\tilde{a}) = \tilde{\sigma}(\iota(a)) = \iota(\sigma(a))\). Then \[\begin{align*} \iota^{-1}(\tilde{\sigma}(\tilde{a})) &= \iota^{-1}(\iota(\sigma(a)))\\[0.75em] &= \sigma(a)\\[0.75em] &= \sigma(\iota^{-1}(\tilde{a})), \end{align*}\] so \(\eqref{eq:equiviso-2}\) is satisfied. \(\blacksquare\)
Proposition 1 implies that \(\iota^{-1}\) satisfies Definition 1, so if \(\iota\) is an isomorphism between \((\symbb{N}, \sigma, 1)\) and \((\tilde{\symbb{N}}, \tilde{\sigma}, \tilde{1})\), then \(\iota^{-1}\) is an isomorphism between \((\tilde{\symbb{N}}, \tilde{\sigma}, \tilde{1})\) and \((\symbb{N}, \sigma, 1)\).
The most important result in what follows is Theorem 2, which shows that the existence of an isomorphism between a Peano system and another triplet guarantees that the latter is itself a Peano system. This result underlies Theorem 3, which defines \(\tilde{\symbb{N}}\subseteq \symbb{Z}\) along with the attendant \(\tilde{\sigma}\) and \(\tilde{1}\), and proves that there is an isomorphism \(\iota\) between \((\symbb{N}, \sigma, 1)\) and \((\tilde{\symbb{N}}, \tilde{\sigma}, \tilde{1})\). By Theorem 2 it follows that the latter is a Peano system, so all the properties of \(\symbb{N}\) developed since the Section 1.1 notes for Katznelson and Katznelson (2024) are applicable to \(\tilde{\symbb{N}}\) as well. This justifies writing \(\symbb{N}\subseteq \symbb{Z}\).
Despite their importance the proofs of Theorem 2 and Theorem 3 are not especially difficult. By contrast Theorem 4 is much more difficult to prove and unfortunately of lesser interest as well; it establishes that between any two Peano systems there is an isomorphism, but if the two triplets in question are already known to be Peano systems then the isomorphism doesn’t serve any apparent purpose.
Theorem 2 Let \((\symbb{N}, \sigma, 1)\) be a Peano system and \((\tilde{\symbb{N}}, \tilde{\sigma}, \tilde{1})\) be a triplet that is isomorphic to \((\symbb{N}, \sigma, 1)\). Then \((\tilde{\symbb{N}}, \tilde{\sigma}, \tilde{1})\) is a Peano system.
Proof. It is necessary to confirm that \((\tilde{\symbb{N}}, \tilde{\sigma}, \tilde{1})\) satisfies the three Peano axioms specified in the Section 1.1 notes for Katznelson and Katznelson (2024).
First suppose by contradiction there were some \(\tilde{a} \in \tilde{\symbb{N}}\) such that \(\tilde{1}= \tilde{\sigma}(\tilde{a})\). Apply \(\iota^{-1}\) to both sides of the equation and use Definition 1 and Proposition 1 to see that \[\begin{align*} \underbrace{\iota^{-1}(\tilde{1})}_{= 1} &= \underbrace{\iota^{-1}(\tilde{\sigma}(\tilde{a}))}_{= \sigma(\iota^{-1}(\tilde{a}))}\\[0.75em] \implies 1 &= \sigma(\iota^{-1}(\tilde{a})), \end{align*}\] which is a contradiction because \(1 \notin \symup{img}(\sigma)\). Therefore \((\tilde{\symbb{N}}, \tilde{\sigma}, \tilde{1})\) satisfies the first Peano axiom.
Next suppose that for \(\tilde{a}, \tilde{b} \in \tilde{\symbb{N}}\), \(\tilde{\sigma}(\tilde{a}) = \tilde{\sigma}(\tilde{b})\). Again applying \(\iota^{-1}\) to both sides of the equation and using Proposition 1, \[\begin{align*} \underbrace{\iota^{-1}(\tilde{\sigma}(\tilde{a}))}_{= \sigma(\iota^{-1}(\tilde{a}))} &= \underbrace{\iota^{-1}(\tilde{\sigma}(\tilde{b}))}_{= \sigma(\iota^{-1}(\tilde{b}))}\\[0.75em] \implies \sigma(\iota^{-1}(\tilde{a})) &= \sigma(\iota^{-1}(\tilde{b}))\\[0.75em] \implies \iota^{-1}(\tilde{a}) &= \iota^{-1}(\tilde{b}) \end{align*}\] because \(\sigma\) is injective. Applying \(\iota\) to both sides of the equation shows that \(\tilde{a} = \tilde{b}\), so \((\tilde{\symbb{N}}, \tilde{\sigma}, \tilde{1})\) satisfies the second Peano axiom.
Lastly, suppose \(\tilde{M} \subseteq \tilde{\symbb{N}}\) is such that \(\tilde{1}\in \tilde{M}\), and \(\tilde{a} \in \tilde{M}\) implies that \(\tilde{\sigma}(\tilde{a}) \in \tilde{M}\). Define the set \(M \coloneq \{ a \in \symbb{N}\colon \iota(a) \in \tilde{M} \}\). If \(M = \symbb{N}\) then for all \(a \in \symbb{N}\), \(\iota(a) \in \tilde{M}\), so \(\symup{img}(\iota) = \tilde{\symbb{N}}\subseteq \tilde{M} \subseteq \tilde{\symbb{N}}\), which implies that \(\tilde{M} = \tilde{\symbb{N}}\). Since \(\iota(1) = \tilde{1}\in \tilde{M}\), \(1 \in M\). Next assume that \(a \in M\), so \(\iota(a) \in \tilde{M}\). Then by assumption \(\tilde{\sigma}(\iota(a)) \in \tilde{M}\), and by Definition 1 \(\tilde{\sigma}(\iota(a)) = \iota(\sigma(a))\), so \(\sigma(a) \in M\), whence \(M = \symbb{N}\). Thus \(\tilde{M} = \tilde{\symbb{N}}\) so \((\tilde{\symbb{N}}, \tilde{\sigma}, \tilde{1})\) satisfies the third Peano axiom. \(\blacksquare\)
Theorem 3 Let \(\tilde{\symbb{N}}\coloneq \{ [(1, \sigma(a))] \colon a \in \symbb{N}\} \subseteq \symbb{Z}\), \(\tilde{\sigma}\colon \tilde{\symbb{N}}\to \tilde{\symbb{N}}\) be defined by \([(1, \sigma(a))] \mapsto [(1, \sigma(\sigma(a)))]\) and \(\tilde{1}\coloneq [(1, \sigma(1))]\). Then the triplet \((\tilde{\symbb{N}}, \tilde{\sigma}, \tilde{1})\) is a Peano system.
Proof. By Theorem 2 it suffices to show that \((\symbb{N}, \sigma, 1)\) and \((\tilde{\symbb{N}}, \tilde{\sigma}, \tilde{1})\) are isomorphic. The informal equations in \(\eqref{eq:inform1}\), \(\eqref{eq:inform2}\) and \(\eqref{eq:inform3}\) suggest a correspondence between elements of \(\symbb{N}\) and \(\tilde{\symbb{N}}\), hence they suggest the definition of \(\iota \colon \symbb{N}\to \tilde{\symbb{N}}\). This definition of \(\iota\) can then be confirmed to conform with Definition 1. Based on these equations, define \(\iota\) by \(\iota(a) = [(1, \sigma(a))]\). Then \(\iota(1) = [(1, \sigma(1))] = \tilde{1}\) so \(\iota\) satisfies \(\eqref{eq:defiso-1}\), and for all \(a \in \symbb{N}\), \(\iota(\sigma(a)) = [(1, \sigma(\sigma(a)))] = \tilde{\sigma}(\iota(a))\) so \(\iota\) satisifies \(\eqref{eq:defiso-2}\).
It remains only to verify that \(\iota\) is a bijection. That \(\iota\) is a surjection is clear because for any \([(1, \sigma(a))] \in \tilde{\symbb{N}}\), \(a \in \symbb{N}\) is such that \(\iota(a) = [(1, \sigma(a))]\). To see that \(\iota\) is an injection, note that \(\iota(a) = \iota(b)\) implies that \([(1, \sigma(a))] = [(1, \sigma(b))]\). By the definition of \(\symbb{Z}\), this implies that \((1, \sigma(a)) \sim (1, \sigma(b))\), so \(1 + \sigma(b) = 1 + \sigma(a)\). By the cancellation law of addition, \(\sigma(a) = \sigma(b)\) and therefore \(a = b\) because \(\sigma\) is an injection, so \(\iota\) itself is an injection. \(\blacksquare\)
Theorem 4 Any two Peano systems \((\symbb{N}, \sigma, 1)\) and \((\tilde{\symbb{N}}, \tilde{\sigma}, \tilde{1})\) are isomorphic.
The proof of Theorem 4 defines an isomorphism \(\iota\) between \((\symbb{N}, \sigma, 1)\) and \((\tilde{\symbb{N}}, \tilde{\sigma}, \tilde{1})\) using the set-theoretic definition of a function \(\iota \colon \symbb{N}\to \tilde{\symbb{N}}\) as a subset of the Cartesian product \(\iota \subseteq \symbb{N}\times \tilde{\symbb{N}}\) with the property that for all \(a \in \symbb{N}\), there is exactly one \(\tilde{a} \in \tilde{\symbb{N}}\) such that \((a, \tilde{a}) \in \iota\).1 A naïve approach to the proof would define a function \(\iota \colon \symbb{N}\to \tilde{\symbb{N}}\) by \(\iota(1) = \tilde{1}\), and then assuming \(\iota(a)\) has been defined, define \(\iota(\sigma(a)) = \tilde{\sigma}(\iota(a))\). By definition \(\iota\) satisfies the criteria \(\eqref{eq:defiso-1}\) and \(\eqref{eq:defiso-2}\) from Definition 1, so all that would remain is to show that \(\iota\) is a bijection.
However, it’s not clear how to complete the proof using this approach. For example, to show that \(\iota\) is an injection one might try to prove that for all \(a, b \in \symbb{N}\), \(\iota(a) = \iota(b)\) implies that \(a = b\). Similar to the proofs of statements depending on \(a, b \in \symbb{N}\) from the Section 1.1.1 notes for Katznelson and Katznelson (2024) one might choose \(a \in \symbb{N}\), define the set \(M_a \coloneq \{ b \in \symbb{N}\colon \iota(a) = \iota(b) \implies a = b \}\) and then try to prove that \(M_a = \symbb{N}\) by induction. Suppose \(a \neq 1\) and assume that \(\iota(a) = \iota(1)\). Then the statement defining \(M_a\) is false, so \(1 \notin M_a\) and the proof by induction doesn’t seem to work.
It isn’t clear how to salvage this proof, but this failed attempt at least explains the necessity for the seemingly unorthodox tactics used in the proof of Theorem 4.
In order to show that a function \(i \colon \symbb{N}\to \tilde{\symbb{N}}\) considered as a subset of the Cartesian product \(\symbb{N}\times \tilde{\symbb{N}}\) is an isomorphism, it will be helpful to reformulate conditions \(\eqref{eq:defiso-1}\) and \(\eqref{eq:defiso-2}\) from Definition 1 from this perspective. This can be done as follows: \[\begin{align} (1, \tilde{1}) &\in i \label{eq:revdefiso-1} \\[0.75em] (a, \tilde{a}) &\in i \implies (\sigma(a), \tilde{\sigma}(\tilde{a})) \in i \qquad \forall a \in \symbb{N}\label{eq:revdefiso-2}. \end{align}\]
Proof. Consider the set \[ I \coloneq \{ i \subseteq \symbb{N}\times \tilde{\symbb{N}}\colon \eqref{eq:revdefiso-1} \text{ and } \eqref{eq:revdefiso-2} \text{ are true} \}. \] Since \(\symbb{N}\times \tilde{\symbb{N}}\in I\), \(I \neq \emptyset\). Define \(\iota \coloneq \cap_{i \in I} i\). Since \((1, \tilde{1}) \in i\) for all \(i \in I\) it follows that \((1, \tilde{1}) \in \iota\), so \(\eqref{eq:revdefiso-1}\) is true for \(\iota\). Furthermore, for all \(i \in I\), \((a, \tilde{a}) \in i\) implies that \((\sigma(a), \tilde{\sigma}(\tilde{a})) \in i\) for all \(a \in \symbb{N}\), so it follows that \((a, \tilde{a}) \in \iota\) implies that \((\sigma(a), \tilde{\sigma}(\tilde{a})) \in \iota\) for all \(a \in \symbb{N}\). Thus \(\eqref{eq:revdefiso-2}\) is also true for \(\iota\), hence \(\iota \in I\) as well.
The goal in the remainder of the proof is to show that \(\iota\) is the desired isomorphism between \((\symbb{N}, \sigma, 1)\) and \((\tilde{\symbb{N}}, \tilde{\sigma}, \tilde{1})\). Since \(\iota\) satisfies \(\eqref{eq:revdefiso-1}\) and \(\eqref{eq:revdefiso-2}\), two more properties of \(\iota\) remain to be established:
- \(\iota\) is a function, and
- \(\iota\) is a bijection.
To prove that \(\iota\) is a function, consider the set \(M \coloneq \{ a \in \symbb{N}\colon \exists! \tilde{a} \in \tilde{\symbb{N}}\text{ such that } (a, \tilde{a}) \in \iota \} \subseteq \symbb{N}\). It’s already been observed that \((1, \tilde{1}) \in \iota\). Suppose there exists \(\tilde{b} \in \tilde{\symbb{N}}\setminus \{ \tilde{1}\}\) such that \((1, \tilde{b}) \in \iota\), and consider the subset \(\iota' \coloneq \iota \setminus \{ (1, \tilde{b}) \} \subseteq \symbb{N}\times \tilde{\symbb{N}}\). Since \(\tilde{b} \neq \tilde{1}\), \((1, \tilde{1}) \in \iota'\) so \(\iota'\) satisfies \(\eqref{eq:revdefiso-1}\). If \(\iota'\) did not satisfy \(\eqref{eq:revdefiso-2}\) then there is some \(a \in \symbb{N}\) such that \((a, \tilde{a}) \in \iota'\) and yet \((\sigma(a), \tilde{\sigma}(\tilde{a})) \notin \iota'\). Since \((1, \tilde{b})\) is not of the form \((\sigma(a), \tilde{\sigma}(\tilde{a}))\) and \(\iota\) satisfies \(\eqref{eq:revdefiso-2}\), \(\iota'\) must satisfy \(\eqref{eq:revdefiso-2}\) as well. Therefore \(\iota' \in I\); this is a contradiction since \(\iota' \subsetneq \iota\) and yet by definition of \(\iota\), \(\iota \subseteq \iota'\). Because of this contradiction there can be no such \(\tilde{b}\), so \(1 \in M\).
Next assume that \(a \in M\), so there exists a unique \(\tilde{a} \in \tilde{\symbb{N}}\) such that \((a, \tilde{a}) \in \iota\). Since \(\iota\) satisfies \(\eqref{eq:revdefiso-2}\), \((\sigma(a), \tilde{\sigma}(\tilde{a})) \in \iota\). Suppose there exists \(\tilde{\beta} \in \tilde{\symbb{N}}\setminus \{ \tilde{\sigma}(\tilde{a}) \}\) such that \((\sigma(a), \tilde{\beta}) \in \iota\), and consider the subset \(\iota'' \coloneq \iota \setminus \{ (\sigma(a), \tilde{\beta}) \}\). Since \((\sigma(a), \tilde{\beta}) \neq (1, \tilde{1})\) and \((1, \tilde{1}) \in \iota\), it must be that \((1, \tilde{1}) \in \iota''\) as well, so \(\iota''\) satisfies \(\eqref{eq:revdefiso-1}\). If \(\iota''\) did not satisfy \(\eqref{eq:revdefiso-2}\), then there exists \(c \in \symbb{N}\) such that \((c, \tilde{c}) \in \iota''\) and yet \((\sigma(c), \tilde{\sigma}(\tilde{c})) \notin \iota'''\). Because \(\iota'' \subseteq \iota\), it follows that \((c, \tilde{c}) \in \iota\), and since \(\iota\) satisfies \(\eqref{eq:revdefiso-2}\), it follows that \((\sigma(c), \tilde{\sigma}(\tilde{c})) \in \iota\). Therefore \((\sigma(c), \tilde{\sigma}(\tilde{c})) = (\sigma(a), \tilde{\beta})\), so \(\sigma(c) = \sigma(a)\) and therefore \(c = a\). By assumption there is a unique \(\tilde{a} \in \tilde{\symbb{N}}\) such that \((a, \tilde{a}) \in \iota\), so \(\tilde{c} = \tilde{a}\), but then \(\tilde{\beta} = \tilde{\sigma}(\tilde{c}) = \tilde{\sigma}(\tilde{a})\), which is a contradiction. Therefore \(\iota''\) must satisfy \(\eqref{eq:revdefiso-2}\) as well, so \(\iota'' \in I\). This is a contradiction for the same reason as above so there can be no such \(\tilde{\beta}\), hence \(\sigma(a) \in M\) and therefore \(M = \symbb{N}\), so \(\iota\) is a function.
To prove that \(\iota\) is a bijection, consider the set \(\tilde{M} \coloneq \{ \tilde{a} \in \tilde{\symbb{N}}\colon \exists! a \in \symbb{N}\text{ such that } \iota(a) = \tilde{a} \} \subseteq \tilde{\symbb{N}}\). Since \(\iota\) is a function, the fact that \((1, \tilde{1}) \in \iota\) can be written in the conventional form \(\iota(1) = \tilde{1}\), so there exists at least one element of \(\symbb{N}\) that \(\iota\) maps to \(\tilde{1}\in \tilde{\symbb{N}}\). If there were another \(a \neq 1\) such that \(\iota(a) = \tilde{1}\), then there exists \(a^- \in \symbb{N}\) such that \(\sigma(a^-) = a\). By \(\eqref{eq:defiso-2}\), \(\tilde{1}= \iota(a) = \iota(\sigma(a^-)) = \tilde{\sigma}(\iota(a^-))\), which is a contradiction because \(\tilde{1}\notin \symup{img}(\tilde{\sigma})\). Therefore \(1 \in \symbb{N}\) is the only element of \(\symbb{N}\) that \(\iota\) maps to \(\tilde{1}\), so \(\tilde{1}\in \tilde{M}\).
Next assume that \(\tilde{a} \in \tilde{M}\), so there is a unique \(a \in \symbb{N}\) such that \(\iota(a) = \tilde{a}\). Using \(\eqref{eq:defiso-2}\) again, \(\iota(\sigma(a)) = \tilde{\sigma}(\iota(a)) = \tilde{\sigma}(\tilde{a})\), so there exists at least one element of \(\symbb{N}\) that \(\iota\) maps to \(\tilde{\sigma}(\tilde{a}) \in \tilde{\symbb{N}}\). If there were another \(b \neq \sigma(a)\) such that \(\iota(b) = \tilde{\sigma}(\tilde{a})\), then \(b \neq 1\), because otherwise this would imply \(\iota(b) = \iota(1) = \tilde{1}= \tilde{\sigma}(\tilde{a})\), which is again a contradiction. Therefore \(b \neq 1\), so there exists \(b^- \in \symbb{N}\) such that \(\sigma(b^-) = b\). Then \(\iota(b) = \iota(\sigma(b^-)) = \tilde{\sigma}(\iota(b^-)) = \tilde{\sigma}(\tilde{a})\), and because \(\tilde{\sigma}\) is an injection, \(\iota(b^-) = \tilde{a}\). By assumption there is a unique \(a \in \symbb{N}\) such that \(\iota(a) = \tilde{a}\), so \(b^- = a\), and after applying \(\sigma\) to both sides, \(\sigma(b^-) = b = \sigma(a)\). Therefore \(\sigma(a)\) is the only element of \(\symbb{N}\) that \(\iota\) maps to \(\tilde{\sigma}(\tilde{a})\), so \(\tilde{\sigma}(\tilde{a}) \in \tilde{M}\) and therefore \(\tilde{M} = \tilde{\symbb{N}}\), so \(\iota\) is a bijection. \(\blacksquare\)
References
Footnotes
The property that \((a, \tilde{a}) \in \iota\) is usually written as \(\iota(a) = \tilde{a}\).↩︎