Teoria dos conjuntos/Imprimir

Conjuntos

Conjuntos e elementos

Quando a Teoria dos conjuntos foi apresentada no nível elementar (até o ensino secundário / ensino médio), foi necessário fazer a distinção entre conjunto e elemento.

Lembrando (ver livro Matemática elementar/Conjuntos):

• um conjunto é uma coleção de elementos, sem importar a ordem em que eles se apresentam;
• qualquer coisa pode ser um elemento.

Assim, temos que a Lua, o livro Dom Quixote, Napoleão, 5, etc são elementos, mas todos os cachorros do mundo, todos os satélites naturais ou artificias da Terra, os números naturais maiores que 4 e menores que 6 são conjuntos.

Isto até apresentarem o conjunto das partes, que é um conjunto cujos elementos são outros conjuntos.

Então, partindo-se do conjunto vazio, podemos construir seu conjunto das partes $\{\varnothing \}\,$, cujo único elemento é $\varnothing$, o conjunto das partes deste conjunto, $\{\varnothing ,\{\varnothing \}\}\,$ de dois elementos, o conjunto das partes deste conjunto, $\{\varnothing ,\{\varnothing \},\{\{\varnothing \}\},\{\varnothing ,\{\varnothing \}\}\}\,$ de quatro elementos, etc.

Pode-se até vislumbrar uma cadeia de infinitos conjuntos, cada um deles sendo o conjunto das partes do conjunto anterior. Que tal agora formar um conjunto cujos elementos são precisamente os elementos dos conjuntos desta cadeia? Este seria um conjunto imenso, com infinitos elementos - mas pode-se continuar criando conjuntos maiores, tomando-se o conjunto das partes deste monstro, e assim por diante.

Na Teoria dos conjuntos axiomática, não existe distinção entre elementos e conjuntos: um conjunto é uma coleção de outros conjuntos. Todos os conjuntos são, essencialmente, formados pelo processo acima, ou seja, na sua fundação está o conjunto vazio.

Fundamentos

A Teoria dos conjuntos axiomática, portanto, é fundamentada em apenas dois conceitos:

• A noção primitiva de conjunto;
• A expressão $x\in y\,$, em que x e y são conjuntos.

Diz-se que x é um elemento de y quando esta última expressão for verdadeira, e x não é um elemento de y quando esta expressão for falsa (neste caso escreve-se $x\not \in y\,$).

Usaremos também a notação $x\in y\in z,$ (e outras expressões parecidas) para representar $x\in y\land y\in z\,$ - note-se que $x\in y\in z\,$ não implica, necessariamente, que $x\in z\,$ (veremos que, em geral, isto não é válido). Tente imaginar uma situação que exemplifique este fato.

Pela experiência anterior, sabe-se que existe um conjunto $\varnothing \,$ com as seguintes propriedades notáveis:

• $\forall x,x\not \in \varnothing \,$

em palavras: o conjunto vazio não tem elemento

• $\forall x,(\not \exists y(y\in x)\implies x=\varnothing )\,$

em palavras: se um conjunto qualquer não tem elementos, então este é igual ao conjunto vazio.

Na Teoria axiomática dos conjuntos, estes dois resultados (resumidos em "o conjunto vazio existe e é único") são teoremas.

Existência

Um problema estético que se tem ao apresentar os axiomas da Teoria dos conjuntos é que os axiomas mais simples (aqueles que são apresentados no início) não garantem a existência de algum conjunto.

Na linguagem da Teoria dos modelos, o campo da lógica que estuda estruturas matemáticas que consubstanciam sistemas de axiomas, esta ideia é expressa por:

O conjunto vazio é um modelo da teoria que consiste dos axiomas de Zermelo-Fraenkel sem o axioma do infinito.

Isto porque todos os outros axiomas tem a expressão "Para todo conjunto X, bla bla bla". Então, se não existe nenhum conjunto na teoria, todos os axiomas são verdadeiros (ver artigo na Wikipédia em inglês, Vacuous truth).

Assim, para podermos entender e exemplificar os primeiros axiomas, será incluído um axioma adicional. Simplesmente, este axioma diz que existe pelo menos um conjunto:

$\exists x\,$

Axioma da extensão

O axioma da extensão diz que a única coisa que distingue dois conjuntos são seus elementos. Ou seja, dois conjuntos são iguais se, e somente se, seus elementos são os mesmos. Como só existem conjuntos (ou seja, os elementos dos conjuntos são conjuntos), este axioma diz dois objetos são iguais quando seus elementos são os mesmos.

Formalmente, o axioma se escreve:

$\forall A\,\forall B\,(\forall C\,(C\in A\iff C\in B)\Rightarrow A=B)$

Subconjuntos

A expressão $\forall C\,(C\in A\implies C\in B)\,$ é usada para representar a noção de subconjunto, ou seja, definimos:

$A\subseteq B\,$

como

$\forall C\,(C\in A\implies C\in B)\,$

Segue-se imediatamente que:

$(A\subseteq B\land B\subseteq A)\iff A=B\,$

Um subconjunto é chamado de subconjunto próprio quando ele não é o próprio conjunto. Por definição:

$A\subset B\,$

significa que:

$A\subseteq B\land A\neq B\,$

Uma consequência das definições é o resultado seguinte:

$A\subset B\implies (\exists x\in B,x\not \in A)\,$

Em palavras: se A é um subconjunto próprio de B, então B possui algum elemento que não é elemento de A.

Propriedades

As propriedades seguintes são imediatas das definições, valendo para todos conjuntos A, B, C:

$A\subseteq B\land B\subseteq C\implies A\subseteq C\,$

$A\subseteq B\land B\subset C\implies A\subset C\,$

$A\subset B\land B\subseteq C\implies A\subset C\,$

$A\subset B\land B\subset C\implies A\subset C\,$

Axioma da separação

O Axioma da separação (também conhecido como Axioma da compreensão ou Axioma de especificação) diz que se um conjunto A existe, e conseguimos descrever (através de uma propriedade) elementos deste conjunto, então existe um conjunto B, subconjunto de A, que contém estes elementos.

Este "axioma" é, a rigor, um esquema de axiomas, porque, para cada propriedade Φ, existe um "axioma da separação".

Axioma

A forma apresentada abaixo se deve a Kunen.

Se z é um conjunto e $\phi \!$ é qualquer propriedade que possa ser atribuída a elementos x de z, então existe um subconjunto y de z que contém os elementos x de z e que possuem essa propriedade.

Formalmente: qualquer fórmula $\phi \!$ na linguagem da teoria dos conjuntos com variáveis livres entre $x,z,w_{1},\ldots ,w_{n}\!$:

$\forall z\forall w_{1}\ldots w_{n}\exists y\forall x(x\in y\iff (x\in z\land \phi ))$

Notar que esse não é um axioma, mas um esquema de axiomas: para cada $\phi \!$ temos um novo axioma.

Notação

Este axioma, combinado com o axioma da extensão, mostra que, para todo conjunto z e toda propriedade Φ, existe um único conjunto cujos elementos são os elementos de z que satisfazem Φ. Ou seja, a notação:

$\{x\in z|\Phi (x)\}\,$

define um conjunto que existe e é único.

Segue-se imediatamente da definição que:

$\forall z,\{x\in z|\Phi (x)\}\subseteq z\,$

Note-se que R definido no Paradoxo de Russell

$R=\{x|x\not \in x\}\,$

não é um conjunto segundo a definição acima: é preciso especificar dentro de qual conjuntos os elementos x são tirados.

Conjunto vazio

Já supomos no capítulo introdutório que existe algum conjunto. Então, seja Φ(x) uma propriedade que é sempre falsa (por exemplo, $\Phi (x)=(x\neq x)\,$).

Sejam, portanto, z e w dois conjuntos quaisquer. Então os conjuntos:

$O_{z}=\{x\in z|\Phi (x)\}\,$

$O_{w}=\{x\in w|\Phi (x)\}\,$

existem e, pelo axioma da extensão, são iguais, já que é fácil provar que

$\forall x,(x\not \in O_{z}\land x\not \in O_{w})\,$

Em outras palavras, qualquer que seja o conjunto de partida (z, w, etc), o conjunto definido acima será sempre o mesmo.

