Abstract Algebra: Preliminaries

Natural numbers

The natural numbers are those numbers used for counting (as in "there are six coins on the table") and ordering (as in "this is the third largest city in the country"). In common mathematical terminology, words colloquially used for counting are "cardinal numbers", and words used for ordering are "ordinal numbers". The natural numbers can, at times, appear as a convenient set of codes (labels or "names"), that is, as what linguists call nominal numbers, forgoing many or all of the properties of being a number in a mathematical sense.

Some definitions begin the natural numbers with 0, corresponding to the non-negative integers {0, 1, 2, 3, ...}, whereas others start with 1, corresponding to the positive integers {1, 2, 3, ...}. Texts that exclude zero from the natural numbers sometimes refer to the natural numbers together with zero as the whole numbers, while in other writings, that term is used instead for the integers (including negative integers).

The natural numbers are a basis from which many other number sets may be built by extension: the integers, by including (if not yet in) the neutral element 0 and an additive inverse (−n) for each nonzero natural number n; the rational numbers, by including a multiplicative inverse (${\tfrac {1}{n}}$) for each nonzero integer n (and also the product of these inverses by integers); the real numbers by including with the rationals the limits of (converging) Cauchy sequences of rationals; the complex numbers, by including with the real numbers the unresolved square root of minus one (and also the sums and products thereof); and so on. This chain of extensions make the natural numbers canonically embedded (identified) in the other number systems.

In common language, particularly in primary school education, natural numbers may be called counting numbers to intuitively exclude the negative integers and zero, and also to contrast the discreteness of counting to the continuity of measurement — a hallmark characteristic of real numbers.

Well-ordering principle

Consider the following set which we define to be the set of natural numbers:

${\begin{aligned}\quad \mathbb {N} =\{1,2,3,...\}\end{aligned}}$

Now consider any subset $A$ of $\mathbb {N}$. For example, let us consider the subsets $A_{1}=\{7,29\}$, $A_{2}=\{1,3,5,...\}$, and $A_{3}=\{2,4,6,...\}$. The subset $A_{1}$ describes a finite set containing two integers. The subset $A_{2}$ describes the infinite set of all odd natural numbers, and the subset $A_{3}$ describes the infinite set of all even natural numbers. Notice that in each of these cases we can identify a least element of the subset. For example, the least element in $A_{1}$ is $7$, the least element in $A_{2}$ is $1$, and the least element in $A_{3}$ is $2$.

In fact, it is impossible to construct a nonempty subset $A$ of $\mathbb {N}$ that does not contain a least element. We describe this very important result below in the following theorem.

Theorem 1 (The Well-Ordering Principle of the Natural Numbers): Let $A$ be a nonempty subset of the natural numbers $\mathbb {N} =\{1,2,3,...\}$. Then there exists a least element $x\in A$, that is, $x\leq y$ for all $y\in A$.

We do not have the tools to prove Theorem 1 although it is a rather intuitively obvious result. Nevertheless, we should note that while Theorem 1 holds true for the set of natural numbers, it does not hold true for all sets of real numbers. For example, consider the set of rational numbers $\mathbb {Q}$:

${\begin{aligned}\quad \mathbb {Q} =\left\{{\frac {a}{b}}:a,b\in \mathbb {Z} ,b\neq 0\right\}\end{aligned}}$

Any subset of the rational numbers need not have a least element. For example, consider the following subset of rational numbers between $0$ and $1$ noninclusive, that is, $A=\{x\in \mathbb {Q} :0<x<1\}$. We claim that $A$ has no least element. To prove this, assume that $A$ does have a least element, say $x\in A$ is such that $x\leq y$ for all $y\in A$. Since $x\in A$ we have that $x={\frac {a}{b}}$ where $a,b\in \mathbb {Z}$ Since $x\in A$ we must have that $x>0$ too since $0<x<1$ and so:

${\begin{aligned}\quad 0<{\frac {a}{b}}<1\end{aligned}}$

Consider the number $y$ in the middle of $0$ and ${\frac {a}{b}}$. This number is $y={\frac {a}{2b}}$. Since $b\in \mathbb {Z}$ and $b\neq 0$ we have that $2b\in \mathbb {Z}$ and $2b\neq 0$, so indeed, $y={\frac {a}{2b}}\in A$ and $0<y<x<1$ which is a contradiction to our assumption that a least element exists in $A$.

It's important to note that while not every subset of the rational numbers $\mathbb {Q}$ contains a least element, there are still subsets of $\mathbb {Q}$ that do contain a least element.

Induction

Mathematical induction is a mathematical proof technique. It is essentially used to prove that a statement P(n) holds for every natural number n = 0, 1, 2, 3, . . . ; that is, the overall statement is a sequence of infinitely many cases P(0), P(1), P(2), P(3), . . . . Informal metaphors help to explain this technique, such as falling dominoes or climbing a ladder:

"Mathematical induction proves that we can climb as high as we like on a ladder, by proving that we can climb onto the bottom rung (the basis) and that from each rung we can climb up to the next one (the step)."

— Concrete Mathematics, page 3 margins.

A proof by induction consists of two cases. The first, the base case (or basis), proves the statement for n = 0 without assuming any knowledge of other cases. The second case, the induction step, proves that if the statement holds for any given case n = k, then it must also hold for the next case n = k + 1. These two steps establish that the statement holds for every natural number n. The base case does not necessarily begin with n = 0, but often with n = 1, and possibly with any fixed natural number n = N, establishing the truth of the statement for all natural numbers n ≥ N.

The method can be extended to prove statements about more general well-founded structures, such as trees; this generalization, known as structural induction, is used in mathematical logic and computer science. Mathematical induction in this extended sense is closely related to recursion. Mathematical induction is an inference rule used in formal proofs, and is the foundation of most correctness proofs for computer programs.

Description

The simplest and most common form of mathematical induction infers that a statement involving a natural number n (that is, an integer n ≥ 0 or 1) holds for all values of n. The proof consists of two steps:

1. Template:AnchorThe initial or base case: prove that the statement holds for 0, or 1.
2. Template:AnchorThe induction step, inductive step, or step case: prove that for every n, if the statement holds for n, then it holds for n + 1. In other words, assume that the statement holds for some arbitrary natural number n, and prove that the statement holds for n + 1.

The hypothesis in the inductive step, that the statement holds for a particular n, is called the induction hypothesis or inductive hypothesis. To prove the inductive step, one assumes the induction hypothesis for n and then uses this assumption to prove that the statement holds for n + 1.

Authors who prefer to define natural numbers to begin at 0 use that value in the base case; those who define natural numbers to begin at 1 use that value.

Example

Mathematical induction can be used to prove the following statement P(n) for all natural numbers n.

$P(n)\!:\ \ 0+1+2+\cdots +n\,=\,{\frac {n(n+1)}{2}}.$

This states a general formula for the sum of the natural numbers less than or equal to a given number; in fact an infinite sequence of statements: $0={\tfrac {(0)(0+1)}{2}}$, $0+1={\tfrac {(1)(1+1)}{2}}$, $0+1+2={\tfrac {(2)(2+1)}{2}}$, etc.

Proposition. For any $n\in \mathbb {N}$, $0+1+2+\cdots +n={\tfrac {n(n+1)}{2}}.$

Proof. Let P(n) be the statement $0+1+2+\cdots +n={\tfrac {n(n+1)}{2}}.$ We give a proof by induction on n.

Base case: Show that the statement holds for the smallest natural number n = 0.

P(0) is clearly true: $0={\tfrac {0(0+1)}{2}}\,.$

Inductive step: Show that for any k ≥ 0, if P(k) holds, then P(k+1) also holds.

Assume the induction hypothesis that for a particular k, the single case n = k holds, meaning P(k) is true:

$0+1+\cdots +k\ =\ {\frac {k(k{+}1)}{2}}.$

It follows that:

$(0+1+2+\cdots +k)+(k{+}1)\ =\ {\frac {k(k{+}1)}{2}}+(k{+}1).$

Algebraically, the right hand side simplifies as:

${\begin{aligned}{\frac {k(k{+}1)}{2}}+(k{+}1)&\ =\ {\frac {k(k{+}1)+2(k{+}1)}{2}}\\&\ =\ {\frac {(k{+}1)(k{+}2)}{2}}\\&\ =\ {\frac {(k{+}1)((k{+}1)+1)}{2}}.\end{aligned}}$

Equating the extreme left hand and right hand sides, we deduce that:

$0+1+2+\cdots +k+(k{+}1)\ =\ {\frac {(k{+}1)((k{+}1)+1)}{2}}.$

That is, the statement P(k+1) also holds true, establishing the inductive step.

Conclusion: Since both the base case and the inductive step have been proved as true, by mathematical induction the statement P(n) holds for every natural number n. ∎

Licensing

Content obtained and/or adapted from:

• Natural number, Wikipedia under a CC BY-SA license
• [] under a CC BY-SA license
• [] under a CC BY-SA license