Teoria dos conjuntos/Explorando os axiomas da extensão, separação, par e união

Como prelúdio para os próximos axiomas, iremos explorar o que pode ser construído ou, pelo menos, definido com base nos axiomas anteriores.

Até agora, fomos capazes de mostrar que existem vários conjuntos, tais como {{1, 3}, {2, {4, 5}}}. Na verdade, com as ferramentas até agora apresentadas - especificamente, a formação dos conjunto {x, y} e sendo x e y conjuntos - podemos construir todos conjuntos hereditariamente finitos, ou seja, os conjuntos que são finitos, e cujos elementos são conjuntos finitos, e assim por diante.

Só não podemos provar isso, já que a linguagem usada até agora não permite escrever que um conjunto é hereditariamente finito sem que, antes, tenhamos o conjunto dos números naturais (e alguns outros axiomas).

Também não foi vista nenhuma construção de um conjunto infinito - e nem foi ainda definido o que é um conjunto infinito. Felizmente, os axiomas e conceitos até agora apresentados permitem esta definição, e algumas outras, que serão fundamentais para a compreensão dos próximos axiomas.

Dentre estes conceitos estão o de função, relação bem ordenada e número ordinal.

Relações

editar

Diz-se que um conjunto G é o gráfico de uma relação quando todo elemento de G é um par ordenado.

Na linguagem formal da teoria dos conjuntos, acrescida das expressões únicas definidas pelos axiomas anteriores, temos:

G é o gráfico de uma relação  

Como exemplos, temos que  ,  , etc são gráficos de relações.

Se G é o gráfico de uma relação, então define-se Dom(G) e Imag(G) (respectivamente, domínio e imagem do gráfico da relação) como os conjuntos dos x e y dos pares ordenados (x,y) que são elementos da relação.

Uma relação tem duas informações a mais que o gráfico de uma relação: temos um conjunto de partida e um conjunto de chegada. Existem várias formas de definir o que seja uma relação; para fixar ideias, uma relação será definida como um conjunto da forma:

((A, B), G)

ou seja, um par ordenado em que o primeiro elemento é um par ordenado, satisfazendo as seguintes propriedades:

G é o gráfico de uma relação
 .

Segue imediatamente das definições que, se ((A, B), G) é uma relação, então   e  .

Uma pergunta natural é quais relações que existem com A como conjunto de partida e B como conjunto de chegada? O conjunto vazio é o gráfico de uma destas relações; analogamente, se A e B não forem vazios, com  , temos que G = { (a, b) } é o gráfico de uma relação.

Será que existe uma relação cujo gráfico inclua todos pares (x, y), com  ? Em outras palavras, existe o conjunto (porque, usando o axioma da extensão, se ele existe, então é único)   com a propriedade notável que  ? A resposta, com base nos axiomas até agora apresentados, é um terrível não sei. Esta pergunta será respondida afirmativamente com o axioma da potência.

Funções

editar

Funções são um tipo especial de relação, satisfazendo as propriedades tradicionais. Em vez de ((A, B), f) para a função, representa-se por:  . Aqui, analogamente, f é o gráfico da função/relação; muitas vezes, por descuido de linguagem, usa-se função para f (e não para a ((A, B), f)) quando o objetivo é falar do seu gráfico, e vice-e-versa.

Funções podem ser injetivas, sobrejetivas, bijetivas - tudo definido a partir dos axiomas!

O problema é que ainda faltam alguns axiomas para podermos construir várias funções. Por exemplo, seja A um conjunto qualquer, e B um conjunto de um único elemento, B = { b }. Será que existe uma função  ? Intuitivamente, este conjunto seria formado pelos pares (x, b) em que   - porém já vimos que a expressão   pode não definir um conjunto, e o que estamos tentando fazer é definir esta função como   - exatamente desta forma "proibida".

Conjuntos infinitos e conjuntos finitos

editar

Seguindo a definição de Dedekind, um conjunto S infinito quando:

 

Um conjunto que não é infinito é um conjunto finito.

Serão mostrados agora alguns conjuntos finitos. Um conjunto infinito só pode ser mostrado com os axiomas seguintes.

É óbvio que   é um conjunto finito, porque não possui nenhum subconjunto próprio.