Este conjunto é chamado de conjunto vazio, representado por $\varnothing \,$.

Os resultados acima podem ser resumidos de forma sintética em existe um conjunto que não tem nenhum elemento, e este conjunto é único.

Pelos axiomas expostos até agora, o conjunto vazio é um ponto final, ou seja, nada pode ser construído a partir dele. Por exemplo, aplicando-se o axioma da separação ao conjunto vazio, obtem-se apenas o conjunto vazio:

$\{x\in \varnothing |\Phi (x)\}=\varnothing \,$

Por outro lado, pode-se mostrar que:

• o conjunto vazio é subconjunto de qualquer outro conjunto
• o conjunto vazio é subconjunto próprio de qualquer outro conjunto que não seja vazio
• nenhum conjunto é subconjunto próprio do conjunto vazio

Interseção

Dados dois conjuntos y e z, e a propriedade $\phi (x,y,z)=(x\in z)\,$, o axioma diz que existe o conjunto w tal que

$w=\{x\in y|x\in z\}\,$

Este conjunto tem uma notação especial, e é chamado de a interseção de y e z, ou seja:

$y\cap z=\{x\in y|x\in z\}\,$

Segue imediatamente das definições acima que:

$\forall y,(y\cap \varnothing =\varnothing )\,$

$\forall y,z,(y\cap z=z\cap y)\,$

$\forall y,(y\cap y=y)\,$

A propriedade associativa demanda um pouco mais de trabalho:

$\forall x,y,z,(x\cap (y\cap z)=(x\cap y)\cap z)\,$

Diferença

Dados dois conjuntos y e z, e a propriedade $\phi (x,y,z)=(x\not \in z)\,$, o axioma diz que existe o conjunto w tal que

$w=\{x\in y|x\not \in z\}\,$

Este conjunto tem uma notação especial, e é chamado de a diferença de y e z, ou seja:

$y-z=\{x\in y|x\not \in z\}\,$

Exercícios

• Mostre que não existe o conjunto de todos os conjuntos. Em outras palavras, para todo conjunto x, existe algum conjunto y tal que $y\not \in x\,$. Sugestão: a prova é por contradição e usa o axioma da regularidade e a ideia do paradoxo de Russel.
• Escreva e demonstre as várias propriedades que combinam a interseção e a diferença, por exemplo $(A-B)\cap (A\cap B)=\varnothing \,$

Ver também

• Em informática, a aplicação deste axioma a listas é chamada de List comprehension. Linguagens funcionais (Haskell, etc) ou com influência destas (Python, etc) tem formas simples de fazer list comprehension.

Axioma do par

Com os axiomas apresentados até agora (o axioma que diz que existe um conjunto, o axioma da extensão e o axioma da separação), já pudemos mostrar que o conjunto vazio, $\varnothing \,$, existe e é único.

Mas não fomos capazes de exibir nenhum outro conjunto!

Uma teoria dos conjuntos cujo único conjunto seja o conjunto vazio não serve para muita coisa. Seria interessante haver pelo menos outro conjunto, e o candidato natural é o conjunto cujo único elemento é o próprio conjunto vazio.

Mas não podemos, pelos axiomas atuais, definir

$x=\{y|y=\varnothing \}\,$

porque esta não é uma definição de conjunto que se enquadra no axioma da separação.

O axioma do par é o que garante a existência deste tipo de conjunto. Na sua forma mais usual, ele garante até algo mais: dados dois conjuntos, existe um conjunto que tem estes dois conjuntos como elementos.

Como o axioma não obriga estes dois conjuntos a serem diferentes, podemos usá-lo para criar o conjunto cujo único elemento é o conjunto vazio.

E assim por diante... Mas, como veremos abaixo, este "adiante" ainda não compreende todos os conjuntos que precisamos para ter uma teoria útil e prática.

O Axioma

Sejam A e B conjuntos quaisquer (que podem ser iguais). Então existe um conjunto C tal que $A\in C\,$ e $B\in C\,$.

Nota: existem formulações alternativas do axioma, que dizem que C não tem outro elemento além de A e B, e que C é único, mas, junto com os axiomas da extensão e da separação, mostra-se que essas formulações são equivalentes.

Em linguagem matemática, o axioma se escreve assim:

$\forall x,y\ \exists z\ (x\in z\land y\in z)\,$

Usando-se os axiomas da extensão e da separação, chega-se ao seguinte teorema:

$\forall x,y\ \exists !z\ (x\in z\land y\in z\land \forall w\ (w\in z\rightarrow (w=x\lor w=y)))\,$

Esboço da prova: o axioma da separação é usado para construir, a partir do z que existe, o conjunto

$\{w\in z:w=x\lor w=y\}\,$

e o axioma da extensão garante que todos conjuntos z que satisfazem $x\in z\land y\in z\land \forall w\ (w\in z\rightarrow (w=x\lor w=y))\,$ são iguais.

Definição de { x, y }, { x } e {}

Como esse conjunto que tem o par de conjuntos como elementos é único, podemos dar um nome para ele, a saber:

$\{x,y\}\,$

Como nada nos axiomas obriga x a ser diferente de y, definimos também:

$\{x\}=\{x,x\}\,$

Observação: por analogia, também é comum a notação

$\{\}=\varnothing \,$

Generalizar esta notação, ou seja, definir o que seria {x,y,z} ainda não é possível: isto será visto com o axioma da união.

Propriedades

Segue-se imediatamente da definição que:

• $x\in \{x,y\}\,$
• $z\in \{x,y\}\implies (z=x\lor z=y)\,$
• $\{x,y\}=\{y,x\}\,$
• $\{x\}\subseteq \{x,y\}\,$
• $\{x\}=\{y\}\implies x=y\,$
• $\{x,y\}=\{z\}\implies (x=z\land y=z)\,$
• $\{x,y\}=\{z,w\}\implies ((x=z\land y=w)\lor (x=w\land y=z))\,$

Definição de 1 e 2

Adotando-se a ideia de von Neumann , vamos definir os seguintes conjuntos:

$1=\{\varnothing \}\,$

$2=\{\varnothing ,1\}\,$

e temos que parar por aqui, porque ainda não definimos o que significa {x, y, z} - e, pelos axiomas até agora listados, não sabemos se existe este tipo de conjunto.

Note-se (exercício: prove) que:

• $\varnothing \in 1\,$
• $\varnothing \in 2\,$
• $\varnothing \subset 1\,$
• $\varnothing \subset 2\,$
• $1\in 2\,$
• $1\subset 2\,$

As propriedades acima não são acidentais: quando definirmos os números naturais, elas serão válidas para todos os números. Iremos mais adiante: estas propriedades valerão para uma classe de conjuntos que amplia uma das funções normalmente atribuídas aos números naturais, que é ordenar elementos.

Note-se que as relações $\in \,$ e $\subset \,$ não são sempre equivalentes. Por exemplo:

• $1\in \{1\}\,$ mas $1\not \subset \{1\}\,$ - porque $\varnothing \in 1\land \varnothing \not \in \{1\}\,$
• $\varnothing \subset \{1\}\,$ mas $\varnothing \not \in \{1\}\,$

Par ordenado

O par ordenado também pode ser definido com o axioma do par. Esta definição se deve a Kuratowski:

$(x,y)=\{\{x\},\{x,y\}\}\,$

O teorema abaixo é de crucial importância para as aplicações do par ordenado:

$(x,y)=(z,w)\implies (x=z\land y=w)\,$

Esboço da demonstração:

Conforme temos $x=y\,$ ou $x\neq y\,$, combinado com $z=w\,$ ou $z\neq w\,$, temos quatro casos possíveis. As propriedades do conjunto { a , b } resolvem trivialmente quase todos os casos, exceto quando $x\neq y\land z\neq w\,$.

Mas, neste caso, temos, por $\{\{x\},\{x,y\}\}=\{\{z\},\{z,w\}\}\,$ que $\{x\}=\{z\}\,$ ou $\{x\}=\{z,w\}\,$. Este segundo caso só é possível quando z = w, o que já foi excluído antes. Assim, temos $\{x\}=\{z\}\,$, o que implica em x = z. Assim, sobra a igualdade $\{x,y\}=\{x,w\}\,$, ou $y=x\lor y=w\,$. Como já vimos que $x\neq y\,$, segue-se que y = w.

