Recursively enumerable (r.e.) sets are “semi-decidable”: if x belongs to an r.e. set W, then there’s a terminating computation proving that fact. But there may not be any way to verify that x does not belong to W. The founding theorem of recursion theory—the unsolvability of the Halting Problem—furnishes an r.e., non-recursive set. For this set, we have a program listing what’s in W, but no program listing what’s out.
“Does this program halt on this input?” is the easiest non-recursive question you can ask; that’s the moral of Kleene’s Arithmetical Hierarchy. Asking whether a partial recursive function is total is an essentially harder question. “It halts” looks like this:
while “It’s total” looks like this:
So, an 
The question, “Are these two r.e. sets the same?” is also Π2. Wi=Wj if and only if
![\big]](https://s0.wp.com/latex.php?latex=%5Cbig%5D&bg=ffffff&fg=333333&s=0&c=20201002)
You would think that listing the r.e. sets without duplication shared at least the same degree of difficulty. After all, the obvious procedure is to go through the list W1, W2, …, crossing out duplicates.
Remarkably, Richard Friedberg found a way to list the r.e. sets without duplication, using a partial recursive function! To be precise, he described a partial recursive function ψ(x,n) with these two properties: if we let Sn be the set of x‘s for which the computation of ψ(x,n) halts, then (a) every r.e. set appears in the list of all the Sn‘s, and (b) no two of the Sn‘s are the same. I wrote up my own version of his proof, to understand it better.
Friedberg did this with the priority method, which he discovered as an undergrad; he used it to solve a celebrated open question (Post’s problem).
On a personal note, Friedberg was my freshman college physics professor. I only found out about his work in recursion theory years later. One of the best and nicest professors I’ve had.
Diagonal Argument 