Tao Analysis: Exercise 2.2.1

This is a proof of the associative property of natural number addition. We will show that for any natural numbers $$ a, b, and\, c $$, we have $$ (a+b)+c = a+(b+c) $$.

To show this, let's induct on $$ c $$. First, let's deal with the base case where $$ c=0$$:

$$ c=0 $$Assumed
$$ b+0=b $$Lemma 2.2.2
$$ (a+b)+c=(a+b)+0 $$Substitution
$$ =a+b $$Lemma 2.2.2
$$ =a+(b+0) $$Substitution
Therefore, $$ (a+b)+0=a+(b+0) $$, proving the base case.

Now, the inductive case. Here we are assuming that $$ (a+b)+c=a+(b+c)$$ for some natural number $$ c $$.

$$ (a+b)+(c++)=(c++)+(a+b) $$Commutative property
$$ =(c+(a+b))++ $$Definition of addition
$$ =((a+b)+c)++ $$Commutative property
$$ =(a+(b+c))++ $$Inductive hypothesis
$$ =((b+c)+a)++ $$Commutative property
$$ =((b+c)++)+a $$Definition of addition
$$ =((c+b)++)+a $$Commutative property
$$ =((c++)+b)+a $$Definition of addition
$$ =a+(b+(c++)) $$Commutative property x2
The induction is closed. Therefore, $$ (a+b)+c=a+(b+c) $$ for all natural numbers $$ a, b, and\,c $$.



Comments

Post a Comment

Popular posts from this blog

Tao Analysis: Exercise 2.2.2

This is a proof that for any positive number $ a $, there exists exactly one natural number $$ b $$ , such that $ b++=a $. To do this, we will first prove that there always exists at most one, then we will prove that there always exists at least one. The existence of at most one predecessor can be proven by contradiction. Say there existed two natural numbers, b and c, such that $ b++=a $, $ c++=a $, and $ b \neq c $. By substitution, this means that $ b++=c++ $ and $ b \neq c $, which violates Axiom 2.4 . The existence of at least one predecessor can be proven by induction. Let $ P(a) $ be the fact that if $ a $ is positive, then there exists at least one natural $ b $ such that $ b++=a $. When $ a=0 $, $ P(a) $ is vacuously true because 0 is not positive, by definition of positive. Now let's assume that $ P(a) $ applies for some natural number $ a $. By Lemma E.-1 , $ a++ $ must be positive. We also know that there exists at least one predecessor to $ a++ $, that
Read more