Show that no two sets in the probability space with $\mathbb{P}(\{k\})=2^{-k!}$ are independent Let $\mathcal{P}(\mathbb{N})$ denote the power set of $\mathbb{N}$.
Show that no two non-trivial sets in the probability space $(\mathbb{N},\mathcal{P}(\mathbb{N}),\mathbb{P})$ with $\mathbb{P}(\{k\})=2^{-k!}$ for $k\ge2$ and $\mathbb{P}(\{1\})=1-\sum\limits_{k\ge2}\mathbb{P}(\{k\})$ are independent.
There are some hints for this task as follows:
For independent sets $A,B\in\mathcal{P}(\mathbb{N})$, i.e., $\mathbb{P}(A\cap B)=\mathbb{P}(A)\mathbb{P}(B)$,

*

*Show that, wlog $1\notin A\cup B$,

*For $N\ge2$, $\sum\limits_{k>N}2^{N!-k!}\leq\frac{1}{4}$,

*Let $k_A=\min\{k\in A\}$, $k_B=\min\{k\in B\}$, and $k_{AB}=\min\{k\in A\cap B\}$.
Then $2^{-k_{AB}!}\leq2\cdot2^{-k_A!-k_B!}$ and $2\cdot2^{-k_{AB}!}\ge2^{-k_A!-k_B!}$. Finally, lead this to a contradiction.

I have shown 2 and 3 but I am unable to show 1 and even after assuming that 1 is true I am stuck after showing 3 and unable to obtain a contradiction.
If someone could help me with these two things I would really appreciate it.
 A: The question outlines a rigorous proof -- but where does the idea come from?
It all becomes clear when you write the probabilities in binary: from the binary representation of one of these probabilities $\mathbb{P}(A)$ you can read off the elements of $A,$ at least when $1\notin A.$  Just look at positions $2, 6, 24, 120, 720, \ldots, k!, \ldots$ in that number: the elements of $A$ are those $k$ for which a $1$ appears in position $k!.$
Consider how you would multiply two such probabilities in evaluating $\mathbb{P}(A)$ and $\mathbb{P}(B).$ Provided neither of $A$ and $B$ contains $1,$ you must compute the product of the sums
$$\mathbb{P}(A)\mathbb{P}(B) = \sum_{i\in A}2^{-i!}\sum_{j\in B}2^{-j!} = \sum_{(i,j)\in A\times B}2^{-(i!+j!)} = \sum_{k\in\mathbb N} \left(\sum_{(i,j)\in A\times B\mid i!+j!=k} 1\right)2^{-k} .$$
In the right hand sum, ordered pairs $(i,i)$ can appear at most once, but ordered pairs $(i,j)$ for $i\ne j$ can appear either once or twice (a fact proven below).  When they appear twice (that is, both $i$ and $j$ are in both $A$ and $B$), note that they still sum to a power of $2:$
$$2^{-(i!+j!)} + 2^{(-i!+j!)} = 2^{-(i!+j!-1)}.$$
This forces on us a consideration of what the sums of two factorials, $i!+j!,$ might be.  Certainly both $i$ and $j$ are $2$ or greater.  Without any loss of generality, let $i\le j.$  These constraints $2\le i\le j$ easily imply the following inequalities:
$$j! \lt  \color{red}{i! + j! - 1} \lt \color{red}{i! + j!} \le 2j! \lt (j+1)j! = (j+1)!.$$
(The proof that a power $k = i!+j!$ cannot appear more than twice comes down to showing that $i!+j!$ determines the set $\{i,j\},$ which corresponds only to the ordered pairs $i\in A,j\in B$ and $j\in A, i\in B.$  The foregoing inequalities show that $j$ (the larger of the two numbers) can be recovered by finding the largest factorial less than $k=i!+j!;$ and now that $j$ is found, $i$ is found by computing $k-j! = i!,$ which determines $i$ uniquely.)
In all cases, the powers of $2$ appearing in the right hand sum, when expressed in binary, are never themselves factorials (because they are all squeezed between two successive factorials).
Consequently, unless at least one of $A$ and $B$ is empty, it is impossible for this product to be the probability of any set, much less $A\cap B,$ because--just like the probabilities of $A$ and $B$--the binary representation of $\mathbb{P}(A\cap B)$ has ones only in the places $2,6,24,\ldots$ after the binary point.  This proves (3).

The proof of (1) seems elusive until you realize that, very generally, independence of events $A$ and $B$ is equivalent to independence of their complements, too; so if $1\in A,$ replace $A$ by its complement and if $1\in B,$ replace $B$ by its complement, and only then proceed as before to check for independence.

Finally, there's no longer any need to prove (2), but we ought to establish that $\mathbb{P}$ is a valid probability measure.  This comes down to showing that $\mathbb{P}(\{1\})$ is non-negative--but that's obvious, since in binary this probability has ones everywhere except at the digits in locations $2,6,24,\ldots$ after the binary point,

0.101110111111111111111110111111111111111111111111111111111111...B

We may evaluate it in double precision with a simple calculation, such as this R expression
sum(2^(-setdiff(1:60, factorial(2:5))))


0.7343749403953552

