Computable isomorphism

<p>In <a href="/facts/Computability_theory_(computer_science)/cqDfXwdf">computability theory</a> two sets 
  
    
      
        A
        ,
        B
      
    
    {\displaystyle A,B}
  
 of <a href="/facts/Natural_number/u65og8JE">natural numbers</a> are computably isomorphic or recursively isomorphic if there exists a <a href="/facts/Total_function/0vJMw0Nm">total</a> <a href="/facts/Computable/VpnJUkPN">computable</a> and <a href="/facts/Bijective/j4gTuTmW">bijective</a> function 
  
    
      
        f
        :
        
          N
        
        →
        
          N
        
      
    
    {\displaystyle f\colon \mathbb {N} \to \mathbb {N} }
  
 such that the image of 
  
    
      
        f
      
    
    {\displaystyle f}
  
 restricted to 
  
    
      
        A
        ⊆
        
          N
        
      
    
    {\displaystyle A\subseteq \mathbb {N} }
  
 equals 
  
    
      
        B
        ⊆
        
          N
        
      
    
    {\displaystyle B\subseteq \mathbb {N} }
  
, i.e. 
  
    
      
        f
        (
        A
        )
        =
        B
      
    
    {\displaystyle f(A)=B}
  
.
</p><p>Further, two <a href="/facts/Numbering_(computability_theory)/ndLJm4aR">numberings</a> 
  
    
      
        ν
      
    
    {\displaystyle \nu }
  
 and 
  
    
      
        μ
      
    
    {\displaystyle \mu }
  
 are called computably isomorphic if there exists a computable bijection 
  
    
      
        f
      
    
    {\displaystyle f}
  
 so that 
  
    
      
        ν
        =
        μ
        ∘
        f
      
    
    {\displaystyle \nu =\mu \circ f}
  
. Computably isomorphic numberings induce the same notion of computability on a set.
</p>

Computable isomorphism open-in-new

Computable isomorphism