Seja S um conjunto unitário (ou seja,  , seja   e   uma função bijetiva. Mas o único subconjunto próprio de S é o conjunto vazio, e a única função   é a função cujo gráfico é o conjunto vazio, portanto não existe (x,y) no gráfico de f tal que y = s - em outras palavras, S não é infinito.

Podemos prosseguir, mostrando vários casos particulares de conjuntos finitos (por exemplo, que {x,y} é um conjunto finito), mas as provas mais gerais precisam de outras construções (composição de função, produto cartesiano, etc), que dependem dos próximos axiomas - por exemplo, não dá para mostrar que um subconjunto de um conjunto finito é também um conjunto finito!


Número natural

editar

Como vimos anteriormente, definimos  , 1 = { 0 }, 2 = { 0, 1}, e prosseguimos definindo até 9 = {0, 1, 2, 3, 4, 5, 6, 7, 8}. Pode-se imaginar (mas não escrever - a notação não é suportada pela linguagem da teoria dos conjuntos) que um número natural é um conjunto da forma n = {0, 1, 2, ... n-1}. O desafio agora é como escrever isto na linguagem da teoria dos conjuntos.

Imediatamente, vemos que o conjunto vazio é um número natural. Então vamos colocar isto na definição.

Além disso, todo número natural diferente do zero é o sucessor (definido por  ) de outro número natural, que é um elemento seu.

Mas um pouco de imaginação mostra que esta definição esboçada acima como uma propriedade  :

 

dá margem a conjuntos bem maiores que os números naturais - veremos adiante que conjuntos são esses.

Mas se incluirmos que todos elementos de x tem esta propriedade  , chegamos à seguinte:

 

Neste momento seria tentador resumir esta propriedade como  , mas a existência de um conjunto dos números naturais deve ser adiada para um axioma seguinte - o axioma do infinito. Por enquanto, a propriedade acima será resumida com  

Outros resultados importantes não são possíveis sem que antes se exclua a possibilidade de conjuntos da forma Q = { Q }. Este conjunto, se existisse, seria chamado de Átomo de Quine), e teria a propriedade desagradável de ser o sucessor dele mesmo ( ), sendo, portanto um número natural -mas, conforme vimos pela construção intuitiva, seria interessante que um número natural fosse da forma {0, 1, 2, ... n-1} e não desta forma patológica. Um conjunto como Q = { Q } é chamado de conjunto não-bem-fundado, e existe um axioma, o axioma da fundação ou axioma da regularidade que exclui estes conjuntos da Teoria que estamos estudando.

O sucessor de um número natural é um número natural

editar

Vamos verificar se os números 0, 1, 2, ... 9 são números naturais.

É óbvio que   é um número natural.

Pode-se demonstrar que se n é um número natural, então s(n) também é. A prova:

Suponha que n é um número natural. Então temos para s(n):
 
Portanto verifica-se que  .
Por outro lado, se  , então  . Em ambos casos, temos que   - o que completa a prova de que s(n) é um número natural.

Com isso, provamos que 1 é um número natural. Com isso, provamos que 2 é um número natural. E a repetição deste argumento mostra que 3, 4, 5, 6, 7, 8 e 9 são número naturais.


Relação bem ordenada e número ordinal

editar

Uma relação de ordem ((A, A), R), na qual   será representado por x < y, é dita bem ordenada quando:

  •   (transitividade)
  •   (aliorrelatividade)
  •   (ordem total)
  •   (bem-ordenação: todo subconjunto não vazio tem um elemento mínimo)