Revendo o axioma da separação

No texto do axioma da separação:

Se z é um conjunto e $\phi \!$ é qualquer propriedade que possa ser atribuída a elementos x de z, então existe um subconjunto y de z que contém os elementos x de z e que possuem essa propriedade.

Ou, em sua forma mais genérica, qualquer fórmula $\phi \!$ na linguagem da teoria dos conjuntos com variáveis livres entre $x,z,w_{1},\ldots ,w_{n}\!$:

$\forall z\forall w_{1}\ldots w_{n}\exists y\forall x(x\in y\iff (x\in z\land \phi ))$

Um ponto que pode não ter ficado muito claro é que tipo de fórmula ou propriedade é admissível para Φ.

Este capítulo tem o objetivo de explorar estas fórmulas.

Exemplo: conjuntos unitários

Seja Φ a propriedade definida como:

$\Phi (x)=(\exists y,(y\in x\land \forall z,(z\in x\implies z=y)))\,$

Em Português, o que esta propriedade afirma?

$\exists y,y\in x\,$ - significa que x não é o conjunto vazio.

$\forall z,(z\in x\implies z=y)\,$ - significa que se x tem algum elemento, então este elemento é igual ao y

Em outras palavras, Φ(x) expressa, na linguagem da teoria dos conjuntos, que x é um conjunto unitário.

Por exemplo, podemos demonstrar (exercício) que Φ(1), Φ({1}) e Φ({2}) são verdadeiros, e que $\Phi (\varnothing )\,$, Φ(2) e Φ({1,2}) são falsos.

Como aplicação do esquema de axiomas, seja A = {1, 2}. Então o conjunto $B=\{x\in A|\Phi (x)\}\,$ é o conjunto B = {1}.

Ao aplicar a propriedade Φ na formação de subconjuntos, deve-se tomar o cuidado de não repetir os símbolos. Se temos uma demonstração lógica que já utilizou os símbolos x, y ou z, devemos usar a definição de Φ trocando o símbolo por algum outro.

Note-se que, pelos axiomas até agora apresentados, a expressão $\{x|\Phi (x)\}\,$ não denota um conjunto - aliás, é possível mostrar (usando uma variação do paradoxo de Russell) que este conjunto não existe, ou seja, que para todo conjunto A existe um conjunto unitário B que não é um elemento de A.

A fórmula do axioma

A fórmula Φ do axioma deve ser uma fórmula bem formada, na linguagem da lógica clássica de primeira ordem.

Isto significa o seguinte:

• Podem ser usadas constantes e fórmulas previamente definidas, e variáveis novas
• Podem ser usados os conectivos lógicos da lógica proposicional (e, ou, não, implica, etc, combinados com parêntesis para mostrar prioridade de avaliação)
• Variáveis devem ser introduzidas pelos quantificadores existe e para todo, e seu uso deve ser limitado à proposição que se segue ao quantificador.
• Variáveis devem se relacionar entre si e com as constantes através unicamente de $\in \,$, ou de outros símbolos definidos anteriormente por fórmulas bem formadas.
• As fórmulas bem formadas são recursivas, ou seja, elementos de uma fórmula bem formada são fórmulas bem formadas.

Como exemplos, sendo A, B e C constantes:

• $x\in A\,$ é um fórmula bem formada na variável x
• $\exists x,x\in A\,$ não é uma fórmula bem formada na variável x, porque x não está livre
• $x\in A\implies x\in B\,$ é uma fórmula bem formada na variável x
• $x\in A\implies (\forall y,(y\in B\implies x\in y))\,$ é uma fórmula bem formada na variável x
• $x\in A\land y\in B\implies x=y\,$ é uma fórmula bem formada nas variáveis x e y
• $\exists y,(y\in x\lor \forall y(y\in A))\,$ não é uma fórmula bem formada em x: y aparece em um quantificador ($\forall y\,$) dentro de uma expressão condicional a outro quantificador $\exists y\,$)
• $(\forall y,z\in x,(y\in z\lor y=z\lor z\in y))\land (\forall y,z\in x,(y\in x\land z\in y\implies z\in x))\,$ é uma fórmula bem formada na variável x (esta é uma das definições de um número ordinal)

Sementinha do mal

Agora é um bom ponto para plantar uma sementinha do mal. O axioma diz explicitamente que para todo conjunto x e toda fórmula φ existe um subconjunto y dos elementos de x que satisfazem esta propriedade.

Uma pergunta interessante é inverter o enunciado do axioma: será que, para todo subconjunto y de x, existe uma fórmula bem formada φ (que, obviamente, seja livre de y) de modo que y seja definido através dela?

Esta pergunta aparentemente inocente tem profundas implicações, mas, por enquanto, ainda não temos ferramentas adequadas para explorá-la.

Axioma da união

Até agora vimos, usando os axiomas anteriores, como construir conjuntos como $1=\{\varnothing \}\,$, $2=\{\varnothing ,1\}\,$ ou mesmo $\{2,\{2\}\}=\{\{\varnothing ,1\},\{2\}\}\,$. É estranho, mas não conseguimos (ainda) construir um conjunto A em que $\varnothing \in A\land 1\in A\land 2\in A\,$ - apesar de termos um conjunto cujos elementos dos seus elementos são precisamente $\varnothing \,$, 1 e 2!

O axioma da união é a ferramenta necessária para se construir este tipo de conjunto, ou seja, a partir de um conjunto A, forma-se um conjunto B cujos elementos são tais que $x\in B\iff x\in y\in A\,$.

Um subproduto importante do axioma é a formação do conjunto união de dois outros conjuntos, ou seja, dados A e B este axioma garante a existência de $C=A\cup B\,$

Definição formal

Na linguagem formal, este axioma é:

$\forall A\,\exists B\,\forall x\,(x\in B\iff \exists y\,(x\in y\land y\in A)\,)$

A definição acima implica (pelo axioma da extensão) que B é único; existem outras formas equivalentes deste axioma, em que o conjunto cuja existência é postulada é um superconjunto da união. Nestes casos, para se obter a união é preciso aplicar o axioma da separação para a propriedade $\phi (X)=(\exists Y,X\in Y\land Y\in A)\,$.

Como B é único, é interessante dar um nome a ele, assim, este conjunto é definido como:

$\bigcup _{X\in A}X\,$

União de dois conjuntos

Sendo A e B conjuntos, pelo axioma do par existe o conjunto X = {A, B}. Aplicando-se o axioma da união a este conjunto X, obtém-se um conjunto $C=\bigcup _{x\in X}x\,$.

É fácil mostrar que $x\in C\iff x\in A\lor x\in B\,$, ou seja, este axioma permite construir a união de dois conjuntos:

$A\cup B=\bigcup _{x\in \{A,B\}}x\,$

Definição de conjuntos com três, quatro, etc elementos

Com as definições da união e dos conjuntos com um elemento e com (possivelmente) dois elementos, podemos definir:

• $\{x,y,z\}=\{x,y\}\cup \{z\}\,$
• $\{w,x,y,z\}=\{w,x,y\}\cup \{z\}\,$
• $\{v,w,x,y,z\}=\{v,w,x,y\}\cup \{z\}\,$

e pode-se continuar definindo conjuntos cada vez maiores. É importante notar que, assim como temos um esquema de axiomas no axioma da separação, aqui temos um esquema de definições - não iremos explicitamente escrever todas as definições, mas o leitor deve se convencer de que qualquer conjunto com um número finito de elementos pode ser definido desde que haja tempo suficiente para enumerar seus elementos.

Sucessor, e os números de 3 a 9

Uma notação, bolada por von Neumann, que será muito conveniente é a do sucessor de um conjunto (mas esta definição só tem sentido prático para números).

Define-se s(x), o sucessor de x, como:

• $s(x)=x\cup \{x\}\,$

Já vimos antes as definições de 1 e 2 como conjuntos. É fácil ver que:

• $1=s(\varnothing )\,$
• $2=s(1)\,$

o que motiva a definir:

• 3 = s(2)
• 4 = s(3)
• 5 = s(4)
• 6 = s(5)
• 7 = s(6)
• 8 = s(7)
• 9 = s(8)

