Class of sets whose complements are recursively enumerable; equivalently, problems for which non-membership can be semi-decided by an effective procedure that halts on negative instances.

Principle

A set is co-recursively enumerable (co-r.e.) when there exists a Turing machine that halts and accepts exactly the inputs not in the set; co-r.e. captures semi-decidability of falsity rather than truth.

Demonstration

If the Halting set K is recursively enumerable, then its complement, consisting of encodings of program-input pairs that do not halt, is co-recursively enumerable; membership in the complement can be confirmed if a recognizer for non-halting runs exists (often by enumeration of proofs of non-halting in restricted contexts).

Misapplication

Assuming co-r.e. implies decidability, or treating a procedure that sometimes disproves membership as a uniform refutation method for all inputs without verifying coverage of all cases.

Consequence

For a co-r.e. set one can algorithmically certify non-membership by running the co-recognizer until acceptance; like r.e. sets, co-r.e. sets may not admit effective universal refutation for membership without additional structure.

Reversal

Recursively Enumerable: sets semi-decidable for membership; Decidable: sets that are both r.e. and co-r.e.; Non-co-r.e.: complements of sets that lack enumerators for non-members.

Boundary

Defined with respect to standard models; the class is not closed under complement in general (the complement of a co-r.e. set is r.e., but many sets are neither r.e. nor co-r.e.); excludes higher-complexity or oracle classes unless stated.

Semantic Tension

Tension lies with r.e.: the asymmetry between recognizing positive evidence and recognizing negative evidence creates different algorithmic behaviors and closure properties.

Synthesis

Co-recursively enumerable formalizes the algorithmic recognizability of non-membership: while membership might remain elusive, non-membership can be certified by a halting effective procedure when the set belongs to this class.