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