# Exploring the Equivalence between Infinite Sets and the Existence of Subsets under Certain Mappings

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.

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

## 2 Answers

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\}$$.

• @user14111 Good call—edited Feb 29 at 8:29
• 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$? Feb 29 at 9:17
• @ChadK sir ،What do you mean by the fixed point here? Feb 29 at 13:13
• @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. 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 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$$.