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 minimale 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₀, x₁, x₂, ...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⁻¹ è 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₁, n₂) < (m₁, m₂ se e solo se n₁ < m₁ and n₂ < m₂;
• 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.

Bibliografia

• Just, Winfried e Weese, Martin (1998) Discovering Modern Set Theory. I, American Mathematical Society ISBN 0-8218-0266-6.
• Karel Hrbáček & Thomas Jech (1999) Introduction to Set Theory, 3rd edition, "Well-founded relations", pp. 251–5, Marcel Dekker ISBN 0-8247-7915-0