I numeri naturali: sintesi e sfide

Riepilogo

Questa lezione chiude l’unità dedicata ai numeri naturali. Ricostruisce la catena deduttiva che va dal linguaggio degli insiemi e dagli assiomi di Peano al binomio di Newton, indicando a ogni anello quale principio si usa e quale risultato si ottiene; colloca ciò che è stato ottenuto rispetto al piano del corso e spiega perché i limiti della sottrazione e della divisione tra naturali conducono all’unità successiva, dedicata agli insiemi numerici. Termina con dieci sfide, di difficoltà superiore a quella dei problemi delle lezioni, che richiedono di combinare gli strumenti di diverse di esse.

Obiettivi di apprendimento

Ricostruire l’ordine logico dei risultati dell’unità, individuando il principio su cui poggia ciascuno.
Spiegare come si collegano l’induzione, il buon ordinamento, la divisione con resto, la fattorizzazione unica e le congruenze.
Giustificare, a partire dai limiti della sottrazione e della divisione tra naturali, la necessità di ampliare gli insiemi numerici.
Risolvere problemi che combinano l’induzione, la divisibilità, la numerazione posizionale e il conteggio.

Ciò che l’unità ha ottenuto

L’unità si era proposta di dedurre l’aritmetica dei naturali da pochi principi, senza ammettere come evidente nessuna delle sue proprietà. Il proposito è stato realizzato con poche riserve, ciascuna dichiarata a suo luogo: le regole della teoria ingenua degli insiemi e della negazione dei quantificatori, che sono il linguaggio in cui si scrive tutto il resto; l’esistenza delle funzioni definite per ricorsione, che il teorema di ricorsione di Dedekind garantisce e che è stata ammessa perché appartiene alla teoria degli insiemi; l’unicità del numero di elementi di un insieme finito, e la finitezza dei suoi sottoinsiemi, su cui poggia il conteggio; la commutatività generalizzata, che permette di riordinare i fattori di un prodotto finito; e le regole elementari degli interi, dei razionali e dei reali, che l’unità ha anticipato in esempi e problemi e che l’unità successiva costruisce. Con queste riserve, il cammino percorso si può leggere come un’unica catena deduttiva in quattro tratti.

I fondamenti: insiemi, assiomi, operazioni e ordine

La lezione su insiemi, relazioni e funzioni ha fissato il linguaggio in cui si scrive l’unità, dichiarando il poco che essa ammette della teoria degli insiemi, e ha dimostrato che le relazioni di equivalenza e le partizioni sono due facce di una stessa idea: le classi di un’equivalenza formano una partizione, e ogni partizione proviene da un’unica equivalenza. Questo risultato ricompare nella classificazione degli interi secondo il loro resto e nelle congruenze, e l’unità successiva lo usa per costruire gli interi e i razionali come classi di coppie. Nella lezione sugli assiomi di Peano i naturali sono stati definiti per mezzo dell’ $1$ , dell’operazione successore e di cinque assiomi; gli assiomi dal secondo al quarto garantiscono che la successione non si arresta né torna su sé stessa, e il quinto, il principio di induzione, garantisce che non ci sono altri naturali oltre a quelli che si raggiungono a partire dall’ $1$ . La lezione sulle operazioni di base e l’ordine ha costruito sul successore, con il teorema di ricorsione, una scala di definizioni ricorsive, in cui ogni operazione si definisce mediante la precedente:

n + S(m) = S(n + m), \qquad n \cdot S(m) = n \cdot m + n, \qquad b^{S(n)} = b^n \cdot b

Da queste definizioni si sono dedotte per induzione la commutatività, l’associatività, la distributività e la legge di cancellazione, e dalla somma si è ottenuto l’ordine, con la tricotomia, la transitività e la monotonia. La sottrazione e la divisione sono state definite come operazioni inverse, ma solo in certi casi: $a - b$ esiste quando $b < a$ , e $\frac{a}{b}$ , quando $b$ divide $a$ .

