Prove that function composition is subalgebra

137 Views Asked by At

Let $\varphi \subseteq A \times B; \psi \subseteq B \times C$. Then $\varphi \circ \psi = \left \{ (a, c)| \exists b: (a,b) \in \varphi, (b,c) \in \psi \right \} \subseteq A \times C$.

Task: Let $\varphi$ and $\psi$ are subalgebras of algebras $A \times B$ and $B \times C$ respectively. Prove that $\varphi \circ \psi$ is subalgebra of algebra $A \times C$.

What I've tried:

$\varphi : A \to B ; \psi : B \to C$. $\omega_{i}$ - operations in A; $\tau_{i}$ - operations in B; $\pi_{i}$ - operations in C. For $\varphi : \varphi(\omega_{i}(x_{j})) = \tau_{i}(\varphi(x_{j}))$. For $\psi: \psi(\tau_{i}(x_{j})) = \pi_{i}(\psi(x_{j}))$. So $(\varphi \circ \psi)(\omega_{i}(x_{j})) = \psi(\varphi(\omega_{i}(x_{j}))) = \psi(\tau_{i}(\varphi(x_{j}))) = \pi_{i}(\psi(\varphi(x_{j})))$. This means that $\varphi \circ \psi$ is homomorphism and $\varphi \circ \psi$ is subalgebra of algebra $A \times C$ as a composition of homomorphisms that are subalgebras.

As for me I went wront with operations in sets. Maybe there have to be something like: For $(a,b) \in A \times B: (\varphi \circ \psi)(a,b) = \psi(\varphi((a,b)))...?$

1

There are 1 best solutions below

4
On BEST ANSWER

Ok, so if you feel the need for this more direct approach, here it goes.
For starters, I'm using a different convention for the composition: $\psi \circ \varphi$ is what you write in reverse order, but I it feels more natural to me this way, although I think I also met that other convention before...

So $\varphi : \mathbf A \to \mathbf B$ and $\psi: \mathbf B \to \mathbf C$ are homomorphisms between algebras of the same similarity type, and you want to prove that $\psi \circ \varphi$ is a sub-algebra of $\mathbf A \times \mathbf C$.

So let $f$ be a $k$-ary operation of these algebras, and let $$(a_1,c_1), \dots, (a_k,c_k) \in \psi \circ \varphi,$$ meaning that $(\psi \circ \varphi)(a_i) = \psi(\varphi(a_i)) = c_i$.
Now we want to prove that $f((a_1,c_1),\dots,(a_k,c_k)) \in \psi \circ \varphi$.
But \begin{align} f((a_1,c_1),\dots,(a_k,c_k)) &= (f(a_1, \dots, a_k), f(c_1, \dots, c_k))\\ &= (f(a_1, \dots, a_k), f((\psi \circ \varphi)(a_1),\dots,(\psi \circ \varphi)(a_k)))\\ &= (f(a_1,\dots,a_k),(\psi \circ \varphi)(f(a_1,\dots,a_k))), \end{align} where the first equality follows by applying the definition of $f$ in the direct product, the second from the definition of $c_i = (\psi \circ \varphi)(a_i)$, and the third from $\psi \circ \varphi$ being a homomorphism.

Since clearly, $(f(a_1, \dots, a_k), f((\psi \circ \varphi)(a_1),\dots,(\psi \circ \varphi)(a_k))) \in \psi \circ \varphi$, the result is proven.