I recently found this equivalence between the two propositions in a book

  1. $( E )$ is an infinite set
  2. $\forall f \in E^E. \exists A \in \mathcal{P}(E) \setminus \{\emptyset, E\} \, :f(A) \subset A$

but I don't see a logical connection between the two propositions. I tried to find a way to relate them, and the best I could come up with was valid for $( \text{rang}(f) \subset E )$ by setting $( A = \text{rang}(f) )$, which leads to $( f(A) \subseteq A )$, This is valid for all sets, whether they are finite or infinite. also It does not cover the case where $rang(f) = E$, which is far less than what is required.

Can anyone provide a proof or a counterexample for this equivalence? I would greatly appreciate it. Thank you.

  • $\begingroup$ Note that setting $A$ equal to the range of $f$ doesn't work when $f$ is surjective, since $A=E$ is explicitly prohibited. $\endgroup$ Feb 29 at 6:35

2 Answers 2


To prove 2 implies 1 (or more precisely its contrapositive), we can note that a cyclic permutation of a finite set (say $f(1)=2$, ..., $f(n-1)=n$, $f(n)=1$) does not have the property in 2.

To prove 1 implies 2: choose $x_0\in E$ arbitrarily, recursively define $x_n = f(x_{n-1})$, and set $A = \{x_1,x_2,\dots\}$.

  • $\begingroup$ @user14111 Good call—edited $\endgroup$ Feb 29 at 8:29
  • $\begingroup$ In the second half, when you proved that 1 implies 2, how did you ensure that there is no element $x_k$ belonging to A where$ f(x_k)=x_0$ and thus $f(A)\nsubseteq A$? $\endgroup$ Feb 29 at 9:17
  • $\begingroup$ @ChadK sir ،What do you mean by the fixed point here? $\endgroup$ Feb 29 at 13:13
  • $\begingroup$ @chadk I understand you, but here you are giving a proof in the case where f has a fixed point and not in the general case. Therefore, if f does not have one, you need the same proof that Greg Martin used. In my opinion, separating f into two conditions where f has a fixed point in one and not in the other does not help us. $\endgroup$ Mar 1 at 8:12

Suppose $E$ is finite, wlog $E=\{1,\cdots,n\}$ where $n\ge 1$. Define $f(x)=x+1$ if $x<n$ and $f(n)=1$ hence an $n$-cycle. Also suppose $\emptyset \subsetneq A\subsetneq E$ and $f(A)\subset A$. Then $A$ contains an elt $x$ and it also contains the forward orbit of $x$, which is $E$. Hence $A=E$, contradiction, which proves $ii\rightarrow i$. Now suppose $E$ is infinite and that some $f$ exists for which there is no $A$. Pick $x_1\in E$ and consider the forward orbit $\{x_1,x_2,\cdots\}$. If $x_1\not=x_k$ for $k> 1$ then we can take $A:=\{x_2,\cdots\}$, contradiction. Hence the forward orbit of $x_1$ is a cycle $(x_1,\cdots,x_n)$ where $n\ge 1$ and the $x_k$ distinct. Then we can take $A:=\{x_1,\cdots,x_n\}$ which is not empty and not $E$. This proves $i\rightarrow ii$.


You must log in to answer this question.

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