I principi di dimostrazione

La lezione sulle sommatorie, progressioni e induzione ha ampliato il repertorio delle dimostrazioni. Ha provato che l’induzione ordinaria implica l’induzione forte e il principio del buon ordinamento, e che, con il lemma secondo cui ogni naturale diverso da $1$ è un successore e con le proprietà dell’ordine, il buon ordinamento implica a sua volta l’induzione, cosicché ogni dimostrazione può usare il principio che le risulta più naturale; ha dato alle somme una definizione ricorsiva e proprietà che permettono di calcolarle, e ha mostrato con le somme telescopiche che una formula si può dedurre, e non soltanto verificare. Il principio del buon ordinamento si è rivelato lo strumento di quasi tutte le dimostrazioni di esistenza che sono seguite, perché permette di scegliere il minimo elemento di un insieme e di ragionare sul più piccolo controesempio.

L’aritmetica della divisibilità

Con il buon ordinamento, la lezione sulla divisibilità ha dimostrato che ogni intero ammette, quando lo si divide per un naturale, un quoziente e un resto unici. Da questo teorema dipendono i quattro risultati seguenti, ciascuno appoggiato ai precedenti:

La classificazione degli interi secondo il loro resto, che permette di dimostrare per casi, e i criteri di divisibilità, che si riducono al fatto che due numeri che differiscono per un multiplo di $d$ danno lo stesso resto nella divisione per $d$ .
Nella lezione sui numeri primi, il lemma di Euclide, dimostrato con il buon ordinamento e la divisione con resto, e con esso il teorema fondamentale dell’aritmetica: ogni naturale maggiore di $1$ è prodotto di primi in un solo modo. Dall’unicità si sono dedotti il numero dei divisori, la caratterizzazione dei quadrati perfetti e l’irrazionalità delle radici che non sono esatte.
Nella lezione sul massimo comune divisore, l’algoritmo di Euclide, che applica la divisione con resto fino a esaurirla, l’identità di Bézout, che se ne deduce, e la soluzione completa delle equazioni diofantee lineari.
Nella lezione sulle congruenze, la trasformazione di tutto ciò che precede in un calcolo: la congruenza modulo $n$ è una relazione di equivalenza compatibile con la somma e il prodotto, le cui classi formano $\mathbb{Z}_n$ ; l’identità di Bézout decide quali resti sono invertibili e quando una congruenza lineare ha soluzione, e dà il teorema cinese del resto; e il lemma di Euclide, insieme agli inversi, dà il piccolo teorema di Fermat.

La scrittura e il conteggio

La lezione sui sistemi di numerazione posizionale ha applicato più e più volte la divisione con resto per dimostrare che ogni naturale si scrive in un solo modo in qualunque base, e con ciò ha giustificato i procedimenti di calcolo e i criteri di divisibilità in ogni base. La lezione sul calcolo combinatorio e il binomio di Newton è tornata al punto di partenza, perché contare è l’operazione che ha dato origine ai naturali: i principi additivo e moltiplicativo, dimostrati a partire dalla definizione del numero di elementi mediante biiezioni (il secondo per induzione a partire dal primo), hanno condotto ai coefficienti binomiali, alla formula di Stifel e al binomio di Newton, la cui dimostrazione riunisce l’induzione, la notazione di sommatoria e il conteggio.

La figura seguente riunisce i quattro tratti in un’unica catena. Ogni nodo della colonna è una definizione o un teorema, numerato secondo l’ordine logico e unito da un arco agli anelli precedenti che la sua dimostrazione usa; intorno fluttuano i sostegni, cioè i principi e gli strumenti a cui la catena ricorre più e più volte, ciascuno unito da una linea continua agli anelli che si appoggiano su di esso e da una tratteggiata all’anello in cui viene stabilito, tranne quelli che si ammettono senza dimostrazione, che sono disegnati come cerchietti vuoti. Facendo clic su un sostegno si evidenziano tutti gli anelli che lo usano, e ogni anello rimanda alla lezione in cui viene dimostrato.

