# Teoria dos conjuntos/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.