Teoria dos conjuntos/Axioma da regularidade
Axioma da regularidade
O axioma da regularidade (também chamado de axioma da fundação) é o que diz que todos os conjuntos são bem fundados. Um conjunto não é bem fundado quando algum elemento dele, ou elemento de elemento, ou elemento de elemento de elemento, etc, for ele mesmo. Por exemplo, se existe um conjunto x com a propriedade , ou se existem t, u, v, w, x, y, z com , então estes conjuntos não são bem fundados.
Por outro lado, se um conjunto é bem fundado, será possível mostrar (mas não agora - precisamos dos outros axiomas) que para todo conjunto z, qualquer cadeia da forma será finita.
Motivação
editarQuando vimos a definição de número natural , em que Φ(x) é definido por , o objetivo primário era que todo número natural fosse da forma n = { 0, 1, 2, ..., n-1}. No entando, se existir um conjunto Q = { Q } ou um conjunto como S = { 0, 1, 2, 3, S }, então é possível mostrar que estes conjuntos satisfazem , já que, para ambos, s(x) = x.
O axioma
editarO axioma é um dos mais simples de serem expressos: ele diz que um conjunto que não é vazio possui um elemento que não tem elementos em comum com ele.
Ou seja: .
O axioma é tão elementar que pode ser escrito sem usar a interseção ou o conjunto vazio:
- .
De modo geral, este axioma é utilizado para "simplificar" conjuntos: por mais complexo que seja um conjunto A, seus elementos são mais "simples" que ele; em particular, o axioma diz que existe um elemento B possivelmente mais simples que os outros, já que A e B não tem elementos em comum.
Conjuntos que são membros de si mesmos não existem
editarPara mostrar que , montamos o conjunto A = { x }. Como A só tem um elementos, B = x, e o axioma diz que , ou seja .
Podemos ver que, dados x e y, um deles não é elemento do outro:
Para isto, basta montar o conjunto A = {x, y} e aplicar o axioma. Como A só tem dois elementos, implica em B = x ou B = y; no primeiro caso, temos , no segundo caso temos . Como já vimos que não é possível, temos finalmente que .
Existem loops finitos de conjuntos pertencentes entre si?
editarUm resultado importante, mas difícil de ser escrito na linguagem da teoria dos conjuntos, é que não existem conjuntos x1, x2, ... xn com
- .
Os problemas de escrever isto é definir o que significa "...".
Uma tentativa pode ser usando-se números naturais e funções, ou seja:
- Seja n um número natural diferente de zero, e seja uma função.
- Suponha que . Então
A demonstração deste fato será adiada; ainda faltam alguns resultados básicos sobre os números naturais para poder dar uma demonstração adequada.
Números naturais
editarEm um capítulo anterior, vimos como é possível definir o que é um número natural na teoria dos conjuntos. Um número natural é um conjunto n satisfazendo a propriedade Φ(n) em que todos seus elementos satisfazem a mesma propriedade Φ(x), sendo
Vimos, porém, que não era possível avançar muito na teoria destes números sem que, antes, excluíssemos conjuntos da forma Q = { Q } ou mesmo A = {0, 1, 2, 3, 4, A}. Com o axioma da regularidade, estes conjuntos em que são excluídos, e é possível começar a gerar resultados interessantes.
Se um número natural não é o conjunto vazio, então o conjunto vazio é seu elemento
editarNote-se que esta propriedade não pode ser provada se existem conjuntos não-bem-fundados; por exemplo, o átomo de Quine Q = { Q } seria um número natural (pela definição) que nem é o conjunto vazio nem tem o conjunto vazio como elemento.
Então, naturalmente a prova usa o axioma da regularidade: seja n um número natural, que não é o conjunto vazio, e apliquemos o axioma ao próprio n.
Então existe um elemento tal que . Mas os elementos de um número natural podem ser de dois tipos: o conjunto vazio, ou o sucessor de outro elemento.
Se x for o sucessor s(y) de , então temos uma contradição, pois .
Concluímos portanto que x é o conjunto vazio, ou seja .
Se um elemento de um número natural não é o conjunto vazio, então o conjunto vazio é seu elemento
editarA prova é muito semelhante à prova dada acima.
Seja N(n), e . Aplicando o axioma da regularidade a x, obtemos , etc.
Propriedade de indução para números naturais
editarEsta ainda não é a propriedade da indução finita para os números naturais, mas é um resultado para subconjuntos de um número natural.
Ou seja, se n é um número natural e K é um subconjunto de n satisfazendo:
então K = n.
A prova é imediata: basta mostrar que leva a um absurdo, e naturalmente o axioma da regularidade é usado para mostrar que o conjunto diferença n - K não pode ter nenhum elemento.
Caso contrário, aplicando o axioma da regularidade a S = n - K, temos que existe algum elemento y com e .
Mas sendo y um elemento do número natural n, temos duas possibilidades:
- , pela hipótese (1) de construção de K, leva a , contradizendo
- também leva a contradição, pois não é possível nem que nem que :
- junto com a hipótese (2) de construção de K leva a contradizendo
- junto com faz com que que, junto com , contradiz
Ou seja, provou-se que S = n - K é o conjunto vazio, e como K é um subconjunto de n, temos que n = K.