Insieme induttivo (logica)

In logica matematica, e più precisamente in teoria degli insiemi, un insieme $X$ si dice induttivo oppure apodittico^[1] se soddisfa l'assioma dell'infinito

$\varnothing \in X;$
$x\in X\Rightarrow x\cup \{x\}\in X.$

In altre parole, in base alla definizione di successore per la costruzione standard (dovuta a John von Neumann) dei numeri naturali, se $X$ è un tale insieme allora $X$ contiene l'insieme dei numeri naturali $\mathbb {N}$ ovvero si ha infatti che $X$ contiene come elemento l'insieme vuoto $0$ ed essendo chiuso per successore si ha che contiene anche $1,2,\ldots$ come elementi.

Esistenza degli insiemi induttivi modifica

Il concetto di insieme induttivo ha un ruolo fondamentale nella teoria degli insiemi di Zermelo-Fraenkel; infatti l'assioma dell'infinito, necessario per garantire appunto l'esistenza di insiemi infiniti in ogni modello della teoria, corrisponde esattamente alla seguente proposizione:

Esiste un insieme induttivo.

Questo assioma, oltre a garantire, apoditticamente, che l'insieme $\mathbb {N} =\{0,1,2,\ldots \}$ dei numeri naturali esiste, permette di dimostrare che $\mathbb {N}$ è un modello di Peano.^[2] La costruzione standard dei numeri naturali all'interno della ZF è espressa da:

Il più piccolo insieme induttivo.

Osserviamo che, nonostante gli insiemi induttivi formino una classe propria (ossia l'insieme degli insiemi induttivi non esista), questa è una definizione valida; sappiamo infatti, dall'assioma appena ricordato, che un tale insieme apodittico o induttivo $X$ esiste. Quindi $\mathbb {N}$ può essere determinato mediante l'intersezione come segue

\mathbb {N} =\bigcap _{X'\in A_{X}}X',

dove $A_{X}=\{X'\subseteq X\mid X'\ {\text{induttivo}}\}$ è la famiglia degli insiemi induttivi contenuti in $X.$ Questa definizione di $\mathbb {N}$ è indipendente dalla scelta di $X.$

Etimologia modifica

Induttivo viene, come si può facilmente intuire, da induzione. Il principio di induzione su $\mathbb {N}$ infatti non è altro che la seguente affermazione:

Se $S\subseteq \mathbb {N}$ è induttivo, allora $S=\mathbb {N} .$