I know that $WKL$ is strictly weaker than $KL$. However, while studying some results on $WKL_0$ I came up with a reasoning that seems to prove that $WKL\rightarrow KL$ over $RCA_0$. This is certainly not possible, so could you please help me in finding the mistake?
For sake of clarity: let $T$ be a tree (a subset of $\mathbb{N}^{<\mathbb{N}}$ closed under initial segment). A path over $T$ is a function $g:\mathbb{N}\to\mathbb{N}$ s.t. $\forall n~g[n]\in T$, where $g[n]=(g(0),...,g(n-1))$.
KL: each infinite, finitely branching tree has a path.
WKL: each infinte tree $T\subset 2^{<\mathbb{N}}$ has a path.
Here's my reasoning: let $T$ be a tree. W.l.o.g. we can assume $T$ to be $2$-branching (i.e. each string has at most $2$ immediate successors - we can prove that $KL$ is equivalent over $RCA_0$ to $KL$ restricted to $2$-branching trees $[1]$).
The idea is to build a binary tree $T'$ that "encodes whether you should go left or right". To formalize this idea, let $\phi(\sigma)$ be a formula that says "there is a $\tau\in T$ s.t. $|\tau|=|\sigma|$ and $\sigma(i)=0$ if $\tau$ takes the left branch of the tree at level $i$ (or is the only branch) and $\sigma(i)=1$ otherwise". It should be possible to write this using a $\Sigma^0_0$ formula (there's only a finite number of strings of length $|\sigma|$ in $T$). I'm not writing it symbolically just to keep the question easy to read.
The set $T'$ defined by $\sigma \in T' \leftrightarrow \phi(\sigma)$ exists by $\Sigma^0_0$-comprehension. Moreover it is a binary tree (easy to see) and is infinite (as $T$ is). Applying the $WKL$ we can conclude that it has a path.
Let $g$ be a path in $T'$. We want to use $g$ to obtain a path in $T$. This should be straightforward: for each $n$ we have that $g[n]\in T'$. This implies that there is a $\tau_n\in T$ s.t. $|\tau_n|=n$ and, for all $i<n$,
- if $g(i)=0$ then for all $\rho \in T$ s.t. $|\rho|=i+1$ we have $\rho[i]=\tau_n[i] \rightarrow \tau_n(i) \le \rho(i)$
- if $g(i)=1$ then for all $\rho \in T$ s.t. $|\rho|=i+1$ we have $\rho[i]=\tau_n[i] \rightarrow \rho(i) < \tau_n(i)$
This just follows from $g[i]\in T'$. Notice also that, for each $n$, $\tau_n$ is a prefix of $\tau_{n+1}$. We can also effectively find $\tau_n$ (for each $n$) as there are only a finite number of strings of length $n$ in $T$. The function $f:= i\mapsto \tau_{i+1}(i)$ is therefore a path of $T$.
$[1]$ Simpson, Subsystems of Second Order Arithmetics, Thm. III.7.2
Your tree $\hat{T}$ (I'm going to avoid the apostrophe notation, because of its use in the Turing jump) is not in fact computable from $T$. It's certainly not $\Sigma^0_0$ relative to $T$ - the quantifier "there is a $\tau\in T$ of length $m$" is unbounded, since all we know a priori is that $T$ is a subtree of $\omega^{<\omega}$!
Before moving on, let me address what I think is the source of the confusion here: the phrase
is indeed quantifying over a finite set, namely the set of nodes in $T$ of length $m$. However, we don't know what that finite set is. From our perspective, the set of things that could be nodes on $T$ of length $m$ is infinite.
This may feel a bit slippery, since we do have a computable way of naming the set of nodes on $T$ of length $m$ - this set can, after all, be computed obviously from $T$! The crucial point, though, is that we can't bound it effectively: we don't just care how many strings there are, we need to know how long we have to search for them. The fact that a second branch in $T$ could "wait until time a billion" to appear (see below) means that this isn't as simple as it seems.
OK, so that's where the mistake was. Having seen that, why should we expect that $\hat{T}$ is in fact not computable relative to $T$ in general? Well, suppose I ask:
The answer is yes if and only if there are two distinct nodes of height $1$ on $T$. However, telling whether this is true is strictly c.e. - to tell that there is no such pair (that is, that $\langle 1\rangle\not\in \hat{T}$) I have to check infinitely many possibilities (is $\langle 0\rangle\in T$? is $\langle 1\rangle\in T$? is $\langle 2\rangle\in T$? etc.).
Having given the motivation, here's an explicit example of a computable $T$ whose associated $\hat{T}$ is not computable: let $T$ be the set of all finite binary strings $\sigma$ such that for all $i$, either $\sigma(i)=0$ or $\sigma(i)-1$ is the least $n$ such that $\Phi_i(i)$ halts in $n$ steps. Basically, $T$ branches twice exactly when a number is in the halting problem. Let $\tau_n$ be the string consisting of $(n-1)$-many $0$s and then a $1$; it's easy to see that $\tau_n\in \hat{T}\iff\Phi_n(n)\downarrow$, so $\hat{T}$ has degree $0'$.
In fact, it's not hard to convert this into a proof that Konig's lemma implies arithmetical comprehension. Specifically, tweak the definition of $T$ above to incorporate truth:
Let $T$ be the set of all finite strings $\sigma$ of natural numbers such that for all $i$,
either $\Phi_i(i)[\vert\sigma\vert]\uparrow$ and $\sigma(i)=0$
or $\sigma(i)=n+1$ and $n$ is the least stage by which $\Phi_i(i)$ has halted.
$T$ has a unique branch, which codes the halting problem. And of course this can be appropriately relativized.