Let us begin by showing that if $a$ and $b$ are integers, then so is $a + b$. We proceed by induction on $b$. The assertion is true for $b = 0$ since $a + 0 = a$. If $a + b$ is an integer, then so is $(a + b) + 1$ (§ 4, no. 1, Proposition 1). But $(a + b) + 1 = a + (b + 1)$ (§ 3, no. 3, Corollary to Proposition 5); hence $a + (b + 1)$ is an integer, and consequently $a + b$ is an integer for all integers $b$.

Next we show by induction on $n = \mathrm{Card}\ (\mathrm{I})$ that $\sum\limits_{i \in \mathrm{I}} a_i$ is an integer. This is clear if $n = 0$, for then $\mathrm{I} = \emptyset$ and $\sum\limits_{i \in \mathrm{I}} a_i = 0$. If $\mathrm{Card}\ (\mathrm{I}) = n + 1$, we may write $\mathrm{I} = \mathrm{J} \cup \{k\}$, where $\mathrm{Card}\ (\mathrm{J}) = n$ and $k \notin \mathrm{J}$. Then

($\S\,3$, no. 3, Proposition 5). The inductive hypothesis is that $\sum\limits_{i \in \mathrm{J}} a_i$ is an integer; hence so is $a_k + \sum\limits_{i \in \mathrm{J}} a_i$, from the first paragraph of the proof. This shows that $\sum\limits_{i \in \mathrm{I}} a_i$ is an integer for all $n$.

Since the product $ab$ of two integers $a$ and $b$ is the sum of a finite family of integers all equal to $a$ ($\S\,3$, no. 4, Proposition 6, Corollary 2), $ab$ is an integer. We shall prove by induction on $n = \mathrm{Card}\ (\mathrm{I})$ that $\prod\limits_{i \in \mathrm{I}} a_i$ is an integer. This is true for $n = 0$, because then

If $\mathrm{Card}\ (\mathrm{I}) = n + 1$, we have (with the same notation as above)

($\S\,3$, no. 3, Proposition 5), and the inductive hypothesis therefore implies that $\prod\limits_{i \in \mathrm{I}} a_i$ is an integer. Consequently $\prod\limits_{i \in \mathrm{I}} a_i$ is an integer for all $n$.

For the sum S of the family $(\mathrm{X}_i)$ is finite; and since there exists a mapping of S onto E (Chapter II, $\S\,4$, no. 8), the set E is finite ($\S\,4$, no. 2, Proposition 2, Corollary 3).

For $a^b$ is the product of a finite family of integers all equal to $a$ ($\S\,3$, no. 5, Proposition 10).

For its cardinal is $2^{\mathrm{Card}\ (\mathrm{E})}$ ($\S\,3$, no. 5, Proposition 12).

If $a < b$, there exists a cardinal $c \leqslant b$ (so that $c$ is an integer (§ 4, no. 2, Proposition 2)) such that $b = a + c$ (§ 3, no. 6, Proposition 13); if $a \neq b$, we must have $c \neq 0$. Conversely, if $b = a + c$ and $c \neq 0$, then $c \geqslant 1$ and hence $a < a + 1 \leqslant a + c = b$.

If also $b_i > 0$ for each $i \in I$, then

Let $j$ be an index such that $a_j < b_j$, and let $J = I - \{j\}$. Then

with $c_j > 0$ (Proposition 2), and therefore (§ 3, no. 6, Proposition 14)

Since $c_j > 0$, the first part of the Proposition follows from Proposition 2. Likewise

Since $c_j$ and all the $b_i$ are $\neq 0$, the product $c_j . \prod_{i \in J} b_i$ is $\neq 0$ (§ 3, no. 4, Proposition 7); hence the second part of the Proposition.

We need only express $a^b$ and ${a'}^b$ as products of finite families of integers (§ 3, no. 5, Proposition 10) and apply Proposition 3, observing that the relation $a < a'$ implies $a' > 0$.

For there exists an integer $c > 0$ such that $b' = b + c$ (Proposition 2); since $c \geqslant 1$, we have $a^c \geqslant a > 1$, whence $a^{b'} = a^b a^c > a^b$.

