proof of commutativity
   HOME

TheInfoList



OR:

This article contains
mathematical proof A mathematical proof is an inferential argument for a mathematical statement, showing that the stated assumptions logically guarantee the conclusion. The argument may use other previously established statements, such as theorems; but every proo ...
s for some properties of addition of the natural numbers: the additive identity, commutativity, and associativity. These proofs are used in the article Addition of natural numbers.


Definitions

This article will use the
Peano axioms In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly ...
for the definition of natural numbers. With these axioms, ''addition'' is defined from the constant 0 and the successor function S(a) by the two rules For the proof of commutativity, it is useful to give the name "1" to the successor of 0; that is, :1 = S(0). For every natural number ''a'', one has


Proof of associativity

We prove
associativity In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement ...
by first fixing natural numbers ''a'' and ''b'' and applying induction on the natural number ''c''. For the base case ''c'' = 0, : (''a''+''b'')+0 = ''a''+''b'' = ''a''+(''b''+0) Each equation follows by definition 1 the first with ''a'' + ''b'', the second with ''b''. Now, for the induction. We assume the induction hypothesis, namely we assume that for some natural number ''c'', : (''a''+''b'')+''c'' = ''a''+(''b''+''c'') Then it follows, In other words, the induction hypothesis holds for ''S''(''c''). Therefore, the induction on ''c'' is complete.


Proof of identity element

Definition 1states directly that 0 is a right identity. We prove that 0 is a left identity by induction on the natural number ''a''. For the base case ''a'' = 0, 0 + 0 = 0 by definition 1 Now we assume the induction hypothesis, that 0 + ''a'' = ''a''. Then This completes the induction on ''a''.


Proof of commutativity

We prove commutativity (''a'' + ''b'' = ''b'' + ''a'') by applying induction on the natural number ''b''. First we prove the base cases ''b'' = 0 and ''b'' = ''S''(0) = 1 (i.e. we prove that 0 and 1 commute with everything). The base case ''b'' = 0 follows immediately from the identity element property (0 is an
additive identity In mathematics, the additive identity of a set that is equipped with the operation of addition is an element which, when added to any element ''x'' in the set, yields ''x''. One of the most familiar additive identities is the number 0 from elemen ...
), which has been proved above: ''a'' + 0 = ''a'' = 0 + ''a''. Next we will prove the base case ''b'' = 1, that 1 commutes with everything, i.e. for all natural numbers ''a'', we have ''a'' + 1 = 1 + ''a''. We will prove this by induction on ''a'' (an induction proof within an induction proof). We have proved that 0 commutes with everything, so in particular, 0 commutes with 1: for ''a'' = 0, we have 0 + 1 = 1 + 0. Now, suppose ''a'' + 1 = 1 + ''a''. Then This completes the induction on ''a'', and so we have proved the base case ''b'' = 1. Now, suppose that for all natural numbers ''a'', we have ''a'' + ''b'' = ''b'' + ''a''. We must show that for all natural numbers ''a'', we have ''a'' + ''S''(''b'') = ''S''(''b'') + ''a''. We have This completes the induction on ''b''.


See also

* Binary operation * Proof *
Ring Ring may refer to: * Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry * To make a sound with a bell, and the sound made by a bell :(hence) to initiate a telephone connection Arts, entertainment and media Film and ...


References

*
Edmund Landau Edmund Georg Hermann Landau (14 February 1877 – 19 February 1938) was a German mathematician who worked in the fields of number theory and complex analysis. Biography Edmund Landau was born to a Jewish family in Berlin. His father was Leopol ...
, Foundations of Analysis, Chelsea Pub Co. . {{DEFAULTSORT:Addition Of Natural Numbers/Proofs Article proofs Abstract algebra Elementary algebra Operations on numbers