Sostegni della catena

APrincipio di induzione. Se una proprietà vale per $1$ e, supposta vera per un naturale qualsiasi $k$ , vale per il suo successore $S(k)$ , allora vale per tutti i naturali. Stabilito in: 2. Assiomi di Peano.
BTeorema di ricorsione. Fissati il valore in $1$ e una regola che dà il valore in $S(n)$ a partire dal valore in $n$ , esiste un’unica funzione sui naturali che li rispetta; così si definiscono la somma, il prodotto, la potenza, la sommatoria e il fattoriale. Si ammette l’esistenza; l’unicità si dimostra per induzione. Ammesso senza dimostrazione in questa unità.
CInduzione forte. Basta provare una proprietà per $1$ e che, supposta vera per tutti i naturali da $1$ a $n$ , essa vale per $n + 1$ . Stabilito in: 9. Induzione forte.
DBuon ordinamento. Ogni insieme non vuoto di naturali ha un elemento minimo, il che permette di ragionare sul più piccolo controesempio. Stabilito in: 10. Principio del buon ordinamento.
EDivisione con resto. Per ogni intero $a$ e ogni naturale $b$ ci sono un unico quoziente $q$ e un unico resto $r$ tali che $a = bq + r$ e $0 \leq r < b$ . Stabilito in: 12. Divisione con resto.
FCombinazioni lineari. Se un intero $d$ divide gli interi $a$ e $b$ , divide $ax + by$ per tutti gli interi $x$ e $y$ ; in particolare, la loro somma e la loro differenza. Stabilito in: 11. Proprietà della divisibilità.
GNumeri anticipati. Le regole elementari di calcolo e di ordine degli interi, dei razionali e dei reali (segni, cancellazione, frazioni, radici) si anticipano in questa unità senza dimostrazione; la loro costruzione è materia dell’unità successiva. Ammesso senza dimostrazione in questa unità.
HNumero di elementi. Un insieme che ammette una biiezione con $\{1, \ldots, n\}$ ha $n$ elementi; si ammette che tale numero è unico e che i sottoinsiemi di un insieme finito sono finiti. Ammesso senza dimostrazione in questa unità.

Tratto 1 I fondamenti: insiemi, assiomi, operazioni e ordine
- Fissare il linguaggio degli insiemi, delle relazioni e delle funzioni, e provare che le relazioni di equivalenza e le partizioni si corrispondono.
- Definire i naturali a partire dall’ $1$ e dal successore mediante i cinque assiomi di Peano.
- Costruire sul successore una scala di definizioni ricorsive: la somma, il prodotto e la potenza.
- Dedurre per induzione la commutatività, l’associatività, la distributività e la legge di cancellazione.
- Ottenere dalla somma l’ordine, con la tricotomia, la transitività e la monotonia, e precisare quando esistono la sottrazione e la divisione.
1. Equivalenze e partizioni. Le classi di una relazione di equivalenza in un insieme formano una partizione di esso, e ogni partizione è l’insieme delle classi di un’unica relazione di equivalenza.
  Dimostrato in: Insiemi, relazioni e funzioni.
2. Assiomi di Peano. I naturali si generano a partire dall’ $1$ mediante il successore: l’ $1$ non è successore di alcuno, naturali distinti hanno successori distinti, e ogni insieme che contiene l’ $1$ e il successore di ciascuno dei suoi elementi contiene tutti i naturali.
  Dimostrato in: I numeri naturali e gli assiomi di Peano.
3. Somma ricorsiva. La somma, definita da $n + 1 = S(n)$ e $n + S(m) = S(n + m)$ , è commutativa, associativa e cancellabile.
  Usa: 2. Assiomi di Peano. Si appoggia su: A (Principio di induzione), B (Teorema di ricorsione). Dimostrato in: Operazioni di base sui numeri naturali e relazioni d’ordine.
