Teorema da extensão homomórfica única

Um Pequeno Lema[editar | editar código-fonte]

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[editar | editar código-fonte]

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:

       (1) $\forall x\in X,{\hat {h}}(x)=h(x)$ ;
       Para toda função f de aridade n > 0, para para todo  $x_{1},...,x_{n}\in X_{+}^{n},$

       (2) ${\hat {h}}(f(x_{1},...,x_{n}))=g({\hat {h}}(x_{1}),...,{\hat {h}}(x_{n})),onde\,g=d(f)$

Implicações[editar | editar código-fonte]

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[editar | editar código-fonte]

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

           $\{(f(x_{1},...,x_{n}),g(h_{i}(x_{1}),...,h_{i}(x_{n})))|(x_{1},...,x_{n})\in X_{i}^{n}-X_{i-1}^{n},f\in F\}\cup grafo(h_{i})$  com  $g=d(f)$

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:

 (3)Seja  $(f_{n})_{n\geq 0}$  uma sequencia parcial de funções  $f_{n}:A\to B$  tal que  $f_{n}\subseteq f_{n+1},\forall n\geq 0$ . Então,  $g=(A,\bigcup grafo(f_{n}),B)$  é uma função parcial. [1]

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.[2]

Exemplo de Caso Particular[editar | editar código-fonte]

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: