Ver o código fonte de «Relación ben fundada»

{{stack|{{Binary relations}}}}
En [[matemáticas]], unha [[relación binaria]] {{Mvar|R}} chámase '''ben fundada''' <ref>vexa a definición 6.21 en {{cite book|last1=Zaring W.M.|first1= G. Takeuti|title=Introduction to axiomatic set theory|date=1971|publisher=Springer-Verlag|location=New York|isbn=0387900241|edition=2nd, rev.}}</ref> nun [[conxunto]] ou, máis xeralmente, nunha [[clase (teoría de conxuntos)|clase]] {{Mvar|X}} se todo [[subconxunto]] [[Conxunto baleiro|non baleiro]] {{Math|''S'' ⊆ ''X''}} ten un [[Elemento maximal e minimal|elemento mínimal]] con respecto a {{Mvar|R}}; é dicir, existe un {{Math|''m'' ∈ ''S''}} tal que, para todo {{Math|''s'' ∈ ''S''}}, non se ten {{Math|''s'' ''R'' ''m''}}. Noutras palabras, unha relación está ben fundada se: <math display="block">(\forall S \subseteq X)\; [S \neq \varnothing \implies (\exists m \in S) (\forall s \in S) \lnot(s \mathrel{R} m)].</math> Algúns autores inclúen unha condición adicional de que {{Mvar|R}} sexa [[Relación binaria#Outros tipos de relación|tipo conxunto]], é dicir, que os elementos menores que calquera elemento dado formen un conxunto.

De forma equivalente, asumindo o [[Axioma de elección dependente|axioma de escolla dependente]], unha relación está ben fundamentada cando non contén [[Orde total|cadeas descendentes infinitas]], o que se pode demostrar cando non hai unha secuencia infinita {{Math|''x''<sub>0</sub>, ''x''<sub>1</sub>, ''x''<sub>2</sub>, ...}} de elementos de {{Mvar|X}} tales que {{Math|''x''<sub>''n''+1</sub> ''R'' ''x''<sub>n</sub>}} para todo número natural {{Mvar|n}}.<ref>{{cite web |title=Infinite Sequence Property of Strictly Well-Founded Relation |url=https://proofwiki.org/wiki/Infinite_Sequence_Property_of_Strictly_Well-Founded_Relation |website=ProofWiki |access-date=10 de maio de 2021}}</ref><ref>{{cite book |last1=Fraisse |first1=R. |title=Theory of Relations, Volume 145 - 1st Edition |date=15 de decembro de 2000 |publisher=Elsevier |isbn=9780444505422 |page=46 |edition=1st |url=https://www.elsevier.com/books/theory-of-relations/fraisse/978-0-444-50542-2 |access-date=20 de febreiro de 2019}}</ref>

Na [[teoría da orde]], unha [[Conxunto parcialmente ordenado|orde parcial]] chámase ben fundada se a [[Conxunto parcialmente ordenado|orde estrita]] correspondente é unha relación ben fundada. Se a orde é unha [[orde total]], denomínase [[Relación ben ordenada|ben ordenada]].

Na [[teoría de conxuntos]], un conxunto {{Mvar|x}} chámase '''conxunto ben fundado''' se a relación [[Elemento (matemáticas)|de pertenza do conxunto]] está ben fundada no [[Peche transitivo (conxunto)|peche transitivo]] de {{Mvar|x}}. 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 {{Mvar|R}} é '''inversa ben fundada''', '''ben fundada para arriba''' ou '''noetheriana''' en {{Mvar|X}}, se a [[relación inversa]] {{Math|''R''<sup>−1</sup>}} está ben fundada en {{Mvar|X}}. Neste caso tamén se di que {{Mvar|R}} 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 [[Inducción transfinita|indución transfinita]]: se ({{Math|''X'', ''R''}}) é unha relación ben fundada, {{Math|''P''(''x'')}} é algunha propiedade dos elementos de {{Mvar|X}}, e queremos demostrar que

: {{Math|''P''(''x'')}} cúmprese para todos os elementos {{Mvar|x}} de {{Mvar|X}},

abonda con demostrar que:

: Se {{Mvar|x}} é un elemento de {{Mvar|X}} e {{Math|''P''(''y'')}} é verdadeira para todo {{Mvar|y}} tal que {{Math|''y'' ''R'' ''x''}}, entón {{Math|''P''(''x'')}} tamén debe ser verdadeira.

É dicir, <math display="block">(\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).</math>

A indución ben fundada chámase ás veces indución noetheriana, <ref>Bourbaki, N. (1972) ''Elements of mathematics. Commutative algebra'', Addison-Wesley.</ref> debido a [[Emmy Noether]].

Ao igual que a indución, as relacións ben fundadas tamén admiten a construción de obxectos mediante [[Recursividade transfinita|recursión transfinita]]. Sexa {{Math|(''X'', ''R'')}} unha relación ben fundada [[Relación binaria|tipo conxunto]] e {{Mvar|F}} unha función que asigna un obxecto {{Math|''F''(''x'', ''g'')}} a cada par dun elemento {{Math|''x'' ∈ ''X''}} e unha función {{Mvar|g}} no [[segmento inicial]] {{Math|{{(}}''y'': ''y'' ''R'' ''x''{{)}}}} de {{Mvar|X}}. Entón hai unha función única {{Mvar|G}} tal que para cada {{Math|''x'' ∈ ''X''}}, <math display="block">G(x) = F\left(x, G\vert_{\left\{y:\, y\mathrel{R}x\right\}}\right).</math>

É dicir, se queremos construír unha función {{Mvar|G}} sobre {{Mvar|X}}, podemos definir {{Math|''G''(''x'')}} usando os valores de {{Math|''G''(''y'')}} para {{Math|''y'' ''R'' ''x''}}.

Como exemplo, considere a relación ben fundamentada {{Math|('''N''', ''S'')}}, onde {{Math|'''N'''}} é o conxunto de todos [[Número natural|os números naturais]] e {{Mvar|S}} é o grafo da función sucesora {{Math|''x'' ↦ ''x''+1}}. Entón a indución en {{Mvar|S}} é a [[indución matemática]] habitual, e a recursión en {{Mvar|S}} dá a [[Funcións recursivas primitivas|recursividade primitiva]]. Se consideramos a relación de orde {{Math|('''N''', <)}}, obtemos [[Indución matemática|a indución completa]] e [[Recurso do curso de valores|a recursión global]]. A afirmación de que {{Math|('''N''', <)}} 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 [[Número ordinal|os números ordinais]], a técnica chámase [[Inducción transfinita|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 (indución epsilon)]].

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

* Os [[Número enteiro|enteiros]] positivos {{Math|{{(}}1, 2, 3, ...{{)}}}}, coa orde definida por {{Math|''a'' < ''b''}} [[se e só se]] {{Mvar|a}} [[Divisor|divide]] {{Mvar|b}} e {{Math|''a'' ≠ ''b''}} .
* O conxunto de todas as cadeas finitas sobre un alfabeto fixo, coa orde definida por {{Math|''s'' < ''t''}} se e só se {{Mvar|s}} é unha subcadea propia de {{Mvar|t}}.
* O conxunto {{Math|'''N''' × '''N'''}} de [[Produto cartesiano|pares]] de [[Número natural|números naturais]], ordenados por {{Math|(''n''<sub>1</sub>, ''n''<sub>2</sub>) < (''m''<sub>1</sub>, ''m''<sub>2</sub>)}} se e só se {{Math|''n''<sub>1</sub> < ''m''<sub>1</sub>}} e {{Math|''n''<sub>2</sub> < ''m''<sub>2</sub>}}.
* Toda clase cuxos elementos son conxuntos, coa relación ∈ ("é un elemento de"). Este é o [[Axioma de regularidade|axioma da regularidade]].
* Os nós de calquera [[Gráfico acíclico dirixido|grafo acíclico finito dirixido]], coa relación {{Mvar|R}} definida de tal xeito que {{Math|''a'' ''R'' ''b''}} se e só se hai unha aresta de {{Mvar|a}} a {{Mvar|b}}.

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

* Os enteiros negativos {{Math|{{(}}−1, −2, −3, ...{{)}}}}, 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 ([[Orde lexicográfica|lexicográfica]]), xa que a secuencia {{Nowrap|"B" > "AB" > "AAB" > "AAAB" > ...}} é 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úmero racional|números racionais]] (ou [[Número real|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 {{Math|(''X'', <)}} é unha relación ben fundada e {{Mvar|x}} é un elemento de {{Mvar|X}}, entón as cadeas descendentes que comezan en {{Mvar|x}} son todas finitas, mais isto non significa que as súas lonxitudes estean necesariamente limitadas. Considere o seguinte exemplo: Sexa {{Mvar|X}} a unión dos enteiros positivos cun novo elemento ω que é maior que calquera número enteiro. Entón {{Mvar|X}} é un conxunto ben fundado, mais hai cadeas descendentes que comezan en ω de gran lonxitude (finita) arbitraria; a cadea {{Math|ω, ''n'' − 1, ''n'' − 2, ..., 2, 1}} {{Math|ω, ''n'' − 1, ''n'' − 2, ..., 2, 1}} ten lonxitude {{Mvar|n}} para calquera {{Mvar|n}} .

O [[Colapso de Mostowski|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 {{Mvar|R}} nunha clase {{Mvar|X}} que é extensional, existe unha clase {{Mvar|C}} tal que {{Math|(''X'', ''R'')}} é isomorfa a {{Math|(''C'', ∈)}}.

== Reflexividade ==
Dise que unha relación {{Mvar|R}} é [[Relación reflexiva|reflexiva]] se {{Math|''a'' ''R'' ''a''}} vale para todo {{Mvar|a}} 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 {{Nowrap|1 ≥ 1 ≥ 1 ≥ ...}} . 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 {{Math|''a'' < ''b''}} se e só se {{Math|''a'' ≤ ''b''}} e {{Math|''a'' ≠ ''b''}}. De xeito máis xeral, cando se traballa cunha [[preorde]] ≤, é común usar a relación < definida de tal xeito que {{Math|''a'' < ''b''}} se e só se {{Math|''a'' ≤ ''b''}} e {{Math|''b'' ≰ ''a''}}. 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 ==
{{reflist|30em}} 

== Véxase tamén ==

=== Bibliografía ===
* Just, Winfried and Weese, Martin (1998) ''Discovering Modern Set Theory. I'', [[American Mathematical Society]] {{isbn|0-8218-0266-6}}.
* [[Karel Hrbáček]] & [[Thomas Jech]] (1999) ''Introduction to Set Theory'', 3rd edition, "Well-founded relations", pages 251–5, [[Marcel Dekker]] {{ISBN|0-8247-7915-0}}

=== Outros artigos ===
* [[Relación ben ordenada]].
* [[Orde total]].


{{control de autoridades}}
[[Categoría:Teoría da orde]]
[[Categoría:Wikipedia:Páxinas con traducións non revisadas]]