9
$\begingroup$

The question was asked by a Computer Scientist and is closely related to parallel computing. But it is clearly of algebraic nature, so I decided to post it here.

Let $X$ be a set and $\bar X$ be the union of all Cartesian powers $X^n$. Let $f$ be a function from $\bar X$ to $X$. We say that $f$ is inductive if there exists a binary operation $F\colon X\times X \to X$ such that for every $x_1,...,x_n \in X$, $n>1$, we have $f(x_1,...,x_n)=F(f(x_1,...,x_{n-1}), x_n)$. If, in addition, $F$ is associative and $(X,F)$ is a monoid (has the identity element), then $f$ is called reducible. For example, if $X$ is the set of all natural numbers, $f$ is the max function on $\bar X$, then we can take $F(x,y)=\max(x,y)$. So $f$ is reducible.

We say that $(X,f)$ has an inductive (resp. reducible) extension if there exists a set $Y$ containing $X$ with a function $g$ from $\bar Y$ to $Y$ and a projection function $p: Y\to X$ such that $$p(g(x_1,...,x_n))=f(x_1,...,x_n)$$ for all $x_1,...,x_n$ in $X$ and $(Y, g)$ is inductive (resp. reducible).

Question: 1) What is known about the set of functions $f$ with inductive (reducible) extensions? 2) In particular, does every function $f$ admit an inductive (reducible) extension?

$\endgroup$
4
  • 2
    $\begingroup$ Besides being notationally convenient, is there a reason to consider f as a function on Xbar (sorry not up to formatting right now) as opposed to a schema of functions f_n which turn out to be term functions in F and a starting unary function? I think the opposing view might lead to find non inductive (non reducible) f. Gerhard "Better To Work With Many" Paseman, 2017.04.16. $\endgroup$ Apr 17, 2017 at 2:05
  • $\begingroup$ @GerhardPaseman: It might be reasonable to view $f$ as a collection of $f_n$. Indeed, $f_n$ is a term of $F$, but it is not an arbitrary term. In any case, then the question is about describing all collections of $f_n$ which come this way from some extension of $X$. $\endgroup$
    – user6976
    Apr 17, 2017 at 2:24
  • 1
    $\begingroup$ Exercise 10, chapter 4.1 in MMT's Algebras Lattices Varieties Vol I. seems related and may be relevant. Unfortunately I can't judge how relevant right now. Gerhard "Too Tired To Think Clearly" Paseman, 2017.04.16. $\endgroup$ Apr 17, 2017 at 2:51
  • $\begingroup$ @GerhardPaseman: It is not the same, but this exercise may mean that the answer to Question 2) is "yes". $\endgroup$
    – user6976
    Apr 17, 2017 at 12:32

1 Answer 1

2
$\begingroup$

I assume that $\bar X$ also contains $\varnothing$ as the Cartesian product of 0 copies of $X$.

Set $Y=\bar X$. If $y_i=(x_{i,1},\dots,x_{i,k_i})\in X^{k_i}$ with $i=1,\dots,\ell$, set $$ g(y_1,\dots,y_\ell)=(x_{1,1},\dots,x_{1,k_1},x_{2,1},\dots,x_{2,k_2},\dots)\in X^{k_1+k_2+\dots}\subset Y $$ (so $g$ is simply the concatenation). Clearly, $g$ is reducible (with $F$ being a binary concatenation; we get a monoid, since we added $\varnothing$). Finally, for $y=(x_1,\dots,x_k)$ define $$ p(y)=f(x_1,\dots,x_k) $$ (we can define $p(\varnothing)$ arbitrarily; on the other elements, $p$ does all the job). Thus we obtain a reducible extension of $f$.

So, each function $f$ indeed has a reducible extension.

$\endgroup$
3
  • $\begingroup$ Yes, it is correct and answers my question. It is not what CS people want because this reducibility would not make their life easier, Surely some computational complexity theory should be involved. When I know what they want exactly, I will post another question. $\endgroup$
    – user6976
    Apr 18, 2017 at 10:51
  • $\begingroup$ Perhaps, they need $Y$ to be small? (E.g., finite when $X$ is finite?) $\endgroup$ Apr 18, 2017 at 11:04
  • $\begingroup$ That is what I suggested too, but it is not the only condition. $\endgroup$
    – user6976
    Apr 18, 2017 at 11:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.