I'm very new to this area of math, so forgive me if this question doesn't make sense.
I am searching for a set X ⊆ N (the naturals) that follows certain decidability rules, and am attempting to work from the halting set as it seemed to be a good starting point: K = {(i, x) | program i halts when run on input x}. However, I'm struggling to understand intuitively if the halting set itself is even a subset of the naturals. Is it? And from an intuitive perspective why/why not? Thanks
In Turing Computability: Theory and Applications, Robert Soare defines $\langle x,y \rangle := \frac{1}{2} (x^2 + 2xy + y^2 + 3x + y)$. According to this definition, each $\langle x, y \rangle$ is a natural number, which implies that $K$ is a set of natural numbers.
One can check that the function $f(x,y) = \frac{1}{2}(x^2 + 2xy + y^2 + 3x + y)$, which is called the Cantor pairing function, is a bijection between pairs of natural numbers and natural numbers. Because this function is a bijection (in particular, because it is an effective bijection), we do not lose any information by treating ordered pairs as numbers defined in this way.
In computability theory, it is standard to define finitary objects, such as finite sets, finite tuples, functions with finite domains, etc., as numbers coded in this way. A coding like this is called a Gödel numbering, and it is useful because:
