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

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

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

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. http://phil.gu.se/logic/books/Gallier:Logic_For_Computer_Science.pdf 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.http://phil.gu.se/logic/books/Gallier:Logic_For_Computer_Science.pdf

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:

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