- Addition of natural numbers/Proofs
Mathematical

proof s foraddition of thenatural numbers : additive identity, commutativity, and associativity. These proofs are used in the articleAddition of natural numbers .**Definitions**This article will use the definitions in addition of natural numbers, particularly [A1] and [A2] :

- a + 0 = a [A1]
- a + S(b) = S(a + b) [A2]

It is useful to define another natural number closely related to the successor function, namely "1". We define 1 to be the successor of 0, in other words,

: $1\; equiv\; S(0),$.

Note that for all natural numbers "a",

: $egin\{align\}S(a)\; =\; S(a\; +\; 0)\backslash =\; a\; +\; S(0)\backslash =\; a\; +\; 1end\{align\}$

due to [A1] and [A2] .

**Proof of associativity**We prove

associativity 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 [A1] ; 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,

: ("a" + "b") + "S"("c") : = "S"(("a" + "b") + "c") [by A2] : = "S"("a" + ("b" + "c")) [by the induction hypothesis] : = "a" + "S"("b" + "c") [by A2] : = "a" + ("b" + "S"("c")) [by A2]

In other words, the induction hypothesis holds for "S"("c"). Therefore, the induction on "c" is complete.

**Proof of identity element**Definition [A1] states 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 [A1] .Now we assume the induction hypothesis, that 0 + "a" = "a".Then: 0 + "S"("a"): = "S"(0 + "a") [by A2] : = "S"("a") [by the induction hypothesis] This completes the induction on "a".

**Proof of commutativity**We prove

commutativity 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), 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). Clearly, for "a" = 0, we have 0 + 1 = 0 + "S"(0) = "S"(0 + 0) = "S"(0) = 1 = 1 + 0. Now, suppose "a" + 1 = 1 + "a". Then

: "S"("a") + 1: = "S"("a") + "S"(0): = "S"("S"("a") + 0) [by A2] : = "S"(("a" + 1) + 0): = "S"("a" + 1) [by A1] : = "S"(1 + "a") [by the induction hypothesis] : = 1 + "S"("a") [by A2]

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

: "a" + "S"("b"): = "a" + ("b" + 1): = ("a" + "b") + 1 [by associativity] : = ("b" + "a") + 1 [by the induction hypothesis] : = "b" + ("a" + 1) [by associativity] : = "b" + (1 + "a") [by the base case "b" = 1] : = ("b" + 1) + "a" [by associativity] : = "S"("b") + "a"

This completes the induction on "b".

**See also***

Binary operation

*Commutativity

*Associativity

*Induction

*Proof

*Identity

*Ring**References***

Edmund Landau , Foundations of Analysis, Chelsea Pub Co. ISBN 0-8218-2693-X.

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**Addition of natural numbers**— is the most basic arithmetic binary operation. The operation addition takes two natural numbers, the augend and addend, and produces a single number, the sum. The set of natural numbers will be denoted by N, and 0 will be used to denote the… … Wikipedia**Addition**— is the mathematical process of putting things together. The plus sign + means that two numbers are added together. For example, in the picture on the right, there are 3 + 2 apples meaning three apples and two other apples which is the same as… … Wikipedia**List of mathematics articles (A)**— NOTOC A A Beautiful Mind A Beautiful Mind (book) A Beautiful Mind (film) A Brief History of Time (film) A Course of Pure Mathematics A curious identity involving binomial coefficients A derivation of the discrete Fourier transform A equivalence A … Wikipedia**Mathematical induction**— can be informally illustrated by reference to the sequential effect of falling dominoes. Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers (positive… … Wikipedia**mathematics, foundations of**— Scientific inquiry into the nature of mathematical theories and the scope of mathematical methods. It began with Euclid s Elements as an inquiry into the logical and philosophical basis of mathematics in essence, whether the axioms of any system… … Universalium**Ordinal arithmetic**— In the mathematical field of set theory, ordinal arithmetic describes the three usual operations on ordinal numbers: addition, multiplication, and exponentiation. Each can be defined in essentially two different ways: either by constructing an… … Wikipedia**Curry–Howard correspondence**— A proof written as a functional program: the proof of commutativity of addition on natural numbers in the proof assistant Coq. nat ind stands for mathematical induction, eq ind for substitution of equals and f equal for taking the same function… … Wikipedia**Rippling**— [Rippling: Meta Level Guidance for Mathematical Reasoning, Alan Bundy, David Basin, Dieter Hutter, Andrew Ireland,Cambridge University Press, 2005. ISBN 052183449X] refers to a group of meta level heuristics, developed primarily in the… … Wikipedia**mathematics**— /math euh mat iks/, n. 1. (used with a sing. v.) the systematic treatment of magnitude, relationships between figures and forms, and relations between quantities expressed symbolically. 2. (used with a sing. or pl. v.) mathematical procedures,… … Universalium**metalogic**— /met euh loj ik/, n. the logical analysis of the fundamental concepts of logic. [1835 45; META + LOGIC] * * * Study of the syntax and the semantics of formal languages and formal systems. It is related to, but does not include, the formal… … Universalium