But $f$ is a given function. In your answer it seems you choose f to be a one-one function.

Ops. There is a mistake in the statement~ The probability is conditional on: the size of X is larger than N/2-c\sqrt{N}. The question is related to an open question in your paper whether there is a set covers REC but not RE.

It's corrected. Sorry for the typo.

Well, we had a proof. But due to the answer below, see arxiv.org/pdf/1807.00658.pdf page 2

I'd look at your analysis more closely later. But for $F = \{0,2,3,\cdots,k+1\}$, $C = k\mathbb{N}$ gives a set of density $1/k$.

Thanks. How can you be sure the set $C$ you give (for F={2,3}) has the minimal density? Plus, I think $F = \{0,2,3,4,\cdots,k+1\}$ is a conterexample to Q2. But I can't see how to prove that $2/(k+2)$ is the minimal density.

Your question is addressed~