3
$\begingroup$

I'd just like to know for my own experimentation a list of known functions in algebra that satisfy $$ f(f(x))=f(x), $$ like how there's a list of known involution functions on wikipedia. But somehow, I can't find a single example anywhere on the internet of even one idempotent function.

$\endgroup$
12
  • 3
    $\begingroup$ Note that if $f$ is idempotent and differentiable, then $f'(f(x)) \cdot f'(x)=f'(x)\,$ so $f'(x)=0$ on its domain, or $f'(y)=1$ on its range, or some combination thereof. That severely limits the potentially candidate functions, and explains some of the posted examples. $\endgroup$
    – dxiv
    Commented Apr 28, 2017 at 4:52
  • $\begingroup$ Correct me if I'm wrong, but $$f(x)=e^{ln(x^n)^{1/n}}$$ is an idemptotent function because $$ e^{ln(e^{ln(x^n)^{1/n}}^n)^{1/n}}=e^{ln(x^n)^{1/n}} $$ correct? This would be the kind of function I'm looking for. if I say n=2, you can see more clearly that wolframalpha.com/input/… $\endgroup$
    – RayOfHope
    Commented Apr 28, 2017 at 5:08
  • $\begingroup$ The MathJax didn't come out right in your previous comment, so I am not sure what function you meant to write. The one in the WA link doesn't look to be idempotent. $\endgroup$
    – dxiv
    Commented Apr 28, 2017 at 5:15
  • $\begingroup$ It comes out right on my end. Here, I have the original function, e^(ln(x^2)^(1/2)) wolframalpha.com/input/?i=e%5E(ln(x%5E2)%5E(1%2F2)) and now, look what happens when I composite that function into itself wolframalpha.com/input/… I get the original function. This is the kind of function I'm looking for. $\endgroup$
    – RayOfHope
    Commented Apr 28, 2017 at 5:18
  • 3
    $\begingroup$ Let your $f(x)=e^{\sqrt{\ln(x^2)}}\,$, then $f(e)=e^{\sqrt{2}}\simeq 4.11\,$, $f(e^{\sqrt{2}})=e^{2^{3/4}} \simeq 5.38\,$, so $f(f(e)) \ne f(e)\,$ $\endgroup$
    – dxiv
    Commented Apr 28, 2017 at 5:43

6 Answers 6

6
$\begingroup$

A projection is a linear map satisfying $P^2=P$. These are always idempotent, by definition.

$\endgroup$
3
  • $\begingroup$ I mean like an actual algebraic function like in functional analysis, not linear algebra, like something involving y=x^2 or y=gamma(x) or something like that, you know? I ran across operators like that in linear algebra and things from computer science, but that's really not what I'm looking for. $\endgroup$
    – RayOfHope
    Commented Apr 28, 2017 at 4:44
  • 2
    $\begingroup$ How about the sign function? $\endgroup$
    – Chappers
    Commented Apr 28, 2017 at 4:47
  • 4
    $\begingroup$ @RayOfHope: Whatever you mean by "functional analysis" doesn't appear to be what the term usually means in mathematics. Linear idempotent maps, and most of linear algebra, are important in functional analysis. You can write formulas for linear idempotent maps. E.g., $f:\mathbb R^2\to\mathbb R^2$ defined by $f(x,y) = (\frac12(x+y),\frac12(x+y))$ is an example. Do you mean you only want functions from $\mathbb R$ to $\mathbb R$? $\endgroup$ Commented Apr 28, 2017 at 6:39
5
$\begingroup$
  1. If $f:\mathbb R\to\mathbb R$ is continuous and idempotent then $I=f(\mathbb R)$ is a closed interval and $f(x)=x$ for all $x\in I$.
  2. If $f$ is also differentiable and nonconstant, then $I=\mathbb R$, i.e., $f(x)=x$ for all $x\in\mathbb R$.

Proof of 1.: If $f$ is continuous and idempotent, then $I=f(\mathbb R)$ is an interval by continuity alone along with the IVT. If $A=\{x\in \mathbb R: f(x)=x\}$, then $A$ is a closed set by continuity, $A\subseteq I$ because each $x\in A$ equals $f(x)\in I$, and $I\subseteq A$ by idempotency. Thus $I=A$, confirming that $I$ is a closed interval on which $f$ is the identity function.

