homomorphism between partial algebras

Definition

Like subalgebras of partial algebras, there are also three ways to define homomorphisms between partial algebras. Similar to the definition of homomorphisms between algebras, a homomorphism $\phi:\boldsymbol{A}\to\boldsymbol{B}$ between two partial algebras of type $\tau$ is a function from $A$ to $B$ that satisfies the equation

$\phi(f_{\boldsymbol{A}}(a_{1},\ldots,a_{n}))=f_{\boldsymbol{B}}(\phi(a_{1}),% \ldots,\phi(a_{n}))$

(1)

for every $n$ -ary function symbol $f\in\tau$ . However, because $f_{\boldsymbol{A}}$ and $f_{\boldsymbol{B}}$ are not everywhere defined in their respective domains, care must be taken as to what the equation means.

1.

$\phi$ is a homomorphism if, given that $f_{\boldsymbol{A}}(a_{1},\ldots,a_{n})$ is defined, so is $f_{\boldsymbol{B}}(\phi(a_{1}),\ldots,\phi(a_{n}))$ , and equation (1) is satisifed.
2.

$\phi$ is a full homomorphism if it is a homomorphism and, given that $f_{\boldsymbol{B}}(b_{1},\ldots,b_{n})$ is defined and in $\phi(A)$ , for $b_{i}\in\phi(A)$ , there exist $a_{i}\in A$ with $b_{i}=\phi(a_{i})$ , such that $f_{\boldsymbol{A}}(a_{1},\ldots,a_{n})$ is defined.
3.

$\phi$ is a strong homomorphism if it is a homomorphism and, given that $f_{\boldsymbol{B}}(\phi(a_{1}),\ldots,\phi(a_{n}))$ is defined, so is $f_{\boldsymbol{A}}(a_{1},\ldots,a_{n})$ .

We have the following implications:

strong homomorphism $\rightarrow$ full homomorphism $\rightarrow$ homomorphism.

For example, field homomorphisms are strong homomorphisms.

Homomorphisms preserve constants: for each constant symbol $f$ in $\tau$ , $\phi(f_{\boldsymbol{A}})=f_{\boldsymbol{B}}$ . In fact, when restricted to constants, $\phi$ is a bijection between constants of $\boldsymbol{A}$ and constants of $\boldsymbol{B}$ .

When $\boldsymbol{A}$ is an algebra (all partial operations are total), a homomorphism from $\boldsymbol{A}$ is always strong, so that all three notions of homomorphisms coincide.

An isomorphism is a bijective homomorphism $\phi:\boldsymbol{A}\to\boldsymbol{B}$ such that its inverse $\phi^{-1}:\boldsymbol{B}\to\boldsymbol{A}$ is also a homomorphism. An embedding is an injective homomorphism. Isomorphisms and full embeddings are strong.

Homomorphic Images

The various types of homomorphisms and the various types of subalgebras are related. Suppose $\boldsymbol{A}$ and $\boldsymbol{B}$ are partial algebras of type $\tau$ . Let $\phi:A\to B$ be a function, and $C=\phi(A)$ . For each $n$ -ary function symbol $f\in\tau$ , define $n$ -ary partial operation $f_{\boldsymbol{C}}$ on $C$ as follows:

for $b_{1},\ldots,b_{n}\in C$ , $f_{\boldsymbol{C}}(b_{1},\ldots,b_{n})$ is defined iff the set

$D:=\{(a_{1},\ldots,a_{n})\in A^{n}\mid\phi(a_{i})=b_{i}\}\cap\operatorname{dom% }(f_{\boldsymbol{A}})$

is non-empty, where $\operatorname{dom}(f_{\boldsymbol{A}})$ is the domain of definition of $f_{\boldsymbol{A}}$ , and when this is the case, $f_{\boldsymbol{C}}(b_{1},\ldots,b_{n}):=\phi(f_{\boldsymbol{A}}(a_{1},\ldots,a% _{n}))$ , for some $(a_{1},\ldots,a_{n})\in D$ .

If $\phi$ preserves constants (if any), and $f_{C}$ is non-empty for each $f\in\tau$ then $\boldsymbol{C}$ is a partial algebra of type $\tau$ .

Fix an arbitrary $n$ -ary symbol $f\in\tau$ . The following are the basic properties of $\boldsymbol{C}$ :

Proposition 1.

$\phi$ is a homomorphism iff $\boldsymbol{C}$ is a weak subalgebra of $\boldsymbol{B}$ .

Proof.

Suppose first that $\phi$ is a homomorphism. If $n=0$ , then $f_{\boldsymbol{A}}\in A$ , and $f_{\boldsymbol{B}}=\phi(f_{\boldsymbol{A}})\in C$ . If $n>0$ , then for some $a_{1},\ldots,a_{n}\in A$ , $f_{\boldsymbol{A}}(a_{1},\ldots,a_{n})$ is defined, and consequently $f_{\boldsymbol{B}}(\phi(a_{1}),\ldots,\phi(a_{n}))$ is defined, and is equal to $\phi(f_{\boldsymbol{A}}(a_{1},\ldots,a_{n}))\in C$ . By the definition for $f_{\boldsymbol{C}}$ above, $f_{\boldsymbol{C}}(\phi(a_{1}),\ldots,\phi(a_{n})):=\phi(f_{\boldsymbol{A}}(a_% {1},\ldots,a_{n}))$ . This shows that $\boldsymbol{C}$ is a $\tau$ -algebra.

To furthermore show that $\boldsymbol{C}$ is a weak subalgebra of $\boldsymbol{B}$ , assume $f_{\boldsymbol{C}}(b_{1},\ldots,b_{n})$ is defined. Then there are $a_{1},\ldots,a_{n}\in A$ with $b_{i}=\phi(a_{i})$ such that $f_{\boldsymbol{A}}(a_{1},\ldots,a_{n})$ is defined. Since $\phi$ is a homomorphism, $f_{\boldsymbol{B}}(\phi(a_{1}),\ldots,\phi(a_{n}))$ , and hence $f_{\boldsymbol{B}}(b_{1},\ldots,b_{n})$ , is defined. Furthermore, $f_{C}(b_{1},\ldots,b_{n})=\phi(f_{\boldsymbol{A}}(a_{1},\ldots,a_{n}))=f_{% \boldsymbol{B}}(\phi(a_{1}),\ldots,\phi(a_{n}))=f_{\boldsymbol{B}}(b_{1},% \ldots,b_{n})$ . This shows that $\boldsymbol{C}$ is weak.

On the other hand, suppose now that $\boldsymbol{C}$ is a weak subalgebra of $\boldsymbol{B}$ . Suppose $a_{1},\ldots,a_{n}\in A$ and $f_{\boldsymbol{A}}(a_{1},\ldots,a_{n})$ is defined. Let $b_{i}=\phi(a_{i})\in C$ . Then, by the definition of $f_{\boldsymbol{C}}$ , $f_{\boldsymbol{C}}(b_{1},\ldots,b_{n})$ is defined and is equal to $\phi(f_{\boldsymbol{A}}(a_{1},\ldots,a_{n}))$ . Since $\boldsymbol{C}$ is weak, $f_{\boldsymbol{B}}(b_{1},\ldots,b_{n})$ is defined and is equal to $f_{\boldsymbol{C}}(b_{1},\ldots,b_{n})$ . As a result, $\phi(f_{\boldsymbol{A}}(a_{1},\ldots,a_{n}))=f_{\boldsymbol{C}}(b_{1},\ldots,b% _{n})=f_{\boldsymbol{B}}(b_{1},\ldots,b_{n})=f_{\boldsymbol{B}}(\phi(a_{1}),% \ldots,\phi(a_{n}))$ . Hence $\phi$ is a homomorphism. ∎

Proposition 2.

$\phi$ is a full homomorphism iff $\boldsymbol{C}$ is a relative subalgebra of $\boldsymbol{B}$ .

Proof.

Suppose first that $\phi$ is full. Since $\phi$ is a homomorphism, $\boldsymbol{C}$ is weak. Suppose $b_{1},\ldots,b_{n}\in C$ such that $f_{\boldsymbol{A}}(b_{1},\ldots,b_{n})$ is defined and is in $C$ . Since $\phi$ is full, there are $a_{i}\in A$ such that $b_{i}=\phi(a_{i})$ and $f_{\boldsymbol{A}}(a_{1},\ldots,a_{n})$ is defined, and $\phi(f_{\boldsymbol{A}}(a_{1},\ldots,a_{n}))=f_{\boldsymbol{B}}(\phi(a_{1}),% \ldots,\phi(a_{n}))=f_{\boldsymbol{B}}(b_{1},\ldots,b_{n})$ , so that $f_{\boldsymbol{B}}(b_{1},\ldots,b_{n})$ is defined and thus $\boldsymbol{C}$ is a relative subalgebra of $\boldsymbol{B}$ .

