If $f[A]$ and $A$ intersect for (most) $A \subset \mathbb{R}$, then how far is $f$ from the identity?

A complete answer for $\ell$-intersecting for infinite $\ell$:

Let $f:Q\to Q$, define $D(f) = \{x \in Q: f(x) \neq x\}$ and $\ell(f)$ be the minimum $k$ such that $f$ is $k$-intersecting.

Theorem: If $\ell(f)$ is infinite, then $|D(f)|<\ell(f)$ and nothing else can be said.

Let $O_f(A)=\{x∈A\mid f(x)∉A\}$, if $|O_f(D(f))|=\ell(f)$ then we are done, $f[O_f(D(f))]∩O_f(D(f))=\emptyset$. If not, let $X_0=O_f(D(f))$, then look at $O_f(O_f(D(f)))$, repeat this process and we get a sequence $(X_i)_{i∈ω}$, let $X=\bigcap_{i\in\omega} X_i$.

Note 1: $f[X]⊆X$

Note 2: $f[X_i]⊆X_{i-1}$

If $|X|≥\ell(f)$, then well order it: $\langle x_i\mid i∈X\rangle$, if $f[X]$ is bounded by $x_γ$, let $B=\{x_α∈X\mid α>γ\}$, then $f[B]∩B=\emptyset$, if not we can take inductively elements into a set: assume you took all the elements bellow $α$ elements, then $α$ will be an element larger than $f(β)$ for all $β<α$ such that $f(α)>β$ for all $β<α$, that set has cardinality of $|X|$ and it is disjoint from it's image under $f$

If $|X|<\ell(f)$ we have either $E=\bigcup_{i\in\omega} X_{2i}$ or $O=\bigcup_{i\in\omega} X_{2i+1}$ are of cardinality $≥\ell(f)$, take $B=\max(E,O)$ and we get $f[B]∩B=\emptyset$

Both cases gives contradiction.

Now, assume that $κ<\ell(f)$, take any function without fix point $g:κ→κ$, well order $A\subseteq Q$ with $|A|=κ$: $\{A_i\mid i\in\kappa\}$, then $f:Q\to Q$ given by $f(x)=x$ if $x≠A_i$ for all $i$, and if $x=A_i$, then $f(x)=A_{g(i)}$. $|D(f)|=κ$

Together with @antkam and @Misha Lavrov the answer is completely finished

A bunch of partial results... (updated 10/25 10:35 EDT with a stronger result for finite case)

Define the deviant set as $D(f) = \{x \in \mathbb{R}: f(x) \neq x\}$. Obviously, deviation $= | D(f)|$.

Claim: For positive integer $n \ge 2$, the max deviation among all $n$-intersecting functions is at least $\color{red}{m = 3(n-1)} $.

The bound is achieveable via this construction:

• Take $D =$ any $3(n-1)$ integers, and form them into $n-1$ disjoint $3$-cycles.

E.g. for $n=3$ we construct $f$ s.t. it permutes $D(f) = \{1,2,3,4,5,6\}$ as two cycles $(123)(456)$.

Then any size-$n$ $A \subset D$ must intersect some $3$-cycle at least at two numbers, since there are only $n-1$ such cycles. Those two numbers $x \neq y$ and their corresponding $f(x) \neq f(y)$ all belong to the same $3$-cycle, and by pigeonhole we have $\{x,y\} \cap \{f(x),f(y)\} \neq \varnothing$ and therefore $A \cap f(A) \neq \varnothing$. Thus, $f$ is $n$-intersecting and has $|D(f)| = 3(n-1)$.

I am guessing this bound is tight, but I can't quite prove it yet...

Claim: If the family of $A$ is the family of any interval, i.e. $f$ is "interval-intersecting", then the max deviation is $\mathfrak{c}$, the cardinal of the continuum.

Constructive example: Take $D =$ the Cantor set and $\forall x \in D: f(x) = 0$. Any interval $A$ must include some $y \notin D$, i.e. some $y = f(y)$, so $f$ is interval-intersecting. OTOH, the cardinality of the Cantor set is $\mathfrak{c}$.

Claim: Any $f$ is $\ell$-intersecting for any cardinal $\ell > |D(f)|$ strictly (because any $A$ with $|A| =\ell$ must include some $y \notin D(f)$).

Corollary: Some $\aleph_{0}$-intersecting $f$ exists with any finite deviation, and some $\mathfrak{c}$-intersecting $f$ exists with $\aleph_{0}$ deviation.

Remarks: This still leaves open the $\aleph_{0}$-intersecting and $\mathfrak{c}$-intersecting cases, i.e. whether they can have deviations of $\aleph_{0}$ and $\mathfrak{c}$ respectively.

In antkam's answer, it's conjectured that an $\ell$-intersecting function has deviation at most $3(\ell-1)$. I will prove that in this answer. It's tight, by considering a permutation with $\ell-1$ $3$-cycles.

Suppose that $f$ is $\ell$-intersecting. Consider the directed graph $G$ with vertex set $V = \{ x : f(x) \ne x\}$ (the non-fixed points of $f$) and an edge from $x$ to $f(x)$ whenever $x\in V$ and $f(x) \in V$.

The weak components of $G$ are either

• trees oriented toward a root $r$ such that $f(r) \notin V$, or
• unicyclic components: a directed cycle, with possibly a tree rooted at each of the cycle's vertices.

A set $A$ such that $f[A] \cap A = \varnothing$ is exactly a subset of $V$ which is an independent set in $G$: we can pick at most one endpoint of each edge. This ignores edge orientations, so from now on, we will not care about those.

All trees are bipartite, so for every component that's a tree, we can $2$-color it, and add the larger of the two color classes to $A$. The same works for a unicyclic component with an even cycle. In such cases, a $k$-vertex component contributes at least $\frac k2$ vertices to $A$.

In other unicyclic components, we can delete one vertex from the cycle and be left with a bipartite graph, which we can treat as above. In such cases, a $k$-vertex component contributes at least $\frac{k-1}{2}$ vertices to $A$. When $k$ is even, this guarantees $\frac k2$ vertices, same as before. When $k$ is odd, because $k > 1$ for any component with a cycle, we have $k\ge3$ and therefore $\frac{k-1}{2} \ge \frac k3$.

So in all cases, a $k$-vertex component can contribute at least $\frac k3$ vertices to an independent set $A$; therefore we can find an independent set of total size at least $\frac{|V|}{3}$. However, because $f$ is $\ell$-intersecting, we cannot find an independent set of size $\ell$. Therefore $\frac{|V|}{3} \le \ell-1$, or $|V| \le 3(\ell-1)$. Since $|V|$ is exactly the deviation of $f$, we are done.