Partial algebra is a structure in universal algebra where some of the fundamental operations are partial—that is, they are not required to be defined for every possible tuple of arguments from the underlying set. Partial algebras generalize ordinary (total) algebras and provide a natural formalism for many mathematical and computational systems in which operations may be undefined for certain inputs, such as division in fields, subtraction in the natural numbers, or the evaluation of expressions with uninitialized variables.
Contents
- Definition
- Formal description
- Examples
- Relation to total algebras
- Homomorphisms and substructures
- Applications
- See also
- References
1. Definition
A partial algebra consists of a non‑empty carrier set together with a collection of partial operations (functions that may be undefined on some tuples). The signature of a partial algebra lists the arities of its operations, just as for total algebras, but the interpretation of each operation is a partial function.
2. Formal description
Let $\Sigma = {,f_i\mid i\in I,}$ be a signature, where each $f_i$ has an arity $n_i\in\mathbb{N}$. A partial $\Sigma$-algebra $\mathcal{A}$ is a pair
$$ \mathcal{A}= (A,{,f_i^{\mathcal{A}}\mid i\in I,}) $$
such that
- $A eq\varnothing$ is the carrier set (or universe).
- For each $i\in I$, $f_i^{\mathcal{A}}$ is a partial function
$$ f_i^{\mathcal{A}}: \operatorname{Dom}(f_i^{\mathcal{A}})\subseteq A^{,n_i}\longrightarrow A . $$
The domain $\operatorname{Dom}(f_i^{\mathcal{A}})$ may be a proper subset of the full Cartesian power $A^{,n_i}$; when the tuple is outside the domain, the operation is said to be undefined.
A partial algebra is total if every operation is defined on all possible argument tuples; then it coincides with an ordinary universal algebra.
3. Examples
| Example | Carrier set | Partial operation(s) | Reason for partiality |
|---|---|---|---|
| Field with division | A field $F$ | Division $/\colon F\times F\to F$ | Undefined when divisor = 0 |
| Natural numbers with subtraction | $\mathbb{N}$ | Subtraction $-\colon \mathbb{N}\times\mathbb{N}\to \mathbb{N}$ | Undefined when the second argument exceeds the first |
| Partial groupoid | Set of strings | Concatenation only defined for strings of bounded length | Technical restrictions (e.g., memory limits) |
| Term algebra with undefined terms | Set of syntactic terms | Evaluation map $eval$ | Undefined when a variable has no assigned value |
| Computer program states | Set of memory configurations | Assignment operation on uninitialized variables | Undefined if variable is not yet allocated |
4. Relation to total algebras
Every total algebra can be viewed as a partial algebra with all operations total. Conversely, a partial algebra can be totalized by adjoining a distinguished element (often denoted $\bot$ or “undefined”) and extending each partial operation to be total by mapping undefined inputs to $\bot$. This construction yields a total completion or extension of the original partial algebra.
5. Homomorphisms and substructures
Homomorphism: A map $h: A\to B$ between partial algebras $\mathcal{A}$ and $\mathcal{B}$ (with the same signature) is a homomorphism if for every operation $f$ and every tuple $\bar a$ in $\operatorname{Dom}(f^{\mathcal{A}})$,
$$ h\bigl(f^{\mathcal{A}}(\bar a)\bigr) = f^{\mathcal{B}}\bigl(h(\bar a)\bigr) $$
and additionally the image of a defined tuple must be defined:
$$ \bar a\in\operatorname{Dom}(f^{\mathcal{A}}) \implies h(\bar a)\in\operatorname{Dom}(f^{\mathcal{B}}). $$
Subalgebra: A subset $S\subseteq A$ forms a subalgebra if for every operation $f$ and every tuple $\bar s\in S^{,n_f}$ that lies in $\operatorname{Dom}(f^{\mathcal{A}})$, we have
$$ f^{\mathcal{A}}(\bar s)\in S. $$
Thus subalgebras must be closed under those parts of the operations that are defined on the subset.
6. Applications
- Computer Science – Semantics of programming languages often involve partial functions (e.g., evaluation may diverge). Partial algebras give a concise algebraic framework for reasoning about such semantics.
- Algebraic Logic – Partial algebras model logical connectives that are not total, such as the conditional (if‑then‑else) operator in three‑valued logics.
- Domain Theory – Domains are partially ordered sets equipped with partial operations; partial algebras formalize the algebraic side of domains.
- Database Theory – Operations like division or outer joins that may be undefined for certain tuples are naturally expressed as partial operations.
- Mathematical Structures with Restrictions – Many classical structures (fields, rings, vector spaces) become partial algebras when restricted to subsets where certain operations lose totality (e.g., division in a field).
7. See also
- Universal algebra
- Total algebra
- Partial function
- Kleene algebra (partial version)
- Domain theory
- Algebraic specification
8. References
- S. Burris & H.P. Sankappanavar, A Course in Universal Algebra, Springer, 1981 – Chapter 6 discusses partial algebras.
- J. A. Goguen, “Partial Algebras for Computer Science,” Journal of Computer and System Sciences, vol. 15, 1978, pp. 165–190.
- R. B. Crole, Categories for Types, Cambridge University Press, 1993 – Section on partiality in categorical algebra.
- W. Rounds, “Partial Algebras and Their Applications,” Algebra Universalis, 2004.
- M. L. D. Anderson, “Totalization of Partial Algebras,” Proceedings of the London Mathematical Society, 1999.