Trước hết, ta chứng minh rằng nếu $a$ và $b$ là các số nguyên thì $a + b$ cũng là một số nguyên. Ta tiến hành quy nạp theo $b$. Mệnh đề đúng với $b = 0$ vì $a + 0 = a$. Nếu $a + b$ là một số nguyên thì $(a + b) + 1$ cũng là một số nguyên (§ 4, no. 1, Mệnh đề 1). Nhưng $(a + b) + 1 = a + (b + 1)$ (§ 3, no. 3, Hệ quả của Mệnh đề 5); do đó $a + (b + 1)$ là một số nguyên, và do đó $a + b$ là một số nguyên với mọi số nguyên $b$.

Tiếp theo, ta chứng minh bằng quy nạp theo $n = \mathrm{Card}\ (\mathrm{I})$ rằng $\sum\limits_{i \in \mathrm{I}} a_i$ là một số nguyên. Điều này hiển nhiên nếu $n = 0$, vì khi đó $\mathrm{I} = \emptyset$ và $\sum\limits_{i \in \mathrm{I}} a_i = 0$. Nếu $\mathrm{Card}\ (\mathrm{I}) = n + 1$, ta có thể viết $\mathrm{I} = \mathrm{J} \cup \{k\}$, trong đó $\mathrm{Card}\ (\mathrm{J}) = n$ và $k \notin \mathrm{J}$. Khi đó

($\S\,3$, no. 3, Mệnh đề 5). Giả thiết quy nạp là $\sum\limits_{i \in \mathrm{J}} a_i$ là một số nguyên; do đó $a_k + \sum\limits_{i \in \mathrm{J}} a_i$ cũng là một số nguyên, theo đoạn đầu tiên của chứng minh. Điều này cho thấy rằng $\sum\limits_{i \in \mathrm{I}} a_i$ là một số nguyên với mọi $n$.

Vì tích $ab$ của hai số nguyên $a$ và $b$ là tổng của một họ hữu hạn các số nguyên đều bằng $a$ ($\S\,3$, no. 4, Mệnh đề 6, Hệ quả 2), $ab$ là một số nguyên. Ta sẽ chứng minh bằng quy nạp theo $n = \mathrm{Card}\ (\mathrm{I})$ rằng $\prod\limits_{i \in \mathrm{I}} a_i$ là một số nguyên. Điều này đúng với $n = 0$, vì khi đó

Nếu $\mathrm{Card}\ (\mathrm{I}) = n + 1$, ta có (với cùng ký hiệu như trên)

($\S\,3$, no. 3, Mệnh đề 5), và do đó giả thiết quy nạp suy ra rằng $\prod\limits_{i \in \mathrm{I}} a_i$ là một số nguyên. Do đó $\prod\limits_{i \in \mathrm{I}} a_i$ là một số nguyên với mọi $n$.

Vì tổng S của họ $(\mathrm{X}_i)$ là hữu hạn; và vì tồn tại một ánh xạ từ S lên E (chương II, $\S\,4$, no. 8), nên tập hợp E là hữu hạn ($\S\,4$, no. 2, Mệnh đề 2, Hệ quả 3).

Vì $a^b$ là tích của một họ hữu hạn các số nguyên đều bằng $a$ ($\S\,3$, no. 5, Mệnh đề 10).

Vì lực lượng của nó là $2^{\mathrm{Card}\ (\mathrm{E})}$ ($\S\,3$, no. 5, Mệnh đề 12).

Nếu $a < b$, tồn tại một lực lượng $c \leqslant b$ (sao cho $c$ là một số nguyên (§ 4, no. 2, Mệnh đề 2)) sao cho $b = a + c$ (§ 3, no. 6, Mệnh đề 13); nếu $a \neq b$, ta phải có $c \neq 0$. Ngược lại, nếu $b = a + c$ và $c \neq 0$, thì $c \geqslant 1$ và do đó $a < a + 1 \leqslant a + c = b$.

Nếu thêm $b_i > 0$ với mỗi $i \in I$, thì

Cho $j$ là một chỉ số sao cho $a_j < b_j$, và đặt $J = I - \{j\}$. Khi đó

