0
$\begingroup$

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?

$\endgroup$
9
  • $\begingroup$ Your $g$s seem to be confused as to whether they have two or three arguments. $\endgroup$
    – jgon
    Jan 12, 2018 at 17:25
  • $\begingroup$ g has a variable but finite arity. I am illustrating with a simple example. $\endgroup$ Jan 12, 2018 at 17:27
  • $\begingroup$ Then you seem to have rediscovered semigroups: en.wikipedia.org/wiki/Semigroup $\endgroup$
    – jgon
    Jan 12, 2018 at 17:29
  • $\begingroup$ *because the condition you've given is usually called associativity. Admittedly you note this, but then your question confuses me. $\endgroup$
    – jgon
    Jan 12, 2018 at 17:30
  • 1
    $\begingroup$ Yeah I agree, I'm eating lunch rn tho, so I'll write it up after $\endgroup$
    – jgon
    Jan 12, 2018 at 17:47

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Thank you. Would it change anything if I also imposed the condition that it is possible to have g(x) = x? That is, g is also unary. $\endgroup$ Jan 12, 2018 at 19:33
  • 1
    $\begingroup$ Ah that's the case where you extend the family to include a unary operation, disccussed towards the end. In that case, $g_1$ is the identity, and hence $T=S$. Thus in that case, if you don't include a $g_0$, nothing changes. If you do include a $g_0$, you get a multiplicative identity and $S$ becomes a monoid. $\endgroup$
    – jgon
    Jan 12, 2018 at 19:39
  • $\begingroup$ Excellent! You have great skills :) $\endgroup$ Jan 12, 2018 at 19:42
  • $\begingroup$ Also, I m wondering if the signs on m and 1 should be reversed in the subscript of $$g_{n+m-1}(x_1,\ldots,x_{n+m-1}),$$ ? $\endgroup$ Jan 12, 2018 at 21:54
  • 1
    $\begingroup$ @MadPhysicist Ah, no, that's because on the LHS you have $g_m$ taking $m$ arguments and $g_n$ taking another $n-1$ arguments in addition to the result of $g_m$, so on the RHS we should get a total of $m + n -1 =n+m-1$ arguments. $\endgroup$
    – jgon
    Jan 12, 2018 at 21:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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