4. Prodotto e potenza. Il prodotto, definito da $n \cdot 1 = n$ e $n \cdot S(m) = n \cdot m + n$ , è commutativo, associativo, distributivo e cancellabile, e la potenza soddisfa $b^n b^m = b^{n + m}$ , $(b^n)^m = b^{nm}$ e $(ab)^n = a^n b^n$ .
  Usa: 3. Somma ricorsiva. Si appoggia su: A (Principio di induzione), B (Teorema di ricorsione). Dimostrato in: Operazioni di base sui numeri naturali e relazioni d’ordine.
5. Ordine, sottrazione e divisione. Se $a < b$ significa che $a + k = b$ per qualche naturale $k$ , tra due naturali vale una e una sola delle relazioni $a < b$ , $a = b$ e $b < a$ , e l’ordine è transitivo e si conserva sommando e moltiplicando; la differenza $a - b$ esiste solo quando $b < a$ , e il quoziente $\frac{a}{b}$ solo quando $b$ divide $a$ , ed entrambi sono unici per la legge di cancellazione.
  Usa: 2. Assiomi di Peano, 3. Somma ricorsiva, 4. Prodotto e potenza. Si appoggia su: A (Principio di induzione). Dimostrato in: Operazioni di base sui numeri naturali e relazioni d’ordine.
Tratto 2 I principi di dimostrazione
- Provare che l’induzione ordinaria, l’induzione forte e il principio del buon ordinamento sono equivalenti.
- Definire ricorsivamente la sommatoria e dedurne le proprietà.
- Dedurre formule con le somme telescopiche, invece di limitarsi a verificarle.
- Sommare le progressioni aritmetiche e geometriche.
1. Induzione a partire da un naturale. Una proprietà che vale per $n_0$ e passa da ogni naturale $k \geq n_0$ a $k + 1$ vale per ogni naturale $n \geq n_0$ .
  Usa: 5. Ordine, sottrazione e divisione. Si appoggia su: A (Principio di induzione). Dimostrato in: Sommatorie, progressioni e induzione.
2. Sommatoria e somma telescopica. Definita ricorsivamente, la sommatoria è lineare, si scompone in somme consecutive e ammette lo spostamento dell’indice e l’inversione dell’ordine; una somma di differenze tra valori consecutivi vale l’ultimo valore meno il primo: $\sum_{k=1}^{n} (b_{k + 1} - b_k) = b_{n + 1} - b_1$ .
  Usa: 4. Prodotto e potenza, 6. Induzione a partire da un naturale. Si appoggia su: A (Principio di induzione), B (Teorema di ricorsione). Dimostrato in: Sommatorie, progressioni e induzione.
3. Progressioni. La somma di $n$ termini di una progressione aritmetica è $\frac{n(a_1 + a_n)}{2}$ , e quella di una geometrica di primo termine $a$ e ragione $r \neq 1$ è $a \cdot \frac{r^n - 1}{r - 1}$ .
  Usa: 7. Sommatoria e somma telescopica. Si appoggia su: A (Principio di induzione), G (Numeri anticipati). Dimostrato in: Sommatorie, progressioni e induzione.
4. Induzione forte. Se una proprietà vale per $1$ e, supposta vera per tutti i naturali da $1$ a $n$ , vale per $n + 1$ , allora vale per tutti i naturali.
  Usa: 6. Induzione a partire da un naturale. Si appoggia su: A (Principio di induzione). Dimostrato in: Sommatorie, progressioni e induzione.
5. Principio del buon ordinamento. Ogni insieme di naturali con almeno un elemento ha un elemento minimo; con il lemma secondo cui ogni naturale diverso da $1$ è un successore e con le proprietà dell’ordine, il buon ordinamento implica a sua volta l’induzione, e i tre principi risultano equivalenti.
  Usa: 5. Ordine, sottrazione e divisione. Si appoggia su: C (Induzione forte). Dimostrato in: Sommatorie, progressioni e induzione.