The existence of $c$ follows from Proposition 13 of § 3, no. 6, and its uniqueness from Corollary 3 above.

¶ The integer $c$ such that $b = a + c$ (where $a \leqslant b$) is called the difference of the integers $b$ and $a$, and is written $b - a$. It is easily verified that if $a$, $b$, $a'$, $b'$ are integers such that $a \leqslant b$ and $a' \leqslant b'$, then

Clearly the relations $0 \leqslant x \leqslant b$ imply $a \leqslant a + x \leqslant a + b$. The mapping $x \rightarrow a + x$ is strictly increasing (and therefore injective) by Proposition 3 of no. 2. Finally, the relations $a \leqslant y \leqslant a + b$ imply $y = a + x$ with $x \geqslant 0$ and $a + x \leqslant a + b$, whence $x \leqslant b$ (no. 2, Proposition 3). This completes the proof.

By Proposition 4 we may restrict ouselves to the case where $a = 0$. The proof is by induction on $b$. If $b = 0$, the result is clear. The relation $0 \leqslant x \leqslant b + 1$ is equivalent to "$0 \leqslant x < b + 1$ or $x = b + 1$", and the relation $0 \leqslant x < b + 1$ is equivalent to $0 \leqslant x \leqslant b$ (§ 4, no. 2, Proposition 2); in other words, the interval $[0, b + 1]$ is the union of $[0, b]$ and $\{b + 1\}$, and these two sets are disjoint. By the inductive hypothesis the number of elements of $[0, b + 1]$ is equal to $(b + 1) + 1$, and the Proposition is proved.

Since E and $[1, n]$ are well-ordered (§ 4, no. 4, Proposition 3, Corollary 1) and have the same number of elements (Proposition 5), the result follows from Theorem 3 of § 2, no. 5 and Corollary 2 to Proposition 2 of § 4, no. 2.

(1)

(2)

(3)

for all $x \in \mathrm{E}$.

The conditions on $q$ and $r$ are equivalent to $bq \leqslant a < b(q + 1)$ and $r = a - bq$ (no. 2, Proposition 2). Hence we have to find $q$ such that $bq \leqslant a < b(q + 1)$; in other words, $q$ must be the smallest integer such that $a < b(q + 1)$, which shows that $q$ and $r = a - bq$ are uniquely determined. To prove their existence, we note that there exist integers $p$ such that $a < bp$, for example $a + 1$ (since $b > 0$). Let $m$ be the least of these integers. We have $m \neq 0$, and we may therefore write $m = q + 1$ with $q \leqslant m$ (§ 4, no. 2, Proposition 2); it follows that $bq \leqslant a < b(q + 1)$.

then the mapping $f_k$ is an isomorphism of the ordered set $E_k$ onto the interval $[0,b^k-1]$.

The proof is by induction on $k$. For $k=1$ it is an immediate consequence of the definitions. For each $r=(r_0,\ldots,r_{k-1},r_k)\in E_{k+1}$ put

Then the mapping $r\mapsto(\varphi(r),r_k)$ is an isomorphism of $E_{k+1}$ onto the lexicographical product of $E_k$ and $J=[0,b-1]$; this is immediate from the definitions. We may write

