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 te un element minimal respecte de R; Això és, per cada subconjunt no buit S d'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 d'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 d'x. En aquest cas R satisfà també la condició de cadena ascendent.

Inducció i recursió

Una raó important per que 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 volem 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 tots els y tals que y R x, llavors P(x) ha de ser veritat. És a dir: $\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} d'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 volem construir una funció G en X, hem de definir G(x) usant valors de G(y) per y R x.

Com exemple, considerem la relació ben fundada (N, S), on 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 es la demostració per inducció habitual, i la recursió en S dóna la recursió primitiva. Si considerem la relació d'ordre (N,<), obtenim la inducció completa, i la Course-of-values_recursion. La sentència que diu que (N.<) està ben fonamentat 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 es un conjunt d'estructures de dades definides recursivament, la tècnica s'anomena com inducció estructural. Quan la relació ben fonamentada és la prova d'element d'una classe universal, la tècnica s'anomena inducció-∈.

Exemples

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 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 son:

• els enters negatius {-1, -2, -3, ...}, amb l'orde habitual, ja que cap conjunt sense límit no te ú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 te mínim.

Altres propietats

Si (X, <) és una relació ben fonamentada, i x és un element d'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 l'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 te 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, s'usa en lloc 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.