Tratto 3 L’aritmetica della divisibilità
- Dimostrare con il buon ordinamento l’esistenza e l’unicità del quoziente e del resto.
- Classificare gli interi secondo il loro resto e fondare su ciò i criteri di divisibilità.
- Dimostrare l’infinità dei primi, il lemma di Euclide e la fattorizzazione unica, con le loro conseguenze.
- Calcolare il massimo comune divisore con l’algoritmo di Euclide, dedurne l’identità di Bézout e risolvere le equazioni diofantee lineari.
- Calcolare con le congruenze, decidere quali resti sono invertibili, risolvere congruenze lineari e sistemi con moduli coprimi, e dimostrare il piccolo teorema di Fermat.
1. Proprietà della divisibilità. La divisibilità tra interi è riflessiva e transitiva, un divisore di un intero $a > 0$ è compreso tra $-a$ e $a$ , e se $d$ divide $a$ e $b$ , divide ogni combinazione $ax + by$ .
  Usa: 5. Ordine, sottrazione e divisione. Si appoggia su: G (Numeri anticipati). Dimostrato in: Divisibilità e divisione con resto.
2. Divisione con resto. Per ogni intero $a$ e ogni naturale $b$ esistono un unico quoziente $q$ e un unico resto $r$ tali che $a = bq + r$ e $0 \leq r < b$ .
  Si appoggia su: D (Buon ordinamento), G (Numeri anticipati). Dimostrato in: Divisibilità e divisione con resto.
3. Resti e criteri. Due interi danno lo stesso resto nella divisione per $d$ se e solo se la loro differenza è multipla di $d$ ; ne seguono il resto di una somma, di un prodotto e di una potenza, e i criteri del $3$ , del $9$ e dell’ $11$ .
  Si appoggia su: A (Principio di induzione), E (Divisione con resto), F (Combinazioni lineari). Dimostrato in: Divisibilità e divisione con resto.
4. Divisore primo e infinità. Ogni naturale $n > 1$ ha un divisore primo, e se $n$ è composto, il suo minimo divisore primo $p$ soddisfa $p^2 \leq n$ ; ne segue che nessuna lista finita contiene tutti i numeri primi.
  Usa: 5. Ordine, sottrazione e divisione, 11. Proprietà della divisibilità. Si appoggia su: D (Buon ordinamento), F (Combinazioni lineari). Dimostrato in: Numeri primi e teorema fondamentale dell’aritmetica.
5. Lemma di Euclide. Se un primo divide il prodotto $ab$ , divide $a$ o divide $b$ ; e se divide un prodotto di più fattori, divide uno di essi.
  Si appoggia su: A (Principio di induzione), D (Buon ordinamento), E (Divisione con resto), F (Combinazioni lineari). Dimostrato in: Numeri primi e teorema fondamentale dell’aritmetica.
6. Teorema fondamentale. Ogni naturale $n > 1$ è prodotto di numeri primi, e tale scomposizione è unica a meno dell’ordine dei fattori.
  Usa: 4. Prodotto e potenza, 15. Lemma di Euclide. Si appoggia su: D (Buon ordinamento). Dimostrato in: Numeri primi e teorema fondamentale dell’aritmetica.
7. Divisori e radici irrazionali. Se $n = p_1^{e_1} \cdots p_k^{e_k}$ , i suoi divisori sono i numeri $p_1^{f_1} \cdots p_k^{f_k}$ con $0 \leq f_i \leq e_i$ , e sono $(e_1 + 1) \cdots (e_k + 1)$ ; un naturale $n > 1$ è una potenza $k$ -esima perfetta se e solo se tutti gli esponenti della sua fattorizzazione sono multipli di $k$ , e se non lo è, non esistono naturali $a$ e $b$ con $a^k = n b^k$ , cioè la sua radice $k$ -esima è irrazionale.
  Usa: 15. Lemma di Euclide, 16. Teorema fondamentale. Si appoggia su: A (Principio di induzione), G (Numeri anticipati). Dimostrato in: Numeri primi e teorema fondamentale dell’aritmetica.
