1

show $h : \underline{A} \to \underline{B}$ is a homomorphism iff $h$ is a subuniverse of $\underline{A} \times \underline{B}$ where $\underline{A}$ and $\underline{B}$ are similar algebras

$\Rightarrow$

Assume $h$ is a homomorphism, $h \subset A \times B$ as $h = \{(a,b) : a \in A \wedge h(a) = b \in B\}$ and additionally by assumption we have for all n-ary operations $f$ in the type of these algebras we have that

$h(f^{A}(a_1, ... , a_n)) = f^{B}(h(a_1),...,h(a_n))$ where $f^{A}$ and $f^{B}$ are operations on $A$ and $B$, respectively.

this is where I get stuck in this direction, I believe what the key is to show this forms a subalgebra of the direct product which gives directly the result that we get a subuniverse

$\Leftarrow$

Assume $h$ is a subuniverse of $\underline{A} \times \underline{B}$, $h$ forms a subset of $A \times B$ such that it is closed under the fundamental operations of $\underline{A} \times \underline{B}$ which gives us a subalgebra.

for the converse, I am not sure how I extract that $h$ gives us a homomorphism

oliverjones
  • 4,199
  • For the converse, you'll also want to assume that $h\subset A\times B$ is the graph of a function. – Alex Kruckman Sep 19 '16 at 21:24
  • @AlexKruckman yes I forgot to mention in the given assumptions that $h$ is a function from $A$ to $B$. so we know that under $h$ we have $a \mapsto b$. Therefore, $h$ only assigns each $a \in A$ to a $b \in B$ ( that is $a$ cannot map to two distinct elements of $B$. I'm still missing something here. Also, am I on the right track for the forward direction? – oliverjones Sep 19 '16 at 22:31

1 Answers1

2

If $h : \mathbf{A} \to \mathbf{B}$ is a homomorphism, and $f$ is a $n$-ary operation of the type of the algebras, then take $n$ elements of $h$ as a subset of $A \times B$: $$(a_1,b_1), \ldots, (a_n,b_n) \in h,$$ which means they have the form (as you say) $$(a_1,h(a_1)), \ldots, (a_n,h(a_n)).$$ Now we want to prove that $$f( (a_1,h(a_1)), \ldots, (a_n, h(a_n)) ) \in h.$$ Now $f$, in $\mathbf{A} \times \mathbf{B}$, is compute coordinate-wise, so that \begin{align} f( (a_1,h(a_1)), \ldots, (a_n, h(a_n)) ) &= ( f(a_1, \ldots, a_n), f(h(a_1), \ldots, h(a_n)) ) \\ &= (f(a_1, \ldots, a_n),h(f(a_1, \ldots, a_n))), \end{align} and this pair, undeed, belongs to $h$.

For the converse, if $h$ is a subuniverse of $\mathbf{A} \times \mathbf{B}$, and (as we both agree with Alex Kruckman), $h:A\to B$ is a map, to see that $h$ is a homomorphism, suppose $f$ is as before, and $a_1, \ldots, a_n \in A$, so that $h(a_1), \ldots, h(a_n) \in B$, and $$f( (a_1,h(a_1)), \ldots, (a_n,h(a_n)) ) \in h,$$ because $h$ is a subuniverse of $\mathbf{A} \times \mathbf{B}$. Now, as before, $f$ is computed coordinate-wise, ,so that \begin{align} f( (a_1,h(a_1)), \ldots, (a_n,h(a_n)) ) &= ( f(a_1, \ldots, a_n), f(h(a_1), \ldots, h(a_n)) )\\ &= ( f(a_1, \ldots, a_n), h(f(a_1, \ldots, a_n)) ), \end{align} where the last equality follows from the fact that $h$ is a map so, if $f(a_1, \ldots, a_n) \in A$, then certainly $$( f(a_1, \ldots, a_n), h(f(a_1, \ldots, a_n)) ) \in h,$$ and is the unique such pair given the first coordinate.
But we already have noticed that $f( (a_1,h(a_1)), \ldots, (a_n,h(a_n)) ) \in h$, and therefore that $( f(a_1, \ldots, a_n), f(h(a_1), \ldots, h(a_n)) ) \in h$, and so these elements must be equal.

amrsa
  • 12,917