Nel definire il concetto di numero primo con la logica, scriveremo una particolare proposizione aperta nella variabile \( x \). Tale proposizione dovrà essere costruita in modo tale da poter essere vera soltanto attribuendo alla \( x \) numeri primi.
Perché 1 non è un numero primo?
Per il teorema fondamentale dell’aritmetica, per ogni numero esiste un’unica fattorizzazione in numeri primi. Ad esempio, il numero \( 56 \) potrà essere fattorizzato come \( 56=2^3 \cdot 7 \). Potremo scambiare l’ordine dei fattori, ma il numero \( 56 \) sarà esprimibile unicamente come prodotto dei soli numeri primi \( 2 \) e \( 7 \), elevati alle rispettive potenze. Per cui la fattorizzazione, non contando l’ordine dei fattori, è unica.
Se \( 1 \) fosse un numero primo, potremmo avere per \( 56 \) infinite fattorizzazioni, tra le quali ad esempio:
\[ 56 = 2^3 \cdot 7 \cdot 1; \qquad 56 = 2^3 \cdot 7 \cdot 1 \cdot 1; \qquad 56=2^3\cdot 7 \cdot 1 \cdot 1 \cdot 1 \cdot 1 \cdot … \]
Per questo motivo, si è convenuto di considerare \( 1 \) come un numero non primo, anche se è comunque divisibile soltanto per sé stesso e per… \( 1 \).
Quindi, per la nostra proposizione, dobbiamo tenere conto che \( 1 \) andrà escluso.
Definizione alternativa di numero primo
Un numero primo è un numero naturale maggiore di \( 1 \) che non può essere esprimibile come prodotto di due numeri entrambi minori del numero primo stesso.
Questa definizione, del tutto equivalente a quella data inizialmente, si presta meglio per scrivere la nostra proposizione.
Affinché un numero naturale possa dirsi primo, abbiamo quindi due condizioni che devono essere soddisfatte contemporaneamente:
- il numero deve essere maggiore di \( 1 \);
- il numero non deve essere esprimibile come \( x=a \cdot b \), con \( a < x \quad \text{et} \quad b < x \).
Capiamo dunque che dobbiamo scrivere due proposizioni, ciascuna per condizione, e collegarle tra loro mediante la congiunzione logica.
Dunque, scritte le due proposizioni \( a(x) \) e \( b(x) \) , la proposizione che individua i numeri primi sarà:
\[ p(x)=a(x) \wedge b(x) \]
Per la prima condizione possiamo scrivere la proposizione:
\[ a(x): “x > 1” \]
Per la seconda proposizione, è necessaria qualche considerazione in più 😉
Partiamo dalla definizione di numero composto: un numero naturale maggiore di \( 1 \) è composto se non è primo. Dunque, un numero composto dovrà essere esprimibile come \( x=a \cdot b \) con \( a, b < x \).
Ora, la seguente proposizione viene verificata attribuendo alla \( x \) un qualsiasi numero composto:
\[ \forall a, \: \forall b \: \in \mathbb{N}, \quad \exists (a,b) \quad \text{t.c} \quad x=a \cdot b \quad \wedge \quad (a < x) \quad \wedge \quad (b < x) \]
Ovvero, fra tutte le coppie di numeri naturali \( a, b \) affinché un numero sia composto deve esistere una coppia \( (a,b) \) di numeri entrambi minori di \( x \) tali che la relazione \( x=a \cdot b \) è verificata. L’esistenza di tale coppia viene indicata con il quantificatore esistenziale \( \exists \).
Siamo praticamente quasi arrivati alla proposizione \( b(x) \). Ci basta soltanto dire che un numero sarà primo solamente se una tale coppia \( (a,b) \) non esiste. Per fare ciò, dobbiamo negare il quantificatore esistenziale \( \exists \), utilizzando il quantificatore \( \nexists \):
\[ b(x): “\forall a, \: \forall b \: \in \mathbb{N}, \quad \nexists (a,b) \quad \text{t.c} \quad (x=a \cdot b) \quad \wedge \quad (a < x) \quad \wedge \quad (b < x)” \]
Come si può notare, abbiamo utilizzato la congiunzione logica per esprimere il fatto che le tre condizioni appena scritte relative agli elementi \( a,b \) devono essere verificate contemporaneamente.
Osserviamo che la proposizione \( b(x) \) è una proposizione aperta nella quale l’argomento variabile è \( x \). Non scriviamo \( b(x, a, b) \) poiché nell’enunciato della proposizione viene esplicitamente detto che agli elementi \( a,b \) vengono attribuiti tutti i numeri naturali, tramite i quantificatori universali \( \forall \).
In conclusione, possiamo dire che un numero naturale \( x \) è primo se risulta vera la seguente proposizione:
\[ a(x) \wedge b(x) \]
ovvero se risulta vera:
\[ p(x): “x > 1 \:\wedge \: (\forall a, \: \forall b \: \in \mathbb{N}, \quad \nexists (a,b) \: \text{t.c} \:\: (x=a \cdot b)\:\wedge \: (a < x) \:\wedge \: (b < x)) ” \]
Osserviamo che questa proposizione individua i numeri primi senza utilizzare criteri di divisibilità 😉
Precisiamo per completezza che questa proposizione, che fornisce una definizione di numero primo con la logica, è definita nell’insieme dei numeri naturali (\( \forall x \in \mathbb{N} \), ovviamente).
Abbiamo dunque visto una possibile definizione di numero primo con la logica. Tale definizione può essere utilizzata in un programma informatico, in modo da poter scrivere rapidamente i numeri primi presenti nei primi \( n \) numeri naturali. Ad esempio, il seguente elenco è stato creato mediante un programma che utilizza la proposizione costruita in questa lezione. Ciao a tutti! 🙂
