congruence on a partial algebra
is a congruence relation on if, given that
both and are defined,
is a strong congruence relation on if it is a congruence relation on , and, given
then is defined.
If is a homomorphism, then the equivalence relation induced by on is a congruence relation. Furthermore, if is a strong, so is .
Let be an -ary function symbol. Suppose and both and are defined. Then , and therefore
so . In other words, is a congruence relation.
Now, suppose in addition that is a strong homomorphism. Again, let . Assume is defined. Since , we get
Since is strong, is defined, which means that is strong. ∎
Congruences as Subalgebras
If is a partial algebra of type , then the direct power is a partial algebra of type . A binary relation on may be viewed as a subset of . For each -ary operation on , take the restriction on , and call it . For , is defined in iff is defined at all, and its value is in . When is defined in , its value is set as . This turns into a partial algebra. However, the type of is only when is non-empty for each function symbol . In particular,
Pick any -ary function symbol . Then is defined for some . Then is defined and is equal to , which is in , since is reflexive. This shows that is defined. As a result, is a partial algebra of type . Furthermore, by virtue of the way is defined for each , is a relative subalgebra of . ∎
An equivalence relation on is a congruence iff is a subalgebra of .
First, assume that is a congruence relation on . Since is reflexive, is a relative subalgebra of . Now, suppose exists, where . Then both exist. Since is a congruence, . In other words, . Hence is a subalgebra of .
Conversely, assume is a subalgebra of . Suppose and both and are defined. Then is defined. Since is a subalgebra of , is also defined, and . This shows that is a congruence relation on . ∎
Quotient Partial Algebras
With congruence relations defined, one may then define quotient partial algebras: given a partial algebra of type and a congruence relation on , the quotient partial algebra of by is the partial algebra whose underlying set is , the set of congruence classes, and for each -ary function symbol , is defined iff there are such that and is defined. When this is the case:
Suppose there are such that , or , and is defined, then and , or, equivalently, , so that is a well-defined operation.
In addition, it is easy to see that is in fact a -algebra. For each -ary , pick such that is defined. Then is defined, and is equal to .
Let and be defined as above. Then , given by , is a surjective full homomorphism, and . Furthermore, is a strong homomorphism iff is a strong congruence relation.
is obviously surjective. The fact that is a full homomorphism follows directly from the definition of , for each . Next, iff iff . This proves the first statement.
The next statement is proved as follows:
. If and is defined, then is defined, which is just , and, as is strong, is defined, showing that is strong.
. Suppose is defined. Then there are with such that is defined. Since is strong, is defined as well, which shows that is strong. ∎
- 1 G. Grätzer: Universal Algebra, 2nd Edition, Springer, New York (1978).
|Title||congruence on a partial algebra|
|Date of creation||2013-03-22 18:43:01|
|Last modified on||2013-03-22 18:43:01|
|Last modified by||CWoo (3771)|
|Defines||strong congruence relation|
|Defines||quotient partial algebra|