Em matemática, uma relação binária é 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 alguns contextos, ainda, pode ser considerado que tal par (s,m) só pode estar em R caso s seja o próprio m, isto é, o único elemento anterior ao minimal, só pode ser ele mesmo. Mas tal nuance deverá estar explicitada no dado contexto.)
Formalizando com a lógica de predicados, temos:
Isto quando tratamos da relação de pertinência em teorias de conjuntos bem-fundados.
Para uma relação R qualquer, equivalentemente podemos denotar, como o descrito no primeiro parágrafo deste artigo: , onde representa o conjunto (ou classe) das partes de X, caso X o admita (como não é o caso de classes próprias).
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 sequência x0, x1,... de elementos de X, tal que .
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 na teoria dos conjuntos de Zermelo-Fraenkel, afirmando 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 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 (), 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 e cada função parcial g em X. Então existe uma única função G tal que para cada
Isto é, se queremos construir uma função G em X, podemos definir G(x) usando os valores de G(y) tais que Como um exemplo, consideremos a relação bem-fundada ( S), onde é 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 ( <), obtemos a indução completa e a recursão sobre curso de valores. A asserção de que ( <) é 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 mínimas, 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 classe universal, a técnica é conhecida como ∈ - indução.
Exemplos Relações bem-fundadas não totalmente ordenadas:
Os inteiros () positivos {1,2,3...} com a ordem definida por 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 se e somente se s é uma substring própria de t. O conjunto x de pares de números naturais, ordenados por (n1,n2)<(m1,m2) se e somente se n1<m1 e n2<m2. O conjunto das expressões regulares sobre um alfabeto fixo, com a ordem definida por 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 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 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 é 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 sequê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 sequê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 se apenas se 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.
Relacao bem-fundada Relacao bem-fundada Relacao bem-fundada