Teoria dos conjuntos/Axioma da regularidade

Origem: Wikilivros, livros abertos por um mundo aberto.

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[editar | editar código-fonte]

Quando 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[editar | editar código-fonte]

O 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[editar | editar código-fonte]

Para 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?[editar | editar código-fonte]

Um 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[editar | editar código-fonte]

Em 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[editar | editar código-fonte]

Note-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[editar | editar código-fonte]

A 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[editar | editar código-fonte]

Esta 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.

Ver também[editar | editar código-fonte]

Wikipedia
Wikipedia
A Wikipédia tem mais sobre este assunto:
Axioma da regularidade