Encodings
Given a set A, an encoding of A is a function e:A→P≥1(N) assigning to each a∈A a nonempty subset of N. Encodings must also satisfy uniqueness: the images e(a) must be pairwise-disjoint.
If we have a value a∈A, then we think of the image e(a) as telling us every valid way to represent a as a natural number, according to e.
Hence, for a∈A and n∈N and relative to an encoding eA of A, if n∈eA(a) then we may say that n encodes a or that it is an encoding of A. (The word ‘encoding’ thus has two meanings)
An encoding gives us a way to represent values a∈A as natural numbers in order for use when working with (partial) recursive functions, since a (partial) recursive function only knows how to input and output natural numbers and tuples thereof. For instance, we may be interested in asking whether the function
f:Q→Qf(x)=x but with every base-10 digit d replaced by 9−d
is computable, but this question doesn’t even make sense since (partial) recursive functions don’t know how to recieve real numbers as input nor how to output real numbers. We have to tell them! So first we must choose some encoding eQ for Q. If we’ve already figured out a way to encode finite tuples, for instance, we could encode a rational q∈Q by first representing it as a/b for a,b∈Z and then encoding q as (a,b).
Note that a single encoding e for a set A may allow for any particular element of A to be represented in multiple different ways. The above encoding eQ, for instance, admits both (−1,2) and (1,−2) as representations for the rational −1/2. (In most cases one can, with some work, ensure that their encoding has unique representations, but this is not always the case.)