với $c_j > 0$ (Mệnh đề 2), và do đó (§ 3, no. 6, Mệnh đề 14)

Vì $c_j > 0$, phần thứ nhất của Mệnh đề suy ra từ Mệnh đề 2. Tương tự,

Vì $c_j$ và tất cả các $b_i$ đều $\neq 0$, tích $c_j . \prod_{i \in J} b_i$ là $\neq 0$ (§ 3, no. 4, Mệnh đề 7); do đó có phần thứ hai của Mệnh đề.

Chỉ cần biểu diễn $a^b$ và ${a'}^b$ dưới dạng các tích của các họ hữu hạn các số nguyên (§ 3, no. 5, Mệnh đề 10) và áp dụng Mệnh đề 3, nhận thấy rằng quan hệ $a < a'$ kéo theo $a' > 0$.

Vì tồn tại một số nguyên $c > 0$ sao cho $b' = b + c$ (Mệnh đề 2); do $c \geqslant 1$, ta có $a^c \geqslant a > 1$, do đó $a^{b'} = a^b a^c > a^b$.

Sự tồn tại của $c$ suy ra từ Mệnh đề 13 của § 3, no. 6, và tính duy nhất của nó suy ra từ Hệ quả 3 ở trên.

¶ Số nguyên $c$ sao cho $b = a + c$ (trong đó $a \leqslant b$) được gọi là hiệu của các số nguyên $b$ và $a$, và được viết là $b - a$. Dễ dàng kiểm tra rằng nếu $a$, $b$, $a'$, $b'$ là các số nguyên sao cho $a \leqslant b$ và $a' \leqslant b'$, thì

Rõ ràng, các quan hệ $0 \leqslant x \leqslant b$ suy ra $a \leqslant a + x \leqslant a + b$. Ánh xạ $x \rightarrow a + x$ là tăng ngặt (và do đó đơn ánh) theo Mệnh đề 3 của no. 2. Cuối cùng, các quan hệ $a \leqslant y \leqslant a + b$ suy ra $y = a + x$ với $x \geqslant 0$ và $a + x \leqslant a + b$, do đó $x \leqslant b$ (no. 2, Mệnh đề 3). Điều này hoàn tất chứng minh.

Theo Mệnh đề 4, ta có thể quy về trường hợp $a = 0$. Chứng minh bằng quy nạp theo $b$. Nếu $b = 0$, kết quả là hiển nhiên. Quan hệ $0 \leqslant x \leqslant b + 1$ tương đương với "$0 \leqslant x < b + 1$ hoặc $x = b + 1$", và quan hệ $0 \leqslant x < b + 1$ tương đương với $0 \leqslant x \leqslant b$ (§ 4, no. 2, Mệnh đề 2); nói cách khác, khoảng $[0, b + 1]$ là hợp của $[0, b]$ và $\{b + 1\}$, và hai tập hợp này rời nhau. Theo giả thiết quy nạp, số phần tử của $[0, b + 1]$ bằng $(b + 1) + 1$, và Mệnh đề được chứng minh.

Vì E và $[1, n]$ được sắp tốt (§ 4, no. 4, Mệnh đề 3, Hệ quả 1) và có cùng số phần tử (Mệnh đề 5), kết quả suy ra từ Định lý 3 của § 2, no. 5 và Hệ quả 2 của Mệnh đề 2 của § 4, no. 2.

(1)

(2)

(3)

với mọi $x \in \mathrm{E}$.

Các điều kiện đối với $q$ và $r$ là tương đương với $bq \leqslant a < b(q + 1)$ và $r = a - bq$ (no. 2, Mệnh đề 2). Vậy ta phải tìm $q$ sao cho $bq \leqslant a < b(q + 1)$; nói cách khác, $q$ phải là số nguyên nhỏ nhất sao cho $a < b(q + 1)$, điều đó chứng tỏ rằng $q$ và $r = a - bq$ được xác định duy nhất. Để chứng minh sự tồn tại của chúng, ta chú ý rằng tồn tại các số nguyên $p$ sao cho $a < bp$, ví dụ $a + 1$ (vì $b > 0$). Gọi $m$ là số nhỏ nhất trong các số nguyên ấy. Ta có $m \neq 0$, và do đó có thể viết $m = q + 1$ với $q \leqslant m$ (§ 4, no. 2, Mệnh đề 2); suy ra $bq \leqslant a < b(q + 1)$.

