加法交換律

引理（Lemmas）

L1: $0 + n = n$

• 當 $n = 0$ 時
  $0 + 0 \overset{\text{A1}}{=} 0$，成立
• 設 $n = k$ 時
  $0 + k = k$，成立
• 則 $n = S(k)$ 時
  $0 + S(k) \overset{\text{A2}}{=} S(0 + k) \overset{\text{IH}}{=} S(k)$，成立
• 由MI可知
  $0 + n = n \quad \forall n \in \mathbb{N}_0$

L2: $S(m) + n = S(m + n)$

固定 $m$，對 $n$ 作歸納：

• 當 $n = 0$ 時
  $S(m) + 0 \overset{\text{A1}}{=} S(m) \overset{\text{A1}}{=} S(m + 0)$，成立
• 設 $n = k$ 時
  $S(m) + k = S(m + k)$，成立
• 則 $n = S(k)$ 時
  $S(m) + S(k) \overset{\text{A2}}{=} S(S(m) + k) \overset{\text{IH}}{=} S(S(m + k)) \overset{\text{A2}}{=} S(m + S(k))$，成立
• 由MI可知
  $S(m) + n = S(m + n) \quad \forall m, n \in \mathbb{N}_0$

加法交換律（Commutative property of addition）

• 當 $n = 0$ 時
  $m + 0 = 0 + m$，成立
  • 當 $m = 0$ 時
    $0 + 0 \overset{\text{A1}}{=} 0 \overset{\text{L1}}{=} 0 + 0$，成立
  • 設 $m = l$ 時
    $l + 0 = 0 + l$，成立
  • 則 $m = S(l)$ 時
    $S(l) + 0 \overset{\text{L2}}{=} S(l + 0) \overset{\text{IH}}{=} S(0 + l) \overset{\text{A2}}{=} 0 + S(l)$，成立
  • 由MI可知
    $m + 0 = 0 + m \quad \forall m \in \mathbb{N}_0$
• 設 $n = k$ 時
  $m + k = k + m$，成立
• 則 $n = S(k)$ 時
  $m + S(k) \overset{\text{A2}}{=} S(m + k) \overset{\text{IH}}{=} S(k + m) \overset{\text{L2}}{=} S(k) + m$，成立
• 由MI可知
  $m + n = n + m \quad \forall m, n \in \mathbb{N}_0$

證明依賴關係