Editing Computably enumerable set (section)

==Properties==

If ''A'' and ''B'' are computably enumerable sets then ''A'' ∩ ''B'', ''A'' ∪ ''B'' and ''A'' × ''B'' (with the ordered pair of natural numbers mapped to a single natural number with the [[Cantor pairing function]]) are computably enumerable sets. The [[preimage]] of a computably enumerable set under a partial computable function is a computably enumerable set.

A set <math>T</math> is called '''co-computably-enumerable''' or '''co-c.e.''' if its [[complement (set theory)|complement]] <math>\mathbb{N} \setminus T</math> is computably enumerable. Equivalently, a set is co-r.e. if and only if it is at level <math>\Pi^0_1</math> of the arithmetical hierarchy. The complexity class of co-computably-enumerable sets is denoted co-RE.

A set ''A'' is [[Computable set|computable]] if and only if both ''A'' and the complement of ''A'' are computably enumerable.

Some pairs of computably enumerable sets are [[effectively separable]] and some are not.