Relación ben fundada

En matemáticas, unha relación binaria  chámase **ben fundada**  nun conxunto ou, máis xeralmente, nunha clase  se todo subconxunto non baleiro  ten un elemento mínimal con respecto a ; é dicir, existe un  tal que, para todo , non se ten . Noutras palabras, unha relación está ben fundada se: (\forall S \subseteq X)\; [S \neq \varnothing \implies (\exists m \in S) (\forall s \in S) \lnot(s \mathrel{R} m)]. Algúns autores inclúen unha condición adicional de que  sexa tipo conxunto, é dicir, que os elementos menores que calquera elemento dado formen un conxunto.

De forma equivalente, asumindo o axioma de escolla dependente, unha relación está ben fundamentada cando non contén cadeas descendentes infinitas, o que se pode demostrar cando non hai unha secuencia infinita  de elementos de  tales que  para todo número natural .

Na teoría da orde, unha orde parcial chámase ben fundada se a orde estrita correspondente é unha relación ben fundada. Se a orde é unha orde total, denomínase ben ordenada.

Na teoría de conxuntos, un conxunto  chámase **conxunto ben fundado** se a relación de pertenza do conxunto está ben fundada no peche transitivo de . O axioma de regularidade, que é un dos axiomas da teoría de conxuntos de Zermelo-Fraenkel, afirma que todos os conxuntos están ben fundados.

Unha relación  é **inversa ben fundada**, **ben fundada para arriba** ou **noetheriana** en , se a relación inversa  está ben fundada en . Neste caso tamén se di que  satisfai a condición de cadea ascendente.

## Indución e recursividade 
Unha razón importante pola que as relacións ben fundadas son interesantes é porque se pode usar nelas unha versión da indución transfinita: se () é unha relación ben fundada,  é algunha propiedade dos elementos de , e queremos demostrar que

:  cúmprese para todos os elementos  de ,

abonda con demostrar que:

: Se  é un elemento de  e  é verdadeira para todo  tal que , entón  tamén debe ser verdadeira.

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

A indución ben fundada chámase ás veces indución noetheriana,  debido a Emmy Noether.

Ao igual que a indución, as relacións ben fundadas tamén admiten a construción de obxectos mediante recursión transfinita. Sexa  unha relación ben fundada tipo conxunto e  unha función que asigna un obxecto  a cada par dun elemento  e unha función  no segmento inicial  de . Entón hai unha función única  tal que para cada , G(x) = F\left(x, G\vert_{\left\{y:\, y\mathrel{R}x\right\}}\right).

É dicir, se queremos construír unha función  sobre , podemos definir  usando os valores de  para .

Como exemplo, considere a relación ben fundamentada , onde  é o conxunto de todos os números naturais e  é o grafo da función sucesora . Entón a indución en  é a indución matemática habitual, e a recursión en  dá a recursividade primitiva. Se consideramos a relación de orde , obtemos a indución completa e a recursión global. A afirmación de que  está ben fundada tamén se coñece como principio da boa ordenación .

Cando a relación ben fundada é a orde habitual na clase de todos os números ordinais, a técnica chámase indución transfinita. Cando o conxunto ben fundado é un conxunto de estruturas de datos definidas recursivamente, a técnica chámase indución estrutural. Cando a relación ben fundada  pertence á clase universal, a técnica coñécese como ∈-indución (indución epsilon).

## Exemplos 
As relacións ben fundadas que non son totalmente ordenadas inclúen:

* Os enteiros positivos , coa orde definida por  se e só se  divide  e  .
* O conxunto de todas as cadeas finitas sobre un alfabeto fixo, coa orde definida por  se e só se  é unha subcadea propia de .
* O conxunto  de pares de números naturais, ordenados por  se e só se  e .
* Toda clase cuxos elementos son conxuntos, coa relación ∈ ("é un elemento de"). Este é o axioma da regularidade.
* Os nós de calquera grafo acíclico finito dirixido, coa relación  definida de tal xeito que  se e só se hai unha aresta de  a .

Exemplos de relacións que non están ben fundadas inclúen:

* Os enteiros negativos , coa orde habitual, xa que calquera subconxunto non limitado non ten menor elemento.
* O conxunto de cadeas sobre un alfabeto finito con máis dun elemento, baixo a orde habitual (lexicográfica), xa que a secuencia  é unha cadea descendente infinita. Esta relación non está ben fundada aínda que todo o conxunto teña un elemento mínimo, é dicir, a cadea baleira.
* O conxunto de números racionais (ou reais) non negativos baixo a orde estándar, xa que, por exemplo, o subconxunto de racionais (ou reais) positivos carece dun mínimo.

## Outras propiedades 
Se  é unha relación ben fundada e  é un elemento de , entón as cadeas descendentes que comezan en  son todas finitas, mais isto non significa que as súas lonxitudes estean necesariamente limitadas. Considere o seguinte exemplo: Sexa  a unión dos enteiros positivos cun novo elemento ω que é maior que calquera número enteiro. Entón  é un conxunto ben fundado, mais hai cadeas descendentes que comezan en ω de gran lonxitude (finita) arbitraria; a cadea   ten lonxitude  para calquera  .

O lema do colapso de Mostowski implica que a pertenza do conxunto é un universal entre as relacións de extensión ben fundadas: para calquera relación ben fundada de tipo conxunto  nunha clase  que é extensional, existe unha clase  tal que  é isomorfa a .

## Reflexividade 
Dise que unha relación  é reflexiva se  vale para todo  no dominio da relación. Toda relación reflexiva nun dominio non baleiro ten cadeas descendentes infinitas, porque calquera secuencia constante é unha cadea descendente. Por exemplo, nos números naturais coa súa orde habitual ≤, temos  . Para evitar estas secuencias descendentes triviais, cando se traballa cunha orde parcial ≤, é común aplicar a definición de fundamento (quizais implícitamente) á relación alternativa < definida de tal xeito que  se e só se  e . De xeito máis xeral, cando se traballa cunha preorde ≤, é común usar a relación < definida de tal xeito que  se e só se  e . No contexto dos números naturais, isto significa que se usa a relación <, que está ben fundada, en lugar da relación ≤, que non o é. Nalgúns textos, a definición dunha relación ben fundada múdase desde a definición deste artigo para incluír estas convencións.
## Notas 
## Véxase tamén 
### Bibliografía 
* Just, Winfried and Weese, Martin (1998) *Discovering Modern Set Theory. I*, American Mathematical Society .
* Karel Hrbáček & Thomas Jech (1999) *Introduction to Set Theory*, 3rd edition, "Well-founded relations", pages 251–5, Marcel Dekker 

### Outros artigos 
* Relación ben ordenada.
* Orde total.