Proof of 2.: Suppose that $f$ is continuous and idempotent, but not constant and not the identity function. Then $I$ is not $\mathbb R$, not a singleton, so by 1. $I$ is a nontrivial closed interval that is either bounded above or below (or both). Suppose $I$ is bounded above, and let $b=\sup(I)=\max(I)$, the last equality holding by closedness of $I$. Because $I$ is a nontrivial interval, $I$ contains $(a,b]$ for some $a<b$. It follows that $f$ is not differentiable at $x=b$, because $\lim\limits_{h\to 0-}\dfrac{f(b+h)-f(b)}{h}=1$, but for all $h>0$, $\dfrac{f(b+h)-f(b)}{h}\leq 0$. If $f$ is bounded below a similar argument applies to show that $f$ is not differentiable at $\inf(I)=\min(I)$. By contraposition, this confirms that if $f$ is idempotent, differentiable and nonconstant, then $I=\mathbb R$, i.e., $f(x)=x$ for all $x\in\mathbb R$.


In the case where $f$ is continuous and not constant or the identity function, the graph of $f$ consists of a closed line segment or ray on the line $y=x$, having the form $\{(x,x):x\in f(\mathbb R)\}$, then extends continuously in a way that is arbitrary as long as the $y$ values stay in $I=f(\mathbb R)=f(I)$. This is a special case of Jair Taylor's more general description, where $S$ must be a interval and the pieced together map must be continuous.

For a given bounded interval $[a,b]$, $a<b$, a formula for a continuous idempotent function $f$ having $[a,b]=f(\mathbb R)$ is $$f(x)=\frac{b-a}{\pi}\arcsin\left(\sin\left(\frac{\pi(x-\frac12(a+b))}{b-a}\right)\right)+\frac{a+b}{2},$$

a triangle wave function obtained by dilating and shifting the example $\arcsin(\sin(x))$ given in Jair Taylor's answer. To get arbitrary closed rays instead, you can shift and reflect $y=|x|$ to get $y=\pm|x-h|+h$.

$\endgroup$
2
  • $\begingroup$ So in other words, it's double proven that the only real idempotent functions are the ones with a derivative of 1? $\endgroup$
    – RayOfHope
    Commented Apr 28, 2017 at 19:35
  • $\begingroup$ @RayOfHope: I wouldn't use those words, but if by "real" you mean differentiable, nonconstant, and defined on all of $\mathbb R$, this does provide proof of something more specific than that the derivative is $1$, namely that the function is the identity function. Are you are referring to how it complements dxiv's answer? I agree they are related. dxiv has commented pointing out how you can have differentiable examples on disconnected domains that are sometimes the identity, other times constant. $\endgroup$ Commented Apr 28, 2017 at 19:58
4
$\begingroup$

Any idempotent function $P: \mathbb{R} \rightarrow \mathbb{R}$ can be constructed by

1) Choosing your favorite set $S$.

2) Find a mapping $P:\mathbb{R} \backslash S$ into $S$.

3) Expand the domain of $P$ by letting let $P(x) = x$ for $x \in S$.

This is, for example, how $P(x) = |x|$ works. It just maps the negative part of the real line onto the positive part, and acts as the identity on the positive part.

But if you want this to be a function with a nice formula it's not quite as obvious. One way is to use any non one-to-one function that $f(x)$ that has a right inverse $g(x)$, so that $f(g(x)) = x$. Then if $P(x) = g(f(x))$ then $P\circ P = g \circ f \circ g \circ f = g \circ f = P$.

Intuitively, $g$ works by mapping an input $y$ to an $x$ in a select domain $A$ of $\mathbb{R}$ so that $f(x) = y$. Then on this particular set $A$, we have $g(f(x)) = g(y) = x$.

For example, think about $P(x) = \arcsin(\sin(x))$ where $arcsin$ is the usual branch taking $x$ into $[-\pi/2, \pi/2]$.

Note that this only really works for certain inverse functions we decided are okay to write in formulas, like $\sqrt{x}$ or $\arcsin(x)$. Most of these examples are going to be a little bit artificial, because if $P$ is the identity on on a set $S$ that contains an interval than it 'really ought' to be the identity everywhere. That is, it must be the identity if it is analytic.

$\endgroup$
3
  • $\begingroup$ A general formula for an idempotent triangle wave map is $$f(x)=a\arcsin\left(\sin\left(\frac{x-h}{a}\right)\right)+h.$$ "...if it is analytic." Isn't it even if it is differentiable and nonconstant? $\endgroup$ Commented Apr 28, 2017 at 7:03
  • $\begingroup$ @JonasMeyer Hmm, I think you're right but the proof's not immediately obvious to me. $\endgroup$ Commented Apr 28, 2017 at 7:50
  • 1
    $\begingroup$ I posted an answer with proof. $\endgroup$ Commented Apr 28, 2017 at 14:45
3
$\begingroup$

Here are several:

  1. $f(x)=x$

  2. $f(x)=\vert x\vert$

  3. $f(x)=\lfloor x\rfloor$

  4. $f(x)=\lceil x\rceil$

