Relación ben fundada

En matemáticas, unha relación binaria  chámase ben fundada vexa a definición 6.21 en  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:  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, 

A indución ben fundada chámase ás veces indución noetheriana, Bourbaki, N. (1972) Elements of mathematics. Commutative algebra, Addison-Wesley. 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 , 

É 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.

Categoría:Teoría da orde
Categoría:Wikipedia:Páxinas con traducións non revisadas