Relazione ben fondata
# Relazione ben fondata

In matematica, una relazione binaria R si dice ben fondata su una classe X se ogni sottoinsieme non vuoto S ⊆ X ha un elemento minimo rispetto a ‘’R’’, cioè un elemento m non correlato da s R m (ad esempio: "s è minore di m"), per ogni s ∈ S. In altre parole, una relazione è ben fondata se:

    $(\forall S\subseteq X)\;[S\neq \emptyset \implies (\exists m\in S)(\forall s\in S)\lnot (s\mathrel {R} m)].$

Alcuni autori includono un'ulteriore condizione, vale a dire che R sia simile ad un insieme, cioè che gli elementi minori di un qualunque elemento dato formino a loro volta un insieme.

In modo analogo, assumendo l'assioma della scelta dipendente, una relazione è fondata quando non contiene infinite catene discendenti, il che può essere dimostrato quando non esiste una sequenza infinita $x_0,$ $x_1,$ $x_2,$ ...di elementi di X tale che $x_{n+1}$ R $x_n$ per ogni numero naturale n.

Nella teoria degli ordini, un ordine parziale si dice ben fondato se l'ordine parziale in senso stretto corrispondente è una relazione ben fondata. Se l'ordine è un ordine totale, la relazione si dice ben fondata.

Nella teoria degli insiemi, un insieme X è chiamato insieme ben fondato se la relazione di appartenenza all'insieme è ben fondata sulla chiusura transitiva di x. L'assioma di regolarità, che è uno degli assiomi della teoria degli insiemi di Zermelo-Fraenkel, afferma che tutti gli insiemi sono ben fondati.

Una relazione R è inversamente fondata, ascendente o noetheriana su X, se la relazione inversa $R^{−1}$ è ben fondata su X . In questo caso, si dice anche che R soddisfi la condizione della catena ascendente. Nel contesto dei sistemi di riscrittura, una relazione noetheriana è anche chiamata terminazione.

## Induzione e ricorsione

Un motivo importante per cui le relazioni ben fondate sono interessanti è perché su di esse può essere utilizzata una versione dell'induzione transfinita: se (X , R) è una relazione ben fondata, P (x) è una proprietà degli elementi di X , tesi che si dimostra come segue:

P (x) vale per tutti gli elementi x di X, è sufficiente dimostrare che: Se x è un elemento di X e P (y) è vero per ogni y tale che y R x, allora anche P ( x ) deve essere vera.

In simboli, si ha:

    $(\forall x\in X)\;[(\forall y\in X)\;[y\mathrel {R} x\implies P(y)]\implies P(x)]\quad {\text{implies}}\quad (\forall x\in X)\,P(x).$

L'induzione ben fondata è talvolta chiamata induzione noetheriana da Emmy Noether.

Al pari dell'induzione, anche le relazioni ben fondate supportano la costruzione di oggetti matematici mediante la ricorsione transfinita.

Sia ( X , R ) una relazione insiemistica ben fondata e F una funzione che assegna un oggetto ‘’F=F( x , g )’’ a ciascuna coppia di un elemento x ∈ X e di una funzione g sul segmento iniziale {y : y R x} di X. Allora esiste una funzione unica G tale che per ogni x ∈ X,

    $G(x)=F\left(x,G\vert _{\left\{y:\,y\mathrel {R} x\right\}}\right).$

Ciò significa che, se si desidera costruire una funzione G su X, è possibile definire G ( x ) utilizzando i valori di G ( y ) per y R x.

A titolo di esempio, si consideri la relazione ben fondata (N , S ), dove N è l'insieme di tutti i numeri naturali e S è il grafico della funzione successore x ↦ x +1. Allora l'induzione su S è la solita induzione matematica, e la ricorsione su S è la ricorsione primitiva. Se consideriamo la relazione d'ordine ( N , <), otteniamo l'induzione completa. L'affermazione che ( N , <) è ben fondata è anche nota come principio del buon ordinamento.

