Generalized Idempotency of Multi-variable Function

196 Views Asked by At

I am wondering what a generalization of idempotency would look like for a function of multiple variables.

For instance, for basic idempotency of a function of one variable, we have: f(f(x)) = f(x).

Suppose we have a function g such that g(x, g(y,z)) = g(x, y, z). What is more, the previous statement is true, no matter where we place the inner g.

That is, the following is also true: g(g(x, y), z)) = g(x, y, z). In a sense, the latter simply demonstrates the associativity of the operation g.

The question is whether the type of above function can be considered idempotent. What is idempotence for a function of several variables? Could this be called partial idempotence?

1

There are 1 best solutions below

5
On BEST ANSWER

This answer will hopefully expand on and clarify my comments on the question.

First let's formalize what we want from $g$. You'll definitely want to look at the Operad article on Wiki, specifically the section on the associative operad. However, I'll try to avoid using the idea of operads in the rest of my answer.

$g$ is a family of $n$-ary operations for $n\ge 2$, thought of as operations on an underlying set $S$, so $g_n : S^n \to S$. The "generalized idempotency" property that you want seems like it can be written formally as $$g_n(x_1,\ldots,x_n) = g_{n-1}(x_1,\ldots,x_{i-1},g_2(x_i,x_{i+1}),x_{i+2},\ldots,x_n)$$ for any $1\le i < n$ and all choices of $x_i\in S$. I claim that this forces $g_2$ to be an associative product, and $g_n$ to be the $n$th finite product, so $g$ contains the same information as a semigroup on $S$.

Then $g_2(x,g_2(y,z))=g_3(x,y,z)=g_2(g_2(x,y),z)$, so $g_2$ is an associative product. Moreover, if $(S,\cdot)$ is a semigroup, the $n$th product operation, $\Pi_n : S^n \to S$ is defined inductively by $\Pi_1(x_1)=x_1$, and $$\Pi_n(x_1,\ldots,x_n) = \Pi_{n-1}(x_1,\ldots,x_{n-1}\cdot x_n).$$

Now if the semigroup is given by the operation $g_2$, which I will now denote by $\cdot$ for brevity, we want to prove that $g_n=\Pi_n$ for $n\ge 2$. We can prove this inductively. First note $\Pi_2(x_1,x_2)=\Pi_1(x_1\cdot x_2)=x_1\cdot x_2=g_2(x_1,x_2)$, so $g_2=\Pi_2$. Now if $g_n=\Pi_n$, then $$ \Pi_{n+1}(x_1,\ldots,x_n,x_{n+1}) = \Pi_n(x_1,\ldots,x_n\cdot x_{n+1}) = g_n(x_1,\ldots,x_n\cdot x_{n+1}) = g_{n+1}(x_1,\ldots,x_n,x_{n+1}) $$ by definition of $\Pi_{n+1}$, the inductive hypothesis, and the given property of $g_n$. Hence the induction holds. Thus a family $g_n$ on $S$ with the given property for $n\ge 2$ is equivalent to the data of a semigroup on $S$.

Generalizing the condition given slightly, we can ask about extending the definition to families of operations $g_n$ for $n\ge 1$ or $n\ge 0$. Note that the condition given generalizes straightforwardly to families $g_n$ for $n\ge N_0$ subject to the condition that
$$g_n(x_1,\ldots,x_i,g_m(x_{i+1},\ldots,x_{i+m}),x_{i+m+1},\ldots,x_{n+m-1}) = g_{n+m-1}(x_1,\ldots,x_{n+m-1}),$$ for all $n,m\ge N_0$, $n\ge 1$, and all choices of $x_1,\ldots,x_{n+m-1}\in S$. We for $N_0\le 2$, we still have that $g_2$ is an associative binary operation and $g_n=\Pi_n$, so we just need to examine what properties $g_1$ and $g_0$ have when defined. First note that the condition given implies that $g_1(g_1(x_1))=g_1(x_1)$, so $g_1$ is idempotent. (Justifying calling the given condition generalized idempotence in a sense.) Now let $T\subset S$ be the image of $g_1$. Since $g_1(g_2(x_1,x_2))=g_2(x_1,x_2)$, $g_2$ induces a well defined operation $T\times T \to T$, making $T$ a semigroup. Then $g_2(x_1,x_2)=g_2(g_1(x_1),g_1(x_2))$, so the semigroup operation on $S$ is induced by the semigroup operation on $T$, so the data of $g_n$ for $n\ge 1$ is equivalent to two sets $T\subset S$, an associative binary operation on $T$, $g_2|_{T\times T}$, and a map $g_1:S\to T$ restricting to the identity on $T$.

Finally if we add $g_0$, then $g_0=g_1(g_0)\in T$, and $g_2(x_1,g_0)=g_1(x_1)=g_2(g_0,x_1)$, so the semigroup $T$ has an identity element $g_0$. Thus the semigroup on $T$ is in fact a monoid in this case. Hence the data of $g_n$ for $n\ge 0$ is equivalent to a pair of sets $T\subset S$, a monoid structure on $T$, and a map $S\to T$ restricting to the identity on $T$.

Last note, it's also interesting to consider what happens when you choose $N_0 > 2$, i.e. where there is no binary operation generating the whole structure. However, it gets a lot more complicated in that case, so I can't say anything about it.