Definition
A recursively enumerable (r.e.) set is a set of natural numbers S such that there exists an algorithm that, run forever, outputs exactly the members of S. On a non-member, the algorithm may take arbitrarily long and need not halt. Equivalently: S is the domain of some partial recursive function.
Why it matters
How it works
To show S is r.e., exhibit a procedure that systematically outputs members. A common technique: enumerate all candidate witnesses for membership in some order, output any whose witness verifies. To show a complement is r.e., do the same for non-membership. If both S and its complement are r.e., S is recursive (run both enumerators in parallel until one outputs the candidate). If only one is r.e., the set is r.e. but undecidable.