Usando a definição de von Neumann, um conjunto α (costumam-se usar letras gregas para os números ordinais) é um número ordinal quando:

  • Existe uma relação bem ordenada ((α, α), R)
  • Esta relação satisfaz  
  • Todo elemento de α é um subconjunto de α (ou seja,  

Será usada a representação Ord(α) para indicar que α é um número ordinal (de von Neumann).

Quando   for um conjunto não-vazio, seu elemento mínimo em α (pelo axioma acima) será representado por  .

Pode-se provar que, se y e z são elementos do ordinal α, então  .

Prova: sem perda de generalidade, podemos supor   (  é a mesma prova, trocando y por z, e y = z é imediato). Então seja  . Pela propriedade transitiva, temos que   - em outras palavras,   - ou seja,  .

Se um ordinal não é o conjunto vazio, então o conjunto vazio é seu elemento

editar

Ou seja,  

Como o próprio α é um subconjunto não-vazio dele mesmo, então ele tem um elemento mínimo z.

Suponha que  . Neste caso, por z ser um elemento de α, temos que z é um subconjunto de α, ou seja,  . Mas como z é mínimo, temos que z = x (violando a aliorrelatividade) ou   (e, aplicando a transitividade, recaimos em  ).

Ou seja, a única forma de α ter um elemento mínimo é este elemento ser o conjunto vazio.

Todo elemento de um número ordinal é um número ordinal

editar

É imediato mostrar que, se Ord(β) e  , então Ord(α).

A prova parte da construção da relação ((α, α), Ra) definida a partir da relação de ordem ((β, β), Rb), definindo o gráfico Ra como um subconjunto de Rb:

 

Então temos:

  • Se   então, como elementos de β, pela transitividade, todo elemento de x será também elemento de α - provamos que todo elemento de α é um subconjunto de α
  • Se x, y e z são elementos de α então são elementos de β, o que prova a transitividade
  • Se x é um elemento de α então também é elemento de β, o que prova a aliorrelatividade
  • Se x e y são elementos de α então são elementos de β, o que prova a ordem total
  • Se S é um subconjunto não-vazio de α, então também é um conjunto não-vazio de β, portanto tem elemento mínimo.

O sucessor de um elemento de um ordinal é um subconjunto deste ordinal

editar

Ou seja, Ord(β) e   implica  .

Isto é óbvio:  , e   e  .

Veremos mais adiante um resultado ainda mais forte que este.

A interseção de dois ordinais é um ordinal

editar

Sejam Ord(α), Ord(β) e γ a sua interseção.

Considerando em γ a relação cujo gráfico é interseção dos gráficos das relações   em α e β, é imediato verificar:

  •   (transitividade)
  •   (aliorrelatividade)
  •   (ordem total)
  •  

Falta apenas verificar:

  •   (bem-ordenação: todo subconjunto não vazio tem um elemento mínimo)

Como S é um subconjunto tanto de α quanto de β, sejam   e  .

Mas estes mínimos, por serem elementos de S, são também elementos de α e de β, portanto um deles não pode ser subconjunto do outro, logo são iguais a = b, sendo, portanto, o mínimo de S em γ.


Se um ordinal é suficientemente maior que outro, então ele tem seu sucessor como elemento

editar

Se Ord(α), Ord(β) e Ord(γ), com  , então  .

Formemos o conjunto  . S não é vazio porque  . Seja m o seu mínimo. Queremos provar que m = s(α).

Primeiro, é óbvio que  : por construção,  , portanto, por ser α um ordinal de m, temos que   - o que completa a prova de que  .

Por outro lado, seja x um elemento de m. Então, comparando x com α, temos três possibilidades: x = α implica  ,   analogamente implica  , finalmente   implica   e, pelo fato de m ser o mí­nimo de S, em  , o que (junto com  ) contradiz a aliorrelatividade

Ou seja,   e  , completando a demonstração de que  

Se um ordinal é subconjunto próprio de outro, então ele é seu elemento

editar

Será provado ainda mais que isso:

 

A prova: como o conjunto β - α não é vazio, então tem um elemento mínimo m.

Provaremos então que   e  .

Primeiro, por construção, é claro que  .

Se  , então  , assim, temos que (pelo fato de m ser mínimo em β - α e s(α) ser um membro deste conjunto) que  , que implica   (absurdo) ou   (igualmente absurdo).

Temos, portanto, que   e  .

Tomemos x um elemento qualquer de α. Comparando x com m, temos que x = m ou   implicam no absurdo  , o que conclui a prova de que  .

Por outro lado, seja x um elemento de m. Se  , então  , contradizendo a propriedade de m ser mínimo - ou seja,  .

Ou seja, provamos que   cujo corolário é que  .

A união de elementos de um número ordinal é um número ordinal

editar

Ou seja, sejam Ord(α),   e  . Então Ord(β).

É fácil ver que:

  •   - pela transitividade e porque  

Logo, define-se a relação ((β, β), Rb) como o subconjunto da relação ((α, α), Ra) para os elementos de β.

Quase todos axiomas seguem imediatamente do fato dos elementos de β serem elementos de α:

  •  
  •   (transitividade)
  •   (aliorrelatividade)
  •   (ordem total)
  •   (bem-ordenação: todo subconjunto não vazio tem um elemento mínimo)

Falta mostrar:

  • Todo elemento de β é um subconjunto de β

Seja portanto x um elemento de β, por construção de β existe um elemento y em S com  , mas como x e y são ordinais, temos que  , ou seja, temos   portanto (ver exercício em Axioma da união)  .

A união de todos elementos de um ordinal é este ordinal ou seu antecessor

editar

Aqui, antecessor de um ordinal β é um ordinal α com β = s(α). Obviamente, o conjunto vazio não tem antecessor. Provaremos mais adiante que o antecessor, se existe, é único. Exibiremos, mais adiante, ordinais não-vazios que não tem antecessor; estes ordinais são chamados de ordinal limite.

Seja portanto Ord(β) e  . Vimos acima que Ord(α) e que  . Falta provar apenas que  .

Suponhamos então que  . Provaremos inicialmente que este x, se existe, é único: se existirem x e y na diferença β - α, pela totalidade, temos que   (e analogamente para  ) implica que  , ou seja  , contradição.

Então temos que  . Basta então mostrar que x = α. Como  , então  . Ou seja,  .

Por outro lado, suponha que  , então, por x e y serem elementos de β, temos que x = y ou   ou  . x = y e   levam a contradição, porque  . Portanto, temos que  , o que conclui  .

Em resumo, mostramos que, se  , então   e x = α, concluindo que β = s(α).

Outras provas

editar

Várias provas importantes sobre os números ordinais (por exemplo, se α é um número ordinal então s(α) também é um número ordinal) precisam dos próximos axiomas, especialmente o axioma da potência.

Próximos capítulos

editar

Os próximos capítulos foram escritos de forma que possam ser estudados de forma independente. Em cada um deles, é apresentado um axioma, e os conceitos aqui introduzidos são um pouco expandidos, com novas provas.

Na seção seguinte, todos os axiomas são supostos, e estes temas serão revistos e aprofundados.

Os axiomas são: