Unique homomorphic extension theorem

The unique homomorphic extension theorem is a result in mathematical logic which formalizes the intuition that the truth or falsity of a statement can be deduced from the truth values of its parts.

The lemma

Let A be a non-empty set, X a subset of A, F a set of functions in A, and $X_{+}$ the inductive closure of X under F.

Let be B any non-empty set and let G be the set of functions on B, such that there is a function $d:F\to G$ in G that maps with each function f of arity n in F the following function $d(f):B^{n}\to B$ in G (G cannot be a bijection).

From this lemma we can now build the concept of unique homomorphic extension.

The theorem

If $X_{+}$ is a free set generated by X and F, for each function $h:X\to B$ there is a single function ${\hat {h}}:X_{+}\to B$ such that:

$\forall x\in X,{\hat {h}}(x)=h(x);\qquad (1)$

For each function f of arity n > 0, for each $x_{1},\ldots ,x_{n}\in X_{+}^{n},$

${\hat {h}}(f(x_{1},\ldots ,x_{n}))=g({\hat {h}}(x_{1}),\ldots ,{\hat {h}}(x_{n})),{\text{ where }}g=d(f)\qquad (2)$

Consequence

The identities seen in (1) e (2) show that ${\hat {h}}$ is an homomorphism, specifically named the unique homomorphic extension of $h$. To prove the theorem, two requirements must be met: to prove that the extension (${\hat {h}}$) exists and is unique (assuring the lack of bijections).

Proof of the theorem

We must define a sequence of functions $h_{i}:X_{i}\to B$ inductively, satisfying conditions (1) and (2) restricted to $X_{i}$. For this, we define $h_{0}=h$, and given $h_{i}$ then $h_{i+1}$shall have the following graph:

${\{(f(x_{1},\ldots ,x_{n}),g(h_{i}(x_{1}),\ldots ,h_{i}(x_{n})))\mid (x_{1},\ldots ,x_{n})\in X_{i}^{n}-X_{i-1}^{n},f\in F\}}\cup {\operatorname {graph} (h_{i})}{\text{ with }}g=d(f)$

First we must be certain the graph actually has functionality, since $X_{+}$ is a free set, from the lemma we have  $f(x_{1},\ldots ,x_{n})\in X_{i+1}-X_{i}$ when $(x_{1},\ldots ,x_{n})\in X_{i}^{n}-X_{i-1}^{n},(i\geq 0)$, so we only have to determine the functionality for the left side of the union. Knowing that the elements of G are functions(again, as defined by the lemma), the only instance where $(x,y)\in graph(h_{i})$ and $(x,z)\in graph(h_{i})$ for some $x\in X_{i+1}-X_{i}$ is possible is if we have  $x=f(x_{1},\ldots ,x_{m})=f'(y_{1},\ldots ,y_{n})$  for some $(x_{1},\ldots ,x_{m})\in X_{i}^{m}-X_{i-1}^{m},(y_{1},\ldots ,y_{n})\in X_{i}^{n}-X_{i-1}^{n}$ and for some generators $f$ and ${f'}$ in $F$.

Since $f(X_{+}^{m})$ and ${f'}(X_{+}^{n})$  are disjoint when $f\neq {f'},f(x_{1},\ldots ,x_{m})=f'(y_{1},\ldots ,Y_{n})$ this implies $f=f'$ and $m=n$. Being all $f\in F$ in $X_{+}^{n}$, we must have $x_{j}=y_{j},\forall j,1\leq j\leq n$.

Then we have $y=z=g(x_{1},\ldots ,x_{n})$ with $g=d(f)$, displaying functionality.

Before moving further we must make use of a new lemma that determines the rules for partial functions, it may be written as:

 (3)Be $(f_{n})_{n\geq 0}$ a sequence of partial functions $f_{n}:A\to B$ such that $f_{n}\subseteq f_{n+1},\forall n\geq 0$. Then, $g=(A,\bigcup graph(f_{n}),B)$ is a partial function.  Archived 2017-07-12 at the Wayback Machine

Using (3), ${\hat {h}}=\bigcup _{i\geq 0}h_{i}$ is a partial function. Since  $dom({\hat {h}})=\bigcup dom(h_{i})=\bigcup X_{i}=X_{+}$ then ${\hat {h}}$ is total in $X_{+}$.

Furthermore, it is clear from the definition of $h_{i}$ that ${\hat {h}}$ satisfies (1) and (2). To prove the uniqueness of ${\hat {h}}$, or any other function ${h'}$ that satisfies (1) and (2), it is enough to use a simple induction that shows ${\hat {h}}$ and ${h'}$ work for $X_{i},\forall i\geq 0$, and such is proved the Theorem of the Unique Homomorphic Extension. Archived 2017-07-12 at the Wayback Machine

Example of a particular case

We can use the theorem of unique homomorphic extension for calculating numeric expressions over whole numbers. First, we must define the following:

$A=\Sigma ^{*}$ where $\Sigma =\mathrm {Variables} \cup \{0,1,2,\ldots ,9\}\cup \{+,-,*\}\cup \{(,)\},{\text{ where }}|*=\mathrm {Variables} \cup \{{0,\ldots ,9}\}$

Be $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}}}^{*}$

Be $EXPR$ he inductive closure of $X$ under $F$ and be$B=\mathbb {Z} ,G={\{Soma(-.-),Mult(-,-),Menos(-)}\}$

Be $d:F\to G$

$d({f-})=menos$

$d({f+})=mais$

$d({f*})=mult$

Then ${\hat {h}}:X_{+}\to \{{0,1}\}$ will be a function that calculates recursively the truth-value of a proposition, and in a way, will be an extension of the function $h:X\to \{{0,1}\}$that associates a truth-value to each atomic proposition, such that:

(1)${\hat {h}}(\phi )=h(\phi )$

(2)${\hat {h}}({(\neg \phi )})=NAO({\hat {h}}(\psi ))$ (Negation)

${\hat {h}}({(\rho \land \theta )})=E({\hat {h}}(\rho ),{\hat {h}}(\theta ))$ (AND Operator)

${\hat {h}}({(\rho \lor \theta )})=OU({\hat {h}}(\rho ),{\hat {h}}(\theta ))$ (OR Operator)

${\hat {h}}({(\rho \to \theta )})=SE\,ENTAO({\hat {h}}(\rho ),{\hat {h}}(\theta ))$ (IF-THEN Operator)

References

• Gallier, Jean (2003), Logic For Computer Science: Foundations of Automatic Theorem Proving (PDF), Philadelphia, archived from the original (PDF) on 2017-07-12, retrieved 2017-10-25{{citation}}: CS1 maint: location missing publisher (link)