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 $\varphi :𝑨\to 𝑩$ between two partial algebras of type $\tau$ is a function from $A$ to $B$ that satisfies the equation

$$\varphi (f_{𝑨}(a_1,\mathrm{\dots },a_n))=f_{𝑩}(\varphi (a_1),\mathrm{\dots },\varphi (a_n))$$(1)

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

1. $\varphi$ is a homomorphism if, given that $f_{𝑨}(a_1,\mathrm{\dots },a_n)$ is defined, so is $f_{𝑩}(\varphi (a_1),\mathrm{\dots },\varphi (a_n))$, and equation (1) is satisifed.

2. $\varphi$ is a full homomorphism if it is a homomorphism and, given that $f_{𝑩}(b_1,\mathrm{\dots },b_n)$ is defined and in $\varphi (A)$, for $b_i\in \varphi (A)$, there exist $a_i\in A$ with $b_i=\varphi (a_i)$, such that $f_{𝑨}(a_1,\mathrm{\dots },a_n)$ is defined.

3. $\varphi$ is a strong homomorphism if it is a homomorphism and, given that $f_{𝑩}(\varphi (a_1),\mathrm{\dots },\varphi (a_n))$ is defined, so is $f_{𝑨}(a_1,\mathrm{\dots },a_n)$.

We have the following implications:

strong homomorphism $\to$ full homomorphism $\to$ homomorphism.

For example, field homomorphisms are strong homomorphisms.

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

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

An isomorphism is a bijective homomorphism $\varphi :𝑨\to 𝑩$ such that its inverse ${\varphi }^{-1}:𝑩\to 𝑨$ 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 $𝑨$ and $𝑩$ are partial algebras of type $\tau$. Let $\varphi :A\to B$ be a function, and $C=\varphi (A)$. For each $n$-ary function symbol $f\in \tau$, define $n$-ary partial operation $f_{𝑪}$ on $C$ as follows:

for $b_1,\mathrm{\dots },b_n\in C$, $f_{𝑪}(b_1,\mathrm{\dots },b_n)$ is defined iff the set

$$D:=\{(a_1,\mathrm{\dots },a_n)\in A^n\mid \varphi (a_i)=b_i\}\cap \mathrm{dom}(f_{𝑨})$$

is non-empty, where $\mathrm{dom}(f_{𝑨})$ is the domain of definition of $f_{𝑨}$, and when this is the case, $f_{𝑪}(b_1,\mathrm{\dots },b_n):=\varphi (f_{𝑨}(a_1,\mathrm{\dots },a_n))$, for some $(a_1,\mathrm{\dots },a_n)\in D$.

If $\varphi$ preserves constants (if any), and $f_C$ is non-empty for each $f\in \tau$ then $𝑪$ is a partial algebra of type $\tau$.

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

Proposition 1.

$\varphi$ is a homomorphism iff $𝐂$ is a weak subalgebra of $𝐁$.

Proof.

Suppose first that $\varphi$ is a homomorphism. If $n=0$, then $f_{𝑨}\in A$, and $f_{𝑩}=\varphi (f_{𝑨})\in C$. If $n>0$, then for some $a_1,\mathrm{\dots },a_n\in A$, $f_{𝑨}(a_1,\mathrm{\dots },a_n)$ is defined, and consequently $f_{𝑩}(\varphi (a_1),\mathrm{\dots },\varphi (a_n))$ is defined, and is equal to $\varphi (f_{𝑨}(a_1,\mathrm{\dots },a_n))\in C$. By the definition for $f_{𝑪}$ above, $f_{𝑪}(\varphi (a_1),\mathrm{\dots },\varphi (a_n)):=\varphi (f_{𝑨}(a_1,\mathrm{\dots },a_n))$. This shows that $𝑪$ is a $\tau$-algebra.

To furthermore show that $𝑪$ is a weak subalgebra of $𝑩$, assume $f_{𝑪}(b_1,\mathrm{\dots },b_n)$ is defined. Then there are $a_1,\mathrm{\dots },a_n\in A$ with $b_i=\varphi (a_i)$ such that $f_{𝑨}(a_1,\mathrm{\dots },a_n)$ is defined. Since $\varphi$ is a homomorphism, $f_{𝑩}(\varphi (a_1),\mathrm{\dots },\varphi (a_n))$, and hence $f_{𝑩}(b_1,\mathrm{\dots },b_n)$, is defined. Furthermore, $f_C(b_1,\mathrm{\dots },b_n)=\varphi (f_{𝑨}(a_1,\mathrm{\dots },a_n))=f_{𝑩}(\varphi (a_1),\mathrm{\dots },\varphi (a_n))=f_{𝑩}(b_1,\mathrm{\dots },b_n)$. This shows that $𝑪$ is weak.