$\endgroup$
1
  • $\begingroup$ and then a*arcsin(sin(...)) $\endgroup$
    – RayOfHope
    Commented Apr 29, 2017 at 2:32
3
$\begingroup$

Expanding on the comment:

Note that if $f$ is idempotent and differentiable, then $f′(f(x))⋅f′(x)=f′(x)$ so $f′(x)=0$ on its domain, or $f′(y)=1$ on its range, or some combination thereof.

Take any partition of the reals $\mathbb{R} = \bigcup R_k\,$, and for each $R_k$ define a function $f_k : R_k \to R_k$ which is either linear $f_k(x)=x$ or constant $f_k(x)=c_k \in R_k$. Then "combine" all those functions into one function $f(x) = f_k(x) \;\;\text{iff}\;\; x \in R_k\,$, and that function $f(x)$ is idempotent. This construction covers several of the posted functions, for example $R_k = [k, k+1)$ and $f_k(x) = k$ gives $f(x)= \lfloor x \rfloor$.

For a more offbeat (and nowhere continuous) idempotent function, consider for example:

$$ f(x) = \begin{cases} \begin{align} 0 &\quad\quad \text{if}\; x \in \mathbb{R} \setminus \mathbb{Q} \\ p\,q &\quad\quad \text{if}\; x =p/q \in \mathbb{Q} \;\;\text{with}\; p, q \in \mathbb{Z}\;\;\text{and}\;\; \gcd(p,q)=1 \end{align} \end{cases} $$

$\endgroup$
4
  • $\begingroup$ "or some combination thereof" No combinations occur; if $f$ is idempotent and differentiable, then $f(x)=x$ for all $x$ or $f$ is constant. Proof is posted in my answer, which I am mentioning to back up my claim, not intending to self-promote. $\endgroup$ Commented Apr 28, 2017 at 15:01
  • $\begingroup$ @JonasMeyer That's correct if the domain of $f$ is an interval or the whole $\mathbb{R}\,$. "Combinations thereof" are still possible if the domain is, for example, the union of two intervals with disjoint closures. $\endgroup$
    – dxiv
    Commented Apr 28, 2017 at 17:03
  • $\begingroup$ Thanks, good point. Would the closures need to be disjoint, or just the closure of each disjoint from the others? I.e., wouldn't disjoint open intervals allow for arbitrary combinations? $\endgroup$ Commented Apr 28, 2017 at 17:13
  • $\begingroup$ @JonasMeyer Right. I was just (overly) careful to avoid misunderstandings like $[0,1) \cup [1,2)\,$. $\endgroup$
    – dxiv
    Commented Apr 28, 2017 at 17:27
1
$\begingroup$

A very late answer, but I just discovered this question and I am a bit surprised by the answers, since the OP did not give any specification on the domain of $f$. There is actually no need of topology and the answer is quite trivial:

Let $f:X \to X$ be a function. Then $f$ is idempotent if and only if its restriction to its range is the identity.

This is implicitly Jair Taylor's answer, but this is also the argument used in this Hagen von Eitzen's answer, over ten years ago.

To answer your question as stated in the title, here is the list of the four functions from $\{1,2\}$ to itself. The idempotents are $I$, $b$ and $c$. $$ \begin{array}{|c|c|c|} \hline &1 &2 \\ \hline I&1 &2 \\ a&2 &1 \\ b&1 &1 \\ c&2 &2 \\ \hline \end{array} $$ Let me add a few comments to make this answer more consistent. Cayley's theorem states that every group is isomorphic to a subgroup of a symmetric group, but this theorem easily generalises to monoids: any monoid is a transformation monoid on its underlying set. Thus this characterisation of idempotent transformations gives a simple way to find the idempotents of any semigroup (and it is useful for computational purpose). See [1, Section 2.7] for more information on idempotents of a transformation semigroup.

Halfway between groups and semigroups, Wagner–Preston's theorem states that any inverse semigroup can be embedded in a symmetric inverse semigroup. The set of all partial bijections (i.e. one-to-one partial functions) on a set $X$ forms an inverse monoid ${\cal I}_X$, called the symmetric inverse semigroup. The idempotents of ${\cal I}_X$ are exactly the partial identities. It follows that they form an idempotent and commutative monoid isomorphic to the monoid $({\cal P}(X), \cap)$.

[1] O. Ganyushkin and V. Mazorchuk, Classical finite transformation semigroups, An introduction. Algebra and Applications, 9. Springer-Verlag London, Ltd., London, (2009). xii+314 pp. ISBN: 978-1-84800-280-7

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .