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:

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

For each function f of arity n > 0, for each $x_1,\dots ,x_n\in X_{+}^n,$

$\hat{h}(f(x_1,\dots ,x_n))=g(\hat{h}(x_1),\dots ,\hat{h}(x_n)),\text{ where }g=d(f)(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,\dots ,x_n),g(h_i(x_1),\dots ,h_i(x_n)))\mid (x_1,\dots ,x_n)\in X_i^n-X_{i-1}^n,f\in F\}\cup \mathrm{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,\dots ,x_n)\in X_{i+1}-X_i$ when $(x_1,\dots ,x_n)\in X_i^n-X_{i-1}^n,(i\ge 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,\dots ,x_m)=f^{\prime }(y_1,\dots ,y_n)$  for some $(x_1,\dots ,x_m)\in X_i^m-X_{i-1}^m,(y_1,\dots ,y_n)\in X_i^n-X_{i-1}^n$ and for some generators $f$ and $f^{\prime }$ in $F$.

Since $f(X_{+}^m)$ and $f^{\prime }(X_{+}^n)$  are disjoint when $f\ne f^{\prime },f(x_1,\dots ,x_m)=f^{\prime }(y_1,\dots ,Y_n)$ this implies $f=f^{\prime }$ and $m=n$. Being all $f\in F$ in $X_{+}^n$, we must have $x_j=y_j,\mathrm{\forall }j,1\le j\le n$.

Then we have $y=z=g(x_1,\dots ,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\ge 0}$ a sequence of partial functions $f_n:A\to B$ such that $f_n\subseteq f_{n+1},\mathrm{\forall }n\ge 0$. Then, $g=(A,\bigcup graph(f_n),B)$ is a partial function. [1]

Using (3), $\hat{h}=\bigcup _{i\ge 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^{\prime }$ that satisfies (1) and (2), it is enough to use a simple induction that shows $\hat{h}$ and $h^{\prime }$ work for $X_i,\mathrm{\forall }i\ge 0$, and such is proved the Theorem of the Unique Homomorphic Extension.[2]

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={\mathrm{\Sigma }}^{*}$ where $\mathrm{\Sigma }=\mathrm{V}\mathrm{a}\mathrm{r}\mathrm{i}\mathrm{a}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{s}\cup \{0,1,2,\dots ,9\}\cup \{+,-,*\}\cup \{(,)\},\text{ where }|*=\mathrm{V}\mathrm{a}\mathrm{r}\mathrm{i}\mathrm{a}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{s}\cup \{0,\dots ,9\}$

Be $F=\{f-,f+,f*\}$

$f:{\mathrm{\Sigma }}^{*}\to {\mathrm{\Sigma }}_{w\mapsto -w}^{*}$

$f:{\mathrm{\Sigma }}^{*}x{\mathrm{\Sigma }}^{*}\to {\mathrm{\Sigma }}_{w_1,w_2\mapsto w_1+w_2}^{*}$

$f:{\mathrm{\Sigma }}^{*}x{\mathrm{\Sigma }}^{*}\to {\mathrm{\Sigma }}_{w_1,w_2\mapsto w_1*w_2}^{*}$

Be $EXPR$ he inductive closure of $X$ under $F$ and be$B=\mathbb{\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}(\varphi )=h(\varphi )$

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

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

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

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

References

• Gallier, Jean (2003), Logic For Computer Science: Foundations of Automatic Theorem Proving, Philadelphia, http://phil.gu.se/logic/books/Gallier:Logic_For_Computer_Science.pdf, retrieved 2017-10-25