Theory of Natural Number Arithmetic

Pre: Predicate Logic, Statements and Quantifiers

Computer scientists consider 0 to be part of the natural numbers: .

The set of natural numbers is countably infinite.

List

The theory contains:

Constants: (no other numerical constants)
Functions:
- (successor, plus 1)
- (addition)
- (multiplication)
Predicates:
- (less than)

is , is 2, etc.

we have finite representation of an infinite set.

Peano's Axioms

Distinction Axioms

Two axioms to state that all natural numbers are distinct:

Axiom 1 - 0 is not a Successor

Axiom 2 - Successors are Distinct

Technically this should be iff, but we don't have to write it because of the theory of equality.

Addition Axioms

Axiom 3 - Addition by 0

Axiom 4 - Addition of Successor

Example - Addition

Find

solution
3 is , 2 is .

is 5.

Note: we don't have to do proofs like this.

Multiplication Axioms

Axiom 5 - Multiplication by 0

Axiom 6 - Multiplication by Successor

Example - Multiplication

Find .

solution
is

is 4.

Induction

Axiom 7 - Induction

Regular Induction

Principle of Mathematical Induction (POMI)

Axiom

Let be an open sentence that depends on .

If statements 1 and 2 are both true:

Then statement 3 is true:

Proof Method - Induction

Proof

To prove the universally quantified statement

Prove (base case)
Prove the universally quantified implication (inductive step)
1. - inductive hypothesis
2. - inductive conclusion

If the definition of natural numbers includes , then you would prove as the base case.

Explanation

You prove that if the hypothesis is true, the conclusion must also be true, and the conclusion "becomes" the hypothesis for the next "term"

Proof of :

Proof of

Such that

AKA "domino principle"

This works because the natural numbers are ordered. Between any two natural numbers and , there are only a finite number of natural numbers.

Example Proof

Prove:

(See Summation and Product Notation, universally quantified statement)
Let be the open sentence
Base Case:
Prove (usually via direct proof])

The expression in the LHS evaluates to

The expression oh the RHS evaluates to

Since LHS = RHE, is true

Inductive Step: Let be an arbitrary natural number
Assume the inductive hypothesis, :

We want to prove , which is

Then starting with the summation on the LHS of :

Summation and Product Notation: 4 - Breaking a sum apart

The result is true for , and hence holds for all by POMI

Induction vs Deduction

Deduction: is showing a conclusion follows from the stated premises using rules of inference
Philosophical induction: deriving general principles from particular observations. The number of observations is always limited, so there can always be exceptions to the principles derived.
Mathematical induction: does deal with generalizations, but because we are dealing with an ordered domain, there can't be exceptions to the properties. As such, mathematical induction is actually mathematical deduction.

Induction with Natural Deduction

See Natural Deduction

Steps

Show these steps:

Example

Prove:

proof

Practical approach for SE212:

Use numbers as constants ()
Use instead of
Use mathematical functions (, etc)
Use predicates with well-known meanings (, etc)

Non-Zero Base Case

We can use a vacuously true implication for our base case starting at 0, which will render all values below our non-zero base case true.

Example

Prove:

proof

Other Axioms

Peano had additional axioms for the operator

Recursive Definitions

We often need to define mathematical functions.

To write a definition of a function on an ordered domain like nat, we can use a recursive function definition. A recursive function definition is one that is defined in terms of itself and certain terminating clauses.

For natural numbers, we can define a function by giving:

Its value for
Its value for in terms of (or its value for in terms of )

Example - Summation

We can write summation recursively:

As a recursive definition:

or more generally:

Example

Prove:

proof

Example

Prove that every third fib is even:

Example

Show that:

is not a tautology.

Domain:
Mapping: