A hypersubstitution $\sigma$ is (see, for example, Universal Algebra and Applications in Theoretical Computer Science, by Denecke and Wismath) mapping from term $f_i(x_1,...,x_{n_i})$ to the term $\sigma(f_i)$. It follows that every hypersubstitution of type $\tau$ induces a mapping $\hat{\sigma}:W_\tau(X)\to W_\tau(X)$ as follows:for any $w\in W_\tau(X)$, the term $\hat{\sigma}[w]$ is defined by
(1) $\hat{\sigma}[x]:=x$ for any variable $x\in X$
(2) $\hat{\sigma}[f_i(w_1,...,w_{n_i})]:=\sigma(f_i)(\hat{\sigma}[w_1],...,\hat{\sigma}[w_{n_i}]).$

From the book M-Solid Varieties of Algebras, by Koppitz and Denecke, we have

Definition 3.1.1 Let $W_{\tau}(X_m)$ and $W_{\tau}(X_n)$ be the sets of all $m$-ary and $n$-ary terms of type $\tau$, for $1 \leq m,n \in \mathbb N$. Then the operation $S_m^n:W_{\tau}(X_n)\times W_{\tau}(X_m)^n \to W_{\tau}(X_m)$ is defined inductively as follows:
(i) $S_m^n(x_i,t_1,\ldots,t_n)=t_i$, $\;x_i \in X_n$, $t_1, \ldots,t_n \in W_{\tau}(X_m)$,
(ii) $S_m^n(f_i(s_1, \ldots,s_{n_i}),t_1,\ldots,t_n)=f_i(S_m^n(s_1,t_1,\ldots,t_n),\ldots,S_m^n(s_{n_i},t_1,\ldots,t_n)),\;$ $f_i(s_1\ldots,s_{n_i})\in W_{\tau}(X_n)$.

And then

Definition 3.1.3 Let $\sigma:\{f_i:i \in I\} \to W_{\tau}(X)$ be a mapping assigning to every $n_i$-ary operation symbol $f_i$ of type $\tau$ an $n_i$-ary operation term $\sigma(f_i)$. Any such map $\sigma$ will be called an hypersubstitution of type $\tau$.
[...] Every hypersubstitution of type $\tau$ induces a mapping $\hat{\sigma}:W_{\tau}(X)\to W_{\tau}(X)$ on the set of all terms of type $\tau$ as follows. For any term $t \in W_{\tau}(X)$, the term $\hat{\sigma}[t]$ is defined inductively by
(1) $\hat{\sigma}[x]=x$ for any variable $x \in X$ and
(2) $\hat{\sigma}[f_i(t_1,\ldots,t_{n_i})]=S_n^{n_i}(\sigma(f_i),\hat{\sigma}[t_1],\ldots,\hat{\sigma}[t_n])$.

How to reconcile the two definitions of hypersubstitution (why are they equivalent)?

  • $\begingroup$ Please have a look at this pages 51 and 53. Definitions 3.1.1 and 3.1.3 $\endgroup$ – user122424 Feb 26 '18 at 8:54
  • $\begingroup$ I do not know where is the problem with my definitions. Can you please EDIT them for me to them be as you wish? $\endgroup$ – user122424 Feb 26 '18 at 15:41
  • $\begingroup$ I suppose what you want to prove is that the definition of hyper-substitution following Def.3.1.3 in the linked doc is equivalent to the one you present in (1) and (2) (although (2) seems to miss an equality and another expression to make sense), but for that you need another condition from Def3.1.3 (that $\hat{\sigma}[x]=x$, which you only include in the second version of the definition, in (2)). I don't think I should edit the question because I don't know for sure what is what you're asking. Is it what I'm describing? $\endgroup$ – amrsa Feb 26 '18 at 15:50
  • $\begingroup$ I think you are right with the variable case, I omit it due to its trviality.And you are right also with the rest, I think. I would appreciate your attempt to fix my definitions and then I'll tell you if it is OK. $\endgroup$ – user122424 Feb 26 '18 at 16:03

Notice that it all amounts to prove that $$S_n^{n_i}(\sigma(f_i),\hat{\sigma}[t_1],\ldots,\hat{\sigma}[t_{n_i}]) = \sigma(f_i)(\hat{\sigma}[t_1],\ldots,\hat{\sigma}[t_{n_i}]).$$ Let $x_1,\ldots,x_{n_i} \in X$. Then $$S_n^{n_i}(\sigma(f_i)(x_1,\ldots,x_{n_i}),\hat{\sigma}[t_1],\ldots,\hat{\sigma}[t_{n_i}]) =\sigma(f_i)(S_n^{n_i}(x_1,\hat{\sigma}[t_1],\ldots,\hat{\sigma}[t_{n_i}]),\ldots,S_n^{n_i}(x_{n_i},\hat{\sigma}[t_1],\ldots,\hat{\sigma}[t_{n_i}])),$$ by Definition 3.1.1 (ii), $$=\sigma(f_i)(\hat{\sigma}[t_1],\ldots,\hat{\sigma}[t_{n_i}]),$$ by Definition 3.1.1 (i).

  • $\begingroup$ I think you're great. I'll reread it a few more times, but I think I understand the idea I wanted. $\endgroup$ – user122424 Feb 26 '18 at 17:20
  • $\begingroup$ But why your left hand side of the last but one equality is $$S_n^{n_i}(\sigma(f_i)(x_1,\ldots,x_{n_i}),\hat{\sigma}[t_1],\ldots,\hat{\sigma}[t_{n_i}])$$ but the previous one is without $x_1,...,x_{n_i}:$ $$S_n^{n_i}(\sigma(f_i),\hat{\sigma}[t_1],\ldots,\hat{\sigma}[t_{n_i}])?$$ AND there are no $x_1,...,x_{n_i}$ on the r.h.s.? $\endgroup$ – user122424 Feb 26 '18 at 17:30
  • $\begingroup$ @user122424 That's because $\sigma(f_i)$ is the term (and implicitly, the map, since every term induces a map), and $\sigma(f_i)(x_1,\ldots,x_{n_i})$ is the image of the $n_i$-tuple by the map. You see it is usual (and often the simplest way) when we want to show that two maps $f$ and $g$ are equal, we show that $f(x)=g(x)$ for all $x$ in the domain. It was not really necessary, but it wouldn't feel natural the application of 3.1.1. By the way, $t_i$ also induce applications, so we could have done the same with those terms, but it wasn't necessary since 3.1.1 keeps those arguments. $\endgroup$ – amrsa Feb 26 '18 at 17:39
  • $\begingroup$ I'm afraid that I would cause more damage to our posts if I copy and paste it. Feel free to do it. Do you have a privilege to do this?I'm happy to finally understand the whole thing. $\endgroup$ – user122424 Feb 26 '18 at 17:47
  • $\begingroup$ BTW would it be possible to also add the variables $x_1,...,x_{n_i}$ to the r.h.s. of your last equality in your answer?I wonder what if we supposed not $x_1,x_2,...,x_{n_i}$ to be our variables but say, $x_3,x_2,x_1,...,x_{n_i}$ I think that the order change of the initial variables should also appear on the r.h.s.,right? $\endgroup$ – user122424 Feb 26 '18 at 17:52

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.