Relació ben fonamentada

En matemàtiques, una relació binaria R està ben fonamentada en una classe X si, i només si, cada subconjunt no buit d'X té un element minimal respecte de R. Això és, per cada subconjunt no buit S de X, existeix un element m de S tal que per cada element s de S, la parella (s,m) no pertany a R:

$\forall S\subseteq X\;\,(S\neq \varnothing \to \exists m\in S\;\;\forall s\in S\;\,(s,m)\notin R)$

Equivalentment, assumint una elecció, una relació està ben fonamentada si, i només si, no conté cap cadena descendent infinita: això és, no existeix cap seqüència infinita x₀, x₁, x₂, ... d'elements de X tal que x_n+1 R x_n per cada nombre natural n.

En Teoria de l'ordre, un conjunt parcialment ordenat està ben fonamentada si l'orde estricte corresponent és una relació ben fonamentada. Si l'orde és un ordre total llavors s'anomena conjunt ben ordenat.

En Teoria de conjunts, un conjunt x s'anomena conjunt ben fonamentat si la relació de ser membre està ben formada per la clausura transitiva de x. En aquest cas R satisfà també la condició de cadena ascendent.

Inducció i recursió

Una raó important per la qual les relacions ben fundades són interessants és perquè es pot usar en elles una versió de la inducció transfinita: si (X,R) és una relació ben formada i P(x) és una propietat dels elements d'X i es vol provar que P (x) és vàlida per tots els elements d'X, és suficient de provar que:

Si x és un element d'X i P(y) és certa per a tots els y tals que y R x, llavors P(x) ha de ser veritat. Resumint: $\forall x\in X((\forall y\in X(y\,R\,x\to P(y)))\to P(x))$.

La inducció ben formada també s'anomena Inducció noetheriana, per Emmy Noether.

En paral·lel a la inducció, les relacions ben fundades també suporten la construcció d'objectes mitjançant la recursió transfinita. Sigui (X,R) una relació ben fundada set-like, i F una funció que assigna un objecte F(x, g) a cada parell d'elements x ∈ X i una funció g en el segment inicial {y: y R x} de X. Llavors hi ha una única funció G tal que per cada x ∈ X,

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

Això és, si es vol construir una funció G en X, cal definir G(x) usant valors de G(y) per y R x.

Com a exemple, es considerarà la relació ben fundada (N, S), en què N és el conjunt de tots els nombre naturals, i S és el graf de la funció de successió x → x + 1. Llavors la inducció en S és la demostració per inducció habitual, i la recursió en S dona la recursió primitiva. Si es considera la relació d'ordre (N,<), s'obté la inducció completa, i la Course-of-values recursion. La sentència que diu que (N.<) està ben fonamentat, això es coneix també com principi de bona ordenació.

Existeixen altres casos especials interessants d'inducció ben fonamentada. Quan la relació ben fonamentada és la forma habitual d'ordenació en una classe de tots els nombres ordinals, la tècnica s'anomena inducció transfinita. Quan el conjunt ben fonamentat és un conjunt d'estructures de dades definides recursivament, la tècnica s'anomena inducció estructural. Quan la relació ben fonamentada és la prova d'element d'una classe universal, la tècnica s'anomena inducció-∈.

Exemples

Les relacions ben formades que no estan totalment ordenades són:

• Els nombres enters positius {1,2,3...}, amb l'ordre definit per a < b si i només si a divideix b ia ≠ b.
• El conjunt de totes les cadenes finites d'un alfabet fixat, amb l'ordre definit com a s < t si, i només si, s és una sub-cadena de t.
• El conjunt N × N de parelles de nombres naturals, ordenat tal que (n₁, n₂) < (m₁, m₂) si, i només si, n₁ < m₁ i n₂ < m₂.
• El conjunt de totes les expressions regulars sobre un alfabet fixat, amb l'orde definit per s < t si, i només si, s és una subexpressió de t.
• Qualsevol classe els elements de la qual siguin conjunts, amb la relació $\in$ (és un element de). Aquest és l'axioma de regularitat.
• Els nodes de qualsevol graf dirigit acíclic amb la relació R definida tal que a R b si, i només si, existeix una aresta d'a cap a b.

Exemples de relacions que no estan ben fonamentades són:

• Els enters negatius {-1, -2, -3, ...}, amb l'orde habitual, ja que cap conjunt sense límit no té últim element.
• El conjunt de cadenes sobre un alfabet finit, sota l'ordre lexicogràfic habitual, ja que la seqüència "B" > "AB" > "AAB" > "AAAB" > … és una cadena descendent infinita.
• Els nombres racionals sota l'ordenació estàndard, ja que, per exemple, el conjunt de racionals positius no té mínim.

Altres propietats

Si (X, <) és una relació ben fonamentada, i x és un element de X, llavors les cadenes descendents començant per x són totes finites, tot i que això no vol dir que les seves longituds estiguin acotades. Considereu el següent exemple: sigui X la unió dels enters positius i un nou element ω, el qual és més gran que qualsevol altre enter. Llavors X és un conjunt ben fonamentat, però hi ha cadenes descendents començant a ω de longitud arbitràriament gran (finita): la cadena ω, n − 1, n − 2, ..., 2, 1 té longitud n per qualsevol n.

Reflexió

Una relació R es diu que és reflexiva si a R a existeix per cada a en el domini de la relació. Cada relació reflexiva en un domini no buit té infinites cadenes descendents, perquè qualsevol seqüència constant és una cadena descendent. Per exemple, en els nombres naturals amb el seu ordre habitual ≤, tenim que $1\geq 1\geq 1\geq \cdots$. Per evitar aquestes seqüències descendents trivials, quan es treballa amb una relació reflexiva R és habitual fer servir (potser implícitament) la relació alternativa R'' definida de manera que a R′ b si, i només si, a R b i a ≠ b. En el context dels nombres naturals, això significa que la relació <, que està ben fonamentada, es fa servir en comptes de la relació ≤, que no ho és.

Referències

• Just, Winfried i Weese, Martin, Discovering Modern Set theory. I, American Mathematical Society (1998) ISBN 0-8218-0266-6.