Tukukkk

Este artigo ou secção contém fontes no fim do texto, mas que não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. (desde junho de 2011) Por favor, melhore este artigo inserindo fontes no corpo do texto quando necessário.

A Wikipédia possui o: Portal da Matemática

Em matemática, uma relação binária R é uma relação bem-fundada numa classe X, se e somente se, todo subconjunto não vazio de X, tiver um elemento R -minimal; ou seja, para todo subconjunto não vazio S de X, existe um elemento m de S tal que para todo elemento s de S, o par (s,m) não está em R.

Em outras palavras, todo subconjunto não vazio de X possui um elemento m tal que para todo s, s∉m.{displaystyle snot in m.} Desta forma, evitamos situações de loop.

Formalizando com a lógica de predicados, temos:

∀S∃m∀s((S⊆X∧S≠{}){displaystyle forall Sexists mforall s((Ssubseteq Xland Sneq {})}

((m∈S∧s∈S)∧¬(s∈m))).{displaystyle ((min Sland sin S)land neg (sin m))).}

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

Na teoria das estruturas ordenadas, uma ordem parcial é dita bem-fundada se a ordem estrita correspondente é uma relação bem-fundada. Se a ordem for uma ordem total, então ela é dita bem-ordenada.

Na teoria dos conjuntos, um conjunto ß é dito um conjunto bem-fundado se a relação de pertinência for bem-fundada no fecho transitivo de ß. O axioma da regularidade, o qual é um dos axiomas de Zermelo-Fraenkel na teoria dos conjuntos, afirma que todos os conjuntos são bem-fundados.

Algumas definições |

• O conjunto vazio é um conjunto bem-fundado;


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


• Se todo elemento de x é bem-fundado, então x é bem-fundado;


• Todo elemento de um conjunto bem-fundado é bem-fundado;


• Todo subconjunto de um conjunto bem-fundado é bem-fundado.

Note que para uma estrutura binária finita ser bem-fundada é necessário e suficiente que essa estrutura não tenha loop, ou seja, um conjunto, por exemplo, em que seu subconjunto é ele mesmo.

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 yRx{displaystyle yRx} significando "y é pai de x".

Se x é um elemento de X e P(y) é verdadeiro para todo y tal que y se relaciona com x (yRx{displaystyle yRx}), então P(x) deve ser também verdadeiro.

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 x∈X{displaystyle xin X} e cada função parcial g em X. Então existe uma única função G tal que para cada x∈X,{displaystyle xin X,}

G(x)=F(x,G|{y:yRx}).{displaystyle G(x)=F(x,Gvert _{{y:y,R,x}}).}

Isto é, se queremos construir uma função G em X, podemos definir G(x) usando os valores de G(y) tais que yRx.{displaystyle yRx.} Como um exemplo, consideremos a relação bem-fundada (N,{displaystyle mathbb {N} ,} S), onde N{displaystyle mathbb {N} } é 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 (N,{displaystyle mathbb {N} ,} <), obtemos a indução completa e a recursão sobre curso de valores. A asserção de que (N,{displaystyle mathbb {N} ,} <) é bem-fundada é também conhecida como 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 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 (Z{displaystyle mathbb {Z} }) positivos {1,2,3...} com a ordem definida por a<b{displaystyle a<b} se e somente se a divide b e a ≠ b.


• O conjunto de todas as strings finitas sobre um alfabeto fixo, com a ordem definida por s<t{displaystyle s<t} se e somente se s é uma substring própria de t.


• O conjunto N{displaystyle mathbb {N} }xN{displaystyle mathbb {N} } de pares de números naturais, ordenados por (n₁,n₂)<(m₁,m₂) se e somente se n₁<m₁ e n₂<m₂.


• O conjunto das expressões regulares sobre um alfabeto fixo, com a ordem definida por s<t{displaystyle s<t} se e somente se s é uma sub-expressão própria de t.


• Qualquer classe cujos elementos são conjuntos, com a relação R definida, tal que aRb{displaystyle aRb} se e somente se a é um elemento de b (assumindo o axioma da regularidade).


• Os nós de qualquer grafo finito acíclico direcionado com a relação R definida de tal modo que aRb{displaystyle aRb} se e somente se existe uma aresta de a até b.

Outras propriedades |

Se (X, <) é uma relação bem-fundada e x é um elemento de X, então as cadeias descendentes começando em x são todas finitas, mas isso não significa que seus comprimentos serão necessariamente limitados. Considere o seguinte exemplo. Seja X a união dos inteiros positivos com um novo elemento ω, o qual é maior do que qualquer inteiro. Então X é um conjunto bem-fundado, mas existem cadeias descendentes começando em ω de comprimento (finito) arbitrariamente grande; a cadeia ω, n-1, n-2,... 2,1 tem comprimento n para qualquer n.

O lema de colapso de Mostowski implica que a pertinência entre conjuntos é uma relação bem-fundada universal: para qualquer relação bem-fundada R conjuntista sobre uma classe X, existe uma classe C tal que (X, R) é isomorfo a (C, E).

Reflexividade |

Uma relação R é dita reflexiva se aRa{displaystyle aRa} é válida para todo a no domínio da relação. Toda relação reflexiva sobre um domínio não vazio tem cadeia descendentes infinitas, porque qualquer seqüência constante é uma cadeia descendente. Por exemplo, para os números naturais com a sua condição de ordem usual ≤, temos 1 ≤ 1 ≤ 1 ≤... . Para evitar estas seqüências descendentes triviais, quando estamos trabalhando com a relação reflexiva R é comum usar,
às vezes implicitamente, a relação alternativa R' definida de tal modo que aR′b{displaystyle aR'b} se apenas se aRb{displaystyle aRb} e a ≠ b. No contexto dos números naturais isso significa que a relação <, que é bem-fundada, é usada em vez da relação ≤, que 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.

Ver também |

• Relação transitiva


• Relação binária


• Relação de ordem


• Relação de equivalência


• Relação composta


• Relação inversa

Referências |

• JONES, Roger Bishop, Dec.2006. Well Founded Relations
  


• TAYLO, Paul. Practical Foundations of Mathematics
  


• LARRECQ, Jean Goubault. Well-Founded Recursive Relations
  


• CONIGLIO, Marcelo Esteban.Teoria axiomática dos conjuntos. Universidade estadual de Campinas-SP, Brasil.


• FORSTER, Thomas.Logic, Computation and Set Theory. 14 jan. 2002.