Jump to content

Unique homomorphic extension theorem

From Wikipedia, the free encyclopedia

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.