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]

The lemma

edit

Let A be a non-empty set, X a subset of AF a set of functions in A, and   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   in G that maps with each function f of arity n in F the following function   in G (G cannot be a bijection).

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

The theorem

edit

If   is a free set generated by X and F, for each function   there is a single function   such that:

 

For each function f of arity n > 0, for each  

 
 
 

Consequence

edit

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

Proof of the theorem

edit

We must define a sequence of functions   inductively, satisfying conditions (1) and (2) restricted to  . For this, we define  , and given   then  shall have the following graph:

 

First we must be certain the graph actually has functionality, since   is a free set, from the lemma we have    when  , 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   and   for some   is possible is if we have     for some   and for some generators   and   in  .

Since   and    are disjoint when   this implies   and  . Being all   in  , we must have  .

Then we have   with  , 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   a sequence of partial functions   such that  . Then,   is a partial function. [1]

Using (3),   is a partial function. Since    then   is total in  .

Furthermore, it is clear from the definition of   that   satisfies (1) and (2). To prove the uniqueness of  , or any other function   that satisfies (1) and (2), it is enough to use a simple induction that shows   and   work for  , and such is proved the Theorem of the Unique Homomorphic Extension.[2]

Example of a particular case

edit

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

  where  

Be  

 

 

 

Be   he inductive closure of   under   and be 

Be  

 

 

 

Then   will be a function that calculates recursively the truth-value of a proposition, and in a way, will be an extension of the function  that associates a truth-value to each atomic proposition, such that:

(1) 

(2)  (Negation)

  (AND Operator)

  (OR Operator)

  (IF-THEN Operator)

References

edit
  1. ^ Gallier (2003), p. 25
  2. ^ Eiter, Thomas; Faber, Wolfgang; Trusczynksi, Miroslaw (2003-08-06). Logic Programming and Nonmonotonic Reasoning: 6th International Conference, LPNMR 2001, Vienna, Austria, September 17-19, 2001. Proceedings. Springer. p. 383. ISBN 9783540454021.
  3. ^ Bloch, Isabelle; Petrosino, Alfredo; Tettamanzi, Andrea G. B. (2006-02-15). Fuzzy Logic and Applications: 6th International Workshop, WILF 2005, Crema, Italy, September 15-17, 2005, Revised Selected Papers. Springer. ISBN 9783540325307.