Esistono altri casi speciali interessanti di induzione ben fondata. Quando la relazione ben fondata è il solito ordinamento sulla classe di tutti i numeri ordinali, la tecnica è chiamata induzione transfinita. Quando l'insieme ben fondato è un insieme di strutture di dati definite in modo ricorsivo, la tecnica è chiamata induzione strutturale. Quando la relazione ben fondata è impostata sull'appartenenza alla classe universale, la tecnica è nota come induzione-epsilon.

## Esempi

Le relazioni ben fondate che non sono del tutto ordinate includono:

* Gli interi positivi {1, 2, 3, ...}, con l'ordine definito da a < b se e solo se a divide b e a ≠ b;
* L'insieme di tutte le stringhe finite su un alfabeto fisso, con l'ordine definito da s < t se e solo se s è una sottostringa propria di t;
* L'insieme N × N di coppie di numeri naturali, ordinato per $(n_1,$ $n_2)$ < $(m_1,$ $m_2$ se e solo se $n_1$ < $m_1$ and $n_2$ < $m_2;$
* Ogni classe i cui elementi sono insiemi, con la relazione $\in$ ("è un elemento di"). Questo è l'assioma di regolarità.
* I nodi di qualsiasi grafo aciclico orientato finito, con la relazione R definita tale che a R b se e solo se esiste un arco da a a b.

Esempi di relazioni non ben fondate includono:

* Gli interi negativi {−1, −2, −3, ...}, con il solito ordine, poiché ogni sottoinsieme illimitato non ha alcun elemento minimo.
* L'insieme delle stringhe su un alfabeto finito con più di un elemento, nell'ordine consueto (lessicografico), poiché la sequenza "B" > "AB" > "AAB" > "AAAB" > ... è una catena discendente infinita. Questa relazione non è ben fondata anche se l'intero insieme ha un elemento minimo, ovvero la stringa vuota
* L'insieme dei numeri razionali (o di quelli reali) non negativi nell'ordinamento standard, poiché, ad esempio, il sottoinsieme dei razionali positivi (o reali) manca di un minimo.

## Altre proprietà

Se ( X , <) è una relazione ben fondata e x è un elemento di X, allora le catene discendenti che iniziano da x sono tutte finite, ma ciò non significa che le loro lunghezze siano necessariamente limitate. Si consideri il seguente esempio: Sia X l'unione degli interi positivi con un nuovo elemento ω maggiore di qualsiasi intero. Allora X è un insieme ben fondato, ma esistono catene discendenti che iniziano da ω di lunghezza arbitraria grande (finita); la catena ω, n − 1, n − 2, ..., 2, 1 ha lunghezza n per ogni n.

Il lemma di collasso di Mostowski implica che l'appartenenza agli insiemi è un universale tra le relazioni estensionali ben fondate: per ogni relazione ben fondata di tipo insiemistico R su una classe X che è estensionale, esiste una classe C tale che ( X , R ) è isomorfo a (C , ∈).

## Riflessività

Una relazione R si dice riflessiva se a R a è vero per ogni a nel dominio della relazione. Ogni relazione riflessiva su un dominio non vuoto ha catene discendenti infinite, perché ogni sequenza costante è una catena discendente. Ad esempio, nei numeri naturali con il loro solito ordine ≤, abbiamo $1\geq 1\geq 1\geq \cdots .$Per evitare queste banali sequenze discendenti, quando si lavora con un ordine parziale ≤, è comune applicare la definizione di relazione ben fondata (forse implicitamente) alla relazione alternativa < definita tale che a < b se e solo se a ≤ b e a ≠ b. Più in generale, quando si lavora con un preordine ≤, è comune utilizzare la relazione < definita tale che a < b se e solo se a ≤ b e b ≰ a. Nel contesto dei numeri naturali, ciò significa che viene utilizzata la relazione <, che è ben fondata, al posto della relazione ≤, che non lo è. In alcuni testi, la definizione di relazione ben fondata viene modificata rispetto alla definizione precedente per includere queste convenzioni.

