No free lunch theorem proof Assume that learning algorithm $A$ is fixed. Let $D = \{(x_1,y_1),...,(x_N,y_N)\}$, $F$ is set of a data-generating functions(meaning $f \in F$ then $f(x_i) = y_i$ and that functions in $F$ are consistent with the data )and $h:X\rightarrow Y$ is a classifier trained by the algorithm $A$. $L(f(x),y) $ is 1/0-loss function. Then i want to show that $\frac{1}{|F|}\sum_{f \in F}E[L(f(q),h(q))] = \frac{1}{2}$ where $q$ is a test point such that $x_i \neq q$ for all $i$.
My attempt $E[L(f(q),h(q))] = E[I_{f(q) \neq h(q) }(q)] = P(\{f(q) \neq h(q))$ where $I_{f(q) \neq h(q) }(q)$ is an indicator function. How should i evaluate $P(\{f(q) \neq h(q)\})$? My intuition says that $P(\{f(q)\neq h(q)\}) = \frac{1}{2}$, but i cant come up with a formal argument for that.
Any help is apperciated.
Update:
Could i argue that if $h$ just makes a random-guess then the probability that the guess is correct is $\frac{1}{2}$ so therefore $P(\{h(q) \neq f(q)\}) = \frac{1}{2}$ and then the claim follows.
Update2:
If i think the problem this way: for all $f \in F$ there exists a classifier $h$ which is trainable by the algorithm $A$. I still need the fact that how good the classifier $h$ is, which is quite hard to find out
Update3
I assume that data-generating functions $f$ are equally likely and that $h$ is fixed. I still think how i define probability of goodness of $h$ given $f$.

Your question is pretty ill-posed as stated, but answerable with some additional assumptions. In this answer, I will give a "mathematically formal" version of the (correct, +1) argument given by @Thomas Lumley above, while highlighting what assumptions are used and when.
First, I will denote $h:=h_A(D)$ to make it clear that it is the classifier learned by algorithm $A$ from sample $D$. Next, I'll assume that $Y = \{0,1\}$ and that $q$ is a fixed point in $X$ (not random) which is different from all $x_i$.
So, with these assumptions, the quantity you want to compute is
$$\frac{1}{|F|}\sum_{f \in F}\mathbb P\big[f(q)=1-h_A(D)[q]\mid D\big] \tag1 $$
(Note the conditional probability here : the classifier $h_A$ is a function of the sample $D$ so the probability is conditional on it.)
Now, let $U$ be the uniform distribution over the set of functions $F$ (that is, for any $f\in F, \mathbb P(U=f)=1/|F|$). $(1)$ is now given by :
$$\mathbb E_{f\sim U}\left[\mathbb P(f(q)=1-h_A(D)[q]\mid D)\right]\tag2 $$
But now notice that conditional on $D$, $1-h_A(D)[q] $ is a constant : it is either $1$ or $0$. This is where we need the additional assumption stated in @Thomas Lumley's answer above that $F$ is the set of all deterministic functions $X\to Y$ that agree with the sample $D$.
(Here, since you assume that $|F|$ is finite, that also implies that $|X|$ is finite, which is again a common assumption for some versions of the NFL theorem, as explained by Thomas).
With this extra assumption, it follows from the law of total expectation that
$$\begin{align}&\quad\ \, \mathbb E_{f\sim U}\left[ \mathbb P(f(q)=1-h_A(D)[q])\mid D\right]\\
&=\mathbb E_{f\sim U}\left[\mathbb P(f(q)=1)\mid h_A(D)[q]=0, D\right]\cdot\mathbb P(h_A(D)[q]=0\mid D)\\
&+\mathbb E_{f\sim U}\left[\mathbb P(f(q)=0)\mid h_A(D)[q]=1, D\right]\cdot\mathbb P(h_A(D)[q]=1\mid D)\\ 
&=1/2\cdot\mathbb P(h_A(D)[q]=0\mid D)+1/2\cdot\mathbb P(h_A(D)[q]=1\mid D)\\
&=1/2\end{align}$$
which implies the desired result.
