Cardinalità e composizione di insiemi numerabili

Gli insiemi numerabili di maggiore utilità in genere possono essere elencati da procedure che, almeno a grandi linee, possono essere definite senza difficoltà.

Per sviluppare lo studio di tali procedure si cerca di individuare classi di procedure e di insiemi numerabili i quali:

1.   abbiano portata il più possibile ampia,
2.   possano dimostrarsi sufficientemente controllabili e
3.   possano essere utilizzati proficuamente per attività computazionali.

Conviene segnalare subito che in genere tra i precedenti requisiti si devono raggiungere dei compromessi.

Ci preoccuperemo anche di introdurre per essi notazioni specifiche che seguano schemi generali.

Indichiamo con $\mathbb {P}$ l'insieme degli interi positivi. Questa convenzione si introduce con la seguente notazione:

$\mathbb {P} :=\{numero\ intero\ positivo\}=\{1,2,3,...,n,...\}$.

In generale per introdurre un simbolo $I$ che denoti un insieme la cui conoscenza si fa dipendere da una denominazione di chiaro significato per il suo elemento generico, e per indicare un elenco di suoi elementi useremo notazioni del tipo:

$I:=\{denominazione\ dell'elemento\ generico\}=\{x_{1},x_{2},x_{3},...,x_{n},...\}$.

Definizioni dello stesso genere sono:

$\mathbb {N} :=\{numero\ intero\ naturale\}=\{0,1,2,...,n,...\}$;

$\mathbb {E} ven:=\{numero\ pari\}=\{2,4,6,...,2n,...\}$;

$\mathbb {O} dd:=\{numero\ dispari\}=\{1,3,5,...,2n-1,...\}$.

Per due generici interi $a\in \mathbb {N}$ e $b\in \mathbb {P}$ si denota $a\cdot \mathbb {N} +b$ l'insieme degli interi naturali esprimibili come $a\cdot n+b$ con $n$ naturale arbitrario. Questa notazione si può definire come una abbreviazione

$a\cdot \mathbb {N} +b:=\{n\in \mathbb {N} :a\cdot n+b\}$.

Nel secondo membro di questa definizione si può individuare facilmente una procedura che consente di elencare ordinatamente gli elementi dell'insieme.

Essa procede a generare i naturali, ciascuno di essi viene moltiplicato per $a$ e aumentato di $b$ e l'intero ottenuto viene emesso.

L'insieme in esame può essere definito anche con la seguente espressione

$a\cdot \mathbb {N} +b:=\{k\in \mathbb {N} :k=a\cdot n+b,\ {\mbox{con}}\ n\in \mathbb {N} \}$.

In essa interviene la sottoespressione $k=a\cdot n+b$ costruita con segni di operatori (aritmetici), il segno «=» indicante la richiesta di una uguaglianza, parametri ($a$, $b$ e $k$) il cui valore si considera noto (invece dei parametri $a$ e $b$ si potrebbero avere dei numeri naturali espliciti) ed un simbolo, $n$ che rappresenta una cosiddetta variabile incognita, cioè un valore da ricercare in un determinato insieme, $\mathbb {N}$, in modo da soddisfare l'uguaglianza espressa.

Questa sottoespressione costituisce una equazione: più precisamente si parla di equazione aritmetica basata sopra una espressione aritmetica, cioè una espressione nella quale compaiono operandi, operatori ed una incognita riguardanti numeri interi. Ad es. si hanno gli insiemi dei quadrati e dei cubi degli interi positivi $\{n\in \mathbb {P} :n^{2}\}$ e $\{n\in \mathbb {P} :n^{3}\}$.

In generale si definisce relazione numerabile un insieme numerabile di coppie di elementi e si dice relazione contabile un insieme contabile di coppie di elementi.

I primi membri ed i secondi membri delle coppie di una relazione numerabile $R$ costituiscono due insiemi contabili: infatti dalla procedura che genera $R$ si ricavano facilmente le due procedure che generano rispettivamente i primi ed i secondi membri delle coppie. Di questi due insiemi contabili almeno uno è numerabile (in caso contrario si avrebbe una relazione finita).

Anche per le relazioni numerabili si distinguono le funzioni, le iniezioni, le suriezioni, le biiezioni, le relazioni simmetriche, le antisimmetriche, le transitive, le riflessive, le relazioni d'ordine, ... basandosi su richieste che differiscono da quelle invocate per le relazioni finite solo in quanto riguardano ambienti non finiti ma numerabili.

Consideriamo una generica procedura elencativa $P$ che individua un insieme contabile $P_{S}$ e le associamo una funzione da un insieme numerabile di base (come $\mathbb {N}$ o come un insieme ${\mathcal {A}}^{*}$ di tutte le stringhe sopra un alfabeto determinato ${\mathcal {A}}$) nell'insieme contabile che la $P$ determina. A $P$ ed $\mathbb {N}$ si associa la funzione del tipo $\{\mathbb {N} \longmapsto P_{S}\}$ la quale, qualora $P$ nella $n$-esima fase emissiva emette $x_{n}$, all'intero $n$ fa corrispondere $x_{n}$ .

Può essere utile esprimere questa funzione numerabilecon una notazione come:

$\left[n\in \mathbb {N} \mapsto {\mathcal {P}}_{n}(=x_{n})\right].$

Due insiemi numerabili si possono porre in corrispondenza biunivoca. Per avere un procedimento generale che faccia questo basta individuare due procedure che emettono due elenchi non ripetitivi riguardanti i due insiemi: indichiamoli rispettivamente come segue:

$x_{1},x_{2},x_{3},...,x_{n},...\qquad \qquad y_{1},y_{2},y_{3},...,y_{n},...$ .

La corrispondenza richiesta è costituita dalle coppie

$\left\langle x_{1},y_{1}\right\rangle ,\left\langle x_{2},y_{2}\right\rangle ,\left\langle x_{3},y_{3}\right\rangle ,...,\left\langle x_{n},y_{n}\right\rangle ,...$.

A tutti gli insiemi numerabili, quindi, si può attribuire una sola cardinalità: questa viene detta cardinalità del numerabile e viene individuata dalla scrittura $\aleph _{0}$ ; essa si legge «alef con zero» in quanto utilizza alef, la prima lettera dell'alfabeto fenicio ed ebraico.

Si dice anche che la totalità degli insiemi numerabili costituisce una classe di equicardinalità.

Si osservi che il termine «totalità» usato nella precedente espressione richiederebbe un approfondimento che necessita di definire in modo preciso cosa si deve intendere con il termine «procedure elencative»; in altri termini si dovrebbe stabilire quali descrizioni di meccanismi possono considerarsi procedure elencative e quali no.

È importante osservare che un insieme numerabile si può porre in biiezione con una sua parte: ad es. l'insieme dei naturali $\mathbb {N}$ si può porre in biiezione con l'insieme degli interi positivi $\mathbb {P}$ o con l'insieme dei numeri pari $\mathbb {E} ven$. Questa possibilità a prima vista un po' paradossale, non si verifica per gli insiemi finiti; anzi essa costituisce una caratteristica degli insiemi infiniti.

Per gli insiemi ricorsivamente enumerabili, in quanto entità per le quali ha senso porre il problema dell'appartenenza ed il problema della possibilità di metterli in biiezione con una loro parte, si possono definire attraverso costruzioni simili a quelle introdotte per gli insiemi espliciti, le relazioni di sottoinsieme, sottoinsieme proprio, sovrainsieme, sovrainsieme proprio, disgiunzione e non confrontabilità e le operazioni di unione, intersezione, eliminazione, differenza simmetrica, complementazione e prodotto cartesiano.

Per queste relazioni ed operazioni si usano le stesse notazioni adottate per gli insiemi espliciti e valgono molte delle proprietà verificabili per gli insiemi espliciti. Ora però sono necessarie cautele e distinzioni per quanto concerne la effettiva verificabilità delle relazioni e la effettiva costruzione dei risultati delle operazioni.

Si abbiano quindi due insiemi ricorsivamente enumerabili $N_{1}$ ed $N_{2}$ individuati risp. dalle procedure elencative $P_{1}$ e $P_{2}$ , che per semplicità consideriamo non ripetitive.

Si dice unione di $N_{1}$ ed $N_{2}$ , e si indica $N_{1}\cup N_{2}$ , l'insieme individuato dalla procedura che si preoccupa di fare svolgere alternatamente a $P_{1}$ ed a $P_{2}$ i relativi passi evolutivi e che si pone in grado di emettere sia gli identificatori di elementi di $N_{1}$ che quelli di elementi di $N_{2}$ , eliminando le eventuali ripetizioni.

Ad es.   $\mathbb {O} dd\cup \mathbb {E} ven=\mathbb {P} \qquad \qquad \left(1+4\cdot \mathbb {N} \right)\cup \left(3+4\cdot \mathbb {N} \right)=1+2\cdot \mathbb {N} =\mathbb {O} dd$.

Si dice intersezione di $N_{1}$ ed $N_{2}$ , e si indica $N_{1}\cap N_{2}$, l'insieme individuato dalla procedura che si incarica di far svolgere alternatamente a $P_{1}$ ed a $P_{2}$ i relativi passi evolutivi mantenendo la registrazione di quanto generato da ciascuna di esse; ad ogni nuovo identificatore emesso essa verifica se tale stringa non è ancora stata emessa ed in tal caso stabilisce se è già stata generata dall'altra procedura: quando questo si verifica la emette.

Si trova ad es. che   $2\cdot \mathbb {N} \cap 3\cdot \mathbb {N} =6\cdot \mathbb {N}$;   più in generale,   $\forall a,b\in \mathbb {P} :\ a\cdot \mathbb {N} \cap b\cdot \mathbb {N} =mcm(a,b)\cdot \mathbb {N}$.

Si dice eliminazione da $N_{1}$ di $N_{2}$ , e si indica $N_{1}-N_{2}$, l'insieme individuato dalla procedura che fa svolgere alternatamente a $P_{1}$ ed a $P_{2}$ i relativi passi evolutivi mantenendo la registrazione di quanto generato da ciascuna di esse; ad ogni nuovo identificatore emesso da $P_{1}$ essa verifica che non sia già stata emessa da $P_{1}$ e da $P_{2}$ ; se non è stata ancora emessa da $P_{1}$ ; nel caso sia già stata emessa da $P_{2}$ si limita ad elencarla fra le emesse da $P_{1}$ ; se non lo è stata la aggiunge al proprio elenco di risultati eventualmente provvisori. Ad ogni nuovo identificatore emesso da $P_{2}$ , si preoccupa di aggiungerla ai risultati di $P_{2}$ e se compare tra i propri risultati cura che sia eliminata.

Ad es.   $6\cdot \mathbb {N} \ -\ 4\cdot \mathbb {N} =6+12\cdot \mathbb {N}$.

Alla eliminazione si riconduce la complementazione di un insieme ricorsivamente enumerabile in un insieme ambiente della stessa natura.

Si dice differenza simmetrica fra $N_{1}$ ed $N_{2}$ , e si indica $N_{1}\triangle N_{2}$ , l'insieme individuato dalla procedura che fa svolgere alternatamente a $P_{1}$ ed a $P_{2}$ i relativi passi evolutivi, mantiene gli elenchi che le due procedure vanno costruendo, cura, come descritto in precedenza, la costruzione di altri due elenchi provvisori nei quali registra gli elementi da assegnare a $N_{1}-N_{2}$ e ad $N_{2}-N_{1}$ e infine procede a costruire sul nastro di uscita l'elenco dell'unione dei due precedenti. Questa procedura per ogni nuovo elemento di $N_{1}$ (di $N_{2}$) si preoccupa se deve essere eliminato dal nastro riguardante $N_{2}-N_{1}$ ($N_{1}-N_{2}$) e quindi dal nastro di uscita.

Ad es.   $2\cdot \mathbb {N} \ \triangle \ 3\cdot \mathbb {N} =\{2,3,4\}+6\cdot \mathbb {N}$.

Si dice prodotto cartesiano di $N_{1}$ ed $N_{2}$ , e si indica $N_{1}\times N_{2}$ , l'insieme individuato dalla procedura che cura che $P_{1}$ e $P_{2}$ svolgano alternatamente i propri passi evolutivi, mantiene i relativi elenchi in costruzione $L_{1}$ ed $L_{2}$ e per ogni nuovo identificatore estende l'elenco sul suo nastro di uscita. Se in un certo istante sono stati costruiti i due elenchi $L_{1}$ ed $L_{2}$ seguenti:

      $x_{1},\ x_{2},\ x_{3},\ ...,\ x_{m}$

      $y_{1},\ y_{2},\ y_{3},\ ...,\ y_{n}$ ,

sul nastro di uscita si ha un elenco della forma

      $\left\langle x_{1},y_{1}\right\rangle ,\ ...,\ \left\langle x_{m},y_{n}\right\rangle$.

Se il successivo identificatore generato è $x_{m+1}$ , l'elenco dei risultati diventa

      $\left\langle x_{1},y_{1}\right\rangle ,\ ...,\ \left\langle x_{m},y_{n}\right\rangle ,\ \left\langle x_{m+1},y_{1}\right\rangle ,\ ...,\ \left\langle x_{m+1},y_{n}\right\rangle$.

Se invece viene generato prima $y_{n+1}$ si ha l'elenco

      $\left\langle x_{1},y_{1}\right\rangle ,\ ...,\ \left\langle x_{m},y_{n}\right\rangle ,\ \left\langle x_{1},y_{n+1}\right\rangle ,\ ...,\ \left\langle x_{m},y_{n+1}\right\rangle$.

Il prodotto cartesiano di un insieme ricorsivamente enumerabile $N$ per sé stesso si dice quadrato cartesiano e si indica $N^{\times 2}$ o semplicemente $N^{2}$.

Sono particolarmente importanti $\mathbb {P} ^{2}$ e $\mathbb {N} ^{2}$, cioè gli insiemi delle coppie di interi positivi o di naturali.

Le procedure che abbiamo delineato per le precedenti operazioni garantiscono che si sono definiti insiemi ricorsivamente enumerabili.

Per le varie operazioni si pone poi il problema di stabilire se operando su insiemi numerabili si ottiene un insieme numerabile.

Le procedure introdotte per l'unione ed il prodotto cartesiano operano senza backtracking , cioè procedono a costruire elenchi che non vengono mai ridotti; si potrebbe dire che «operano senza ripensamenti». Questo tipo di comportamento garantisce che le due procedure individuano insiemi numerabili. Dunque l'unione e il prodotto cartesiano di insiemi numerabili sono insiemi numerabili. Inoltre evidentemente l'unione e il prodotto cartesiano di un insieme numeabile e un insieme finito sono insiemi numerabili. Si può anche affermare che l'unione e il prodotto cartesiano di insiemi contabili sono insiemi contabili.

Succede invece che l'intersezione di due insiemi numerabili è stata costruita con passi riduttivi. In effetti si hanno coppie di insiemi numerabili la cui intersezione risulta numerabile   (come   $5\cdot \mathbb {N} \cap 7\cdot \mathbb {N} =35\mathbb {N}$  ), finita   (come   $\left(-\infty ,1\right]\cap \left[-1,+\infty \right)=\{-1,0,1\}$  ) o anche vuota   (come   $\mathbb {E} ven\cap \{n\in \mathbb {O} dd:n^{3}\}$  ).

Considerazioni analoghe valgono per l'eliminazione e la differenza simmetrica. Rimangono quindi da esaminare caso per caso i problemi della finitezza e della vacuità delle intersezioni, eliminazioni e differenze simmetriche di due insiemi numerabili.

Per il prodotto cartesiano, gestendo opportunamente le emissioni delle procedure che forniscono gli insiemi fattori, si può ottenere un cosiddetto elenco diagonale alla Cantor della forma

      $\left\langle x_{1},y_{1}\right\rangle ,\left\langle x_{1},y_{2}\right\rangle ,\left\langle x_{2},y_{1}\right\rangle ,\left\langle x_{1},y_{3}\right\rangle ,\left\langle x_{2},y_{2}\right\rangle ,\left\langle x_{3},y_{1}\right\rangle ,...$,

oppure un elenco che cresce con l'aggiunta dei cosiddetti nuovi ganci :       $\left\langle x_{1},y_{1}\right\rangle ,\left\langle x_{1},y_{2}\right\rangle ,\left\langle x_{2},y_{2}\right\rangle ,\left\langle x_{2},y_{1}\right\rangle ,\left\langle x_{1},y_{3}\right\rangle ,\left\langle x_{2},y_{3}\right\rangle ,\left\langle x_{3},y_{3}\right\rangle ,\left\langle x_{3},y_{2}\right\rangle ,\left\langle x_{3},y_{1}\right\rangle ,...$

Vediamo ora quali cautele si devono adottare per utilizzare effettivamente le entità individuate componendo le operazioni precedenti.

Innanzi tutto si pone il problema dell'appartenenza di una generica entità $x$ di un certo ambiente $U$ ad un sottoinsieme numerabile $S\subseteq U$.

Per insiemi ricorsivi definiti in modo semplice si possono anche cercare metodi che risolvono il precedente problema efficientemente.

Ad es. è piuttosto banale stabilire una tale proprietà a partire da una rappresentazione decimale di un intero per alcuni sottoinsiemi di $\mathbb {N}$ come l'insieme dei pari, l'insieme dei dispari, l'insieme degli interi divisibili per 3, per 4 e per 5. È un po' meno banale per i naturali divisibili per 7 e può costituire un lavoro molto impegnativo stabilire se un intero molto grande sia primo o meno.

Per tutti questi sottoinsiemi di $\mathbb {N}$, comunque, risulta possibile per un intero naturale qualsiasi $n$ dare risposta alla domanda esprimibile come “$n\in S$?”, cioè ad un cosiddetto problema di appartenenza.

Diciamo insieme ricorsivo un insieme numerabile per il quale è possibile risolvere il problema dell'appartenenza.

Evidentemente tutti gli insiemi espliciti sono ricorsivi, mentre può essere problematico stabilire se un insieme ricorsivamente enumerabile sia ricorsivo.

Il problema dell'appartenenza si risolve con procedimenti semplici, almeno in linea di principio, nel caso di insiemi numerabili di ambienti numerabili che si possono generare con le cosiddette procedure elencative progressive , cioè con procedure che generano elenchi non ripetitivi che seguono ordinamenti totali controllabili da meccanismi che dati due elementi diversi sono in grado di stabilire con un numero finito di passi quale dei due sia il precedente. Questi insiemi si dicono insiemi numerabili progressivi .

Due di tali ambienti sono chiaramente ${\mathcal {A}}^{*}$ per ogni alfabeto finito ${\mathcal {A}}$ ed $\mathbb {N}$; altri ambienti numerabili progressivi si ottengono mediante unioni e prodotti cartesiani dei precedenti.

Per gli insiemi numerabili progressivi il problema dell'appartenenza si può risolvere seguendo una strategia sostanzialmente semplice nelle sue linee generali.

Se si tratta di stabilire se l'oggetto $x$ dell'ambiente $U$ appartiene o meno al sottoinsieme $S\subseteq U$, si procede a generare l'elenco degli elementi di $S$ con la relativa procedura progressiva e ad ogni nuovo elemento $y_{n}$ si verifica se $x=y_{n}$ e in caso negativo con il meccanismo di confronto per $U$ si stabilisce se $y_{n}$ precede $x$: in caso positivo si prosegue l'indagine, in caso contrario si decide che $x\not \in S$. In ogni caso questo procedimento deve concludersi dopo un numero finito di passi.

Con gli ambienti numerabili progressivi si possono effettuare costruzioni e ricerche particolarmente utili ed interessanti.

Si possono però incontrare procedure elencative che emettono stringhe senza seguire un ordine che si sappia controllare, eventualmente effettuando manovre di backtracking, i quali in certe fasi delle loro evoluzioni potrebbero presentare comportamenti poco chiari.

Per un tale meccanismo $P_{S}$ e per l'insieme ricorsivamente enumerabile $S$ che esso genera può accadere di non riuscire a risolvere il problema dell'appartenenza $x\in S?$. Sostanzialmente quando la $P_{S}$ genera un elemento $y_{n}\in S$ diverso da $x$ può accadere che non si riesca a porlo in relazione con $x$ stesso in modo da stabilire se $x$ potrà essere generato successivamente dalla $P_{S}$ oppure se la cosa risulta impossibile.

Si dice procedura selettiva relativa ad un insieme ricorsivo ambiente $U$ una procedura ${\mathcal {S}}$ che ha lo scopo di assegnare ad un generico elemento di $U$ un valore ${\mbox{t}}$ (o yes, o 1) oppure un valore ${\mbox{f}}$ (o no, o 0). Se questa assegnazione può essere effettuata in un numero finito di passi per ogni elemento di $U$ si parla di algoritmo selettivo.

Completando una procedura che elenca ordinatamente $U$ con un algoritmo selettivo ${\mathcal {S}}$ e con un meccanismo che decide di emettere solo gli elementi di $U$ cui ${\mathcal {S}}$ assegna il valore “affermativo” ${\mbox{t}}$, si individua un sottoinsieme ricorsivo di $U$ che indicheremo $U\left({\mathcal {S}}\right)$. Con una semplice modifica del ruolo di ${\mathcal {S}}$, cioè decidendo di emettere solo gli elementi di $U$ cui ${\mathcal {S}}$ assegna il valore “negativo” ${\mbox{f}}$, si individua il complementare dell'insieme ricorsivo precedente $U\left({\bar {\mathcal {S}}}\right):=U-U\left({\mathcal {S}}\right)$. Evidentemente anche questo è un insieme ricorsivo.

Non è difficile dimostrare che un sottoinsieme di un ambiente ricorsivo $U$ è ricorsivo se e solo se sia $S$ che $U-S$ sono ricorsivamente enumerabili.

Quindi un sottoinsieme ricorsivamente enumerabile e non ricorsivo di un ambiente ricorsivo $U$ è caratterizzato dall'avere il complementare non ricorsivamente enumerabile.

Ora si dimostra che un tale sottoinsieme esiste: quindi esistono sottoinsiemi ricorsivamente enumerabili non ricorsivi. In altri termini esistono procedure che individuano sottoinsiemi “dai confini tanto complessi” che non esiste alcun algoritmo in grado di decidere in un numero finito di passi per ogni elemento dell'ambiente ricorsivo se appartiene o meno ad uno di essi.

Si tratta quindi di sottoinsiemi scarsamente controllabili, decisamente più sfuggenti dei ricorsivi.

Si trova anche che non esiste alcun modo generale che consente di stabilire se un insieme ricorsivamente enumerabile sia ricorsivo o meno. Questo comporta che i confini della collezione degli insiemi ricorsivamente enumerabili meno controllabili sono inerentemente mal definiti e questo costituisce un altro aspetto oscuro di questi insiemi.

Questi fatti costituiscono dei limiti sostanziali alla portata della matematica. Ciò nonostante risulta essenziale proseguire nello studio degli insiemi ricorsivamente enumerabili, sia per dare chiarezza a questioni generali che per inquadrare meglio intere famiglie di metodi costruttivi di elevato interesse applicativo.

Sorgono problemi per il controllo dell'intersezione di due insiemi numerabili, la quale evidentemente potrebbe essere un insieme numerabile, un insieme finito o l'insieme vuoto.

Sorgono problemi per le eliminazioni ovvero per gli insiemi complementari. È facile costruire il complementare entro un insieme costruito mediante un elenco ordinato di un suo sottoinsieme dello stesso genere: il risultato è un insieme dello stesso genere e quindi ricorsivo. Nei casi meno controllabili la costruzione deve essere studiata per casi specifici o per famiglie di casi specifici.

Può anche accadere di non saper risolvere il problema della finitezza o meno, problema riguardante il fatto che una evoluzione di una procedura elencativa comporti l'emissione di un elenco limitato o meno di identificatori diversi.

Più in particolare si pone il problema della vacuità o meno, problema che si chiede se una evoluzione di una procedura elencativa non emetta alcun identificatore.

A questo problema si riducono altri problemi: ad esempio il problema espresso con il quesito “$A\subseteq B?$” è del tutto equivalente a quello esprimibile come “$A-B=\varnothing ?$”.

Con le nozioni di procedure e di insieme numerabile risulta possibile ampliare l'insieme dei numeri naturali agli insiemi dei numeri interi relativi ed all'insieme dei numeri razionali. Ricordiamo brevemente le motivazioni di queste estensioni della nozione di numero. L'insieme degli interi relativi consente di introdurre l'operazione binaria di differenza come operazione inversa della somma definita per tutti i numeri. L'insieme dei numeri razionali consente invece di risolvere il problema dell'inversione della moltiplicazione introducendo l'operazione binaria di divisione definita per quasi tutti i numeri (risulta inopportuno definire la divisione per 0).