Relação bem-fundada: diferenças entre revisões

 

 

 

 

<center>

:<math>\forall S \exists m \forall s ((S \subseteq X \and S \neq \{\})</math> → <math>((m \in S\and s \in S) \and \neg (s \in m)))

</math>.

</center>

 

Equivalentemente, assumindo uma função de [[Axioma da escolha|escolha]] qualquer, uma relação será bem-fundada se e somente se essa relação não contiver cadeia [[Conjunto contável|descendente infinitamente enumerável]], isto é, se não existir uma seqüência ''x''₀, ''x''₁,... de elementos de ''X'', tal que ''x''_n+1''Rx''_n para todo número natural ''n''.

Na teoria das [[Relação de ordem|estruturas ordenadas]], uma [[ordem parcial]] é dita bem-fundada se a [http://en.wikipedia.org/wiki/Strict_order#Strict_and_non-strict_partial_orders ordem estrita] correspondente é uma [[relação]] bem-fundada. Se a ordem for uma [[Topologia da ordem|ordem total]], então ela é dita [http://www.cs.utexas.edu/users/moore/acl2/v2-9/WELL-FOUNDED-RELATION.html bem-ordenada].

Na [[teoria dos conjuntos]], um conjunto ''ß'' é dito um conjunto bem-fundado se a relação de [[ Conjunto|pertinência]] for bem-fundada no [http://en.wikipedia.org/wiki/Transitive_set fecho transitivo] de ''ß''. O axioma da regularidade, o qual é um dos axiomas de [[Axiomas de Zermelo-Fraenkel|Zermelo-Fraenkel]] na teoria dos conjuntos, afirma que todos os conjuntos são bem-fundados.

*O conjunto vazio é um conjunto bem-fundado;

*Toda coleção de conjuntos bem-fundados, é um conjunto bem-fundado;

==Indução e Recursão==

Se (''X'', ''R'') é uma relação binária bem-fundada e ''P''(''x'') é alguma propriedade dos elementos de ''X'', queremos mostrar que ''P''(''x'') vale para todos os elementos de ''X'', então é suficiente mostrar que:

Considerando a propriedade ''P'' como sendo "olhos claros" e a relação <math>yRx</math> significando "''y'' é pai de ''x''".

<center>

Se ''x'' é um elemento de ''X'' e ''P''(''y'') é verdadeiro para todo ''y'' tal que ''y'' se relaciona com ''x'' (<math>yRx</math>), então ''P''(''x'') deve ser também verdadeiro.

</center>

Talvez o significado considerado para a propriedade ''P'' e para a relação ''R'' não seja tão expressivo para este caso, pois se ''y'' for pai de ''x'', não necessariamente ''x'' terá olhos claros (como seu pai), mas há significado mais expressivo a ser considerado.

Relações bem-fundadas dão suporte não apenas à indução, mas também a construções de objetos por recursão transfinita. Seja (''X'', ''R'') uma relação bem-fundada conjuntista e ''F'' uma função que determina um objeto ''F''(''x'', ''g'') para cada <math>x \in X</math> e cada função parcial ''g'' em ''X''. Então existe uma única função ''G'' tal que para cada <math>x \in X</math>,

<center>

:<math>G(x)=F(x,G\vert_{\{y: y\,R\,x\}})</math> .

</center>

Isto é, se queremos construir uma função ''G'' em ''X'', podemos definir ''G''(''x'') usando os valores de ''G''(''y'') tais que <math>yRx</math>. Como um exemplo, consideremos a relação bem-fundada (<math>\mathbb{N}</math>,''S''), onde <math>\mathbb{N}</math> é o conjunto de todos os [[números naturais]] e ''S'' é o gráfico da função sucessor x->x+1. Então uma indução sobre ''S'' é a [[indução]] matemática usual e a [[recursão]] em ''S'' se trata da recursão primitiva. Se considerarmos a [[relação de ordem]] (<math>\mathbb{N}</math>,<), obtemos a indução completa e a recursão sobre curso de valores. A asserção de que (<math>\mathbb{N}</math>,<) é bem-fundada é também conhecida como [[Princípio da boa-ordenação|princípio da boa ordenação]].

Existem outros casos especiais de indução bem-fundada. Quando a relação bem-fundada é ordenação usual na classe de todos os [[números ordinais]], a técnica é chamada de [[Indução matemática|indução transfinita]]; quando o conjunto bem-fundado é um conjunto de estruturas de dados recursivamente definidas, a técnica é chamada de [[indução estrutural]] (método de demonstração em que a proposição vale para todas as estruturas minimais, e que se valer para as subestruturas de uma determinada estrutura ''S'', então deverá valer para ''S'' também). Quando a relação bem-fundada é pertinência de conjuntos na na classe universal, a técnica é conhecida como ∈ - [[indução]].

 

== Exemplos ==

Relações bem-fundadas não totalmente ordenadas:

*Os [[inteiros]] (<math>\mathbb{Z}</math>) positivos {1,2,3...} com a ordem definida por ''<math>a<b</math>'' [[se e somente se]] ''a'' [[divisor|divide]] ''b'' e ''a'' &ne; ''b''.

*O conjunto de todas as [[Cadeia de caracteres|strings]] finitas sobre um alfabeto fixo, com a ordem definida por ''<math>s<t</math>'' se e somente se ''s'' é uma substring própria de ''t''.

às vezes implicitamente, a relação alternativa ''R''' definida de tal modo que <math>aR'b</math> se apenas se <math>aRb</math> e ''a'' &ne; ''b''. No contexto dos números naturais isso significa que a relação <, que é bem-fundada, é usada em vez da relação ≤, que [http://en.wikipedia.org/wiki/Non-well-founded_set_theory não é bem-fundada]. Em alguns textos, a definição de uma relação bem-ordenada é uma versão modificada da definição acima, proposta com o intuito de incluir esta convenção.

 

 

 

 

 

 

 

[[Categoria:Teoria dos conjuntos|Relacao bem-fundada]]

[[Categoria:Álgebra|Relacao bem-fundada]]

[[Categoria:Lógica|Relacao bem-fundada]]