Arithmetic in \(\symbb{N}\)

Proof. To prove existence, define the set \[ M \coloneq \{ a \in \symbb{N}\colon \exists f_a \colon \symbb{N}\to \symbb{N}\text{ satisfying } \eqref{eq:1} \text{ and } \eqref{eq:2} \} \subseteq \symbb{N} \] and apply the principle of induction. Define \(f_1 \colon \symbb{N}\to \symbb{N}\) by \(f_1(b) = \sigma(b)\) for all \(b \in \symbb{N}\).² Then \(f_1\) satisfies \(\eqref{eq:1}\) because \(f_1(1) = \sigma(1)\), and \(f_1\) satisfies \(\eqref{eq:2}\) because for all \(b \in \symbb{N}\), \(f_1(\sigma(b)) = \sigma(\sigma(b)) = \sigma(f_1(b))\). Since \(f_1\) satisfies \(\eqref{eq:1}\) and \(\eqref{eq:2}\), \(1 \in M\).

Next suppose \(a \in M\), so there is at least one function \(f_a \colon \symbb{N}\to \symbb{N}\) satisfying \(\eqref{eq:1}\) and \(\eqref{eq:2}\). Using \(f_a\), define \(f_{\sigma(a)} \colon \symbb{N}\to \symbb{N}\) by \(f_{\sigma(a)}(b) = \sigma(f_a(b))\) for all \(b \in \symbb{N}\).³ Then \(f_{\sigma(a)}\) satisfies \(\eqref{eq:1}\) because \(f_{\sigma(a)}(1) = \sigma(f_a(1)) = \sigma(\sigma(a))\), and \(f_{\sigma(a)}\) satisfies \(\eqref{eq:2}\) because \[\begin{align*} f_{\sigma(a)}(\sigma(b)) &= \sigma(f_a(\sigma(b)))\\[0.75em] &= \sigma(\sigma(f_a(b)))\\[0.75em] &= \sigma(f_{\sigma(a)}(b)). \end{align*}\] Since \(f_{\sigma(a)}\) satisfies \(\eqref{eq:1}\) and \(\eqref{eq:2}\), \(\sigma(a) \in M\), so \(M = \symbb{N}\).

To prove uniqueness, for chosen \(a \in \symbb{N}\) suppose there are functions \(f_a \colon \symbb{N}\to \symbb{N}\) and \(g_a \colon \symbb{N}\to \symbb{N}\) both satisfying \(\eqref{eq:1}\) and \(\eqref{eq:2}\), and define the set \[ N \coloneq \{ b \in \symbb{N}\colon f_a(b) = g_a(b) \} \subseteq \symbb{N} \] and apply the principle of induction. By \(\eqref{eq:1}\), \(f_a(1) = \sigma(a) = g_a(1)\), so \(1 \in N\). Next suppose \(b \in N\), so \(f_a(b) = g_a(b)\). Then by \(\eqref{eq:2}\) and this assumption, \(f_a(\sigma(b)) = \sigma(f_a(b)) = \sigma(g_a(b)) = g_a(\sigma(b))\), so \(\sigma(b) \in N\). Therefore \(N = \symbb{N}\), and the uniqueness of \(f_a\) has been proven for the chosen \(a \in \symbb{N}\). Since \(a \in \symbb{N}\) was arbitrary, this argument applies for any \(a \in \symbb{N}\). \(\blacksquare\)

Proof. To prove existence, for any \(a \in \symbb{N}\), define \(a + b \coloneq f_a(b)\) for all \(b \in \symbb{N}\) where \(f_a\) comes from Lemma 1. By Lemma 1, this is well-defined. Using this definition of addition, \(a + 1 = f_a(1) = \sigma(a)\) by \(\eqref{eq:1}\), so \(\eqref{eq:3}\) is satisfied. Again using the definition of addition, \(a + \sigma(b) = f_a(\sigma(b)) = \sigma(f_a(b)) = \sigma(a + b)\) by \(\eqref{eq:2}\), so \(\eqref{eq:4}\) is satisfied.