On the other hand, suppose now that $𝑪$ is a weak subalgebra of $𝑩$. Suppose $a_1,\mathrm{\dots },a_n\in A$ and $f_{𝑨}(a_1,\mathrm{\dots },a_n)$ is defined. Let $b_i=\varphi (a_i)\in C$. Then, by the definition of $f_{𝑪}$, $f_{𝑪}(b_1,\mathrm{\dots },b_n)$ is defined and is equal to $\varphi (f_{𝑨}(a_1,\mathrm{\dots },a_n))$. Since $𝑪$ is weak, $f_{𝑩}(b_1,\mathrm{\dots },b_n)$ is defined and is equal to $f_{𝑪}(b_1,\mathrm{\dots },b_n)$. As a result, $\varphi (f_{𝑨}(a_1,\mathrm{\dots },a_n))=f_{𝑪}(b_1,\mathrm{\dots },b_n)=f_{𝑩}(b_1,\mathrm{\dots },b_n)=f_{𝑩}(\varphi (a_1),\mathrm{\dots },\varphi (a_n))$. Hence $\varphi$ is a homomorphism.∎

Proposition 2.

$\varphi$ is a full homomorphism iff $𝐂$ is a relative subalgebra of $𝐁$.

Proof.

Suppose first that $\varphi$ is full. Since $\varphi$ is a homomorphism, $𝑪$ is weak. Suppose $b_1,\mathrm{\dots },b_n\in C$ such that $f_{𝑨}(b_1,\mathrm{\dots },b_n)$ is defined and is in $C$. Since $\varphi$ is full, there are $a_i\in A$ such that $b_i=\varphi (a_i)$ and $f_{𝑨}(a_1,\mathrm{\dots },a_n)$ is defined, and $\varphi (f_{𝑨}(a_1,\mathrm{\dots },a_n))=f_{𝑩}(\varphi (a_1),\mathrm{\dots },\varphi (a_n))=f_{𝑩}(b_1,\mathrm{\dots },b_n)$, so that $f_{𝑩}(b_1,\mathrm{\dots },b_n)$ is defined and thus $𝑪$ is a relative subalgebra of $𝑩$.

Conversely, suppose that $𝑪$ is a relative subalgebra of $𝑩$. Then $𝑪$ is a weak subalgebra of $𝑩$ and $\varphi$ is a homomorphism. To show that $\varphi$ is full, suppose that $b_i\in C$ such that $f_{𝑩}(b_1,\mathrm{\dots },b_n)$ is defined in $C$. Then $f_{𝑪}(b_1,\mathrm{\dots },b_n)$ is defined in $C$ and is equal to $f_{𝑩}(b_1,\mathrm{\dots },b_n)$. This means that there are $a_i\in A$ such that $b_i=\varphi (a_i)$, and $f_{𝑨}(a_1,\mathrm{\dots },a_n)$ is defined, showing that $f_{𝑨}$ is full.∎

Proposition 3.

$\varphi$ is a strong homomorphism iff $𝐂$ is a subalgebra of $𝐁$.

Proof.

Suppose first that $\varphi$ is strong. Since $\varphi$ is full, $𝑪$ is a relative subalgebra of $𝑩$. Suppose now that for $b_i\in C$, $f_{𝑩}(b_1,\mathrm{\dots },b_n)$ is defined. Since $b_i=\varphi (a_i)$ for some $a_i\in A$, and since $\varphi$ is strong, $f_{𝑨}(a_1,\mathrm{\dots },a_n)$ is defined. This means that $f_{𝑩}(b_1,\mathrm{\dots },b_n)=f_{𝑩}(\varphi (a_1),\mathrm{\dots },\varphi (a_n))=\varphi (f_{𝑨}(a_1,\mathrm{\dots },a_n))$, which is in $C$. So $𝑪$ is a subalgebra of $𝑩$.

Going the other direction, suppose now that $𝑪$ is a subalgebra of $𝑩$. Since $𝑪$ is a relative subalgebra of $𝑩$, $\varphi$ is full. To show that $\varphi$ is strong, suppose $f_{𝑩}(\varphi (a_1),\mathrm{\dots },\varphi (a_n))$ is defined. Then $f_{𝑪}(\varphi (a_1),\mathrm{\dots },\varphi (a_n))$ is defined and is equal to $f_{𝑩}(\varphi (a_1),\mathrm{\dots },\varphi (a_n))$. By definition of $f_{𝑪}$, $f_{𝑨}(a_1,\mathrm{\dots },a_n)$ is therefore defined. So $\varphi$ is strong.∎

Definition. Let $𝑨$ and $𝑩$ be partial algebras of type $\tau$. If $\varphi :𝑨\to 𝑩$ is a homomorphism, then $𝑪$, as defined above, is a partial algebra of type $\tau$, and is called the homomorphic image of $A$ via $\varphi$, and is sometimes written $\varphi (𝑨)$.