In
computability theory two sets
of
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''cardinal ...
s are computably isomorphic or recursively isomorphic if there exists a
total bijective
In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...
computable function
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do ...
with
. By the
Myhill isomorphism theorem
In computability theory the Myhill isomorphism theorem, named after John Myhill, provides a characterization for two numberings to induce the same notion of computability on a set.
Myhill isomorphism theorem
Sets ''A'' and ''B'' of natural nu ...
,
[Theorem 7.VI, Hartley Rogers, Jr., ''Theory of recursive functions and effective computability''] the relation of computable isomorphism coincides with the relation of mutual
one-one reducibility.
Two
numbering
There are many different numbering schemes for assigning nominal numbers to entities. These generally require an agreed set of rules, or a central coordinator. The schemes can be considered to be examples of a primary key of a database management ...
s
and
are called computably isomorphic if there exists a computable bijection
so that
Computably isomorphic numberings induce the same notion of computability on a set.
References
*.
Reduction (complexity)
{{mathlogic-stub