Relación ben fundada

De testwiki
Saltar á navegación Saltar á procura

Modelo:Stack En matemáticas, unha relación binaria Modelo:Mvar chámase ben fundada [1] nun conxunto ou, máis xeralmente, nunha clase Modelo:Mvar se todo subconxunto non baleiro Modelo:Math ten un elemento mínimal con respecto a Modelo:Mvar; é dicir, existe un Modelo:Math tal que, para todo Modelo:Math, non se ten Modelo:Math. Noutras palabras, unha relación está ben fundada se: (∀S⊆X)[S≠∅⟹(∃m∈S)(∀s∈S)¬(sRm)]. Algúns autores inclúen unha condición adicional de que Modelo:Mvar 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 Modelo:Math de elementos de Modelo:Mvar tales que Modelo:Math para todo número natural Modelo:Mvar.[2][3]

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 Modelo:Mvar chámase conxunto ben fundado se a relación de pertenza do conxunto está ben fundada no peche transitivo de Modelo:Mvar. 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 Modelo:Mvar é inversa ben fundada, ben fundada para arriba ou noetheriana en Modelo:Mvar, se a relación inversa Modelo:Math está ben fundada en Modelo:Mvar. Neste caso tamén se di que Modelo:Mvar 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 (Modelo:Math) é unha relación ben fundada, Modelo:Math é algunha propiedade dos elementos de Modelo:Mvar, e queremos demostrar que

Modelo:Math cúmprese para todos os elementos Modelo:Mvar de Modelo:Mvar,

abonda con demostrar que:

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

É dicir, (∀x∈X)[(∀y∈X)[yRx⟹P(y)]⟹P(x)]implica(∀x∈X)P(x).

A indución ben fundada chámase ás veces indución noetheriana, [4] 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 Modelo:Math unha relación ben fundada tipo conxunto e Modelo:Mvar unha función que asigna un obxecto Modelo:Math a cada par dun elemento Modelo:Math e unha función Modelo:Mvar no segmento inicial Modelo:Math de Modelo:Mvar. Entón hai unha función única Modelo:Mvar tal que para cada Modelo:Math, G(x)=F(x,G|{y:yRx}).

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

Como exemplo, considere a relación ben fundamentada Modelo:Math, onde Modelo:Math é o conxunto de todos os números naturais e Modelo:Mvar é o grafo da función sucesora Modelo:Math. Entón a indución en Modelo:Mvar é a indución matemática habitual, e a recursión en Modelo:Mvar dá a recursividade primitiva. Se consideramos a relación de orde Modelo:Math, obtemos a indución completa e a recursión global. A afirmación de que Modelo:Math 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:

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

  • Os enteiros negativos Modelo:Math, 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 Modelo:Nowrap é 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 Modelo:Math é unha relación ben fundada e Modelo:Mvar é un elemento de Modelo:Mvar, entón as cadeas descendentes que comezan en Modelo:Mvar son todas finitas, mais isto non significa que as súas lonxitudes estean necesariamente limitadas. Considere o seguinte exemplo: Sexa Modelo:Mvar a unión dos enteiros positivos cun novo elemento ω que é maior que calquera número enteiro. Entón Modelo:Mvar é un conxunto ben fundado, mais hai cadeas descendentes que comezan en ω de gran lonxitude (finita) arbitraria; a cadea Modelo:Math Modelo:Math ten lonxitude Modelo:Mvar para calquera Modelo:Mvar .

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 Modelo:Mvar nunha clase Modelo:Mvar que é extensional, existe unha clase Modelo:Mvar tal que Modelo:Math é isomorfa a Modelo:Math.

Reflexividade

Dise que unha relación Modelo:Mvar é reflexiva se Modelo:Math vale para todo Modelo:Mvar 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 Modelo:Nowrap . 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 Modelo:Math se e só se Modelo:Math e Modelo:Math. De xeito máis xeral, cando se traballa cunha preorde ≤, é común usar a relación < definida de tal xeito que Modelo:Math se e só se Modelo:Math e Modelo:Math. 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

Modelo:Reflist

Véxase tamén

Bibliografía

Outros artigos


Modelo:Control de autoridades

  1. ↑ vexa a definición 6.21 en Modelo:Cite book
  2. ↑ Modelo:Cite web
  3. ↑ Modelo:Cite book
  4. ↑ Bourbaki, N. (1972) Elements of mathematics. Commutative algebra, Addison-Wesley.
Obtido de «https://gl.wiki.beta.math.wmflabs.org/w/index.php?title=Relación_ben_fundada&oldid=1630»