Mathematical logic and foundations Definition

Computable set

Definition

Let $A \subseteq \N$ be a subset of the natural numbers. The characteristic function of $A$ is $\chi_A \colon \N \to \set{0, 1}$ , with $\chi_A(n) = 1$ if $n \in A$ and $\chi_A(n) = 0$ if $n \notin A$ . The set $A$ is computable, or recursive, or decidable, if $\chi_A$ is a total computable function. The same definition applies to subsets of $\N^k$ .

Remarks

Example: the set of prime numbers is computable. A machine can test $n \ge 2$ for divisors $d$ with $2 \le d < n$ , which takes finitely many steps, and so computes $\chi_A$ .

Non-example: the set $K = \set{e : \text{program } e \text{ halts on input } e}$ is not computable, by the undecidability of the halting problem. Its characteristic function is total but not computable.

A set $A$ is computable if and only if both $A$ and $\N \setminus A$ are computably enumerable. The computable sets are closed under union, intersection and complement.

Reading path

To understand this page from the ground up, read these 3 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Computable function concept
Subset concept
Computable set definition

Tag	`DN5G4NAF95`
URI	`m2://DN5G4NAF95`
Kind	definition
Writing	W0 stub
MSC	03D25, 03D20
Defines	Computable set
Uses	Computable function, Subset
Changed	2 November 2026

Computable set

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here