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 $𝐍(n)=(\mathrm{\Phi }(n)\wedge \mathrm{\forall }y\in n,(\mathrm{\Phi }(y))$, em que Φ(x) é definido por $\mathrm{\Phi }(x)=(x=\varnothing \vee \mathrm{\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 $𝐍(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: $\mathrm{\forall }A\ne \varnothing ,\mathrm{\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:

$\mathrm{\forall }A,\mathrm{\exists }x\in A⟹\mathrm{\exists }B\in A,\mathrm{\forall }x,(\mathrm{\neg }(x\in A\wedge 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 $\mathrm{\forall }x,(x\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\in ̸x$.

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

$\mathrm{\forall }x,y,(\mathrm{\neg }(x\in y\wedge 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\in ̸x\wedge y\in ̸x$, no segundo caso temos $x\in ̸y\wedge y\in ̸y$. Como já vimos que $x\in x$ não é possível, temos finalmente que $y\in ̸x\vee x\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 \dots \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 $\mathrm{\forall }m\in n,f(m)\in f(s(m))$. Então $f(n)\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 [[../Explorando os axiomas da extensão, separação, par e união/|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 $\mathrm{\Phi }(x)=(x=\varnothing \vee \mathrm{\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\ne \varnothing$. Aplicando o axioma da regularidade a x, obtemos $y\in x\wedge 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⟹\varnothing \in K$
2. $x\in K\wedge s(x)\in n⟹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)\wedge z\in x$ também leva a contradição, pois não é possível nem que $z\in K$ nem que $z\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\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.