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 $x\in x\,$, ou se existem t, u, v, w, x, y, z com $t\in u\in v\in w\in x\in y\in z\in t\,$, 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 $a\in b\in c\in d\in e...\in z\,$ será finita.

Motivação

Quando vimos a definição de número natural $\mathbf {N} (n)=(\Phi (n)\land \forall y\in n,(\Phi (y))\,$, em que Φ(x) é definido por $\Phi (x)=(x=\varnothing \lor \exists y\in x,x=y\cup \{y\})\,$, 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 $\mathbf {N} (n)\,$, já que, para ambos, s(x) = x.

O axioma

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: $\forall A\neq \varnothing ,\exists B\in A,(A\cap B=\varnothing )\,$.

O axioma é tão elementar que pode ser escrito sem usar a interseção ou o conjunto vazio:

$\forall A,\exists x\in A\implies \exists B\in A,\forall x,(\neg (x\in A\land x\in B))\,$.

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

Para mostrar que $\forall x,(x\not \in x)\,$, montamos o conjunto A = { x }. Como A só tem um elementos, B = x, e o axioma diz que $\{x\}\cap x=\varnothing \,$, ou seja $x\not \in x\,$.

Podemos ver que, dados x e y, um deles não é elemento do outro:

$\forall x,y,(\neg (x\in y\land y\in x))\,$

Para isto, basta montar o conjunto A = {x, y} e aplicar o axioma. Como A só tem dois elementos, $B\in A\,$ implica em B = x ou B = y; no primeiro caso, temos $x\not \in x\land y\not \in x\,$, no segundo caso temos $x\not \in y\land y\not \in y\,$. Como já vimos que $x\in x\,$ não é possível, temos finalmente que $y\not \in x\lor x\not \in y\,$.

Existem loops finitos de conjuntos pertencentes entre si?

Um resultado importante, mas difícil de ser escrito na linguagem da teoria dos conjuntos, é que não existem conjuntos x₁, x₂, ... x_n com

$x_{1}\in x_{2}\in \ldots \in x_{n}\in x_{1}\,$.

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 $f:s(n)\to S\,$ uma função.

Suponha que $\forall m\in n,f(m)\in f(s(m))\,$. Então $f(n)\not \in f(0)\,$

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

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 $\Phi (x)=(x=\varnothing \lor \exists y\in x(x=s(y)))\,$

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 $x\in x\,$ 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

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 $x\in n\,$ tal que $x\cap n=\varnothing \,$. 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 $y\in n\,$, então temos uma contradição, pois $y\in s(y)\,$.

Concluímos portanto que x é o conjunto vazio, ou seja $\varnothing \in n\,$.

Se um elemento de um número natural não é o conjunto vazio, então o conjunto vazio é seu elemento

A prova é muito semelhante à prova dada acima.

Seja N(n), $x\in n\,$ e $x\neq \varnothing \,$. Aplicando o axioma da regularidade a x, obtemos $y\in x\land x\cap y=\varnothing \,$, etc.

Propriedade de indução para números naturais

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:

1. $\varnothing \in n\implies \varnothing \in K\,$
2. $x\in K\ \land s(x)\in n\implies s(x)\in K\,$

então K = n.

A prova é imediata: basta mostrar que $K\subset n\,$ 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 $y\in n-K\,$ e $y\cap K=\varnothing \,$.

Mas sendo y um elemento do número natural n, temos duas possibilidades:

• $y=\varnothing \,$, pela hipótese (1) de construção de K, leva a $y\in K\,$, contradizendo $y\in n-K\,$
• $y=s(z)\land z\in x\,$ também leva a contradição, pois não é possível nem que $z\in K\,$ nem que $z\not \in K\,$:
  • $z\in K\,$ junto com a hipótese (2) de construção de K leva a $y\in K\,$ contradizendo $y\in n-K\,$
  • $z\not \in K\,$ junto com $z\in n\,$ faz com que $z\in S\,$ que, junto com $z\in y\,$, contradiz $y\cap S=\varnothing \,$

Ou seja, provou-se que S = n - K é o conjunto vazio, e como K é um subconjunto de n, temos que n = K.