Natural Number Addition Commutativity with Successor

Theorem

Let $\N$ be the natural numbers.

Then:

$\forall m, n \in \N: m^+ + n = \left({m + n}\right)^+$

Proof

Proof by induction:

From Definition by Induction of Natural Number Addition‎, we have by definition that:

	\(\displaystyle \)	\(\displaystyle \forall m, n \in \N:\)	\(\displaystyle \)	\(\displaystyle m + 0\)	\(=\)	\(\displaystyle m\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \left({m + n}\right)^+\)	\(=\)	\(\displaystyle m + n^+\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

For all $n \in \N$, let $P \left({n}\right)$ be the proposition:

$\forall m \in \N: m^+ + n = \left({m + n}\right)^+$

Basis for the Induction

By definition, we have:

	\(\displaystyle \)	\(\displaystyle \forall m \in \N:\)	\(\displaystyle \)	\(\displaystyle m^+ + 0\)	\(=\)	\(\displaystyle m^+\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	by definition
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({m + 0}\right)^+\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	by definition: $m = m + 0$

Thus $P \left({0}\right)$ is seen to be true.

This is our basis for the induction.

Induction Hypothesis

Now we need to show that, if $P \left({k}\right)$ is true, where $k \ge 0$, then it logically follows that $P \left({k^+}\right)$ is true.

So this is our induction hypothesis $P \left({k}\right)$:

$\forall m \in \N: m^+ + k = \left({m + k}\right)^+$

Then we need to show that $P \left({k^+}\right)$ follows directly from $P \left({k}\right)$:

$\forall m \in \N: m^+ + k^+ = k^+ = \left({m + k^+}\right)^+$

Induction Step

This is our induction step:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle m^+ + k^+\)	\(=\)	\(\displaystyle \left({m^+ + k}\right)^+\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	by definition
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({\left({m + k}\right)^+}\right)^+\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	from the induction hypothesis
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({m + k^+}\right)^+\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	by definition

So $P \left({k}\right) \implies P \left({k^+}\right)$ and the result follows by the Principle of Finite Induction.

Therefore:

$\forall m, n \in \N: m^+ + n = \left({m + n}\right)^+$

$\blacksquare$

Sources

• Paul R. Halmos: Naive Set Theory (1960)... (previous)... (next): $\S 13$: Arithmetic