1
$\begingroup$

Let $A \subset \mathbb{R}$ be a finite set with $|A| = n$ and let $f : A \to A$ satisfy the strict contraction condition $|f(x) - f(y)| < |x - y|$ for all $x \neq y$ in $A$. Prove that $f$ is not injective and that the iterate $f^{n}$ is a constant function.

My idea

I was able to show that $f$ is not injective, but not that the iterate is a constant function. So, I let the $n$ elements of $A$ be $x_1 < x_2 < \dots<x_n$ and I noted $y_i=f(x_i)$ for every $i \in \{ 1, \dots n \}$. I suppose that $f$ is injective, and because $f: A \to A$ and A is finite with $n$ elements, we can say that $f$ is bijective. If we note $k$ be the smallest difference in module between any $2$ elements of $A$, we can let $x_i$ and $x_j$ be those elements, then we get that $|y_i-y_j|<|x_i-x_j|=k$ and $y_i, y_j$ are also elements from $A$, which is a contradiction of our suppose so we get that $f$ is not injective. Now I don't know what I should to do to show that the iterate is constant. Hope one of you can help me find a solution without orbits (I've seen these kind of problem use orbits).

$\endgroup$
7
  • $\begingroup$ I suggest proceeding by induction on $|A|$. $\endgroup$ Commented 15 hours ago
  • $\begingroup$ @lulu I thought of demonstrating $|f^n(x)-f^n(y)|<|x-y|$, but idk if f(x) is diffrent from f(y) $\endgroup$ Commented 15 hours ago
  • 4
    $\begingroup$ Again, I suggest induction on $|A|$. Can you do it if $|A|=1$? What if $|A|=2$? The general principle should become clear quickly. $\endgroup$ Commented 15 hours ago
  • $\begingroup$ @lulu For $|A|=1$ you only have one possible function that is constant. For $|A|=2$ the function is not surjective(because of the theorem i mentioned that in these conditions f injective is equiv to f surjective) so from here we get that one of the eements from A is not in the image so because there are 2 elements, the function f is constant, so $f^2$ is constant $\endgroup$ Commented 11 hours ago
  • $\begingroup$ @lulu What should i do for the induction? $\endgroup$ Commented 11 hours ago

2 Answers 2

Reset to default
0
$\begingroup$

This is trivial if $n = 1$. If $n > 1$, then you have shown that $f$ is not injective, and hence it is not surjective (do you see why?). Hence, there is some $a \in A$ that is not in the range of $f$ and we can consider the restriction $g: A' \to A'$ of $f$ to $A' = A \setminus \{a\}$. By induction, $g^{n-1}$ is a constant function: say $g^{n-1}(x) = b$ for some $b$ and any $x \in A'$. But that implies that $f^{n-1} [A] = \{f^{n-1}(a), b\}$ and then, we can only have that $f^n[A] = \{b\}$.

$\endgroup$
4
  • $\begingroup$ We can suppose that f is surjective and by the thorem i mentione d we would get that f is injective which is flase so f is not surjective. Now my question is how did you showed that $g^{n-1}$ Also how do you know that there is only one a that is not in range of f? $\endgroup$ Commented 12 hours ago
  • $\begingroup$ Why can we only have b in the nth iterate how did you get this conclusion? $\endgroup$ Commented 11 hours ago
  • $\begingroup$ @PamMunozRyan It is never claimed that only one is not in the range of $f$, only that there is at least one. Then we can reduce our set by one. As we are doing induction over the size of our set, we know that the claim holds for $g$ (as it is defined on a set of size $n-1$). $\endgroup$ Commented 10 hours ago
  • $\begingroup$ Only $b$ is in the $n$-th iterate, because we must have that $f(b) = b$ (because $f[A'] = \{b\}$) and we know that $f^{n-1})(a)$ is not equal to $b$ already then $f^n(a)$ is an element of $\{f^{n-1}(a), b\}$ that is closer to $b$ then $f^{n-1}(a)$. $\endgroup$ Commented 10 hours ago
0
$\begingroup$

Put $x_1<x_2<\cdots<x_n$. For the injectivity, since the set is finite an injective function will also be surjective and $|x_n-x_1|$ is the biggest distance realized in the set. Since $f$ is surjective we have $f(x_i)=x_1$ and $f(x_j)=x_n$ for some $i$ and $j$ and we have that $|f(x_i)-f(x_j)|=|x_n-x_1|>|x_i-x_j|$ which is a contradiction.

Since $A$ is finite there is a shortest (nonzero) distance realized and iterating $f$ strictly reduces distances so eventually the distance between two iterates will be less then the minimal distance so it must be zero. This means that for some $k$ the iterate $f^{(k)}$ is constant. The worst case that can happen is that we started with two elements that realize the biggest distance ($x_n$ and $x_1$) and that the closest elements in the sets are $x_1$ and $x_2$ (or equivalently $x_{n-1}$ and $x_n$). It will take at most $n$ steps so $f^{(n)}$ will be constant.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.