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
editarDiz-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
editarFunçõ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
editarSeguindo 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
editarComo 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
editarVamos 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
editarUma 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
editarOu 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
editarOu 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
editarSejam 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
editarSe 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
editarSerá 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
editarOu 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
editarAqui, 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
editarVá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
editarOs 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: