# Teorema da extensão homomórfica única
## Um Pequeno Lema

Seja A um conjunto não vazio, X um subconjunto de A, F um conjunto de funções em A, e $X_{+}$ o fecho indutivo de X sob F.
Seja B qualquer conjunto não vazio e seja G o conjunto de funçoes sobre o conjunto B, de forma que exista uma função $d:F\to G$ em G ,que associa com cada função f de aridade n em F a seguinte função $d(f):B^{n}\to B$ em G(G não pode ser uma bijeção).
Partindo deste lema podemos construir o conceito de Extensão Homomórfica Unica.

## O Teorema

Se $X_{+}$ é livremente gerado por X e F , para cada função $h:X\to B$ existe uma única função ${\hat {h}}:X_{+}\to B$ tal que:

## Implicações

As identidades vistas em (1) e (2) demonstram que ${\hat {h}}$ é um homomorfismo, chamado especificamente de Extensão Homomórfica Única de $h$. Para provar o teorema, dois requisitos devem ser satisfeitos: provar que a extensão(${\hat {h}}$) existe e é única (garantindo a ausência de bijeções).

### Prova do Teorema da Extensão Homomórfica Unica

Precisamos definir uma sequencia de funções $h_{i}:X_{i}\to B$ de forma indutiva , satisfazendo as condições (1) e (2) restritas a $X_{i}$. Para isso definimos $h_{0}=h$ e dado $h_{i}$ então $h_{i+1}$ terá o seguinte grafo (lembre-se, estamos tratando um homomorfismo e portanto precisamos provar isso via grafos):
Primeiro devemos checar se o grafo realmente possui funcionalidade, já que $X_{+}$ é livremente gerado, pelo pequeno lema temos que $f(x_{1},...,x_{n})\in X_{i+1}-X_{i}$ quando $(x_{1},...,x_{n})\in X_{i}^{n}-X_{i-1}^{n},(i\geq 0)$,então preciamos apenas determinar a funcionalidade apenas para a primeira parte da união. Tendo que os elementos de G são funções(novamente, como definido pelo lema), a unica possibilidade de ter $(x,y)\in grafo(h_{i})$ e $(x,z)\in grafo(h_{i})$ para algum $x\in X_{i+1}-X_{i}$ é ter $x=f(x_{1},...,x_{m})=f'(y_{1},...,y_{n})$ para algum $(x_{1},...,x_{m})\in X_{i}^{m}-X_{i-1}^{m},(y_{1},...,y_{n})\in X_{i}^{n}-X_{i-1}^{n}$ e para alguns construtores $f$ e ${f'}$ em $F$.
Já que $f(X_{+}^{m})$ e ${f'}(X_{+}^{n})$ são disjuntos quando $f\neq {f'},f(x_{1},...,x_{m})=f'(y_{1},...,Y_{n})$isto implica que $f=f'$ e $m=n$. Sendo todo $f\in F$ em $X_{+}^{n}$,nós temos que ter $x_{j}=y_{j},\forall j,1\leq j\leq n$.
Mas então temos $y=z=g(x_{1},...x_{n})$ com $g=d(f)$, mostrando funcionalidade.
Antes de continuar precisamos utilizar um novo lema que determine regras para funções parciais, ele pode ser escrito como:
Usando (3), ${\hat {h}}=\bigcup _{i\geq 0}h_{i}$ é uma função parcial. Já que $dom({\hat {h}})=\bigcup dom(h_{i})=\bigcup X_{i}=X_{+}$então ${\hat {h}}$ é total em $X_{+}$.
Indo além, é claro pela definição de $h_{i}$ que ${\hat {h}}$ satisfaz (1) e (2). Para provar a unicidade de ${\hat {h}}$, para qualquer outra função ${h'}$ que satifaça (1) e (2), basta usar uma indução simples que mostre que ${\hat {h}}$ e ${h'}$ servem para $X_{i},\forall i\geq 0$, provando assim o Teorema da Extensão Homomórfica Unica.

## Exemplo de Caso Particular

Podemos usar o teorema da extensão no calculo numérico de expressões sobre números inteiros. Primeiramente devemos definir o seguinte:
$A=\Sigma ^{*}$ onde $\Sigma =Variaveis\cup \{{0,1,2,...9}\}\cup \{{+,-,*}\}\cup \{{(,)}\},onde\,*=Variaveis\cup \{{0,...,9}\}$
Seja $F=\{{f-,f+,f*}\}$
$f:\Sigma ^{*}\to \Sigma _{w\mapsto {-w}}^{*}$
$f:\Sigma ^{*}x\Sigma ^{*}\to \Sigma _{w_{1},w_{2}\mapsto {w_{1}+w_{2}}}^{*}$
$f:\Sigma ^{*}x\Sigma ^{*}\to \Sigma _{w_{1},w_{2}\mapsto {w_{1}*w_{2}}}^{*}$
Seja $EXPR$ o fecho indutivo de $X$ sob $F$ e seja $B=\mathbb {Z} ,G={\{Soma(-.-),Mult(-,-),Menos(-)}\}$
Seja $d:F\to G$
$d({f-})=menos$
$d({f+})=mais$
$d({f*})=mult$
Então ${\hat {h}}:X_{+}\to \{{0,1}\}$ será uma função que calcula recursivamente o valor-verdade de uma proposição, e de certa forma, será uma extensão de função $h:X\to \{{0,1}\}$ que associa um valor verdade a cada proposição atômica,tal que:
(1)${\hat {h}}(\phi )=h(\phi )$
(2)${\hat {h}}({(\neg \phi )})=NAO({\hat {h}}(\psi ))$ (Negação)
${\hat {h}}({(\rho \land \theta )})=E({\hat {h}}(\rho ),{\hat {h}}(\theta ))$ (Operação E)
${\hat {h}}({(\rho \lor \theta )})=OU({\hat {h}}(\rho ),{\hat {h}}(\theta ))$ (Operação OU)
${\hat {h}}({(\rho \to \theta )})=SE\,ENTAO({\hat {h}}(\rho ),{\hat {h}}(\theta ))$ (Operação Se-Então)