Skip to main content
2 of 4
deleted 4 characters in body
Keshav Srinivasan
  • 4.6k
  • 2
  • 25
  • 51

Understanding a part of Friedberg’s Priority Argument Paper

This is Richard Friedberg’s original 1957 proof of the Friedberg-Muchnik Theorem, the origin of the ground-breaking priority argument. The paper is actually surprisingly understandable once you get past the notation, except for one part that I can’t quite make sense of. But first, let me write the construction in modern notation:

  • Definition: $\Omega \left( x \right) $ denotes the number of prime factors of $x$

  • Stage $s=0$: Let $ f_{0} \left( x \right) =g_{0} \left( x \right) =1$ and $u_{0}(e) =v_{0}(e) =2^{e} $.

  • Stage $s=2n+1$: If $f_{s-1} \left( u_{s-1} \left( \Omega \left( n \right) \right) \right) =1$ and $ \varphi _{ \Omega \left( n \right) ,s}^{g_{s-1}} \left( u_{s-1} \left( \Omega \left( n \right) \right) \right) =1 $, then let $$f_s(x)=\begin{cases} 0 & x= u_{s-1} ( \Omega ( n ) ) \\ f_{s-1}(x)& otherwise \\ \end{cases}, g_{s} \left( x \right) =g_{s-1} \left( x \right) ,u_{s} \left( e \right) =u_{s-1} \left( e \right), v_s(e)=\begin{cases} 2^{e} \left( 2s+1 \right) & e \geq \Omega \left( n \right) \\ v_{s-1}(e)& otherwise \\ \end{cases} $$ If not, let $$f_{s} \left( x \right) =f_{s-1} \left( x \right) ,g_{s} \left( x \right) =g_{s-1} \left( x \right) ,u_{s} \left( e \right) =u_{s-1} \left( e \right) , v_{s} \left( e \right) =v_{s-1} \left( e \right)$$

  • Stage $s=2n+2$: If $g_{s-1} \left( u_{s-1} \left( \Omega \left( n \right) \right) \right) =1$ and $ \varphi _{ \Omega \left( n \right) ,s}^{f_{s-1}} \left( u_{s-1} \left( \Omega \left( n \right) \right) \right) =1 $, then let $$f_{s} \left( x \right) =f_{s-1} \left( x \right), g_s(x)=\begin{cases} 0 & x= u_{s-1} ( \Omega ( n ) ) \\ g_{s-1}(x)& otherwise \\ \end{cases}, u_s(e)=\begin{cases} 2^{e} \left( 2s+1 \right) & e > \Omega \left( n \right) \\ u_{s-1}(e)& otherwise \\ \end{cases}, v_{s} \left( e \right) =v_{s-1} \left( e \right) $$ If not, let $$f_{s} \left( x \right) =f_{s-1} \left( x \right) ,g_{s} \left( x \right) =g_{s-1} \left( x \right) ,u_{s} \left(e\right) =u_{s-1} \left( e \right) , v_{s} \left( e \right) =v_{s-1} \left( e \right)$$

  • End Result: Let $$ f \left( x \right) =\lim_{s \rightarrow \infty}f_{s} \left( x \right) ,g \left( x \right) =\lim_{s \rightarrow \infty}g_{s} \left( x \right) ,u \left( x \right) =\lim_{s \rightarrow \infty}u_{s} \left( x \right) ,v \left( x \right) =\lim_{s \rightarrow \infty}v_{s} \left( x \right) $$

Now the part I don’t understand is the proof of the following Lemma that Friedberg proves:

If $f(u(e))=0$, then $\phi^g_e(u(e))=1$

(If you look at the paper, it’s one direction of Lemma II.) So can anyone explain how to prove this result, either explaining Friedberg’s proof of it or proving it some other way?

Keshav Srinivasan
  • 4.6k
  • 2
  • 25
  • 51