khi đó ánh xạ $f_k$ là một đẳng cấu của tập hợp có thứ tự $E_k$ lên khoảng $[0,b^k-1]$.

Chứng minh bằng quy nạp theo $k$. Với $k=1$ điều đó là một hệ quả ngay lập tức của các định nghĩa. Với mỗi $r=(r_0,\ldots,r_{k-1},r_k)\in E_{k+1}$ đặt

Khi đó ánh xạ $r\mapsto(\varphi(r),r_k)$ là một đẳng cấu của $E_{k+1}$ lên tích từ điển của $E_k$ và $J=[0,b-1]$; điều này suy ra ngay lập tức từ các định nghĩa. Ta có thể viết

ta hãy chứng minh rằng quan hệ $r<r'$ trong $E_{k+1}$ kéo theo $f_{k+1}(r)<f_{k+1}(r')$. Thật vậy, hoặc là $\varphi(r)<\varphi(r')$, hoặc là $\varphi(r)=\varphi(r')$ và $r_k<r'_k$. Trong trường hợp thứ nhất, giả thiết quy nạp kéo theo $f_k(\varphi(r))<f_k(\varphi(r'))$, và do đó (§ 4, no. 2, Mệnh đề 2) $f_k(q(r'))\geq f_k(\varphi(r))+1$; do đó

vì $r_k\leq b-1$ (no. 2, Mệnh đề 3). Mặt khác, nếu $\varphi(r)=\varphi(r')$ và $r_k<r'_k$, thì hiển nhiên là $f_{k+1}(r)<f_{k+1}(r')$. Bây giờ giả thiết quy nạp cho thấy rằng $f_k(\varphi(r))\leq b^k-1$, do đó

Suy ra $f_{k+1}$ là một đẳng cấu từ $E_{k+1}$ lên một tập con của khoảng $[0,b^{k+1}-1]$; nhưng khoảng này và $E_{k+1}$ có cùng số phần tử, tức là $b^{k+1}$ (no. 3, Mệnh đề 5); do đó $f_{k+1}$ là một song ánh (§ 4, no. 2, Mệnh đề 2, Hệ quả 4), và chứng minh là đầy đủ. ¶ Bây giờ ta chú ý rằng với mọi số nguyên $a$ ta có $a < b^a$. Điều này được chứng minh bằng quy nạp theo $a$; kết quả là hiển nhiên đối với $a = 0$, và giả thiết $a < b^a$ kéo theo $a + 1 \leqslant b^a < b \cdot b^a = b^{a+1}$ (no. 2, Mệnh đề 3 and § 4, no. 2, Mệnh đề 2). Do đó tồn tại một số nguyên nhỏ nhất $k$ sao cho $a < b^k$, và khi đó Mệnh đề 8 cho thấy rằng tồn tại một dãy hữu hạn duy nhất $(r_h)_{0 \leqslant h \leqslant k-1}$ sao cho $0 \leqslant r_h \leqslant b - 1$ với $0 \leqslant h \leqslant k - 1$ và

Hơn nữa, ta phải có $r_0 > 0$, vì nếu không thì $a < b^{k-1}$ theo Mệnh đề 8. Biểu thức được gọi là khai triển theo cơ sở $b$ của số nguyên $a$.

\* Trong mọi phần của toán học không liên quan đến các phép tính số, Mệnh đề 8 chủ yếu hữu ích khi được áp dụng cho một số nguyên tố $b$. \*

Khi số nguyên $b$ đủ nhỏ để việc này là khả thi, ta có thể biểu diễn mỗi số nguyên $< b$ bằng một ký hiệu phân biệt gọi là một chữ số. Các chữ số biểu diễn 0 và 1 thường là 0 và 1. Cho $a$ là một số nguyên và $\sum_{h=0}^{k-1} r_h b^{k-h-1}$ là khai triển của nó theo cơ sở $b$. Nếu số nguyên $k$ xuất hiện trong khai triển này đủ nhỏ để việc này là khả thi, thì người ta thường liên kết với số nguyên $a$ dãy ký hiệu thu được bằng cách viết $r_0 r_1 \ldots r_{k-2} r_{k-1}$ từ trái sang phải rồi thay thế mỗi số nguyên $r_i$ bằng chữ số biểu diễn nó; ký hiệu thu được như vậy được gọi là ký hiệu số liên kết với $a$. Khi đó người ta thường thay thế $a$ bằng ký hiệu số của nó trong các thuật ngữ và quan hệ mà nó xuất hiện.

Ví dụ, nếu C, Q, F, D là các chữ số, thì các ký hiệu số CQ, CQF, CQFD lần lượt được liên kết với $\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}$.

Suy ra từ Mệnh đề 8 rằng ký hiệu số liên kết với một số nguyên $a$ là duy nhất, và rằng nếu $a < b^k$ thì nó chứa nhiều nhất $k$ chữ số. Lưu ý rằng ký hiệu số liên kết với số nguyên $b^k$ gồm chữ số 1 theo sau bởi $k$ chữ số 0.

Hệ biểu diễn các số nguyên bằng các ký hiệu số này được gọi là hệ đếm cơ sở $b$. Trong các phép tính số học thực hành, người ta dùng các hệ sau: (a) hệ cơ sở 2, hay hệ nhị phân, trong đó các chữ số là 0 và 1; (b) hệ thập phân, trong đó các chữ số là $0$, $1$, $2$, $3$, $4$, $5 = 4 + 1$, $6 = 5 + 1$, $7 = 6 + 1$, $8 = 7 + 1$, $9 = 8 + 1$, và trong đó $b$ là số nguyên $9 + 1$ (vì thế ký hiệu số của nó trong hệ này là 10).

Từ thời Trung cổ, hệ thập phân theo truyền thống đã được dùng trong các phép tính số học, và chúng tôi sẽ dùng nó trong bộ sách này mỗi khi cần viết tường minh một số nguyên. Chúng tôi dẫn người đọc đến phần của bộ sách này dành cho phép tính số học để biết các phương pháp thu được các ký hiệu số liên kết với tổng, hiệu, tích và phần nguyên của thương của hai số nguyên được cho bởi các ký hiệu số của chúng.

Vì họ $(\overset{-1}{f}(y))_{y \in \mathrm{F}}$ là một phân hoạch của $\mathrm{E}$, mà mỗi phần tử của phân hoạch này là một tập hợp có lực lượng $\mathfrak{c}$; do đó suy ra kết quả (§ 3, no. 4, Mệnh đề 6, Hệ quả 2).

Chứng minh bằng quy nạp theo số $m \leqslant n$ phần tử của $\mathrm{A}$. Nếu $m = 0$ thì kết quả là hiển nhiên. Giả sử rằng $m + 1 \leqslant n$. Cho $\mathrm{A}$ là một tập hợp có $m + 1$ phần tử, $\mathrm{A}'$ là một tập con của $\mathrm{A}$ có $m$ phần tử, và $\{a\} = \mathrm{A} - \mathrm{A}'$. Cho $\mathrm{F}$, $\mathrm{F}'$ lần lượt là các tập hợp các ánh xạ đơn ánh từ $\mathrm{A}$, $\mathrm{A}'$ vào $\mathrm{B}$, và cho $\varphi$ là ánh xạ $f \to f\,|\mathrm{A}'$ biến mỗi hàm $f \in \mathrm{F}$ thành hạn chế của nó trên $\mathrm{A}'$. Với mỗi $f' \in \mathrm{F}'$, một phần tử $f$ của $\overset{-1}{\varphi}(f')$ được xác định duy nhất bởi giá trị $f(a)$ của nó; vì $f$ là đơn ánh nên ta phải có $f(a) \in \mathrm{B} - f'(\mathrm{A}')$. Suy ra $\overset{-1}{\varphi}(f')$ có cùng số phần tử $n - m$ như $\mathrm{B} - f'(\mathrm{A}')$. Do đó, theo Mệnh đề 9, $\mathrm{F}$ có

phần tử theo giả thiết quy nạp. Điều này hoàn tất chứng minh.

Thật vậy, số này bằng số các phép đơn ánh của tập hợp đó vào chính nó (§ 4, no. 2, Mệnh đề 2, Hệ quả 4).

Cho G là tập hợp các phép hoán vị của E và gọi P là tập hợp các phủ $(X_i)_{1 \leqslant i \leqslant h}$ thỏa mãn các điều kiện của Mệnh đề. Vì $\sum_{i=1}^{h} p_i = n$, P không rỗng. Cho $(A_i)_{1 \leqslant i \leqslant h}$ là một phần tử của P. Với mỗi phép hoán vị $f \in G$ thì họ $(f(A_i))_{1 \leqslant i \leqslant h}$ lại thuộc P; ta ký hiệu nó bởi $\varphi(f)$. Với mỗi phần tử $(X_i)_{1 \leqslant i \leqslant h}$, hãy tính số các phép hoán vị $f \in G$ sao cho $\varphi(f) = (X_i)$. Ta có $\varphi(f) = (X_i)$ khi và chỉ khi với mỗi chỉ số $i$ ta có $f(A_i) = X_i$. Do đó tập hợp các phép hoán vị $f$ đang xét có cùng lực lượng với tích của các tập hợp song ánh từ $A_i$ lên $X_i$ (Chương II, § 4, no. 7, Mệnh đề 8); do đó tập hợp $\overset{-1}{\varphi}((X_i)_{1 \leqslant i \leqslant h})$ có $\prod_{i=1}^{h} p_i!$ phần tử (Hệ quả của Mệnh đề 10). Vì G có $n!$ phần tử, kết quả bây giờ suy ra từ Mệnh đề 9.

Đặt $h = 2$, $p_1 = p$, $p_2 = n - p$ trong Mệnh đề 11.

¶ Số các tập con chứa $p$ phần tử trong một tập hợp có $n$ phần tử (với $p \leqslant n$) được ký hiệu bởi $\begin{pmatrix} n \\ p \end{pmatrix}$ và được gọi là hệ số nhị thức với chỉ số n và p. Từ quan hệ $\begin{pmatrix} n \\ p \end{pmatrix} = \dfrac{n!}{p!(n-p)!}$ suy ra ngay lập tức rằng $\begin{pmatrix} n \\ p \end{pmatrix} = \begin{pmatrix} n \\ n-p \end{pmatrix}$.

Đây cũng là một hệ quả của sự kiện rằng, nếu E là một tập hợp có $n$ phần tử, thì $X \to E - X$ là một song ánh từ tập hợp các tập con của E gồm $p$ phần tử lên tập hợp các tập con có $n - p$ phần tử.

Ta đặt $\binom{n}{p} = 0$ cho mỗi cặp số nguyên tự nhiên sao cho $p > n$. Với quy ước này, số các tập con gồm $p$ phần tử của một tập hợp gồm $n$ phần tử là $\binom{n}{p}$ với mọi số nguyên tự nhiên $p$.

Thật vậy, một ánh xạ như thế là một đơn ánh từ E vào F (§ 1, no. 12, Mệnh đề 11), và vì E và F được sắp tốt (§ 4, no. 4, Hệ quả 1 của Mệnh đề 3), nên với mỗi tập con X gồm $p$ phần tử của F có đúng một ánh xạ tăng ngặt từ E lên X (§ 2, no. 5, Định lý 3).

Thật vậy, nếu E là một tập hợp gồm $n$ phần tử, thì vế trái của đẳng thức là số các tập con của E. Bây giờ áp dụng Mệnh đề 12 của § 3, no. 5.

Cho E là một tập hợp có $n + 1$ phần tử, gọi P là tập hợp tất cả các tập hợp con của E chứa $p + 1$ phần tử, gọi $a$ là một phần tử của E, và đặt

Gọi P′ (resp. P″) là tập hợp các tập hợp con có $p + 1$ phần tử của E mà chứa $a$ (resp. không chứa $a$). Tập hợp P″ là tập hợp các tập hợp con có $p + 1$ phần tử của E′ và do đó có $\binom{n}{p+1}$ phần tử. Ánh xạ $\mathrm{X} \to \mathrm{X} \cap \mathrm{E}'$ là một song ánh từ P′ lên tập hợp các tập hợp con có $p$ phần tử của E′, và do đó P′ có $\binom{n}{p}$ phần tử. Kết quả suy ra ngay từ việc P là hợp của hai tập hợp rời nhau P′ và P″.

Mệnh đề 13 cũng có thể được chứng minh bằng một phép tính đơn giản từ công thức $\binom{n}{p} = \dfrac{n!}{p!(n-p)!}$ với $p \leqslant n$.

Thật vậy, $b_n$ là số các tập con gồm 2 phần tử của $[1, n]$; do đó

Giá trị của $a_n$ được suy ra từ điều này bằng cách nhận thấy rằng tập hợp các cặp có thứ tự $(i, j)$ sao cho $1 \leqslant i \leqslant j \leqslant n$ là hợp của tập hợp các cặp có thứ tự $(i, j)$ sao cho $1 \leqslant i \leqslant j < n$ và tập hợp các cặp $(i, i)$ với $1 \leqslant i \leqslant n$. Do đó $a_n = n + b_n = \frac{1}{2} n(n+1)$.

Trong tập hợp A gồm các cặp số nguyên có thứ tự $(i, j)$ sao cho $1 \leqslant i \leqslant j \leqslant n$, gọi $A_k$ là tập con các cặp $(i, k)$, với $1 \leqslant i \leqslant k$ (đối với một số nguyên tùy ý $k \leqslant n$). Khi đó $A_k$ có $k$ phần tử. Nhưng $(A_k)_{1 \leqslant k \leqslant n}$ là một phân hoạch của A; do đó suy ra kết quả.

Ký hiệu $A(h, n)$ (tương ứng $B(h, n)$) là số các ánh xạ $u$ từ E vào $[0, n]$ sao cho $\sum_{x \in E} u(x) \leqslant n$ (tương ứng $\sum_{x \in E} u(x) = n$ với $h > 0$). Trước hết ta chứng minh rằng $A(h-1, n) = B(h, n)$. Thật vậy, gọi E′ là một tập con của E có $h - 1$ phần tử, và đặt $\{a\} = E - E'$. Nếu $u$ là một ánh xạ từ E vào $[0, n]$ sao cho $\sum_{x \in E} u(x) = n$, thì hạn chế $u'$ của nó lên E′ thỏa mãn $\sum_{x \in E'} u'(x) \leqslant n$, và hơn nữa $u(a) = n - \sum_{x \in E'} u'(x)$. Ngược lại, mọi ánh xạ $u'$ từ E′ vào $[0, n]$ thỏa mãn $\sum_{x \in E'} u'(x) \leqslant n$ xác định một ánh xạ duy nhất $u$ từ E vào $[0, n]$, mà $u'$ là hạn chế, và sao cho $\sum_{x \ni E} u(x) = n$.

Tiếp theo ta chú ý rằng nếu $\sum_{x \in E} u(x) \leqslant n$, thì hoặc là $\sum_{x \in E} u(x) = n$, hoặc nếu không thì $\sum_{x \in E} u(x) \leqslant n-1$, và hai khả năng này loại trừ lẫn nhau. Do đó

Vì $A(0, 0) = 1 = \binom{0}{0}$, công thức $A(h, n) = \binom{n+h}{h}$ suy ra từ trên và từ Mệnh đề 13, bằng quy nạp theo $n + h$.

\* Số các đơn thức $X_1^{\alpha_1} X_2^{\alpha_2} \ldots X_h^{\alpha_n}$ theo $h$ bất định với tổng bậc $\leqslant n$ hiển nhiên bằng số các ánh xạ $i \rightarrow \alpha_i$ từ $[1, h]$ vào $[0, n]$ sao cho $\sum_{i=0}^{h} \alpha_i \leqslant n$, và do đó bằng $\binom{n+h}{h}$ theo Mệnh đề 15; số này cũng là số các đơn thức theo $h + 1$ bất định với tổng bậc $n$. \*