Saltar para o conteúdo

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

Origem: Wikilivros, livros abertos por um mundo aberto.

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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: