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

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 $\iff \forall g\in G,\exists x,y,(g=(x,y))\,$

Como exemplos, temos que $G=\varnothing \,$, $G=\{(2,5)\}\,$, 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

$\forall (x,y)\in G,(x\in A\land y\in B)\,$.

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

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 $a\in A,b\in B\,$, 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 $x\in A,y\in B\,$? Em outras palavras, existe o conjunto (porque, usando o axioma da extensão, se ele existe, então é único) $A\times B\,$ com a propriedade notável que $(x,y)\in A\times B\iff x\in A\land y\in B\,$? 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

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: $f:A\to B\,$. 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 $f:A\to B\,$? Intuitivamente, este conjunto seria formado pelos pares (x, b) em que $x\in A\,$ - porém já vimos que a expressão $\{x|\Phi (x)\}\,$ pode não definir um conjunto, e o que estamos tentando fazer é definir esta função como $\{(x,b)|x\in A\}\,$ - exatamente desta forma "proibida".

Conjuntos infinitos e conjuntos finitos

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

$\exists A,f:A\to S,(A\subset S\land {\mbox{ f é bijetiva }})\,$

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 $\varnothing \,$ é um conjunto finito, porque não possui nenhum subconjunto próprio.

Seja S um conjunto unitário (ou seja, $\exists s,S=\{s\}\,$, seja $A\subset S\,$ e $f:A\to S\,$ uma função bijetiva. Mas o único subconjunto próprio de S é o conjunto vazio, e a única função $f:\varnothing \to S\,$ é 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

Como vimos anteriormente, definimos $0=\varnothing \,$, 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 $s(x)=x\cup \{x\}\,$) 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 $\Phi (x)\,$:

$x=\varnothing \lor \exists y\in x(x=y\cup \{y\})\,$

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 $\Phi (x)\,$, chegamos à seguinte:

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

Neste momento seria tentador resumir esta propriedade como $n\in \mathbb {N} \,$, 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 $\mathbf {N} (n)=\Phi (n)\land \forall y\in x,(\Phi (y))\,$

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 ($s(Q)=Q\cup \{Q\}=Q\cup Q=Q\,$), 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

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

É óbvio que $0=\varnothing \,$ é 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):

