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

Let A be a non-empty set, X a subset of A, F a set of functions in A, and ${\displaystyle 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 ${\displaystyle d:F\to G}$ in G that maps with each function f of arity n in F the following function ${\displaystyle 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.

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

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

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

${\displaystyle {\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)}$

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

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

${\displaystyle {\{(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 ${\displaystyle X_{+}}$ is a free set, from the lemma we have  ${\displaystyle f(x_{1},\ldots ,x_{n})\in X_{i+1}-X_{i}}$ when ${\displaystyle (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 ${\displaystyle (x,y)\in graph(h_{i})}$ and ${\displaystyle (x,z)\in graph(h_{i})}$ for some ${\displaystyle x\in X_{i+1}-X_{i}}$ is possible is if we have  ${\displaystyle x=f(x_{1},\ldots ,x_{m})=f'(y_{1},\ldots ,y_{n})}$  for some ${\displaystyle (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 ${\displaystyle f}$ and ${\displaystyle {f'}}$ in ${\displaystyle F}$.

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

Then we have ${\displaystyle y=z=g(x_{1},\ldots ,x_{n})}$ with ${\displaystyle 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 ${\displaystyle (f_{n})_{n\geq 0}}$ a sequence of partial functions ${\displaystyle f_{n}:A\to B}$ such that ${\displaystyle f_{n}\subseteq f_{n+1},\forall n\geq 0}$. Then, ${\displaystyle g=(A,\bigcup graph(f_{n}),B)}$ is a partial function. [1] Archived 2017-07-12 at the Wayback Machine

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

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

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

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

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

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

${\displaystyle f:\Sigma ^{*}x\Sigma ^{*}\to \Sigma _{w_{1},w_{2}\mapsto {w_{1}+w_{2}}}^{*}}$

${\displaystyle f:\Sigma ^{*}x\Sigma ^{*}\to \Sigma _{w_{1},w_{2}\mapsto {w_{1}*w_{2}}}^{*}}$

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

Be ${\displaystyle d:F\to G}$

${\displaystyle d({f-})=menos}$

${\displaystyle d({f+})=mais}$

${\displaystyle d({f*})=mult}$

Then ${\displaystyle {\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 ${\displaystyle h:X\to \{{0,1}\}}$that associates a truth-value to each atomic proposition, such that:

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

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

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

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

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

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