Poderíamos continuar assim, mas para ser possível provar alguma coisa em aritmética, será melhor parar por aqui. Note-se que até agora não foi falado do zero; por consistência temos que $0=\varnothing \,$ é a melhor definição, porque assim temos 1 = s(0).

Com os axiomas até agora vistos, falta pouco para poder construir um modelo da Aritmética de Peano - falta demonstrar que existe um conjunto dos números naturais.

Obs: o nome sucessor não é um acidente. É fácil ver que se x é um conjunto qualquer, então qualquer conjunto "entre" x e seu sucessor será igual a x ou "equivalente" a x: $x\in y\in s(x)\,$ implica (por $y\in s(x)\,$) em $y=x\,$ ou $y\in x\,$; assim temos finalmente que, se este conjunto y existe, então $x\in x\,$ ou $x\in y\in x\,$. Conjuntos com propriedades parecidas com esta são chamados de "conjuntos não-bem-fundados"; veremos adiante um axioma (o axioma da regularidade) que diz que estes conjuntos não existem.

Exercícios

• Sejam A e a conjuntos, e seja $B=A\cup \{a\}\,$. Mostre que

$\bigcup _{x\in B}x=(\ \bigcup _{x\in A}x\ )\cup a\,$

• Sejam $B=\bigcup _{x\in A}x\,$. Mostre que:

$x\in A\implies x\subseteq B\,$

• Sejam $A\subseteq B\,$. Mostre que:

$\bigcup _{x\in A}x\subseteq \bigcup _{x\in B}x\,$

• Dê um exemplo em que $A\subset B\,$ e $\bigcup _{x\in A}x=\bigcup _{x\in B}x\,$
• Sejam A, B e C, em que $A\subseteq B\,$ e $B\in C\,$. Mostre que:

$A\subseteq \bigcup _{x\in C}x\,$

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

Axioma da potência

Axioma da potência

Dado um conjunto do tipo {x, y}, podemos construir (usando os axiomas anteriores) o conjunto {0, {x}, {y}, {x,y}} - ou seja, um conjunto cujos elementos são os subconjuntos do conjunto anterior.

O axioma da potência diz que este tipo de conjunto existe sempre, ou seja:

$\forall x,\exists y,\forall z(z\subseteq x\implies z\in y)\,$

O conjunto das partes

Combinando este axioma com o axioma da extensão, constrói-se o único conjunto P(x) (chamado de conjunto das partes de x ou conjunto potência de x) definido por:

$P(x)=\{z\in y|z\subseteq x\}\,$

Segue imediatamente da definição que:

$\forall x,y,(y\subseteq x\iff y\in P(x))\,$

Propriedades

As propriedades abaixo são imediatas (além de outras parecidas); a demonstração delas fica como exercício:

$\forall x,(\varnothing \in P(x))\,$

