Rappresentabilità dei naturali in base arbitraria

Teorema

Sia $b \in N$ con $b \geq 2$ . Ogni numero $n \in N$ è rappresentabile in base $b$ , cioè esiste una successione ${ε_{i}}_{i \in N}$ composta da interi $0 \leq ε_{i} < b_{i}$ , che sia definitivamente nulla, ovvero per la quale esiste un valore $k \in N$ per cui $ε_{i} = 0 \forall i > k$ , e tale che $n = \sum_{i = 0}^{\infty} ε_{i} \cdot b^{i}$ . Inoltre, se esiste un'altra tale successione ${ε_{i}^{'}}_{i \in N}$ , vale $ε_{i}^{'} = ε_{i}$ per ogni $i \in N$ .

Dimostrazione

Esistenza

Ogni $n$ è rappresentabile in base $b$ ?
Procediamo per induzione su $n \in N$ di seconda forma.
$n = 0$ (BASE DELL'INDUZIONE)
Osserviamo che essendo $n = 0$ posso esprimere $0$ come una somma polinomiale di zeri.
$n = 0 = \sum_{i \in N}^{} 0 \cdot b^{i}$

$n \geq 1, \forall k < n ⟹ n$ (PASSO INDUTTIVO)
Assumiamo per ipotesi induttiva che tutti i $k \in N$ , con $k < n$ si possa rappresentare in base $b$ .
Dobbiamo dimostrare che anche $n$ ammette una tale rappresentazione in base $b$ .
Consideriamo la divisione euclidea tra $n$ e $b$ .

n = q \cdot b + r, 0 \leq r < | b |

Per ipotesi sappiamo che $b \geq 2$ , quindi vale $q < q \cdot b \leq q b + r = n$
Poichè $q < n$ , grazie all'ipotesi induttiva, $q$ si può rappresentare in base $b$ , ovvero $\exists {δ_{i}}_{i \in I}$ in $I_{b}$ definitivamente nulla e $$q = \underline{\sum_{i = 0}^{\infty}\delta_i \cdot b^i}$$
Segue che:

\begin{aligned} n & = \underset{―}{(\sum_{i = 0}^{\infty} δ_{i} \cdot b^{i})} b + r \\ = \sum_{i = 0}^{\infty} δ_{i} \cdot b^{i + 1} + r \end{aligned}

Sia ora $r = ε_{0}$ . Effettuando un cambio di indice ( $j = i + 1$ ), otteniamo:

n = ε_{0} + \sum_{j = 1}^{\infty} δ_{j - 1} \cdot b^{j} = ε_{0} b^{0} + δ_{0} b^{1} + δ_{1} b^{2} + . . . = \sum_{i \in N} ε_{i} b^{i}

Il passo induttivo è stato fatto. Grazie al principio di induzione di seconda forma, ogni $n$ è rappresentabile in base $b$ .

Unicità

Possono esistere due diverse rappresentazioni per un $n$ ?
Procediamo per induzione su $n \in N$ di seconda forma.

$n = 0$ (BASE DELL'INDUZIONE)
Se $n = 0$ allora tutti gli addendi della sommatoria saranno nulli $⟹ ε_{i} = 0 \forall i \in N$

$n > 0, \forall k < n ⟹ n$ (PASSO INDUTTIVO)
Sia $n > 0$ . Assumiamo che ogni $k \in N$ con $k < n$ ammette una sola rappresentazione in base $b$ (ipotesi induttiva). Dobbiamo provare che ciò è vero anche per $n$ .
Siano ${ε_{i}}_{i \in N}$ , ${ε_{i}^{'}}_{i \in N}$ due successione definitivamente nulle. Proviamo che $ε_{i} = ε_{i}^{'} \forall i \in N$ . Osserviamo che:

n = \sum_{i = 0}^{\infty} ε_{i} \cdot b^{i} = ε_{0} + b (\sum_{i = 1}^{\infty} ε_{i} \cdot b^{i - 1})

n = \sum_{i = 0}^{\infty} ε_{i}^{'} \cdot b^{i} = ε_{0}^{'} + b (\sum_{i = 1}^{\infty} ε_{i}^{'} \cdot b^{i - 1})

dove $ε_{0}, ε_{0}^{'}$ sono i resti delle divisioni di n per b. Ma per l'unicità della divisione euclidea vale $ε_{0} = ε_{0}^{'}$ .
Stesso discorso per i quozienti, che inoltre risultano per definizione $< n$ . Segue, cambiando gli indici della sommatoria:

q = \sum_{j = 0}^{\infty} ε_{j + 1} \cdot b^{j} = \sum_{j = 0}^{\infty} ε_{j + 1}^{'} \cdot b^{j} < n

In conclusione si ha che $ε_{i} = ε_{i}^{'} \forall i \in N$ .
Il passo induttivo è stato fatto. Dunque, grazie al principio di induzione di seconda forma, ogni $n \in N$ ammette una sola rappresentazione in base $b$ .