To prove uniqueness, suppose there are binary operations \(+ \colon \symbb{N}\times \symbb{N}\to \symbb{N}\) and \(\mathbin{\tilde{+}}\colon \symbb{N}\times \symbb{N}\to \symbb{N}\), both of which satisfy \(\eqref{eq:3}\) and \(\eqref{eq:4}\). For chosen \(a \in \symbb{N}\), define the set \(M_a \coloneq \{ b \in \symbb{N}\colon a + b = a \mathbin{\tilde{+}}b \} \subseteq \symbb{N}\). By \(\eqref{eq:3}\), \(a + 1 = \sigma(a) = a \mathbin{\tilde{+}}1\), so \(1 \in M_a\). Next assume that \(b \in M_a\), so \(a + b = a \mathbin{\tilde{+}}b\). Then by \(\eqref{eq:4}\), \(a + \sigma(b) = \sigma(a + b) = \sigma(a \mathbin{\tilde{+}}b) = a \mathbin{\tilde{+}}\sigma(b)\), so \(\sigma(b) \in M_a\) and therefore \(M_a = \symbb{N}\). Since \(a \in \symbb{N}\) was arbitrary, this argument applies for any \(a \in \symbb{N}\) and therefore \(a + b = a \mathbin{\tilde{+}}b\) for all \(a, b \in \symbb{N}\). \(\blacksquare\)

Proof. For chosen \(a, b \in \symbb{N}\), define the set \(M_{a, b} \coloneq \{ c \in \symbb{N}\colon (a + b) + c = a + (b + c) \} \subseteq \symbb{N}\). Since \(+\) is a binary operation, \(a + b \in \symbb{N}\), and by definition of \(+\), \((a + b) + 1 = \sigma(a + b) = a + \sigma(b) = a + (b + 1)\), so \(1 \in M_{a, b}\). Next assume that \(c \in M_{a, b}\), so \((a + b) + c = a + (b + c)\). Then \[\begin{align*} (a + b) + \sigma(c) &= \sigma((a + b) + c)\\[0.75em] &= \sigma(a + (b + c))\\[0.75em] &= a + \sigma(b + c)\\[0.75em] &= a + (b + \sigma(c)), \end{align*}\] so \(\sigma(c) \in M_{a, b}\) and therefore \(M_{a, b} = \symbb{N}\). Since \(a, b \in \symbb{N}\) were arbitrary, this argument applies for any \(a, b \in \symbb{N}\). \(\blacksquare\)

Proof. For chosen \(a \in \symbb{N}\), define the set \(M_a \coloneq \{ b \in \symbb{N}\colon a + b = b + a \} \subseteq \symbb{N}\). By \(\eqref{eq:3}\) and the definition of addition in terms of the functions \(f\) as in the proofs of Proposition 1 and Lemma 1, \(a + 1 = \sigma(a) = f_1(a) = 1 + a\), so \(1 \in M_a\). Next assume that \(b \in M_a\), so \(a + b = b + a\). Then by \(\eqref{eq:4}\) and again using the proofs of Proposition 1 and Lemma 1, \[\begin{align*} a + \sigma(b) &= \sigma(a + b)\\[0.75em] &= \sigma(b + a)\\[0.75em] &= \sigma(f_b(a))\\[0.75em] &= f_{\sigma(b)}(a)\\[0.75em] &= \sigma(b) + a, \end{align*}\] so \(\sigma(b) \in M_{a}\), and therefore \(M_a = \symbb{N}\). Since \(a \in \symbb{N}\) was arbitrary, this argument applies for any \(a \in \symbb{N}\). \(\blacksquare\)

Proof. To prove existence, define the set \[ M \coloneq \{ a \in \symbb{N}\colon \exists g_a \colon \symbb{N}\to \symbb{N}\text{ satisfying } \eqref{eq:5} \text{ and } \eqref{eq:6} \} \subseteq \symbb{N} \] and apply the principle of induction. Define \(g_1 \colon \symbb{N}\to \symbb{N}\) by \(g_1(b) = b\) for all \(b \in \symbb{N}\).⁴ Then \(g_1\) satisfies \(\eqref{eq:5}\) because \(g_1(1) = 1\), and \(g_1\) satisfies \(\eqref{eq:6}\) because for all \(b \in \symbb{N}\), \(g_1(\sigma(b)) = \sigma(b) = b + 1 = g_1(b) + 1\). Since \(g_1\) satisfies \(\eqref{eq:5}\) and \(\eqref{eq:6}\), \(1 \in M\).

