Simple set (original) (raw)
In computability theory, a subset of the natural numbers is called simple if it is computably enumerable (c.e.) and co-infinite (i.e. its complement is infinite), but every infinite subset of its complement is not c.e.. Simple sets are examples of c.e. sets that are not computable.
| Property | Value |
|---|---|
| dbo:abstract | Einfache und immune Mengen sind Klassen von Teilmengen der natürlichen Zahlen und liefern wichtige Gegenbeispiele in der Berechenbarkeitstheorie.Sie sind eng mit dem Begriff der rekursiven Aufzählbarkeit (RE) verbunden:Während immune Mengen genau die abzählbar unendlichen Mengen natürlicher Zahlen sind, die keine unendliche rekursiv aufzählbare Teilmenge besitzen, sind die einfachen Mengen die rekursiv aufzählbaren Komplemente immuner Mengen.Die Definitionen lassen sich weiter verstärken und führen so auf den Begriff der hyper- oder gar hyperhypereinfachen Mengen. Emil Post vermutete bereits in den 1940er-Jahren die Existenz einfacher Mengen, doch erst 1956 bzw. 1957 konnte dies (unabhängig voneinander) von Richard Friedberg und Albert Muchnik auch bewiesen werden. (de) In computability theory, a subset of the natural numbers is called simple if it is computably enumerable (c.e.) and co-infinite (i.e. its complement is infinite), but every infinite subset of its complement is not c.e.. Simple sets are examples of c.e. sets that are not computable. (en) 単純集合（たんじゅんしゅうごう、英：simple set）とは、数理論理学における再帰理論で扱われるある種の集合。帰納的可算だが帰納的ではない集合の例。 (ja) Иммунное множество — бесконечное множество (например, натуральных чисел), любое перечислимое подмножество которого конечно. В конструктивной математике иммунные множества иногда используются для построения примеров объектов с «патологическими» (с точки зрения традиционной теоретико-множественной математики) свойствами. (ru) |
| dbo:wikiPageExternalLink | https://archive.org/details/classicalrecursi0000odif |
| dbo:wikiPageID | 2451294 (xsd:integer) |
| dbo:wikiPageLength | 3607 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1026378654 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Computability_theory dbr:Computably_enumerable dbr:Emil_Leon_Post dbr:Computable_set dbr:Many-one_reduction dbr:Halting_problem dbc:Computability_theory dbr:Turing_reduction dbr:Post's_problem dbr:Springer-Verlag dbr:Priority_method |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Reflist |
| dct:subject | dbc:Computability_theory |
| rdfs:comment | In computability theory, a subset of the natural numbers is called simple if it is computably enumerable (c.e.) and co-infinite (i.e. its complement is infinite), but every infinite subset of its complement is not c.e.. Simple sets are examples of c.e. sets that are not computable. (en) 単純集合（たんじゅんしゅうごう、英：simple set）とは、数理論理学における再帰理論で扱われるある種の集合。帰納的可算だが帰納的ではない集合の例。 (ja) Иммунное множество — бесконечное множество (например, натуральных чисел), любое перечислимое подмножество которого конечно. В конструктивной математике иммунные множества иногда используются для построения примеров объектов с «патологическими» (с точки зрения традиционной теоретико-множественной математики) свойствами. (ru) Einfache und immune Mengen sind Klassen von Teilmengen der natürlichen Zahlen und liefern wichtige Gegenbeispiele in der Berechenbarkeitstheorie.Sie sind eng mit dem Begriff der rekursiven Aufzählbarkeit (RE) verbunden:Während immune Mengen genau die abzählbar unendlichen Mengen natürlicher Zahlen sind, die keine unendliche rekursiv aufzählbare Teilmenge besitzen, sind die einfachen Mengen die rekursiv aufzählbaren Komplemente immuner Mengen.Die Definitionen lassen sich weiter verstärken und führen so auf den Begriff der hyper- oder gar hyperhypereinfachen Mengen. (de) |
| rdfs:label | Einfache und immune Mengen (de) 単純集合 (ja) Simple set (en) Иммунное множество (ru) |
| owl:sameAs | freebase:Simple set wikidata:Simple set dbpedia-de:Simple set dbpedia-ja:Simple set dbpedia-ru:Simple set https://global.dbpedia.org/id/3tp4C |
| prov:wasDerivedFrom | wikipedia-en:Simple_set?oldid=1026378654&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Simple_set |
| is dbo:wikiPageRedirects of | dbr:Hyperimmune_set dbr:Hypersimple dbr:Hypersimple_set dbr:Immune_set |
| is dbo:wikiPageWikiLink of | dbr:Hyperimmune_set dbr:Hypersimple dbr:Hypersimple_set dbr:Computability_theory dbr:Computably_enumerable_set dbr:Immune_set dbr:Maximal_set dbr:Turing_degree |
| is foaf:primaryTopic of | wikipedia-en:Simple_set |