$\forall x,y,(P(x)\cap P(y)=P(x\cap y)\,$

$\forall x,y,(P(x)\cup P(y)\subseteq P(x\cup y)\,$

Produto cartesiano

Dados dois conjuntos A e B, já vimos o que é o gráfico de uma relação de A para B: é qualquer conjunto cujos elementos são pares ordenados da forma (a, b) com $a\in A,b\in B\,$. Porém, exceto em casos muito simples, não fomos capazes de mostrar que o conjunto de todos estes pares existem.

O axioma da potência é necessário para construir este conjunto: como um par ordenado foi definido como (a, b) = {{a}, {a,b}}, temos que este é um conjunto cujos elementos são subconjuntos de A e de $A\cup B\,$:

$\{a\}\subseteq A\,$

$\{a,b\}\subseteq A\cup B\,$

portanto, temos que:

$\{a\}\in P(A\cup B),\{a,b\}\in P(A\cup B)\,$

ou seja:

$(a,b)=\{\{a\},\{a,b\}\}\subseteq P(A\cup B)\,$

e, finalmente,

$(a,b)\in P(P(A\cup B))\,$

Com isso, definimos o produto cartesiano A x B como o conjunto:

$A\times B=\{x\in P(P(A\cup B))|\exists a\in A,b\in B,(x=(a,b))\}\,$

O raciocínio acima descrito (para mostrar que $(a,b)\in P(P(A\cup B))\,$ mostra que o produto cartesiano satisfaz à seguinte propriedade:

$\forall a\in A,b\in B,(a,b)\in A\times B\,$

Propriedades do produto cartesiano

Estas propriedades (e outras parecidas) são fáceis de provar:

• $(A\cup B)\times C=(A\times C)\cup (B\times C)\,$
• $A\times (B\cup C)=(A\times B)\cup (A\times C)\,$
• $A\times (B\cap C)=(A\times B)\cap (A\times C)\,$

Composição de funções

Na conceituação das funções vistas em um capítulo anterior, foi possível definir o que são funções injetivas, sobrejetivas e bijetivas - mas não foi possível conceituar o que é a função composta. Isto porque era preciso construir o produto cartesiano. Temos, portanto:

Sejam $f:A\to B\,$ e $g:B\to C\,$ funções. Considere-se então a relação g o f de A para C cujo gráfico é o subconjunto de $A\times C\,$ definido por:

$graf(g\circ f)=\{(x,z)\in A\times C|\exists y\in B,((x,y)\in graf(f)\land (y,z)\in graf(g)\}\,$.

Lema: $g\circ f\,$ é uma função.

Prova: exercício.

Funções especiais

Sempre partindo do produto cartesiano e obtendo subconjuntos, podemos obter várias funções especiais:

Função constante

Se $b\in B\,$, define-se a função constante $f:A\to B\,$ cujo gráfico é $A\times \{b\}\,$.

Exercício: mostre que esta é uma função.

Função identidade

Para todo conjunto A, a função identidade é a função $id_{A}:A\to A\,$ cujo gráfico são os pares ordenados de forma (a,a).

Exercício: mostre que esta é uma função.

Composição com a função identidade

Se $f:A\to B\,$ é uma função qualquer, então:

$f\circ id_{A}=f\,$

$id_{B}\circ f=f\,$

Função inversa

Se $f:A\to B\,$ é uma função bijetiva, define-se a função inversa como $f^{-1}:B\to A\,$ cujo gráfico são os pares (y,x) em que $(x,y)\in graf(f)\,$.

Exercício: mostre que esta é uma função bijetiva.

Composição da função com a sua inversa

Se $f:A\to B\,$ é uma função bijetiva, então:

$(f\circ f^{-1}):B\to B\,$ é igual à função $id_{B}:B\to B\,$

$(f^{-1}\circ f):A\to A\,$ é igual à função $id_{A}:A\to A\,$

Inversa da composição

Se $f:A\to B\,$ e $g:B\to C\,$ são funções bijetivas, então $g\circ f\,$ é uma função bijetiva, e sua inversa é $(g\circ f)^{-1}=f^{-1}\circ g^{-1}\,$

União de funções

Sejam $f:A\to C\,$ e $g:B\to C\,$ funções quaisquer, em que $A\cap B=\varnothing \,$.

É possível mostrar que existe uma função $h:A\cup B\to C\,$ cujo gráfico é a união dos gráficos de f e g.

Esta função costuma ser representada desta forma:

$h(x)={\begin{cases}f(x)&{\mbox{se }}x\in A,\\g(x)&{\mbox{se }}x\in B.\end{cases}}$

Conjuntos finitos

De posse das ferramentas agregadas com o axioma da potência, em especial as várias propriedades das funções, podemos voltar aos conjuntos finitos (segundo Dedekind), e provar várias propriedades importantes.

Por exemplo: se A é um conjunto infinito e $A\subseteq B\,$, então B é um conjunto infinito.

A prova é simples: seja $f:S\to A\,$ uma função bijetiva em que $S\subset A\,$. Então vamos construir a função $g:(S\cup (B-A))\to B\,$. Como $S\cap (B-A)=\varnothing \,$, a definição abaixo é válida:

$g(x)={\begin{cases}f(x)&{\mbox{se }}x\in S,\\id_{B-A}{x}&{\mbox{se }}x\in B-A.\end{cases}}$

A demonstração de que g é uma função bijetiva é tediosa, mas segue imediatamente das definições. Além disso, como S é um subconjunto próprio de A, este elemento que falta será o elemento que falta em $S\cup (B-A)\subset B\,$.

Surpreendentemente, não podemos ainda avançar - parece óbvio que a união de dois conjuntos finitos também é um conjunto finito, mas esta demonstração requer outro axioma.

Números ordinais

Já definimos o que é um número ordinal (segundo von Neumann), através da propriedade Ord(α) definida:

• 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 ))\,$

Podemos agora provar alguns fatos básicos sobre números ordinais.

O sucessor de um ordinal é um ordinal

Se α é um número ordinal, então seu sucessor $s(\alpha )=\alpha \cup \{\alpha \}\,$ também é.

A demonstração - que não podia ser feita antes - parte da construção da relação ((s(α), s(α)), R) simplesmente definindo o seu gráfico $R=\{(x,y)\in s(\alpha )xs(\alpha )|x\in y\}\,$.

É imediato (pela definição) que $\forall x,y\in s(\alpha ),((x,y)\in R\iff x\in y\,$.

Analogamente, todo elemento de s(α) é um elemento de α (portanto subconjunto de α, logo subconjunto de s(α)) ou é o próprio α, que é um subconjunto de s(α).

Falta mostrar que esta relação é bem ordenada, ou seja:

• $\forall x,y,z\in s(\alpha ),(x\in y\land y\in z\implies x\in z)\,$ (transitividade)
• $\forall x\in s(\alpha ),(\neg x\in x)\,$ (aliorrelatividade)
• $\forall x,y\in s(\alpha ),(x\in y\lor x=y\lor y\in x)\,$ (ordem total)
• $\forall S\subseteq s(\alpha ),(\exists s\in S\implies \exists i\in S,(\forall x\in S,(i=x\lor i\in x)))\,$ (bem-ordenação)

e que o que falta mostrar é se estas propriedades valem quando algum destes x, y, z ou S são iguais (ou contém, no caso de S) α

Na primeira propriedade, a única exceção possível é quando z = α, neste caso, é óbvio que $x\in z\,$.

Na segunda propriedade, basta mostrar que $\alpha \not \in \alpha \,$, mas isto é óbvio, porque se $\alpha \in \alpha \,$ então, pela segunda propriedade aplicada ao conjunto x = α como elemento do ordinal α chega-se a $\alpha \not \in \alpha \,$.

Na terceira propriedade, sendo x igual a α e y diferente, então y é um elemento de α; os demais casos também são imediatos.

Finalmente, seja S um subconjunto de s(α) que inclua o elemento α. Então, se S possui qualquer outro elemento, tomamos i como sendo o mínimo de $S-\{\alpha \}\,$, caso contrário i = α - e isto conclui a demonstração.

O sucessor de um elemento de um ordinal é seu elemento ou igual a ele

Ou seja, sejam α e β ordinais com $\alpha \in \beta \,$. Então $s(\alpha )\in \beta \,$ ou $s(\alpha )=\beta \,$.

Suponhamos então que $s(\alpha )\neq \beta \,$. Já vimos que $s(\alpha )\subseteq \beta \,$, portanto temos que $s(\alpha )\subset \beta \,$. Mas já vimos que, se um ordinal é subconjunto próprio de outro, então é seu elemento, o que completa a prova $s(\alpha )\in \beta \,$

Se dois ordinais são distintos, então um deles é elemento do outro

Suponhamos então que Ord(α) e Ord(β) sejam dois ordinais distintos, e seja $\gamma =\alpha \cap \beta \,$.

Se γ não for nem α nem β então temos que $\gamma \subset \alpha \implies \gamma \in \alpha \,$ e, analogamente, $\gamma \in \beta \,$, portanto $\gamma \in \alpha \cap \beta \,$ o que leva a $s(\gamma )\subseteq \alpha \cap \beta \,$, contradizendo $\gamma =\alpha \cap \beta \,$.

Portanto, γ é igual a α ou igual a β, completando a prova.

Axioma da substituição

Axioma da substituição

Vimos até agora várias definições que pegam um conjunto e formam outro conjunto, único, a partir daquele conjunto.

Por exemplo, temos (sendo x o conjunto sobre o qual vamos operar, e C um conjunto fixo):

• $\bigcup _{y\in x}y\,$ - a união dos elementos de x
• $s(x)=x\cup \{x\}\,$ - o sucessor de x
• $x\cap C\,$, $x\cup C\,$, e várias outras operações

Parece natural perguntar se, sendo A um conjunto fixo, se é possível construir uma função

$f:A\to B\,$

cujo gráfico seja precisamente os pares de valores definidos por estas propriedades, ou seja, aquilo que, intuitivamente (e tradicionalmente) escrevemos como:

• $f(x)=\bigcup _{y\in x}y\,$
• $f(x)=s(x)\,$
• $f(x)=x\cap C\,$, etc

Infelizmente, os axiomas até agora apresentados (mesmo com a inclusão do axioma da potência) não permitem a construção desta função - porque não conseguimos definir que o conjunto B existe!

O axioma da substituição vem preencher esta lacuna. Seu nome é devido ao esquema de substituição, ou seja, se existe alguma regra que associa a cada conjunto x que é elemento de A um único conjunto y (ou seja, esta regra faz o papel de uma função) então existe um conjunto B (único, pelo axioma da extensão) cujos elementos são estes y.

Assim, se existe alguma lei que, para cada conjunto x gera um único conjunto y = f(x), então existem f(A) e a função $f:A\to f(A)\,$ cujo gráfico são os pares (x, f(x)).

Definição

Este axioma é, assim como o axioma da separação, um esquema de axiomas. Seja A um conjunto, e Φ(x, y) uma fórmula bem formada em x e y com a propriedade de:

$\forall x\in A,\exists y,(\Phi (x,y)\land \forall z,(\Phi (x,z)\implies y=z))\,$

ou seja, para todo x, existe um y que satisfaz Φ(x, y) e este y é único.

Com estas condições:

$\exists B,\forall x\in A,\exists y\in B,(\Phi (x,y)\,$.

Notação

Uma fórmula Φ(x, y) que tem esta propriedade de unicidade do y costuma ser representada por y = φ(x). Assim, o que o axioma diz é que, se y = φ(x) está definido para todo elemento x de um conjunto A, então existe (e é único) o conjunto:

$B=\{y|y=\phi (x),x\in A\}\,$

Funções definidas por leis

Aplicando várias vezes o axioma da substituição, podemos justificar a notação tão comum para funções da forma:

$f:A\to B,f(x)=\phi (x)\,$

em que são explicitamente exibidos apenas o conjunto A e a lei y = φ(x).

O que esta notação significa é o seguinte:

O conjunto B é obtido pelo axioma da substituição, usando-se a fórmula bem formada Φ(x,y) = (y = φ(x))

O gráfico da função é obtido pelo axioma da substituição, usando-se a fórmula bem formada Φ(x, z) = (z = (x, φ(x))

Segue direto da definição que esta função é sobrejetiva.

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 $\mathbf {N} (n)=(\Phi (n)\land \forall y\in n,(\Phi (y))\,$, em que Φ(x) é definido por $\Phi (x)=(x=\varnothing \lor \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 $\mathbf {N} (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: $\forall A\neq \varnothing ,\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:

$\forall A,\exists x\in A\implies \exists B\in A,\forall x,(\neg (x\in A\land 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 $\forall x,(x\not \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\not \in x\,$.

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

$\forall x,y,(\neg (x\in y\land 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\not \in x\land y\not \in x\,$, no segundo caso temos $x\not \in y\land y\not \in y\,$. Como já vimos que $x\in x\,$ não é possível, temos finalmente que $y\not \in x\lor x\not \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 \ldots \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 $\forall m\in n,f(m)\in f(s(m))\,$. Então $f(n)\not \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 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 $\Phi (x)=(x=\varnothing \lor \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\neq \varnothing \,$. Aplicando o axioma da regularidade a x, obtemos $y\in x\land 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\implies \varnothing \in K\,$
2. $x\in K\ \land s(x)\in n\implies 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)\land z\in x\,$ também leva a contradição, pois não é possível nem que $z\in K\,$ nem que $z\not \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\not \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.

Axioma da escolha

Axioma da escolha

Este é, sem dúvida, o mais controverso dos axiomas. Os demais axiomas, ao dizerem que determinado conjunto existe (ou não existe), sempre exibem como este conjunto é formado, e, usando-se o axioma da extensão, quase sempre chega-se a um conjunto único.

O axioma da escolha é diferente. Ele diz que determinado conjunto existe, mas não dá nenhuma pista sobre como este conjunto pode ser construído. Vários matemáticos importantes rejeitaram este axioma, e, para consubstanciar a rejeição, apresentaram resultados aparentemente paradoxais para justificar a rejeição.

Um dos argumentos mais interessantes é o paradoxo de Banach-Tarski, que, usando uma construção baseada no axioma da escolha, divide uma esfera em um número finito de partes, aplica translações e rotações a estas partes, e remonta duas esferas idênticas à primeira.

O axioma é apresentado sob várias formas equivalentes. Estas formas serão apresentadas abaixo:

• se o conjunto vazio não é elemento de um conjunto, então existe uma função-escolha neste conjunto
• todo conjunto pode ser bem-ordenado
• se um conjunto for dividido em classes de equivalência, então existe um conjunto com um representante de cada classe
• Lema de Zorn

Função escolha

Uma função escolha em um conjunto A é uma função:

$f:A\to \bigcup _{x\in A}x\,$

em que $f(x)\in x\,$. Por exemplo, no conjunto $A=\{1,2,3\}$, uma função escolha poderia ser dada pelo gráfico $\{(1,0),(2,1),(3,2)\}$. Obviamente, outras funções-escolha são possíveis neste conjunto, como, por exemplo, a função constante $f(x)=0.$

Note-se que se $\varnothing \in A\,$, então $A$ não pode ter função escolha, porque não há como satisfazer $f(\varnothing )\in \varnothing \,$.

O axioma da escolha diz que este é o único caso em que não existe função-escolha. Ou seja:

$\forall \,A\not \ni \varnothing \implies \exists \,f:A\to \bigcup _{x\in A}x,\forall \,x\in A,(f(x)\in x)\,.$

Todo conjunto pode ser bem-ordenado

Já vimos o que é uma relação bem-ordenada em um conjunto $A$: ela é definida por ${\big (}(A,A),<{\big )}$, em que $<$ é um conjunto de pares ordenados de elementos de $A$ com:

• $\forall \,x,y,z\in A,(x<y\land y<x\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,(\neg (S=\varnothing )\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)

O axioma da bem-ordenação diz que para todo conjunto $A$ existe uma relação bem-ordenada em $A$.

Representantes das classes de equivalência

Em resumo, uma relação de equivalência em um conjunto $A$ é uma relação $((A,A),\sim )\,$ satisfazendo:

• $\forall x\in A,(x\sim x)\,$ (reflexividade).
• $\forall x,y\in A,(x\sim y\implies y\sim x)\,$ (simetria).
• $\forall x,y,z\in A,(x\sim y\land y\sim z\implies x\sim z)\,$ (transitividade).

Uma relação de equivalência permite particionar o conjunto $A$ em classes de equivalência, que é construir o conjunto $A/\sim \,$ definido como um subconjunto do conjunto das partes de $A$ por:

$A/\sim \,:={\big \{}x\in \wp (A)\mid \forall \,y,z\in x,(y\sim z){\big \}}.\,$

É fácil mostrar que para todo elemento $x\in A$, existe uma (e apenas uma) classe de equivalência $\left[x\right]\in A/\sim \,$ com $x\in \left[x\right]\,$.

Temos também que se duas classes de equivalência são diferentes, então elas são disjuntas.

A versão do axioma da escolha diz que se um conjunto tem a propriedade acima, então podemos escolher um representante de cada classe, de forma que a interseção de qualquer classe com o conjunto de representantes seja um conjunto unitário.

Na linguagem formal:

$\forall \,B,{\big (}\forall \,x,y\in B,(x\neq y\implies x\cap y=\varnothing ){\big )}\implies \exists \,C\subseteq \bigcup _{x\in B}x,{\Big (}\forall \,x\in B,\exists \,y\in C,(x\cap C=\{y\}){\Big )}.\,$

Lema de Zorn

Uma relação de ordem parcial em um conjunto é uma relação $((A,A),\sim )\,$ satisfazendo:

• $\forall \,x,y,z\in A,(x<y\land y<z\implies x<z)\,$ (transitividade)
• $\forall \,x\in A,(\neg x<x)\,$ (aliorrelatividade)

Uma relação de ordem total em um conjunto é uma relação de ordem parcial com a propriedade de totalidade:

• $\forall \,x,y\in A,(x<y\lor x=y\lor y<x)\,$ (ordem total)

Fixando uma determinada relação de ordem parcial em $A$, temos:

• Um subconjunto ${\mathcal {C}}\subseteq A$ é uma cadeia quando ${\mathcal {C}}$ for totalmente ordenado pela relação, ou seja, $\forall \,x,y\in {\mathcal {C}},(x<y\lor x=y\lor y<x)\,$
• Um elemento $a\in A$ é uma quota superior de um subconjunto $B\subseteq A$ quando $\forall \,x\in B,x<a\,$
• Um elemento $a\in A$ é maximal se $\forall \,x\in A,\neg (a<x)\,$

O Lema de Zorn diz que, se toda cadeia tem uma quota superior, então existe um elemento maximal.

Axioma do infinito

Axioma do infinito

Já vimos vários processos que constroem conjuntos cada vez maiores. Por exemplo, aplicando-se o axioma do par da forma {x}, partindo-se do conjunto vazio, obtemos {}, {{}}, {{{}}}, {{{{}}}}, ....

Ou, aplicando-se o sucessor a partir do conjunto vazio, obtemos 0, 1, 2, 3, .... Pelos axiomas até agora vistos, estas listas não são conjuntos.

O axioma do infinito diz que existe um conjunto que é {0, 1, 2, 3, ...}. A aplicação dos outros axiomas permite construir outros conjuntos infinitos, tais como {0, 1, P(1), P(P(1)), ...}.

O axioma

O axioma diz que existe um conjunto que tem o conjunto vazio como elemento e que, para cada elemento, tem o seu sucessor.

Simbolicamente:

$\exists N,(\varnothing \in N\land \forall x\in N,(s(x)\in N))\,$

Conjunto dos números naturais

O conjunto dos números naturais é construído aplicando-se o axioma da extensão a algum conjunto definido pelo axioma do infinito.

No entanto, para podermos definir $\mathbb {N} =\{n\in N|\mathbf {N} (n)\}\,$ é preciso mostrar que, se temos dois conjuntos A e B que satisfazem o axioma do infinito, então os conjuntos $N_{A}=\{n\in A|\mathbf {N} (n)\}\,$ e $N_{B}=\{n\in B|\mathbf {N} (n)\}\,$ são iguais.

O problema é que precisamos dos demais axiomas para demonstrar isso. Por exemplo, sem usar o axioma da regularidade, não há como provar que um conjunto do tipo A = {0, 1, ..., A} não pode existir; este conjunto satisfaz à definição do axioma do infinito e é um número natural, mas é obviamente bem diferente do conjunto que imaginamos para $\mathbb {N} \,$.

Funções e relações

Já vimos em um capítulo anterior (Explorando os axiomas da extensão, separação, par e união) como definir funções e relações.

Recapitulando, e atualizando com os novos conceitos:

• um conjunto G é o gráfico de uma relação quando todo elemento de G é um par ordenado
• uma relação de um conjunto A para um conjunto B é representada por ((A, B), G), em que $G\subseteq A\times B\,$.
• uma função é uma relação que satisfaz determinados axiomas adicionais, de forma que faz sentido escrever f(x), ou seja, para todo $x\in A\,$, f(x) existe e é único.

Funções

Sejam A e B dois conjuntos quaisquer. Uma correspondência que associe a todo elemento pertencente a A um e apenas um elemento y do conjunto B. Essa correspondência entre os elementos de A e os elementos de B recebe o nome de "aplicação de A em B". Diz-se também "função" como sinônimo para aplicação.

Para dizer que f é uma função de A em B, escreve-se:
${\begin{aligned}f\colon A&\to B\\x&\mapsto f(x)\end{aligned}}$
Ou simplesmente f: A → B.

A letra x, que representa um elemento qualquer de A, chama-se "variável" e o elemento correspondente f(x) chama-se "valor de f em x ou imagem de x por f".

Definindo funções

Um cuidado que se deve ter, em um texto rigoroso, é na hora de definirmos funções.

O leitor deve estar familiarizado com os paradoxos numéricos que são gerados ao se usar expressões como ${\sqrt {.}}\,$ e $\log \,$, sem tomar cuidado com o domínio destas funções. Como exemplo, temos seguinte prova de que 1 = -1: ${\sqrt {x^{2}}}=x\,$, logo ${\sqrt {(-1)^{2}}}=-1\,$, etc.

Em Teoria dos conjuntos não é diferente; definindo-se funções de forma descuidada também é possível gerar paradoxos.

A formas de se definir uma função são:

Pelo seu gráfico

Em que o gráfico, aqui, é o conjunto dos pontos (x, y) em que y = f(x). O cuidado que se deve tomar é:

• o domínio deve ser formado pelos x (e apenas por eles) que aparecem nos pontos (x, y) do gráfico
• se (x, y₁) e (x, y₂) pertencem ao gráfico, então y₁ = y₂.
• o contra-domínio deve ser a imagem ou um superconjunto da imagem

Exemplo: seja G = {(1, 2), (3, 4), (5, 2)}. Uma função definida por este gráfico poderia ser $f:\{1,3,5\}\to \{2,3,4\}\,$, em que f(1) = f(5) = 2 e f(3) = 4.

Por uma fórmula ou expressão

Esta definição é consequência do Axioma da substituição. Se φ(x) for uma expressão (escrita através de símbolos já definidos) que sempre está definida para valores de um conjunto X, então existe uma (única) função sobrejetiva $f:X\to f(X)\,$ em que $f(x)=\phi (x)\,$.

Muitas vezes φ(x) está definida implicitamente, através de uma fórmula Φ(x, y) que se comporta analogamente ao gráfico de uma função. Nestes casos, é preciso mostrar que para todo $x\in X\,$, a fórmula Φ(x, y) é satisfeita por um, e apenas um, y.

Exemplo: sejam X e a conjuntos. Então existe uma única função sobrejetiva $f:X\to f(X)\,$ em que $f(x)=x\cup A\,$.

Por propriedades das funções

Definições por composição de funções, por inversão de funções bijetivas, etc.

Por casos particulares, usando funções já definidas

Este é o caso em que aparecem expressões da forma:

$h(x)={\begin{cases}f(x)&{\mbox{se }}x\in A,\\g(x)&{\mbox{se }}x\in B.\end{cases}}$

Obviamente, temos que $f:A\to C\,$ e $g:B\to C\,$ são funções anteriormente definidas (ou expressões bem definidas), e $A\cap B=\varnothing \,$.

Através do Axioma da Escolha

O Axioma da escolha diz que existe uma função escolha em todo conjunto que não tem o conjunto vazio como seu elemento. Quando necessário, podemos invocar o axioma e dizer que tal função existe.

Este axioma é controverso porque, ao contrário dos demais axiomas, ele não dá a menor ideia de como esta função possa ser construída.

O conjunto dos números naturais

O objetivo deste capítulo é mostrar que o conjunto dos números naturais existe, é único, e provar algumas de suas propriedades básicas.

Um capítulo anterior (Explorando os axiomas da extensão, separação, par e união) definiu o que um conjunto deve satisfazer para ser chamado de um número natural.

O Axioma do infinito diz que existe um conjunto que inclui o conjunto vazio e, para cada elemento seu, inclui o seu sucessor (definido no capítulo Axioma da união). Assim, para cada conjunto que o axioma do infinito provém, podemos definir, pelo Axioma da extensão, um conjunto dos números naturais - o que prova a existência.

Nosso primeiro objetivo é mostrar que todo número natural é elemento de qualquer conjunto dos números naturais; com isto mostramos que este conjunto é único.

Unicidade

Devemos provar o seguinte:

Seja A um conjunto que satisfaz ao Axioma do infinito. Então todo número natural n é um elemento de A.

Como vimos antes, n é um número natural quando:

1. n é o conjunto vazio ou n é um sucessor de algum seu elemento
2. todo elemento de n é o conjunto vazio ou um sucessor de algum seu elemento

Nos capítulos anteriores, mostramos vários teoremas a respeito dos números naturais. Em particular, no capítulo sobre o Axioma da regularidade, mostramos que para todo número natural n e todo subconjunto K de n satisfazendo:

1. $\varnothing \in n\implies \varnothing \in K\,$
2. $x\in K\ \land s(x)\in n\implies s(x)\in K\,$

temos que K = n.

É óbvio como provaremos que todo número natural n é elemento de A: basta formar o subconjunto $K=n\cap A\subseteq n\,$ e mostrar que $K=n\cap A=n\,$.

É imediato que:

1. Como $\varnothing \in A\,$, temos que $\varnothing \in n\implies \varnothing \in n\cap A=K\,$
2. Como $x\in A\implies s(x)\in A\,$ e $K\subseteq A\,$, temos que $x\in K\ \land s(x)\in n\implies s(x)\in n\cap A=K\,$

O que completa a prova.

Assim, sendo A e B dois conjuntos que satisfazem ao Axioma do infinito, pelo Axioma da separação, podemos definir:

• $\mathbb {N} _{A}=\{x\in A|x{\mbox{ eh um numero natural }}\}\,$
• $\mathbb {N} _{B}=\{x\in B|x{\mbox{ eh um numero natural }}\}\,$

é imediato que $\mathbb {N} _{A}=\mathbb {N} _{B}\,$, ou seja, temos que o conjunto dos números naturais existe e é único, o que justifica a definição:

$\mathbb {N} =\{x|x{\mbox{ eh um numero natural }}\}\,$

Princípio da indução finita

A unicidade de $\mathbb {N} \,$ permite imediatamente demonstrar vários fatos.

Por exemplo, seja K um subconjunto de $\mathbb {N} \,$ satisfazendo:

• $\varnothing \in K\,$
• $n\in K\implies s(n)\in K\,$

Então, obviamente, K é um conjunto que satisfaz ao Axioma do infinito, então $\mathbb {N} \subseteq K\,$, completando a prova.

Esta propriedade costuma ser apresentada como um esquema de teoremas: seja P(x) uma propriedade escrita na linguagem formal da teoria dos conjuntos.

Então se:

• $P(\varnothing )\,$
• $P(n)\implies P(s(n))\,$

então

• $\forall n\in \mathbb {N} ,(P(n))\,$

A demonstração parte da construção do conjunto $K=\{n\in \mathbb {N} |P(n)\}\,$, e aplicando-se o resultado anterior para provar que $K=\mathbb {N} \,$.

Todo número natural é um número ordinal

A indução finita torna muito simples várias propriedades dos números naturais.

Por exemplo, podemos provar que todo número natural é um número ordinal (ver a definição de ordinal segundo von Neumann em Explorando os axiomas da extensão, separação, par e união). Isto porque $\varnothing \,$ é um número ordinal, e o sucessor de todo número ordinal também é um número ordinal (ver prova em Axioma da potência) - logo, por indução, todo número natural é um número ordinal.

Axiomas de Peano

O estudo de várias estruturas algébricas complexas parte, quase sempre, do estudo da estrutura mais elementar, que é o conjunto dos números naturais com sua relação de ordem e as operações binárias de soma e produto de números naturais.

Veremos aqui como é possível construir esta estrutura algébrica de forma axiomática.

Uma forma é partir do conjunto $\mathbb {N} \,$ e definí-las.

Mas uma forma mais elegante é partir dos Axiomas de Peano.

Peano, em 1889, propôs nove axiomas que servem como fundamentos da aritmética - na verdade, estes axiomas são tão completos, que servem como fundamentos para quase toda a matemática. Destes axiomas, os quatro primeiros são sobre lógica, e os cinco últimos supõem a existência de um conjunto N satisfazendo:

1. $\exists 0\in N\,$
2. $\exists s:N\to N\,$
3. $\not \exists n\in N,(s(n)=0)\,$
4. $\forall n,m,(s(n)=s(m)\implies n=m)\,$
5. $\forall K\subseteq N,(0\in K\land (n\in K\implies s(n)\in K)\implies K=N)\,$

Em palavras:

1. N possui um elemento, que chamaremos de 0
2. Todo elemento de N possui um sucessor em N; chamamos de s(n) ao sucessor de n
3. Não existe um número cujo sucessor seja o 0
4. Se os sucessores de dois números são iguais, então eles são iguais (equivalente: Se dois elementos de N são diferentes, então seus sucessores são diferentes)
5. Se um subconjunto de N tem 0 como elemento, e este conjunto tem o sucessor de cada um dos seus elementos, então este conjunto é igual a N (princípio da indução)

Mostremos agora que $N=\mathbb {N} \,$, $0=\varnothing \,$ e $s(x)=x\cup \{x\}\,$ é um modelo dos axiomas de Peano.

1. $\varnothing \in \mathbb {N} \,$ - por construção
2. $\exists s:\mathbb {N} \to \mathbb {N} \,$ - por construção
3. $\not \exists n\in \mathbb {N} ,(s(n)=\varnothing )\,$ - verdadeiro, pois s(n) é um conjunto que possui (pelo menos) um elemento - n - logo $s(n)\neq \varnothing \,$
4. $\forall n,m,(s(n)=s(m)\implies n=m)\,$ - deixaremos esta prova para o final
5. o princípio da indução foi demonstrado acima

Então falta mostrar que se dois números tem o mesmo sucessor então eles são iguais. Mas isto segue do axioma da separação, porque se s(n) = s(m) temos que $n\in m\cup \{m\}\,$ e $m\in n\cup \{n\}\,$ e, dos quatro casos seguintes, apenas um deles não viola o axioma da separação:

1. $n\in m\land m\in n\,$
2. $n\in m\land m=n\,$
3. $n=m\land m\in n\,$
4. $n=m\land m=n\,$

que é o caso n = m.

Números ordinais

Nos capítulos anteriores foram apresentados os ordinais segundo von Neumann, e foram exibidas e demonstradas várias propriedades. Este capítulo sintetiza os resultados anteriores e apresenta novos resultados.

Ordinais

Conforme visto no capítulo Explorando os axiomas da extensão, separação, par e união, um ordinal segundo von Neumann é um conjunto α satisfazendo:

• 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 ))\,$

Classificação dos ordinais

Vimos até agora dois tipos de ordinal:

• $\varnothing \,$ - o conjunto vazio
• s(α) - o sucessor de um outro ordinal

Um terceiro tipo de ordinal, ordinal limite, é definido como um ordinal que não é nem o conjunto vazio nem o sucessor de outro ordinal. Ainda não vimos se existe, mas, se existir, este ordinal tem uma propriedade notável:

• Seja α um ordinal limite. Então $\alpha =\bigcup _{x\in \alpha }x\,$.

Prova: já vimos anteriormente que $\bigcup _{x\in \alpha }x\,$ é um ordinal (ver Explorando os axiomas da extensão, separação, par e união). É imediato verificar que $\bigcup _{x\in \alpha }x\subseteq \alpha \,$. Suponha, portanto, que $\bigcup _{x\in \alpha }x\subset \alpha \,$, então mostraremos que α é um ordinal sucessor, o que completa a prova.

Mas se $\bigcup _{x\in \alpha }x\subset \alpha \,$, então temos que existe um elemento $\beta \in \alpha \,$ tal que $\beta \not \in \bigcup _{x\in \alpha }x\,$. Mas vimos anteriormente (ver Axioma da potência) que $\beta \in \alpha \implies (s(\beta )=\alpha \lor s(\beta )\in \alpha )\,$, Neste caso, $s(\beta )\,$ não pode ser elemento de α, portanto α = s(β).

A recíproca é obviamente verdadeira: se temos um ordinal α em que $\alpha =\bigcup _{x\in \alpha }x\,$, então obviamente α não é um ordinal sucessor (é imediato verificar que $\bigcup _{x\in s(\alpha )}x\subset s(\alpha )\,$, pois α é um elemento de s(α) mas não é um elemento de algum elemento de s(α)), então este ordinal é o conjunto vazio ou um ordinal limite.

A boa ordenação dos ordinais

O que foi visto até agora permite escrever as seguintes propriedades:

$Ord(\alpha )\land Ord(\beta )\implies (\alpha \in \beta \lor \alpha =\beta \lor \beta \in \alpha )\,$

$Ord(\alpha )\land Ord(\beta )\implies (\alpha \in \beta \iff \alpha \subset \beta )\,$

Por definição, se S for um conjunto não-vazio de ordinais contido em algum outro ordinal, então S possui elemento mínimo (considerando a relação de ordem total definida por $x\in y\,$).

Este fato pode ser generalizado: se S for um conjunto não-vazio de ordinais, então S tem um elemento mínimo.

Na verdade, podemos generalizar ainda mais: se Φ(x) for uma propriedade escrita na linguagem formal da teoria dos conjuntos através de uma fórmula bem formada, e existir algum ordinal α que satisfaça Φ(α), então existe um ordinal μ que é mínimo para Φ(x), ou seja, que, qualquer que seja x satisfazendo Φ(x) temos que x = μ ou $\mu \in x\,$.

Informalmente, costuma-se dizer que uma propriedade Φ(x) que pode valer ou não valer conforme o conjunto x define uma classe; existem outras apresentações da teoria dos conjuntos em que o conceito de classe faz parte da teoria. Este teorema, então, diz que uma classe não-vazia de ordinais tem um elemento mínimo.

Note-se que este não é apenas um teorema: é um esquema de teoremas, e para cada fórmula Φ(x) temos uma nova versão do teorema.

Prova: suponha que a fórmula Φ(x) seja satisfeita para os ordinais α e β.

Então vamos formar os conjuntos (bem definidos, pelo Axioma da extensão):

$S_{A}=\{x\in s(\alpha )\ |\ \Phi (x)\}\,$

$S_{B}=\{x\in s(\beta )\ |\ \Phi (x)\}\,$

Estes conjuntos são subconjuntos não-vazios de ordinais (por exemplo, $\alpha \in S_{A}\subseteq s(\alpha )\,$), logo podemos tomar seus mínimos

$a=\min _{s(\alpha )}S_{A}\,$

$b=\min _{s(\beta )}S_{B}\,$

Afirmação: a = b.

Prova: sem perda de generalidade, se a ≠ b, suponhamos que $a\in b\,$. Neste caso, como $b\in s(\beta )\,$, pela transitividade, $a\in s(\beta )\,$, ou seja, $a\in S_{B}\,$, contradizendo o fato de b ser mínimo.

Ou seja, se a fórmula Φ(x) é satisfeita por qualquer ordinal, então o mínimo de Φ(x) existe e não depende do ordinal escolhido, ou seja, ele existe e é único.

Cardinalidade

O conceito de cardinalidade é a forma rigorosa de comparar o tamanho dos conjuntos.

Intuitivamente, dois conjuntos tem o mesmo tamanho quando é possível colocar seus elementos em correspondência. Rigorosamente, isto é feito através de funções bijetivas.

Neste capítulo representaremos $A\sim B\,$ quando A e B tiverem o mesmo tamanho.

Definição

Define-se $A\sim B\,$ quando existe uma função bijetiva $f:A\to B\,$.

Segue-se imediatamente da existência da função inversa (demonstrada no capítulo do Axioma da potência) que se $A\sim B\,$ então $B\sim A\,$.

Diz-se também que A e B são equipotentes, que A e B tem a mesma cardinalidade ou, menos formalmente, que A e B tem o mesmo número de elementos.

Propriedades

Segue imediatamente de propriedades de funções bijetivas que:

$A\sim A\,$ - basta usar a função identidade em A

$A\sim B\implies B\sim A\,$ - porque a função inversa de uma função bijetiva existe e é uma função bijetiva

$A\sim B\land B\sim C\implies A\sim C\,$ - porque a composta de funções bijetivas é uma função bijetiva

Bibliografia

• Halmos, Paul Richard. Naive set theory. Springer, 1974. ISBN 978-0-387-90092-6