Namespaces
Variants
Actions

Difference between revisions of "Decidable set"

From Encyclopedia of Mathematics
Jump to: navigation, search
(→‎References: better)
(TeX done)
Line 1: Line 1:
A set of constructive objects (cf. [[Constructive object|Constructive object]]) of some fixed type which admits an [[Algorithm|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030390/d0303901.png" /> of natural numbers is said to be decidable if there exists a [[General recursive function|general recursive function]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030390/d0303902.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030390/d0303903.png" />. In this case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030390/d0303904.png" /> is an algorithm for checking whether a natural number belongs to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030390/d0303905.png" />. Actually, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030390/d0303906.png" /> is equivalent to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030390/d0303907.png" />. A decidable set of natural numbers is also often called a general recursive set or a recursive 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|Algorithmic problem]]).
+
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====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  E. Mendelson,  "Introduction to mathematical logic" , v. Nostrand  (1964)</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[1]</TD> <TD valign="top">  E. Mendelson,  "Introduction to mathematical logic" , v. Nostrand  (1964)</TD></TR>
 +
</table>
  
  
Line 17: Line 19:
 
<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>
 
<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>
 
</table>
 +
 +
{{TEX|done}}

Revision as of 22:37, 10 January 2016

A set of constructive objects 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

[1] E. Mendelson, "Introduction to mathematical logic" , v. Nostrand (1964)


Comments

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

References

[a1] H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967) pp. 164–165
[a2] S.C. Kleene, "Introduction to metamathematics" , North-Holland (1951) pp. 288
[a3] William I. Gasarch, Georgia Martin, "Bounded Queries in Recursion Theory", Progress in Computer Science and Applied Logic 16. Springer (1999) ISBN 0817639667
How to Cite This Entry:
Decidable set. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Decidable_set&oldid=34536
This article was adapted from an original article by N.M. Nagornyi (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article