Next suppose \(a \in M\), so there is at least one function \(g_a \colon \symbb{N}\to \symbb{N}\) satisfying \(\eqref{eq:5}\) and \(\eqref{eq:6}\). Using \(g_a\), define \(g_{\sigma(a)} \colon \symbb{N}\to \symbb{N}\) by \(g_{\sigma(a)}(b) = g_a(b) + b\) for all \(b \in \symbb{N}\).⁵ Then \(g_{\sigma(a)}\) satisfies \(\eqref{eq:5}\) because \(g_{\sigma(a)}(1) = g_a(1) + 1 = a + 1 = \sigma(a)\), and \(g_{\sigma(a)}\) satisfies \(\eqref{eq:6}\) because \[\begin{align*} g_{\sigma(a)}(\sigma(b)) &= g_a(\sigma(b)) + \sigma(b)\\[0.75em] &= (g_a(b) + a) + \sigma(b)\\[0.75em] &= g_a(b) + (a + \sigma(b))\\[0.75em] &= g_a(b) + \sigma(a + b)\\[0.75em] &= g_a(b) + \sigma(b + a)\\[0.75em] &= g_a(b) + (b + \sigma(a))\\[0.75em] &= (g_a(b) + b) + \sigma(a)\\[0.75em] &= g_{\sigma(a)}(b) + \sigma(a). \end{align*}\] Since \(g_{\sigma(a)}\) satisfies \(\eqref{eq:5}\) and \(\eqref{eq:6}\), \(\sigma(a) \in M\), so \(M = \symbb{N}\).

To prove uniqueness, for chosen \(a \in \symbb{N}\) suppose there are functions \(g_a \colon \symbb{N}\to \symbb{N}\) and \(h_a \colon \symbb{N}\to \symbb{N}\) both satisfying \(\eqref{eq:5}\) and \(\eqref{eq:6}\), and define the set \[ N \coloneq \{ b \in \symbb{N}\colon g_a(b) = h_a(b) \} \subseteq \symbb{N} \] and apply the principle of induction. By \(\eqref{eq:5}\), \(g_a(1) = a = h_a(1)\), so \(1 \in N\). Next suppose \(b \in N\), so \(g_a(b) = h_a(b)\). Then by \(\eqref{eq:6}\) and this assumption, \(g_a(\sigma(b)) = g_a(b) + a = h_a(b) + a = h_a(\sigma(b))\), so \(\sigma(b) \in N\). Therefore \(N = \symbb{N}\), and the uniqueness of \(g_a\) has been proven for the chosen \(a \in \symbb{N}\). Since \(a \in \symbb{N}\) was arbitrary, this argument applies for any \(a \in \symbb{N}\). \(\blacksquare\)

Proof. To prove existence, for any \(a \in \symbb{N}\), define \(a \cdot b \coloneq g_a(b)\) for all \(b \in \symbb{N}\) where \(g_a\) comes from Lemma 2. By Lemma 2, this is well-defined. Using this definition of multiplication, \(a \cdot 1 = g_a(1) = a\), so \(\eqref{eq:7}\) is satisfied. Again using the definition of multiplication, \(a \cdot \sigma(b) = g_a(\sigma(b)) = g_a(b) + a = (a \cdot b) + a\) by \(\eqref{eq:6}\), so \(\eqref{eq:8}\) is satisfied.

To prove uniqueness, suppose there are binary operations \(\cdot \colon \symbb{N}\times \symbb{N}\to \symbb{N}\) and \(\mathbin{\tilde{\cdot}}\colon \symbb{N}\times \symbb{N}\to \symbb{N}\), both of which satisfy \(\eqref{eq:7}\) and \(\eqref{eq:8}\). For chosen \(a \in \symbb{N}\), define the set \(M_a \coloneq \{ b \in \symbb{N}\colon a \cdot b = a \mathbin{\tilde{\cdot}}b \} \subseteq \symbb{N}\). By \(\eqref{eq:7}\), \(a \cdot 1 = a = a \mathbin{\tilde{\cdot}}1\), so \(1 \in M_a\). Next assume that \(b \in M_a\), so \(a \cdot b = a \mathbin{\tilde{\cdot}}b\). Then by \(\eqref{eq:8}\), \(a \cdot \sigma(b) = (a \cdot b) + a = (a \mathbin{\tilde{\cdot}}b) + a = a \mathbin{\tilde{\cdot}}\sigma(b)\), so \(\sigma(b) \in M_a\) and therefore \(M_a = \symbb{N}\). Since \(a \in \symbb{N}\) was arbitrary, this argument applies for any \(a \in \symbb{N}\) and therefore \(a \cdot b = a \mathbin{\tilde{\cdot}}b\) for all \(a, b \in \symbb{N}\). \(\blacksquare\)

