Problem Statement

Let $X$ be any set whatsoever, and let $f:X\to X$ be any function. Note that in general, no structure is imposed on $f$ whatsoever (i.e. continuity, linearity, etc). The problem is thus entirely set-theoretic.

Define $f^n (x)\equiv f(f^{n-1}(x))$, so that $f^n$ denotes the $n$-th iterate of $f$. Call a subset $C\subseteq X$ a compression of $X$ under $f$ if for every $x\in X$ there exists an $N\in \mathbb{N}$ so that $n>N$ implies $x$ is in the image of $C$ under $f^n$. Denote the set of all of $f$'s compressions, called the compression space, by $\mathcal{C}(f)$.

Given $C_1,C_2\in\mathcal{C}(f)$, is it always true that $C_1\cap C_2\in\mathcal{C}(f)$?


The problem is my own, as is the terminology, although it is quite possible that these ideas appear elsewhere. I have done a brief literature search and come up short. If there is a pre-existing name for "compressions" I will happily update my post. Any literature could be helpful.

Progress so Far

Clearly, for $f$ to have any compressions, it must be a surjection, as otherwise not everything will be mapped to.

In the case of $X$ being a finite set, surjectivity implies bijection. For any bijection, $X$ is trivially a compression. We can also see that for finite bijective $f$ there are no other compressions, as follows. First note that finite bijective endofunctions are symmetric functions, and thus partition $X$ into cycles. Let $C\subset X$ be a proper subset of $X$ and $x\in X-C$. If $x$ lies in a cycle of length $k$ then $f^{mk}(x)=x$ for every $m\ge0$, and $x$ will "oscillate" in and out of $f^n (C)$ infinitely many time, and $C$ is not a compression.

Things get much more interesting when $|X|>\infty$. First of all it will be helpful to think of endofunctions as directed graphs, where each node $x\in X$ is mapped to $f(x)$. In the finite case, endofunction graphs will look like cycles with trees attached to them (see https://en.wikipedia.org/wiki/Pseudoforest). In the infinite case we can still have cycles, but the trees attached can be "infinitely high".

For any given $x$, if we follow the path $x\mapsto f(x) \mapsto f(f(x)) \mapsto\cdots$, we will either end in a finite-length cycle after a finite number of iterations, or we will form an infinite chain with no end.

Surjections have the property that every node $x$ has at least one node leading into it, and for bijections every node $x$ has exactly one node leading in. We can prove that the compressions of arbitrary bijections are closed under intersection as follows.

As in the finite case, the nodes of the cycles in a bijection do not have any trees attached. However, for infinite $f$, we may still form chains. Because each node in a chain only has a single precursor, the chains are bidirectional. Let us choose from each chain some arbitrary representative $x_i$ indexed over the chains, $i\in I$.

If $C_1$ is a compression of this bijective $f$, then for each $x_i$ there will be a corresponding $M_i$ such that $f^m(x_i)\in C_1$ for all $m>M_i$. Similarly, if $C_2$ is another compression, there will be a corresponding $N_i$ for each $i$. Thus every compression of a bijection contains truncations of each bidirectional chain. The intersection of $C_1$ and $C_2$ will simply move those truncations further along the chain, to $\max\lbrace M_1,M_2\rbrace$. Every element in chain $i$ will still hit the truncation in a finite number of iterations, $C_1\cap C_2\in\mathcal{C}(f)$.

To summarize, we know that any non-surjective function has empty compression space, and is trivially closed under finite intersection. We also know that the compression spaces of finite surjections and arbitrary bijections are closed under finite intersection.

What Remains

Things break down for surjections where $|X|=\infty$. The problem is that for arbitrary surjections we can have trees that branch infinitely many times. I have tried off and on over the past year to construct an example of paths in the branches which, when intersected, leave gaps in the chains. I cannot seem to construct such an example, but I have no idea how to prove the theorem either.

I feel like the answer to this question may depend on which axioms are chosen, as we are trying to partition infinitely many nodes among at least countably many paths in certain ways, but I really am not sure.

Any help, or even partial results, would be great!



$$f:\Bbb N\to\Bbb N:n\mapsto\left\lfloor\frac{n}2\right\rfloor\;,$$

let $A=\{2n:n\in\Bbb N\}$, and let $B=\Bbb N\setminus A=\{2n+1:n\in\Bbb N\}$. Then $f[A]=f[B]=\Bbb N$, so $A,B\in\mathscr{C}(f)$, but $A\cap B=\varnothing\notin\mathscr{C}(f)$.

  • $\begingroup$ I do not believe that works. The image of $B$ is certainly $\mathbb{N}$, but $\mathbb{N}$ is not a subset of $B$. In particular, once any $x$ leaves hits $0$ under iteration, it will leave $B$ forever, and $B$ is not a compression of $\mathbb{N}$. $\endgroup$ – clevy Jan 30 '16 at 4:28
  • $\begingroup$ @clevy: According to your definition, that doesn’t matter: for each $k\in\Bbb N$, $k\in f^n[A]$ and $k\in f^n[B]$ for all $n\ge 1$, and that’s enough. $\endgroup$ – Brian M. Scott Jan 30 '16 at 4:30
  • $\begingroup$ My apologies. Indeed you are correct. Out of curiosity, how were you able to come up with an example so quickly? Had you seen some similar problem before? $\endgroup$ – clevy Jan 30 '16 at 22:31
  • $\begingroup$ @clevy: No problem. No, this was new to me. It just struck me that if $f[A]=X$, then automatically $A\in\mathscr{C}(f)$, so that all that I needed was a function that mapped disjoint subsets of $X$ onto $X$. That just required $X$ to be infinite, and I picked the simplest example that came to mind. $\endgroup$ – Brian M. Scott Jan 30 '16 at 22:38

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.