View source for Decidable set

A set of [[constructive object]]s of some fixed type which admits an [[algorithm]] for checking whether an element belongs to it. In fact one can restrict oneself to the concept of a decidable set of natural numbers, since the more general case can be reduced to this case by enumerating the objects under consideration. A set $M$ of natural numbers is said to be decidable if there exists a [[general recursive function]] $f$ such that $M = \{ n : f(n) = 0 \}$. In this case $f$ is an algorithm for checking whether a natural number belongs to $M$: indeed, $n \in M$ is equivalent to $f(n) = 0$. A decidable set of natural numbers is also often called a general recursive set or a recursive set.

In many well-known mathematical problems (such as the word identity problem, the homeomorphism problem, Hilbert's 10th problem, the  "Entscheidungsproblem"  in mathematical logic) one is required to prove or refute the assertion that a certain concrete set is decidable. Well-known (negative) solutions to the problems listed above consist of establishing that the sets corresponding to them are undecidable (see also [[Algorithmic problem]]).

====References====
<table>
<TR><TD valign="top">[1]</TD> <TD valign="top">  E. Mendelson,   "Introduction to mathematical logic" , v. Nostrand  (1964)</TD></TR>
</table>



====Comments====
Decidable sets are also referred to as ''recursive'' or ''solvable''.  ([a3], p.11)

====References====
<table>
<TR><TD valign="top">[a1]</TD> <TD valign="top">  H. Rogers jr.,   "Theory of recursive functions and effective computability" , McGraw-Hill  (1967)  pp. 164–165</TD></TR>
<TR><TD valign="top">[a2]</TD> <TD valign="top">  S.C. Kleene,   "Introduction to metamathematics" , North-Holland  (1951)  pp. 288</TD></TR>
<TR><TD valign="top">[a3]</TD> <TD valign="top">  William I. Gasarch, Georgia Martin,   "Bounded Queries in Recursion Theory", Progress in Computer Science and Applied Logic '''16'''. Springer  (1999) ISBN 0817639667</TD></TR>
</table>

{{TEX|done}}