Proof. For chosen \(a, b \in \symbb{N}\), define the set \(M_{a, b} \coloneq \{ c \in \symbb{N}\colon a \cdot (b + c) = (a \cdot b) + (a \cdot c) \} \subseteq \symbb{N}\). By definition of addition and multiplication, \(a \cdot (b + 1) = a \cdot \sigma(b) = (a \cdot b) + a = (a \cdot b) + (a \cdot 1)\), so \(1 \in M_{a, b}\). Next assume that \(c \in M_{a, b}\), so \(a \cdot (b + c) = (a \cdot b) + (a \cdot c)\). Then \[\begin{align*} a \cdot (b + \sigma(c)) &= a \cdot \sigma(b + c)\\[0.75em] &= (a \cdot (b + c)) + a\\[0.75em] &= ((a \cdot b) + (a \cdot c)) + a\\[0.75em] &= (a \cdot b) + ((a \cdot c) + a)\\[0.75em] &= (a \cdot b) + (a \cdot \sigma(c)), \end{align*}\] so \(\sigma(c) \in M_{a, b}\) and therefore \(M_{a, b} = \symbb{N}\). Since \(a, b \in \symbb{N}\) were arbitrary, this argument applies for any \(a, b, \in \symbb{N}\). \(\blacksquare\)

Proof. For chosen \(a, b \in \symbb{N}\), define the set \(M_{a, b} \coloneq \{ c \in \symbb{N}\colon (a \cdot b) \cdot c = a \cdot (b \cdot c) \} \subseteq \symbb{N}\). Since \(\cdot\) is a binary operation, \(a \cdot b \in \symbb{N}\), and by definition of \(\cdot\), \((a \cdot b) \cdot 1 = a \cdot b = a \cdot (b \cdot 1)\), so \(1 \in M_{a, b}\). Next assume that \(c \in M_{a, b}\), so \((a \cdot b) \cdot c = a \cdot (b \cdot c)\). Then \[\begin{align*} (a \cdot b) \cdot \sigma(c) &= ((a \cdot b) \cdot c) + (a \cdot b)\\[0.75em] &= (a \cdot (b \cdot c)) + (a \cdot b)\\[0.75em] &= a \cdot ((b \cdot c) + b)\\[0.75em] &= a \cdot (b \cdot \sigma(c)), \end{align*}\] so \(\sigma(c) \in M_{a, b}\) and therefore \(M_{a, b} = \symbb{N}\). Since \(a, b \in \symbb{N}\) were arbitrary, this argument applies for any \(a, b, \in \symbb{N}\). \(\blacksquare\)

Proof. For chosen \(a \in \symbb{N}\), define the set \(M_a \coloneq \{ b \in \symbb{N}\colon a \cdot b = b \cdot a \} \subseteq \symbb{N}\). By \(\eqref{eq:7}\) and the definition of multiplication in terms of the functions \(g\) as in the proofs of Proposition 2 and Lemma 2, \(a \cdot 1 = a = g_1(a) = 1 \cdot a\), so \(1 \in M_a\). Next assume that \(b \in M_a\), so \(a \cdot b = b \cdot a\). Then by \(\eqref{eq:8}\) and again using the proofs of Proposition 2 and Lemma 2, \[\begin{align*} a \cdot \sigma(b) &= (a \cdot b) + a\\[0.75em] &= (b \cdot a) + a\\[0.75em] &= g_b(a) + a\\[0.75em] &= g_{\sigma(b)}(a)\\[0.75em] &= \sigma(b) \cdot a, \end{align*}\] so \(\sigma(b) \in M_a\) and therefore \(M_a = \symbb{N}\). Since \(a \in \symbb{N}\) was arbitrary, this argument applies for any \(a \in \symbb{N}\). \(\blacksquare\)