Index set (computability)

<h2 id="definition">Definition</h2>
<p>Let 
  
    
      
        
          φ
          
            e
          
        
      
    
    {\displaystyle \varphi _{e}}
  
 be a computable enumeration of all partial computable functions, and 
  
    
      
        
          W
          
            e
          
        
      
    
    {\displaystyle W_{e}}
  
 be a computable enumeration of all <a href="/facts/Computably_enumerable/lpzr8jHn">c.e. sets</a>.
</p><p>Let 
  
    
      
        
          
            A
          
        
      
    
    {\displaystyle {\mathcal {A}}}
  
 be a class of partial computable functions.  If 
  
    
      
        A
        =
        {
        x
        
        :
        
        
          φ
          
            x
          
        
        ∈
        
          
            A
          
        
        }
      
    
    {\displaystyle A=\{x\,:\,\varphi _{x}\in {\mathcal {A}}\}}
  
 then 
  
    
      
        A
      
    
    {\displaystyle A}
  
 is the index set of 
  
    
      
        
          
            A
          
        
      
    
    {\displaystyle {\mathcal {A}}}
  
. In general 
  
    
      
        A
      
    
    {\displaystyle A}
  
 is an index set if for every 
  
    
      
        x
        ,
        y
        ∈
        
          N
        
      
    
    {\displaystyle x,y\in \mathbb {N} }
  
 with 
  
    
      
        
          φ
          
            x
          
        
        ≃
        
          φ
          
            y
          
        
      
    
    {\displaystyle \varphi _{x}\simeq \varphi _{y}}
  
 (i.e. they index the same function), we have 
  
    
      
        x
        ∈
        A
        ↔
        y
        ∈
        A
      
    
    {\displaystyle x\in A\leftrightarrow y\in A}
  
.  Intuitively, these are the sets of natural numbers that we describe only with reference to the functions they index.
</p>
<h2 id="index-sets-and-rices-theorem">Index sets and Rice's theorem</h2>
<p>Most index sets are non-computable, aside from two trivial exceptions. This is stated in <a href="/facts/Rice%27s_theorem/BhXVzM1z">Rice's theorem</a>:
</p>
<p>Let 
  
    
      
        
          
            C
          
        
      
    
    {\displaystyle {\mathcal {C}}}
  
 be a class of partial computable functions with its index set 
  
    
      
        C
      
    
    {\displaystyle C}
  
. Then 
  
    
      
        C
      
    
    {\displaystyle C}
  
 is computable if and only if 
  
    
      
        C
      
    
    {\displaystyle C}
  
 is empty, or 
  
    
      
        C
      
    
    {\displaystyle C}
  
 is all of 
  
    
      
        
          N
        
      
    
    {\displaystyle \mathbb {N} }
  
.</p>
<p>Rice's theorem says "any nontrivial property of partial computable functions is undecidable".<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a>
</p>
<h2 id="completeness-in-the-arithmetical-hierarchy">Completeness in the arithmetical hierarchy</h2>
<p>Index sets provide many examples of sets which are complete at some level of the <a href="/facts/Arithmetical_hierarchy/rQptcBFK">arithmetical hierarchy</a>. Here, we say a 
  
    
      
        
          Σ
          
            n
          
        
      
    
    {\displaystyle \Sigma _{n}}
  
 set 
  
    
      
        A
      
    
    {\displaystyle A}
  
 is <i>
  
    
      
        
          Σ
          
            n
          
        
      
    
    {\displaystyle \Sigma _{n}}
  
-complete</i> if, for every 
  
    
      
        
          Σ
          
            n
          
        
      
    
    {\displaystyle \Sigma _{n}}
  
 set 
  
    
      
        B
      
    
    {\displaystyle B}
  
, there is an <a href="/facts/Many-one_reduction/YUKNlYPh">m-reduction</a> from 
  
    
      
        B
      
    
    {\displaystyle B}
  
 to 
  
    
      
        A
      
    
    {\displaystyle A}
  
. 
  
    
      
        
          Π
          
            n
          
        
      
    
    {\displaystyle \Pi _{n}}
  
-completeness is defined similarly. Here are some examples:<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a>
</p>
<ul><li>
  
    
      
        
          E
          m
          p
        
        =
        {
        e
        
        :
        
        
          W
          
            e
          
        
        =
        ∅
        }
      
    
    {\displaystyle \mathrm {Emp} =\{e\,:\,W_{e}=\varnothing \}}
  
 is 
  
    
      
        
          Π
          
            1
          
        
      
    
    {\displaystyle \Pi _{1}}
  
-complete.</li>
<li>
  
    
      
        
          F
          i
          n
        
        =
        {
        e
        
        :
        
        
          W
          
            e
          
        
        
           is finite
        
        }
      
    
    {\displaystyle \mathrm {Fin} =\{e\,:\,W_{e}{\text{ is finite}}\}}
  
 is 
  
    
      
        
          Σ
          
            2
          
        
      
    
    {\displaystyle \Sigma _{2}}
  
-complete.</li>
<li>
  
    
      
        
          I
          n
          f
        
        =
        {
        e
        
        :
        
        
          W
          
            e
          
        
        
           is infinite
        
        }
      
    
    {\displaystyle \mathrm {Inf} =\{e\,:\,W_{e}{\text{ is infinite}}\}}
  
 is 
  
    
      
        
          Π
          
            2
          
        
      
    
    {\displaystyle \Pi _{2}}
  
-complete.</li>
<li>
  
    
      
        
          T
          o
          t
        
        =
        {
        e
        
        :
        
        
          φ
          
            e
          
        
        
           is total
        
        }
        =
        {
        e
        :
        
          W
          
            e
          
        
        =
        
          N
        
        }
      
    
    {\displaystyle \mathrm {Tot} =\{e\,:\,\varphi _{e}{\text{ is total}}\}=\{e:W_{e}=\mathbb {N} \}}
  
 is 
  
    
      
        
          Π
          
            2
          
        
      
    
    {\displaystyle \Pi _{2}}
  
-complete.</li>
<li>
  
    
      
        
          C
          o
          n
        
        =
        {
        e
        
        :
        
        
          φ
          
            e
          
        
        
           is total and constant
        
        }
      
    
    {\displaystyle \mathrm {Con} =\{e\,:\,\varphi _{e}{\text{ is total and constant}}\}}
  
 is 
  
    
      
        
          Π
          
            2
          
        
      
    
    {\displaystyle \Pi _{2}}
  
-complete.</li>
<li>
  
    
      
        
          C
          o
          f
        
        =
        {
        e
        
        :
        
        
          W
          
            e
          
        
        
           is cofinite
        
        }
      
    
    {\displaystyle \mathrm {Cof} =\{e\,:\,W_{e}{\text{ is cofinite}}\}}
  
 is 
  
    
      
        
          Σ
          
            3
          
        
      
    
    {\displaystyle \Sigma _{3}}
  
-complete.</li>
<li>
  
    
      
        
          R
          e
          c
        
        =
        {
        e
        
        :
        
        
          W
          
            e
          
        
        
           is computable
        
        }
      
    
    {\displaystyle \mathrm {Rec} =\{e\,:\,W_{e}{\text{ is computable}}\}}
  
 is 
  
    
      
        
          Σ
          
            3
          
        
      
    
    {\displaystyle \Sigma _{3}}
  
-complete.</li>
<li>
  
    
      
        
          E
          x
          t
        
        =
        {
        e
        
        :
        
        
          φ
          
            e
          
        
        
           is extendible to a total computable function
        
        }
      
    
    {\displaystyle \mathrm {Ext} =\{e\,:\,\varphi _{e}{\text{ is extendible to a total computable function}}\}}
  
 is 
  
    
      
        
          Σ
          
            3
          
        
      
    
    {\displaystyle \Sigma _{3}}
  
-complete.</li>
<li>
  
    
      
        
          C
          p
          l
        
        =
        {
        e
        
        :
        
        
          W
          
            e
          
        
        
          ≡
          
            
              T
            
          
        
        
          H
          P
        
        }
      
    
    {\displaystyle \mathrm {Cpl} =\{e\,:\,W_{e}\equiv _{\mathrm {T} }\mathrm {HP} \}}
  
 is 
  
    
      
        
          Σ
          
            4
          
        
      
    
    {\displaystyle \Sigma _{4}}
  
-complete, where 
  
    
      
        
          H
          P
        
      
    
    {\displaystyle \mathrm {HP} }
  
 is the <a href="/facts/Halting_problem/Xz1bac40">halting problem</a>.</li></ul>
<p>Empirically, if the "most obvious" definition of a set 
  
    
      
        A
      
    
    {\displaystyle A}
  
 is 
  
    
      
        
          Σ
          
            n
          
        
      
    
    {\displaystyle \Sigma _{n}}
  
 [resp. 
  
    
      
        
          Π
          
            n
          
        
      
    
    {\displaystyle \Pi _{n}}
  
], we can usually show that 
  
    
      
        A
      
    
    {\displaystyle A}
  
 is 
  
    
      
        
          Σ
          
            n
          
        
      
    
    {\displaystyle \Sigma _{n}}
  
-complete [resp. 
  
    
      
        
          Π
          
            n
          
        
      
    
    {\displaystyle \Pi _{n}}
  
-complete].
</p>
<h2 id="notes">Notes</h2>

<ul><li>Odifreddi, P. G. (1992). <i>Classical Recursion Theory, Volume 1</i>. Elsevier. p. 668. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-444-89483-7.</li>
<li>Rogers Jr., Hartley (1987). <i>Theory of Recursive Functions and Effective Computability</i>. MIT Press. p. 482. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-262-68052-1.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Odifreddi, P. G. Classical Recursion Theory, Volume 1.; page 151 <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Soare, Robert I. (2016), "Turing Reducibility", Turing Computability, Theory and Applications of Computability, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 51–78, doi:10.1007/978-3-642-31933-4_3, ISBN 978-3-642-31932-7, retrieved 2021-04-21 <a href="978-3-642-31932-7" target="_blank">978-3-642-31932-7</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
</ol>

Index set (computability) open-in-new

Index set (computability)