Conversely, suppose that $\boldsymbol{C}$ is a relative subalgebra of $\boldsymbol{B}$ . Then $\boldsymbol{C}$ is a weak subalgebra of $\boldsymbol{B}$ and $\phi$ is a homomorphism. To show that $\phi$ is full, suppose that $b_{i}\in C$ such that $f_{\boldsymbol{B}}(b_{1},\ldots,b_{n})$ is defined in $C$ . Then $f_{\boldsymbol{C}}(b_{1},\ldots,b_{n})$ is defined in $C$ and is equal to $f_{\boldsymbol{B}}(b_{1},\ldots,b_{n})$ . This means that there are $a_{i}\in A$ such that $b_{i}=\phi(a_{i})$ , and $f_{\boldsymbol{A}}(a_{1},\ldots,a_{n})$ is defined, showing that $f_{\boldsymbol{A}}$ is full. ∎

Proposition 3.

$\phi$ is a strong homomorphism iff $\boldsymbol{C}$ is a subalgebra of $\boldsymbol{B}$ .

Proof.

Suppose first that $\phi$ is strong. Since $\phi$ is full, $\boldsymbol{C}$ is a relative subalgebra of $\boldsymbol{B}$ . Suppose now that for $b_{i}\in C$ , $f_{\boldsymbol{B}}(b_{1},\ldots,b_{n})$ is defined. Since $b_{i}=\phi(a_{i})$ for some $a_{i}\in A$ , and since $\phi$ is strong, $f_{\boldsymbol{A}}(a_{1},\ldots,a_{n})$ is defined. This means that $f_{\boldsymbol{B}}(b_{1},\ldots,b_{n})=f_{\boldsymbol{B}}(\phi(a_{1}),\ldots,% \phi(a_{n}))=\phi(f_{\boldsymbol{A}}(a_{1},\ldots,a_{n}))$ , which is in $C$ . So $\boldsymbol{C}$ is a subalgebra of $\boldsymbol{B}$ .

Going the other direction, suppose now that $\boldsymbol{C}$ is a subalgebra of $\boldsymbol{B}$ . Since $\boldsymbol{C}$ is a relative subalgebra of $\boldsymbol{B}$ , $\phi$ is full. To show that $\phi$ is strong, suppose $f_{\boldsymbol{B}}(\phi(a_{1}),\ldots,\phi(a_{n}))$ is defined. Then $f_{\boldsymbol{C}}(\phi(a_{1}),\ldots,\phi(a_{n}))$ is defined and is equal to $f_{\boldsymbol{B}}(\phi(a_{1}),\ldots,\phi(a_{n}))$ . By definition of $f_{\boldsymbol{C}}$ , $f_{\boldsymbol{A}}(a_{1},\ldots,a_{n})$ is therefore defined. So $\phi$ is strong. ∎

Definition. Let $\boldsymbol{A}$ and $\boldsymbol{B}$ be partial algebras of type $\tau$ . If $\phi:\boldsymbol{A}\to\boldsymbol{B}$ is a homomorphism, then $\boldsymbol{C}$ , as defined above, is a partial algebra of type $\tau$ , and is called the homomorphic image of $A$ via $\phi$ , and is sometimes written $\phi(\boldsymbol{A})$ .

References

1 G. Grätzer: Universal Algebra, 2nd Edition, Springer, New York (1978).

Title	homomorphism between partial algebras
Canonical name	HomomorphismBetweenPartialAlgebras
Date of creation	2013-03-22 18:42:57
Last modified on	2013-03-22 18:42:57
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	13
Author	CWoo (3771)
Entry type	Definition
Classification	msc 08A55
Classification	msc 03E99
Classification	msc 08A62
Defines	homomorphism
Defines	full homomorphism
Defines	strong homomorphism
Defines	isomorphism
Defines	strong
Defines	homomorphic image
Defines	embedding