let us show that the relation $r<r'$ in $E_{k+1}$ implies $f_{k+1}(r)<f_{k+1}(r')$. Indeed, we have either $\varphi(r)<\varphi(r')$, or else $\varphi(r)=\varphi(r')$ and $r_k<r'_k$. In the first case, the inductive hypothesis implies that $f_k(\varphi(r))<f_k(\varphi(r'))$, and therefore (§ 4, no. 2, Proposition 2) $f_k(q(r'))\geq f_k(\varphi(r))+1$; consequently

since $r_k\leq b-1$ (no. 2, Proposition 3). If, on the other hand, $\varphi(r)=\varphi(r')$ and $r_k<r'_k$, it is clear that $f_{k+1}(r)<f_{k+1}(r')$. Now the inductive hypothesis shows that $f_k(\varphi(r))\leq b^k-1$, whence

It follows that $f_{k+1}$ is an isomorphism of $E_{k+1}$ onto a subset of the interval $[0,b^{k+1}-1]$; but this interval and $E_{k+1}$ have the same number of elements, namely $b^{k+1}$ (no. 3, Proposition 5); therefore $f_{k+1}$ is a bijection (§ 4, no. 2, Proposition 2, Corollary 4), and the proof is complete. ¶ We note now that for every integer $a$ we have $a < b^a$. This is proved by induction on $a$; the result is evident for $a = 0$, and the hypothesis $a < b^a$ implies $a + 1 \leqslant b^a < b \cdot b^a = b^{a+1}$ (no. 2, Proposition 3 and § 4, no. 2, Proposition 2). There is therefore a least integer $k$ such that $a < b^k$, and Proposition 8 then shows that there exists a unique finite sequence $(r_h)_{0 \leqslant h \leqslant k-1}$ such that $0 \leqslant r_h \leqslant b - 1$ for $0 \leqslant h \leqslant k - 1$ and

Furthermore, we must have $r_0 > 0$, for otherwise $a < b^{k-1}$ by virtue of Proposition 8. The expression is called the expansion to base $b$ of the integer $a$.

\* In all parts of mathematics which do not involve numerical computations, Proposition 8 is useful mainly when applied to a prime number $b$. \*

When the integer $b$ is small enough for this to be practicable, we may represent each integer $< b$ by a distinctive symbol called a digit. The digits which represent 0 and 1 are usually 0 and 1. Let $a$ be an integer and let $\sum_{h=0}^{k-1} r_h b^{k-h-1}$ be its expansion to base $b$. If the integer $k$ which appears in this expansion is sufficiently small for this to be practicable, it is usual to associate with the integer $a$ the succession of symbols obtained by writing $r_0 r_1 \ldots r_{k-2} r_{k-1}$ from left to right and then replacing each integer $r_i$ by the digit which represents it; the symbol so obtained is called the numerical symbol associated with $a$. One then often replaces $a$ by its numerical symbol in the terms and relations in which it appears.

For example, if C, Q, F, D are digits, the numerical symbols CQ, CQF, CQFD are respectively associated with $\mathrm{C}b + \mathrm{Q}$, $\mathrm{C}b^2 + \mathrm{Q}b + \mathrm{F}$, $\mathrm{C}b^3 + \mathrm{Q}b^2 + \mathrm{F}b + \mathrm{D}$.

It follows from Proposition 8 that the numerical symbol associated with an integer $a$ is unique, and that if $a < b^k$ it contains at most $k$ digits. Notice that the numerical symbol associated with the integer $b^k$ consists of the digit 1 followed by $k$ digits 0.

This system of representation of integers by numerical symbols is called the system of numeration to base $b$. In practical numerical computations, the following systems are used : (a) the system to base 2, or the dyadic system, in which the digits are 0 and 1; (b) the decimal system, in which the digits are $0$, $1$, $2$, $3$, $4$, $5 = 4 + 1$, $6 = 5 + 1$, $7 = 6 + 1$, $8 = 7 + 1$, $9 = 8 + 1$, and in which $b$ is the integer $9 + 1$ (whose numerical symbol in this system is therefore 10).

Since the Middle Ages the decimal system has been traditionally used in numerical calculations, and we shall use it in this series whenever we have occasion to write down an integer explicitly. We refer the reader to the part of this series devoted to numerical calculation for an account of methods for obtaining the numerical symbols associated with the sum, difference, product, and integral part of the quotient of two integers given by their numerical symbols.

For the family $(\overset{-1}{f}(y))_{y \in \mathrm{F}}$ is a partition of $\mathrm{E}$, each element of which partition is a set of cardinal $\mathfrak{c}$; hence the result (§ 3, no. 4, Proposition 6, Corollary 2).

The proof is by induction on the number $m \leqslant n$ of elements of $\mathrm{A}$. If $m = 0$, the result is evident. Suppose that $m + 1 \leqslant n$. Let $\mathrm{A}$ be a set with $m + 1$ elements, let $\mathrm{A}'$ be a subset of $\mathrm{A}$ with $m$ elements, and let $\{a\} = \mathrm{A} - \mathrm{A}'$. Let $\mathrm{F}$, $\mathrm{F}'$ be the sets of injective mappings of $\mathrm{A}$, $\mathrm{A}'$ respectively into $\mathrm{B}$, and let $\varphi$ be the mapping $f \to f\,|\mathrm{A}'$ which maps each function $f \in \mathrm{F}$ to its restriction to $\mathrm{A}'$. For each $f' \in \mathrm{F}'$ an element $f$ of $\overset{-1}{\varphi}(f')$ is uniquely determined by its value $f(a)$; since $f$ is injective, we must have $f(a) \in \mathrm{B} - f'(\mathrm{A}')$. It follows that $\overset{-1}{\varphi}(f')$ has the same number $n - m$ of elements as $\mathrm{B} - f'(\mathrm{A}')$. Hence, by Proposition 9, $\mathrm{F}$ has

elements by virtue of the inductive hypothesis. This completes the proof.

For this number is equal to the number of injections of the set into itself (§ 4, no. 2, Proposition 2, Corollary 4).

Let G be the set of permutations of E and let P be the set of coverings $(X_i)_{1 \leqslant i \leqslant h}$ which satisfy the conditions of the Proposition. Since $\sum_{i=1}^{h} p_i = n$, P is not empty. Let $(A_i)_{1 \leqslant i \leqslant h}$ be an element of P. For each permutation $f \in G$ the family $(f(A_i))_{1 \leqslant i \leqslant h}$ again belongs to P; let us denote it by $\varphi(f)$. For each element $(X_i)_{1 \leqslant i \leqslant h}$ let us calculate the number of permutations $f \in G$ such that $\varphi(f) = (X_i)$. We shall have $\varphi(f) = (X_i)$ if and only if for each index $i$ we have $f(A_i) = X_i$. Hence the set of permutations $f$ under consideration is equipotent to the product of the sets of bijections of $A_i$ onto $X_i$ (Chapter II, § 4, no. 7, Proposition 8); consequently the set $\overset{-1}{\varphi}((X_i)_{1 \leqslant i \leqslant h})$ has $\prod_{i=1}^{h} p_i!$ elements (Corollary to Proposition 10). Since G has $n!$ elements, the result now follows from Proposition 9.

Put $h = 2$, $p_1 = p$, $p_2 = n - p$ in Proposition 11.

¶ The number of subsets containing $p$ elements in a set of $n$ elements (where $p \leqslant n$) is denoted by $\begin{pmatrix} n \\ p \end{pmatrix}$ and is called the binomial coefficient with indices n and p. From the relation $\begin{pmatrix} n \\ p \end{pmatrix} = \dfrac{n!}{p!(n-p)!}$ it follows immediately that $\begin{pmatrix} n \\ p \end{pmatrix} = \begin{pmatrix} n \\ n-p \end{pmatrix}$.

This is also a consequence of the fact that, if E is a set with $n$ elements, $X \to E - X$ is a bijection of the set of subsets of E consisting of $p$ elements onto the set of subsets of $n - p$ elements.

We put $\binom{n}{p} = 0$ for each pair of natural integers such that $p > n$. With this convention the number of subsets of $p$ elements in a set of $n$ elements is $\binom{n}{p}$ for every natural integer $p$.

For such a mapping is an injection of E into F (§ 1, no. 12, Proposition 11), and since E and F are well-ordered (§ 4, no. 4, Corollary 1 to Proposition 3), for each subset X of $p$ elements of F there is exactly one strictly increasing mapping of E onto X (§ 2, no. 5, Theorem 3).

For if E is a set of $n$ elements, the left-hand side of the equality is the number of subsets of E. Now apply Proposition 12 of § 3, no. 5.

Let E be a set with $n + 1$ elements, let P be the set of all subsets of E containing $p + 1$ elements, let $a$ be an element of E, and put

Let P′ (resp. P″) denote the set of subsets of $p + 1$ elements of E which contain $a$ (resp. do not contain $a$). The set P″ is the set of subsets of $p + 1$ elements of E′ and therefore has $\binom{n}{p+1}$ elements. The mapping $\mathrm{X} \to \mathrm{X} \cap \mathrm{E}'$ is a bijection of P′ onto the set of subsets of $p$ elements of E′, and P′ therefore has $\binom{n}{p}$ elements. The result now follows from the fact that P is the union of the disjoint sets P′ and P″.

Proposition 13 can also be proved by means of a simple calculation from the formula $\binom{n}{p} = \dfrac{n!}{p!(n-p)!}$ for $p \leqslant n$.

For $b_n$ is the number of subsets of 2 elements in $[1, n]$; hence

The value of $a_n$ is deduced from this by noting that the set of ordered pairs $(i, j)$ such that $1 \leqslant i \leqslant j \leqslant n$ is the union of the set of ordered pairs $(i, j)$ such that $1 \leqslant i \leqslant j < n$ and the set of pairs $(i, i)$ where $1 \leqslant i \leqslant n$. Thus $a_n = n + b_n = \frac{1}{2} n(n+1)$.

In the set A of ordered pairs of integers $(i, j)$ such that $1 \leqslant i \leqslant j \leqslant n$, let $A_k$ denote the subset of pairs $(i, k)$, where $1 \leqslant i \leqslant k$ (for an arbitrary integer $k \leqslant n$). Then $A_k$ has $k$ elements. But $(A_k)_{1 \leqslant k \leqslant n}$ is a partition of A; hence the result.

Let $A(h, n)$ (resp. $B(h, n)$) denote the number of mappings $u$ of E into $[0, n]$ such that $\sum_{x \in E} u(x) \leqslant n$ (resp. $\sum_{x \in E} u(x) = n$ for $h > 0$). We show first that $A(h-1, n) = B(h, n)$. For this, let E′ be a subset of E with $h - 1$ elements, and let $\{a\} = E - E'$. If $u$ is a mapping of E into $[0, n]$ such that $\sum_{x \in E} u(x) = n$, then its restriction $u'$ to E′ is such that $\sum_{x \in E'} u'(x) \leqslant n$, and moreover $u(a) = n - \sum_{x \in E'} u'(x)$. Conversely, every mapping $u'$ of E′ into $[0, n]$ which satisfies $\sum_{x \in E'} u'(x) \leqslant n$ defines a unique mapping $u$ of E into $[0, n]$, of which $u'$ is the restriction, and which is such that $\sum_{x \ni E} u(x) = n$.

We note next that if $\sum_{x \in E} u(x) \leqslant n$, then either $\sum_{x \in E} u(x) = n$, or else $\sum_{x \in E} u(x) \leqslant n-1$, and these two possibilities are mutually exclusive. Consequently

Since $A(0, 0) = 1 = \binom{0}{0}$, the formula $A(h, n) = \binom{n+h}{h}$ follows from above and from Proposition 13, by induction on $n + h$.

\* The number of monomials $X_1^{\alpha_1} X_2^{\alpha_2} \ldots X_h^{\alpha_n}$ in $h$ indeterminates with total degree $\leqslant n$ is evidently equal to the number of mappings $i \rightarrow \alpha_i$ of $[1, h]$ into $[0, n]$ such that $\sum_{i=0}^{h} \alpha_i \leqslant n$, and is therefore equal to $\binom{n+h}{h}$ by Proposition 15; this number is also the number of monomials in $h + 1$ indeterminates with total degree $n$. \*