Editing Computable set (section)

==Properties==

Both ''A'', ''B'' are sets in this section.

* If ''A'' is computable then the [[complement (set theory)|complement]] of ''A'' is computable.
* If ''A'' and ''B'' are computable then:
** ''A'' ∩ ''B'' is computable.
** ''A'' ∪ ''B'' is computable.
** The image of ''A'' × ''B'' under the [[Cantor pairing function]] is computable.

In general, the image of a computable set under a computable function is computably enumerable, but possibly not computable.

* ''A'' is computable [[if and only if]] ''A'' and the [[complement (set theory)|complement]] of ''A'' are both [[computably enumerable|computably enumerable(c.e.)]].
* The [[preimage]] of a computable set under a [[total function|total]] [[computable function]] is computable.
* The image of a computable set under a total computable [[bijection]] is computable.

''A'' is computable if and only if it is at level <math>\Delta^0_1</math> of the [[arithmetical hierarchy]].

''A'' is computable if and only if it is either the image (or range) of a nondecreasing total computable function, or the empty set.