Do either of Markov's Principle and the Fan Theorem imply the other? To be concrete: Let's define Markov's Principle as
$$\forall P \subseteq \mathbb N, (\forall n \in \mathbb N, n \in P \vee n \notin P) \to \neg(\forall n \in \mathbb N, n \notin P) \to \exists n \in \mathbb N, n \in P$$
and the Fan Theorem as stated on its nLab page.
 A: To show that Markov's principle doesn't imply the fan theorem:
Markov's principle holds in the effective topos. However, the fan theorem is false in the effective topos, using (the complement of) the Kleene tree. These are respectively corollary 3.1.4 and theorem 3.2.25 in Van Oosten, Realizability: An Introduction to its Categorical Side.
To show that the fan theorem doesn't imply Markov's principle:
In sheaves over Cantor space the fan theorem holds, but not Markov's principle. The fan theorem holds in any topos of sheaves over a topological space (theorem 3.2 in Fourman & Hyland, Sheaf Models for Analysis). To show Markov's principle fails, let $\alpha$ be the generic element of Cantor space. Then the truth value of $(\exists n) \;\alpha(n) = 1$ is $2^\mathbb{N} \setminus \{\lambda x.0\}$, but the truth value of $(\forall n) \;\alpha(n) = 0$ is the interior of $\{\lambda x.0\}$, which is empty, and so the truth value of $\neg (\forall n) \;\alpha(n) = 0$ is $2^\mathbb{N}$ and in particular contains the constant function $\lambda x.0$, so the truth value of $\neg (\forall n) \;\alpha(n) = 0 \;\rightarrow\;(\exists n) \;\alpha(n) = 1$ is not all of $2^\mathbb{N}$.
