Addition of natural numbers/Proofs


Addition of natural numbers/Proofs

Mathematical proofs for addition of the natural numbers: additive identity, commutativity, and associativity. These proofs are used in the article Addition 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)\&= a + S(0)\&= 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


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.