# Is the halting set a subset of the natural numbers?

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

• What kind of thing is $(i,x)$? Is it an element of $\mathbb{N}$? Commented Nov 14, 2023 at 3:03
• I took this definition from en.wikipedia.org/wiki/Halting_problem. Presumably x is any natural number, and i is one of any programs, of which there are countably many Commented Nov 14, 2023 at 3:09
• So I guess that would mean there are countably many tuples (i,x)? Commented Nov 14, 2023 at 3:14
• This is a perfectly good question. Why is there a downvote? Commented Nov 14, 2023 at 6:34

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.
• Written less mysteriously the Cantor pairing function is $\binom{x+y+1}2+x$. Commented Nov 14, 2023 at 6:57