Skip to main content
Logo image

Elementary Foundations: An introduction to topics in discrete mathematics

Jeremy Sylvestre

🔗

Section 11.4 Inductive definitions

🔗
We can use the idea of recursive definitions in a more general manner.
🔗
inductive definition
🔗
a method of defining a collection of objects, where each object in the collection can be constructed from objects assumed or already known to exist in the collection
base clause
🔗
a statement specifying some specific initial objects that belong to the inductively-defined set
inductive clause
🔗
a statement describing a means to determine new objects in the inductively-defined set from those already known to belong
limiting clause
🔗
a declaration that no objects belong to the inductively-defined set unless obtained from a finite number of applications of the base and inductive clauses
🔗

Example 11.4.1. Set of all possible logical statements.

🔗
Let us define a set L with the following inductive definition.
🔗

Base clause.

🔗
For every m∈N, the statement variable pm belongs to L.
🔗

Inductive clause.

🔗
🔗
Given statements A,B∈L, the statements
¬A,A∧B,A∨B,A→B,A↔B
🔗
are also elements of L.
🔗

Limiting clause.

🔗
The set L does not contain any elements except those that can be obtained from a finite number of applications of the base and inductive clauses.
🔗
🔗
For example, the logical statement ¬p2∧(p1→p2) is in L by the following construction.
p1,p2∈L⇒¬p2∈L,p1→p2∈L⇒¬p2∧(p1→p2)∈L
🔗

Example 11.4.2. Set-theoretic construction of the natural numbers.

🔗
We assume that an empty set ∅ exists. Let us define a set N inductively.
🔗

Base clause.

🔗
The empty set ∅ is an element of N.
🔗

Inductive clause.

🔗
If X is an element of N and X itself is a set, then the set X+=X∪{X} is also an element of N.
🔗

Limiting clause.

🔗
The set N does not contain any other elements except those that can be obtained from a finite number of applications of the base and inductive clauses.
🔗
Note that the three clauses together imply that every element of N must be a set, so the “and X itself is a set” part of the inductive clause is superfluous.
🔗
🔗
Since the base clause involves a single initial element of N and the inductive clause produces one new element of N from a single old element of N, we can explicitly carry out the construction step-by-step. We now define the natural numbers to be the elements in this construction:
0=∅,1=0+=0∪{0}=∅∪{0}={0}≠0,2=1+=1∪{1}={0}∪{1}={0,1}≠0,1,3=2+=2∪{2}={0,1}∪{2}={0,1,2}≠0,1,2⋮
🔗
We usually write N for this set instead of N.
🔗
Note that the number of elements in each natural number (as a set) is equal to the number defined by that set, and that each natural number m is defined to be the set that we have previously called N<m.
🔗

Bonus.

🔗
In Example 11.4.2 above, we constructed the set N inductively using only the axioms of set theory. But how do we do arithmetic with this definition? We can define addition as an infinite collection of inductively-defined functions: for each m∈N, define a “sum with m” function sm:N→N as follows.
🔗

Inductive clause.

🔗
🔗
For n∈N such that sm(n) is already defined, set
sm(n+)=sm(n)+=sm(n)∪{sm(n)}.
🔗
That is, if sm(n) is defined and n+ is the next natural number after n in the inductive definition of N, then define sm(n+) to be the next natural number after sm(n).
🔗
We then use the symbols m+n to mean sm(n). In this notation, you can think of the inductive clause above as saying that once m+n is defined, we can define m+(n+1) as (m+n)+1.
🔗
If you are bored on a Friday or Saturday night, you can try the following using the above definition of addition in N.
🔗

Checkpoint 11.4.3.

🔗
  1. 🔗
    Prove that addition in N is:
    1. 🔗
      commutative: m+n=n+m, i.e. sm(n)=sn(m) for all m,n∈N; and
    2. 🔗
      associative: (m+n)+ℓ=m+(n+ℓ), i.e. ssm(n)(ℓ)=sm(sn(ℓ)), for all m,n,ℓ∈N.
  2. 🔗
    Use the idea that every positive integer should have a negative to define Z as a subset of the Cartesian product N×N. Then define addition and subtraction in Z.
Hint.
To define Z, first choose an appropriate one-to-one function embedding N into N×N in such a way that will then allow you to attach an additional second piece of information to each natural number (namely, a designator of the sign of the number).
<Prev^TopNext>