View source for Direct product is cancellative for finite algebras in any variety with zero

==Statement==

Suppose <math>\mathcal{V}</math> is a [[variety of algebras]] that is a [[variety with zero]]. Suppose <math>G,H,K</math> are ''finite'' algebras in <math>\mathcal{V}</math>. Further, suppose that the algebras <math>G \times H</math> and <math>G \times K</math> are isomorphic as algebras in <math>\mathcal{V}</math>. Then, <math>H</math> is isomorphic to <math>K</math>.

==Related facts==

* [[Direct product is cancellative for finite groups]]: Essentially the same proof, tailored to groups (the key specific detail for groups is that the congruences can be described using the [[normal subgroup]]s that function as their kernels).

==Facts used==

# [[uses::Homomorphism set to direct product is Cartesian product of homomorphism sets]]: If <math>A,B,C</math> are algebras, then there is a natural bijection:
#* <math>\operatorname{Hom}(A,B) \times \operatorname{Hom}(A,C) \leftrightarrow \operatorname{Hom}(A,B \times C)</math>.
#* The bijection is defined as: <math>(\alpha,\beta) \mapsto (g \mapsto (\alpha(g),\beta(g))</math>.
# [[uses::Homomorphism set is disjoint union of injective homomorphism sets]]: For algebras <math>A</math> and <math>B</math>, let <math>\operatorname{Hom}(A,B)</math> denotes the set of homomorphisms from <math>A</math> to <math>B</math>, and <math>\operatorname{IHom}(A,B)</math> denote the set of injective homomorphisms from <math>A</math> to <math>B</math>. Then we have:

<math>\operatorname{Hom}(A,B) = \bigsqcup_{~} \operatorname{IHom}(A/~, B)</math>.

Here <math>~</math> varies over the set of all possible [[congruence]]s on the algebra <math>A</math>.
==Proof==

'''Given''': Finite algebras <math>G, H, K</math> such that <math>G \times H \cong G \times K</math>.

'''To prove''': <math>H \cong K</math>.

'''Proof''': Let <math>L</math> be an arbitrary finite algebra in <math>\mathcal{V}</math>. Note that the trivial homomorphism refers to the map that sends every element to the zero element.

{| class="sortable" border="1"
! Step no. !! Assertion/construction !! Facts used !! Given data used !! Previous steps used !! Explanation
|-
| 1 || <math>|\operatorname{Hom}(L,G \times H)| = |\operatorname{Hom}(L,G)||\operatorname{Hom}(L,H)|</math> as an equality of finite numbers. || Fact (1) || <math>G,H</math> are finite || || <toggledisplay>By Fact (1), there is a bijection between <math>\operatorname{Hom}(L,G) \times \operatorname{Hom}(L,H)</math> and <math>\operatorname{Hom}(L,G\times H)</math>. Since all algebras involved are finite, so are all <math>\operatorname{Hom}</math>-sets, so the bijection gives a fact about cardinalities.</toggledisplay>
|-
| 2 || <math>|\operatorname{Hom}(L,G \times K)| = |\operatorname{Hom}(L,G)||\operatorname{Hom}(L,K)|</math> as an equality of finite numbers. || Fact (1) || <math>G,K</math> are finite || || <toggledisplay>By Fact (1), there is a bijection between <math>\operatorname{Hom}(L,G) \times \operatorname{Hom}(L,K)</math> and <math>\operatorname{Hom}(L,G\times K)</math>. Since all algebras involved are finite, so are all <math>\operatorname{Hom}</math>-sets, so the bijection gives a fact about cardinalities.</toggledisplay>
|-
| 3 || <math>|\operatorname{Hom}(L,G \times H)| = |\operatorname{Hom}(L,G \times K)|</math> as an equality of finite numbers. || || <math>G \times H \cong G \times K</math> ||  || The number of homomorphisms to an algebra depends only on its isomorphism type.
|-
| '''4''' || <math>|\operatorname{Hom}(L,H)| = |\operatorname{Hom}(L,K)|</math> as an equality of finite numbers. || || || Steps (1),(2),(3) || <toggledisplay>Combining the previous three steps, we get <math>|\operatorname{Hom}(L,G)||\operatorname{Hom}(L,H)| = |\operatorname{Hom}(L,G)||\operatorname{Hom}(L,K)|</math>. Note now that <math>|\operatorname{Hom}(L,G)|</math> is nonzero since there is at least one homomorphism (the trivial homomorphism) between the algebras. So, it can be canceled from the product of numbers (''it is critical here that we are working with finite numbers rather than infinite cardinals'')</toggledisplay>
|-
| 5 || For any finite algebra <math>L</math>, the number of injective homomorphisms from <math>L</math> to <math>H</math> equals the number of injective homomorphisms from <math>L</math> to <math>K</math>. We show this by induction on the order of <math>L</math>. In other words, <math>|\operatorname{IHom}(L,H)| = |\operatorname{IHom}(L,K)|</math> || Fact (2) || || Step (4) || <toggledisplay>''Base case for induction on the order of <math>L</math>'': Case of zero algebra is obvious.<br>''Inductive step'': By Fact (2), we have<math>|\operatorname{Hom}(L,H)| = \sum_{~} |\operatorname{IHom}(L/~,H)|</math> and <math>|\operatorname{Hom}(L,K)| = \sum_{~} |\operatorname{IHom}(L/~,K)|</math>. By induction on the order, we can assume that for every congruence other than the discrete congruence, <math>\operatorname{IHom}(L/~,H) = \operatorname{IHom}(L/~,K)</math>. Since the left sides of both equations are equal by step (4), we obtain that <math>\operatorname{IHom}(L,H) = \operatorname{IHom}(L,K)</math>.</toggledisplay>
|-
| 6 || <math>H</math> is isomorphic to a subalgebra of <math>K</math> and <math>K</math> is isomorphic to a subalgebra of <math>H</math> || || <math>H,K</math> are finite || Step (5) || <toggledisplay>Set <math>L = H</math> in step (5). Clearly, <math>\operatorname{IHom}(H,H)</math> is nonempty (it contains the identity map, and all the automorphisms of <math>H</math>). Thus, <math>\operatorname{IHom}(H,K)</math> is nonempty, yielding that <math>H</math> is isomorphic to the subalgebra of <math>K</math>. Similarly, <math>K</math> is isomorphic to a subalgebra of <math>H</math>.</toggledisplay>
|-
| 7 || <math>H</math> is isomorphic to <math>K</math> || || <math>H,K</math> are finite || Step (6) || <toggledisplay>For finite algebras, each being isomorphic to a subalgebra of the other forces them to be equal in size, hence forcing the injective homomorphisms to be isomorphisms.</toggledisplay>
|}