Relação bem-fundada: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
-código HTML obsoleto, format. <math> e pontuação, -predef's obsoletas +correções automáticas (v0.38/3.1.35) |
|||
Linha 3:
{{Portal-Matemática}}
Em [[matemática]], uma [[relação binária]] ''R'' é uma '''relação bem-fundada''' numa [[classe (teoria dos conjuntos)|classe]] ''X'', se e somente se, todo [[subconjunto]] não [[vazio]] de ''X'', tiver um [[elemento]] ''R'' -[[Elemento minimal|minimal]]; ou seja, para todo
Em outras palavras, todo subconjunto não vazio de ''X'' possui um elemento ''m'' tal que para todo ''s'', <math>s \not\in m.</math>
Formalizando com a lógica de predicados, temos:
.<
▲:<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)))
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''<sub>0</sub>, ''x''<sub>1</sub>,... de elementos de ''X'', tal que ''x''<sub>n+1</sub>''Rx''<sub>n</sub> para todo número natural ''n''.
Linha 20 ⟶ 17:
Na [[teoria dos conjuntos]], um conjunto ''ß'' é dito um conjunto bem-fundado se a relação de [[Conjunto|pertinência]] for bem-fundada no [[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.
== Algumas definições ==
* O conjunto vazio é um conjunto bem-fundado;
*
*
*
* Todo
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 <math>yRx</math> 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'' (<math>yRx</math>), 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 <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>
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>
▲:<math>G(x)=F(x,G\vert_{\{y: y\,R\,x\}})</math> .
▲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]].
Linha 53 ⟶ 45:
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'' ≠ ''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''.
* O conjunto <math>\mathbb{N}</math>x<math>\mathbb{N}</math> de [[Par ordenado|pares]] de [[números naturais]], ordenados por (''n<sub>1</sub>,n<sub>2</sub>'')<(''m<sub>1</sub>,m<sub>2</sub>'') se e somente se ''n<sub>1</sub><m<sub>1</sub>'' e ''n<sub>2</sub><m<sub>2</sub>''.
* O conjunto das [[expressões regulares]] sobre um alfabeto fixo, com a ordem definida por ''<math>s<t</math>'' [[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 <math>aRb</math> se e somente se ''a'' é um elemento de ''b'' (assumindo o [[axioma da regularidade]]).
* Os nós de qualquer grafo finito [[Árvore (grafo)|acíclico]] direcionado com a relação R definida de tal modo que <math>aRb</math> [[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''.
▲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'') é [[isomorfismo|isomorfo]] a (''C'', ''E'').
== Reflexividade ==
Uma relação ''R'' é dita [[Relação (matemática)|reflexiva]] se <math>aRa</math> é válida para todo ''a'' no domínio da relação. Toda relação
▲Uma relação ''R'' é dita [[Relação (matemática)|reflexiva]] se <math>aRa</math> é válida para todo ''a'' no domínio da relação. Toda relação [[Relação (matemática)|reflexiva]] sobre um [[funções|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 (matemática)|relação reflexiva]] ''R'' é comum usar,
à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'' ≠ ''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.
==
* [[Relação
* [[Relação
* [[Relação de
* [[Relação
* [[Relação
▲*[[Relação inversa]]
==Referências==▼
▲== Referências ==
* JONES, Roger Bishop, Dec.2006. [http://www.rbjones.com/rbjpub/pp/doc/t005.pdf Well Founded Relations]
* TAYLO, Paul. [http://www.cs.man.ac.uk/~pt/Practical_Foundations/html/s26.html Practical Foundations of Mathematics]
* LARRECQ, Jean Goubault. [http://citeseer.ist.psu.edu/goubault-larrecq01wellfounded.html 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.
[[Categoria:Teoria dos conjuntos|Relacao bem-fundada]]
| |||