$s(n)=n\cup \{n\}\implies \exists n\in s(n)(s(n)=n\cup \{n\}\,$

Portanto verifica-se que $\Phi (s(n))\,$.

Por outro lado, se $y\in s(n)\,$, então $y=n\lor y\in n\,$. Em ambos casos, temos que $\Phi (y)\,$ - 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

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

• $\forall x,y,z\in A,(x<y\land y<z\implies x<z)\,$ (transitividade)
• $\forall x\in A,(\neg x<x)\,$ (aliorrelatividade)
• $\forall x,y\in A,(x<y\lor x=y\lor y<x)\,$ (ordem total)
• $\forall S\subseteq A,(\exists s\in S\implies \exists i\in S,(\forall x\in S,(i=x\lor i<x)))\,$ (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 $\forall x,y\in \alpha ,((x,y)\in R\iff x\in y)\,$
• Todo elemento de α é um subconjunto de α (ou seja, $\forall x\in \alpha ,(x\subseteq \alpha ))\,$

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

Quando $S\subseteq \alpha \,$ for um conjunto não-vazio, seu elemento mínimo em α (pelo axioma acima) será representado por $\min _{\alpha }S\,$.

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

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

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

Ou seja, $\forall \alpha ,Ord(\alpha )\land \exists y\in \alpha \implies \varnothing \in \alpha \,$

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

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

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

É imediato mostrar que, se Ord(β) e $\alpha \in \beta \,$, 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:

$R_{a}=\{(x,y)\in R_{b}|x\in \alpha \land y\in \alpha \}\,$

Então temos:

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

Ou seja, Ord(β) e $\alpha \in \beta \,$ implica $s(\alpha )\subseteq \beta \,$.

Isto é óbvio: $s(\alpha )=\alpha \cup \{\alpha \}\,$, e $\alpha \subset \beta \,$ e $\{\alpha \}\subseteq \beta \,$.

Veremos mais adiante um resultado ainda mais forte que este.

A interseção de dois ordinais é um ordinal

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

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

• $\forall x,y,z\in \gamma ,(x<y\land y<x\implies x<z)\,$ (transitividade)
• $\forall x\in \gamma ,(\neg x<x)\,$ (aliorrelatividade)
• $\forall x,y\in \gamma ,(x<y\lor x=y\lor y<x)\,$ (ordem total)
• $\forall x\in \gamma ,(x\subseteq \gamma ))\,$

Falta apenas verificar:

• $\forall S\subseteq \gamma ,(\exists s\in S\implies \exists i\in S,(\forall x\in S,(i=x\lor i<x)))\,$ (bem-ordenação: todo subconjunto não vazio tem um elemento mínimo)

Como S é um subconjunto tanto de α quanto de β, sejam $a=\min _{\alpha }S\,$ e $b=\min _{\beta }S\,$.

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

Se Ord(α), Ord(β) e Ord(γ), com $\alpha \in \beta \in \gamma \,$, então $s(\alpha )\in \gamma \,$.

Formemos o conjunto $S=\{x\in \gamma |\alpha \in x\}\,$. S não é vazio porque $\beta \in S\,$. Seja m o seu mínimo. Queremos provar que m = s(α).

Primeiro, é óbvio que $s(\alpha )\subseteq m\,$: por construção, $\alpha inm\,$, portanto, por ser α um ordinal de m, temos que $\alpha \subset m\,$ - o que completa a prova de que $\alpha \cup \{\alpha \}\subseteq m\,$.

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

Ou seja, $m\subseteq s(\alpha )\,$ e $s(\alpha )\subseteq m\,$, completando a demonstração de que $s(\alpha )=m\in \gamma \,$

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

Será provado ainda mais que isso:

$Ord(\alpha ),Ord(\beta ),\alpha \subset \beta \implies \alpha =\min _{\beta }(\beta -\alpha )\,$

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

Provaremos então que $m\subseteq \alpha \,$ e $\alpha \subseteq m\,$.

Primeiro, por construção, é claro que $m\not \in \alpha \,$.

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

Temos, portanto, que $m\not \in \alpha \,$ e $\alpha \ \not \in m\,$.

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

Por outro lado, seja x um elemento de m. Se $x\not \in \alpha \,$, então $x\in \beta -\alpha \,$, contradizendo a propriedade de m ser mínimo - ou seja, $m\subseteq \alpha \,$.

Ou seja, provamos que $\alpha \subset \beta \implies \alpha =\min _{\beta }(\beta -\alpha )\,$ cujo corolário é que $\alpha \in \beta \,$.

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

Ou seja, sejam Ord(α), $S\subseteq \alpha \,$ e $\beta =\bigcup _{xinS}x\,$. Então Ord(β).

É fácil ver que:

• $\beta \subseteq \alpha \,$ - pela transitividade e porque $x\in \beta \implies \exists y\in S,(x\in y\in S)\,$

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 α:

• $\forall x,y\in \beta ,((x,y)\in R_{b}\iff x\in y)\,$
• $\forall x,y,z\in \beta ,(x<y\land y<x\implies x<z)\,$ (transitividade)
• $\forall x\in \beta ,(\neg x<x)\,$ (aliorrelatividade)
• $\forall x,y\in \beta ,(x<y\lor x=y\lor y<x)\,$ (ordem total)
• $\forall S'\subseteq \beta ,(\exists s\in S'\implies \exists i\in S',(\forall x\in S',(i=x\lor i<x)))\,$ (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 $x\in y\in S\,$, mas como x e y são ordinais, temos que $x\subset y\,$, ou seja, temos $x\subseteq y\in S\,$ portanto (ver exercício em Axioma da união) $x\subseteq \bigcup _{yinS}y=\beta \,$.

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

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 $\alpha =\bigcup _{x\in \beta }x\,$. Vimos acima que Ord(α) e que $\alpha \subseteq \beta \,$. Falta provar apenas que $\alpha \neq \beta \implies \beta =s(\alpha )\,$.

Suponhamos então que $\exists x,x\in \beta -\alpha \,$. Provaremos inicialmente que este x, se existe, é único: se existirem x e y na diferença β - α, pela totalidade, temos que $x\in y\,$ (e analogamente para $y\in x\,$) implica que $x\subseteq y\in \beta \,$, ou seja $x\in \bigcup _{y\in \beta }y=\alpha \,$, contradição.

Então temos que $\beta =\alpha \cup \{x\}\,$. Basta então mostrar que x = α. Como $x\in \beta \,$, então $\alpha \cup x=\bigcup _{y\in \beta }y\cup x=\bigcup _{y\in \beta \cup \{x\}}y=\bigcup _{y\in \beta }y=\alpha \,$. Ou seja, $x\subseteq \alpha \,$.

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

Em resumo, mostramos que, se $\alpha \subset \beta \,$, então $\beta =\alpha \cup \{x\}\,$ e x = α, concluindo que β = s(α).

Outras provas

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

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:

• Axioma da potência
• Axioma da substituição
• Axioma da regularidade
• Axioma do infinito
• Axioma da escolha