8. Algoritmo di Euclide. Se $a = bq + r$ , le coppie $a, b$ e $b, r$ hanno gli stessi divisori comuni; pertanto $\operatorname{MCD}(a, b)$ è l’ultimo resto non nullo delle divisioni successive.
  Si appoggia su: D (Buon ordinamento), E (Divisione con resto), F (Combinazioni lineari). Dimostrato in: Massimo comune divisore e minimo comune multiplo.
9. Identità di Bézout. Esistono interi $x$ e $y$ tali che $ax + by = \operatorname{MCD}(a, b)$ , e il massimo comune divisore è il minimo naturale che si scrive in tale forma.
  Usa: 18. Algoritmo di Euclide. Si appoggia su: A (Principio di induzione), F (Combinazioni lineari), G (Numeri anticipati). Dimostrato in: Massimo comune divisore e minimo comune multiplo.
10. Prodotto del MCD per il mcm. Vale $\operatorname{MCD}(a, b) \cdot \operatorname{mcm}(a, b) = ab$ , e ogni multiplo comune di $a$ e di $b$ è multiplo del loro minimo comune multiplo.
  Usa: 4. Prodotto e potenza, 16. Teorema fondamentale, 17. Divisori e radici irrazionali. Si appoggia su: D (Buon ordinamento), E (Divisione con resto), F (Combinazioni lineari). Dimostrato in: Massimo comune divisore e minimo comune multiplo.
11. Equazioni diofantee. L’equazione $ax + by = c$ ha soluzioni intere se e solo se $d = \operatorname{MCD}(a, b)$ divide $c$ , e allora sono tutte $x = x_0 + \frac{b}{d} t$ e $y = y_0 - \frac{a}{d} t$ , con $t$ intero.
  Usa: 19. Identità di Bézout, 20. Prodotto del MCD per il mcm. Si appoggia su: F (Combinazioni lineari), G (Numeri anticipati). Dimostrato in: Massimo comune divisore e minimo comune multiplo.
12. Congruenze e resti. Due interi sono congrui modulo $n$ se e solo se danno lo stesso resto nella divisione per $n$ ; la congruenza è una relazione di equivalenza compatibile con la somma e il prodotto, e le sue $n$ classi, quelle dei resti $0, 1, \ldots, n - 1$ , formano $\mathbb{Z}_n$ .
  Usa: 1. Equivalenze e partizioni, 13. Resti e criteri. Si appoggia su: E (Divisione con resto), F (Combinazioni lineari). Dimostrato in: Congruenze e aritmetica modulare.
13. Resti invertibili. Un intero $a$ ha inverso modulo $n$ se e solo se $\operatorname{MCD}(a, n) = 1$ , e in tal caso è unico modulo $n$ ; la congruenza $ax \equiv b \pmod{n}$ ha soluzione se e solo se $d = \operatorname{MCD}(a, n)$ divide $b$ , e in tal caso ha $d$ soluzioni modulo $n$ .
  Usa: 22. Congruenze e resti, 19. Identità di Bézout, 21. Equazioni diofantee. Si appoggia su: F (Combinazioni lineari). Dimostrato in: Congruenze e aritmetica modulare.
14. Teorema cinese del resto. Se i naturali $m$ e $n$ sono coprimi, il sistema formato da $x \equiv a \pmod{m}$ e $x \equiv b \pmod{n}$ ha soluzione, ed è unica modulo $mn$ .
  Usa: 22. Congruenze e resti, 19. Identità di Bézout, 20. Prodotto del MCD per il mcm. Si appoggia su: G (Numeri anticipati). Dimostrato in: Congruenze e aritmetica modulare.
15. Piccolo teorema di Fermat. Se $p$ è primo e non divide l’intero $a$ , allora $a^{p - 1} \equiv 1 \pmod{p}$ ; e per ogni intero $a$ , $a^p \equiv a \pmod{p}$ .
  Usa: 22. Congruenze e resti, 15. Lemma di Euclide, 23. Resti invertibili. Dimostrato in: Congruenze e aritmetica modulare.
Tratto 4 La scrittura e il conteggio
- Dimostrare che ogni naturale si scrive in un solo modo in qualunque base.
- Giustificare in ogni base la somma in colonna e i criteri di divisibilità.
- Contare con i principi additivo e moltiplicativo, e ricavarne i coefficienti binomiali e la formula di Stifel.
- Dimostrare il binomio di Newton, che riunisce l’induzione, la notazione di sommatoria e il conteggio.
1. Rappresentazione posizionale. Per ogni base $b \geq 2$ , ogni naturale si scrive in un solo modo come $a_k b^k + \cdots + a_1 b + a_0$ , con cifre comprese tra $0$ e $b - 1$ e $a_k \neq 0$ .
  Si appoggia su: C (Induzione forte), D (Buon ordinamento), E (Divisione con resto). Dimostrato in: Sistemi di numerazione posizionale.
2. Calcolo e criteri in ogni base. La somma in colonna dà la rappresentazione della somma, e in base $b$ un numero dà lo stesso resto della somma delle sue cifre nella divisione per $b - 1$ , e della sua somma a segni alterni nella divisione per $b + 1$ .
  Usa: 7. Sommatoria e somma telescopica, 13. Resti e criteri, 26. Rappresentazione posizionale. Si appoggia su: A (Principio di induzione), E (Divisione con resto). Dimostrato in: Sistemi di numerazione posizionale.
3. Principi di conteggio. L’unione di due insiemi senza elementi comuni, di $m$ e di $n$ elementi, ha $m + n$ elementi, e una scelta in due fasi, di $m$ e di $n$ modi, si effettua in $mn$ modi.
  Usa: 3. Somma ricorsiva, 4. Prodotto e potenza, 5. Ordine, sottrazione e divisione. Si appoggia su: A (Principio di induzione), H (Numero di elementi). Dimostrato in: Calcolo combinatorio elementare e binomio di Newton.
4. Coefficienti binomiali e formula di Stifel. Un insieme di $n$ elementi ha $\binom{n}{k} = \frac{n!}{k!\,(n - k)!}$ sottoinsiemi di $k$ elementi; vale $\binom{n + 1}{k} = \binom{n}{k - 1} + \binom{n}{k}$ , da cui i coefficienti formano il triangolo di Tartaglia, e la riga $n$ ha somma $2^n$ .
  Usa: 28. Principi di conteggio. Si appoggia su: B (Teorema di ricorsione), H (Numero di elementi). Dimostrato in: Calcolo combinatorio elementare e binomio di Newton.
5. Binomio di Newton. Per tutti i numeri $x$ e $y$ , naturali o, anticipando l’unità successiva, reali, e per ogni naturale $n$ , vale $(x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n - k} y^k$ .
  Usa: 7. Sommatoria e somma telescopica, 29. Coefficienti binomiali e formula di Stifel. Si appoggia su: A (Principio di induzione), G (Numeri anticipati). Dimostrato in: Calcolo combinatorio elementare e binomio di Newton.

Verso gli insiemi numerici. La catena si ferma dove i naturali smettono di bastare: la sottrazione e la divisione esistono solo in certi casi, e l’equazione $x^2 = n$ non ha soluzione razionale quando $n$ non è un quadrato perfetto. L’unità successiva amplia i naturali per porvi rimedio.