Recursive and Recursively Enumerable Sets

8 minute read

Published: August 21, 2026

Some sets are easy to recognize.

Given an integer, we can determine whether it is even.

Given a string, we can determine whether it is valid UTF-8.

Other sets are stranger.

There may be a procedure that eventually confirms membership when the answer is yes, but may run forever when the answer is no.

This distinction leads to two central concepts in computability theory:

recursive sets,
recursively enumerable sets.

Sets as Decision Problems

Suppose:

[ A\subseteq \mathbb{N} ]

For any natural number (n), ask:

[ n\in A? ]

A set can therefore be viewed as a yes/no problem.

The computational question is:

Can an algorithm always answer correctly?

Characteristic Function

A set A has a characteristic function:

[ \chi_A(n)= \begin{cases} 1 & \text{if } n\in A
0 & \text{if } n\notin A \end{cases} ]

If this function is computable, membership in A is decidable.

Recursive Sets

A set is called recursive, or decidable, if there is an algorithm that:

halts on every input,
answers yes exactly for members,
answers no exactly for nonmembers.

The algorithm always finishes.

Example: Even Numbers

Let:

[ E={n\in\mathbb{N}: n\text{ is even}} ]

Given n, divide by 2 or inspect the last binary bit.

The procedure always terminates.

So E is recursive.

Example: Prime Numbers

The set of prime numbers is also recursive.

A simple algorithm can test divisibility up to:

[ \sqrt n ]

Better algorithms exist.

Efficiency is not the defining issue.

Termination is.

Decidable Does Not Mean Fast

An algorithm may take:

seconds,
years,
longer than the age of the universe.

If it always halts in finite time, the set is still decidable.

Computability and complexity are different questions.

Recursively Enumerable Sets

A set is recursively enumerable, or computably enumerable, if there is an algorithm that can recognize its members.

One equivalent formulation:

if (n\in A), the algorithm eventually halts and says yes;
if (n\notin A), it may run forever.

This is weaker than decidability.

Recognition vs Decision

A decider always returns:

yes or no.

A recognizer may only guarantee:

yes for members.

Silence is ambiguous.

If it keeps running, we do not know whether:

the answer is no,
it simply has not found the confirmation yet.

Enumeration

Another equivalent viewpoint:

A recursively enumerable set can be generated by a program that lists all its members, perhaps in no useful order and with repetition allowed.

If you wait long enough, every member eventually appears.

Nonmembers never appear.

Why “Enumerable”?

The word reflects this listing idea.

A machine can enumerate:

[ a_1,a_2,a_3,\ldots ]

containing exactly the elements of the set.

The enumeration itself may be infinite.

Every Recursive Set Is Recursively Enumerable

If membership is decidable, then membership is certainly recognizable.

So:

[ Recursive \subseteq RE ]

But the inclusion is strict.

Some recursively enumerable sets are not recursive.

Complements

A key theorem says:

A set A is recursive iff:

A is recursively enumerable,
its complement (\overline A) is recursively enumerable.

Why?

Run both recognizers in parallel.

One of them must eventually accept.

Then we obtain a decision.

Dovetailing

Running two potentially infinite computations “in parallel” can be implemented by dovetailing.

Perform:

one step of computation 1,
one step of computation 2,
then repeat.

No computation is allowed to monopolize time.

Dovetailing is a basic computability technique.

The Halting Set

Consider the set:

[ K={\langle P,x\rangle : P\text{ eventually halts on input }x} ]

This set is recursively enumerable.

Why?

Simulate P on x.

If it halts, accept.

If it never halts, simulation continues forever.

But the Halting Set Is Not Recursive

There is no algorithm that always determines whether arbitrary program P halts on arbitrary input x.

This is the halting problem.

So K is the canonical example of:

recognizable but undecidable.

Why This Matters

The distinction tells us that:

having a proof of membership

can be easier than proving nonmembership.

This structure appears throughout logic.

Theorem Sets

In an effectively axiomatized formal system, the set of theorems is often recursively enumerable.

We can enumerate all possible formal proofs.

Whenever a proof ends with formula F, output F.

Every theorem eventually appears.

Non-Theorems Are Harder

What about formulas that are not theorems?

If the theory is undecidable, there may be no algorithm that always confirms non-theoremhood.

Proof search may run forever.

This is the logical version of recognition without decision.

Proof as Certificate

A proof is a finite certificate.

If someone claims:

“This formula is a theorem,”

they can provide a proof.

The proof can be checked mechanically.

No similar finite certificate must exist for non-theoremhood.

Semi-Decidability

“Recursively enumerable” is closely related to the term:

semi-decidable.

A yes answer is eventually detectable.

A no answer may not be.

The asymmetry matters.

Diophantine Equations

Hilbert’s Tenth Problem asks whether an integer polynomial equation has a solution.

If a solution exists, one can search integer tuples until one is found.

So solvability is recognizable.

But Matiyasevich’s theorem shows there is no general decider.

Again:

yes can be witnessed, no may resist algorithmic confirmation.

Search Procedures

Many mathematical problems naturally have this form.

To prove existence, search for an object.

If one exists, eventually find it.

If none exists, exhaustive search may never terminate.

Infinite search creates asymmetry.

Finite vs Infinite Domains

On a finite domain, exhaustive search eventually finishes.

On an infinite domain, failure to find something does not establish nonexistence.

This is why computability becomes subtle.

Recursively Enumerable Relations

The same ideas apply to relations, not just sets.

For example:

“program P halts on input x”

is a binary relation.

Computability theory generalizes membership questions.

Gödel Numbers Return

Because formulas and proofs can be encoded as numbers, sets of syntactic objects become sets of integers.

Examples:

codes of valid formulas,
codes of theorems,
codes of proofs.

Computability theory can therefore study formal logic arithmetically.

Syntax as a Computable Set

The set of well-formed formulas is normally recursive.

Given a finite string, a parser can determine whether grammar accepts it.

Syntax checking terminates.

Proof Validity as a Computable Relation

Given:

a purported proof,
a formal system,

checking whether every step is valid is generally mechanical.

So:

“p is a valid proof of formula f”

is decidable as a relation for ordinary effective proof systems.

Provability as an Existential Search

But theoremhood asks:

Does there exist some proof p of formula f?

[ \exists p\,Proof(p,f) ]

This existential search can be recursively enumerable without being decidable.

The distinction is now visible inside Gödel’s framework.

Church and Turing

Church and Turing gave rigorous models of effective computation.

Their work showed that certain recognizable mathematical sets cannot be decided algorithmically.

Formal limits became mathematical objects.

Enumeration Is Powerful

A recursively enumerable set may still contain extremely complex structure.

“Enumerable” does not mean simple.

It only means a machine can eventually list all members.

Complement Asymmetry

For the halting set K:

K is recursively enumerable.

Its complement is not recursively enumerable.

There is no universal procedure that eventually certifies every nonhalting computation.

This asymmetry is fundamental.

Knowledge Analogy

Recognizable membership resembles:

eventual positive evidence.

A proof appears.

A witness is found.

Nonmembership may lack any finite confirmation.

Computability gives a formal version of epistemic asymmetry.

The Philosophical Lesson

Recursive sets are algorithmically transparent:

membership and nonmembership can both be settled.

Recursively enumerable sets are weaker:

membership can be confirmed, but nonmembership may remain forever unresolved.

The difference between:

“not yet found”

and:

“does not exist”

is one of the deepest boundaries in computation.

The Next Question

Formal systems also need another kind of stability.

A system should not be able to prove both:

[ P ]