Movatterモバイル変換

[0]ホーム

Jump to content

Computable set

Edit links

From Wikipedia, the free encyclopedia

(Redirected fromRecursive set)

Set with algorithmic membership test

Incomputability theory, aset ofnatural numbers iscomputable (ordecidable orrecursive) if there is analgorithm that computes the membership of every natural number in a finite number of steps. A set is noncomputable (or undecidable) if it is not computable.

Definition

[edit]

A subset $S {\displaystyle S}$ of thenatural numbers iscomputable if there exists atotal computable function $f {\displaystyle f}$ such that:

f(x)=1

x\in S

f(x)=0

x\notin S

In other words, the set $S {\displaystyle S}$ is computableif and only if theindicator function $\mathbb {1} _{S}$ iscomputable.

Examples

[edit]

Everyrecursive language is computable.
Every finite orcofinite subset of the natural numbers is computable.
- Theempty set is computable.
- The entire set of natural numbers is computable.
- Every natural number is computable.^{[note 1]}
The subset ofprime numbers is computable.
The set of Gödel numbers is computable.^{[note 2]}

Non-examples

[edit]

Main article:List of undecidable problems

The set ofTuring machines that halt is not computable.
The set of pairs ofhomeomorphic finitesimplicial complexes is not computable.^[1]
The set ofbusy beaver champions is not computable.
Hilbert's tenth problem is not computable.

Properties

[edit]

BothA,B are sets in this section.

IfA is computable then thecomplement ofA is computable.
IfA andB are computable then:
- A ∩B is computable.
- A ∪B is computable.
- The image ofA ×B under theCantor 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 computableif and only ifA and thecomplement ofA are bothcomputably enumerable(c.e.).
Thepreimage of a computable set under atotal computable function is computable.
The image of a computable set under a total computablebijection is computable.

A is computable if and only if it is at level $\Delta _{1}^{0}$ of thearithmetical 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.

Notes

[edit]

^That is, under theSet-theoretic definition of natural numbers, the set of natural numbers less than a given natural number is computable.
^c.f.Gödel's incompleteness theorems;"On formally undecidable propositions of Principia Mathematica and related systems I" by Kurt Gödel.

References

[edit]

^Markov, A. (1958). "The insolubility of the problem of homeomorphy".Doklady Akademii Nauk SSSR.121:218–220.MR 0097793.

Bibliography

[edit]

Cutland, N.Computability. Cambridge University Press, Cambridge-New York, 1980.ISBN 0-521-22384-9;ISBN 0-521-29465-7
Rogers, H.The Theory of Recursive Functions and Effective Computability, MIT Press.ISBN 0-262-68052-1;ISBN 0-07-053522-1
Soare, R.Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987.ISBN 3-540-15299-7

External links

[edit]

Sakharov, Alex."Recursive Set".MathWorld.

Mathematical logic

General

Theorems (list)
and paradoxes

Logics

Traditional	Classical logic Logical truth Tautology Proposition Inference Logical equivalence Consistency Equiconsistency Argument Soundness Validity Syllogism Square of opposition Venn diagram
Propositional	Boolean algebra Boolean functions Logical connectives Propositional calculus Propositional formula Truth tables Many-valued logic 3 finite ∞
Predicate	First-order list Second-order Monadic Higher-order Fixed-point Free Quantifiers Predicate Monadic predicate calculus

Set theory

Set hereditary Class (Ur-)Element Ordinal number Extensionality Forcing Relation equivalence partition Set operations: intersection union complement Cartesian product power set identities
Types ofsets	Countable Uncountable Empty Inhabited Singleton Finite Infinite Transitive Ultrafilter Recursive Fuzzy Universal Universe constructible Grothendieck Von Neumann
Maps and cardinality	Function/Map domain codomain image In/Sur/Bi-jection Schröder–Bernstein theorem Isomorphism Gödel numbering Enumeration Large cardinal inaccessible Aleph number Operation binary
Set theories	Zermelo–Fraenkel axiom of choice continuum hypothesis General Kripke–Platek Morse–Kelley Naive New Foundations Tarski–Grothendieck Von Neumann–Bernays–Gödel Ackermann Constructive

Formal systems (list),
language and syntax

Example axiomatic
systems (list)

Principia Mathematica

Proof theory

Model theory

Computability theory

Mathematics portal

v t e Set theory
Overview	Set (mathematics)
Axioms	Adjunction Choice countable dependent global Constructibility (V=L) Determinacy projective Extensionality Infinity Limitation of size Pairing Power set Regularity Union Martin's axiom Axiom schema replacement specification
Operations	Cartesian product Complement (i.e. set difference) De Morgan's laws Disjoint union Identities Intersection Power set Symmetric difference Union
Concepts Methods	Almost Cardinality Cardinal number (large) Class Constructible universe Continuum hypothesis Diagonal argument Element ordered pair tuple Family Forcing One-to-one correspondence Ordinal number Set-builder notation Transfinite induction Venn diagram
Set types	Amorphous Countable Empty Finite (hereditarily) Filter base subbase Ultrafilter Fuzzy Infinite (Dedekind-infinite) Recursive Singleton Subset · Superset Transitive Uncountable Universal
Theories	Alternative Axiomatic Naive Cantor's theorem Zermelo General Principia Mathematica New Foundations Zermelo–Fraenkel von Neumann–Bernays–Gödel Morse–Kelley Kripke–Platek Tarski–Grothendieck
Paradoxes Problems	Russell's paradox Suslin's problem Burali-Forti paradox
Set theorists	Paul Bernays Georg Cantor Paul Cohen Richard Dedekind Abraham Fraenkel Kurt Gödel Thomas Jech John von Neumann Willard Quine Bertrand Russell Thoralf Skolem Ernst Zermelo