| 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
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 3607 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| 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
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
