単純集合

単純集合（たんじゅんしゅうごう、英：simple set）とは、数理論理学における再帰理論で扱われるある種の集合。帰納的可算だが帰納的ではない集合の例。

ポストの問題との関係

単純集合はエミール・ポストによってチューリング完全でなく再帰的でもない帰納的可算集合の研究の中で考案された。そのような集合が存在するかどうかはポストの問題として知られる。ポストはこの問題の解答のために2つの事を証明する必要があった。ひとつは、単純集合は空集合にチューリング還元できないということである。いまひとつは、停止問題は単純集合にチューリング還元できないということである。彼が成功したのは前者であり（これは定義より明白）、後者は多対一還元についてのみ遂げられた。

このような集合が存在することはフリードバーグとムチニクにより1950年に独立に証明された。そこでは優先法と呼ばれる手法が用いられた。彼らは単純だが停止性問題を還元できない集合の構成を与えた。[1]

性質

  • 集合 が免疫(immune)とは、 は無限集合であるが、任意の指標 に対して が成り立つことをいう。あるいは同じことであるが、 の無限部分集合で帰納的可算なものが存在しないことをいう。
  • 集合 が単純(simple)とは、それが帰納的可算であり、補集合が免疫であることをいう。あるいは同じことであるが が補無限な帰納的可算集合であって、任意の帰納的可算な無限集合と交わることをいう。
  • 集合 が実効的免疫(effectively immune)とは、 は無限集合であるが、帰納的関数 が存在して、任意の指標 に対して が成り立つことをいう。
  • 集合 が実効的単純(effectively simple)とは、それが帰納的可算であり、補集合が実効的免疫であることをいう。任意の実効的単純集合は単純かつチューリング完全である。
  • 集合 が超免疫(hyper-immune)とは、 は無限集合であるが、 は計算可能な関数によって支配されないことをいう。ただし は の元を昇順に枚挙する関数である。[2]
  • 集合 が超単純(hyper-simple)とは、それが帰納的可算であり、補集合が超免疫であることをいう。[3]任意の超単純集合は単純である。

免疫集合の中には、補集合が同じく免疫であるものもある。このような集合の対は bi-immune[4]と呼ばれる。bi-immune集合は（定義により帰納的可算ではないので）単純集合ではない。

性質

  • 単純集合の集合とクリエイティブ集合の集合の和集合は交わりを持たない（非交和）。単純集合がクリエイティブであることはなく、その逆もない。
  • 集合がクリエイティブであることとm-完全であることとは同値である。ゆえに単純集合はm-完全でない。
  • 単純または余有限(cofinite)である集合の系(collection)は、帰納的可算集合の束の中でフィルターを形成する。

脚注

  1. ^ Nies (2009) p.35
  2. ^ Nies (2009) p.27
  3. ^ Nies (2009) p.37
  4. ^ 訳注：「双免疫」などと訳すべきかも知れないが、定訳不明のため原語のまま

参考文献

  • Robert I. Soare, Recursively Enumerable Sets and Degrees, Springer-Verlag, 1987. ISBN 0-387-15299-7

Read other articles:

Jean Domat

Jean Domat Jean Domat adalah seorang sarjana hukum berkebangsaan Prancis abad ke-17 (pada masa pemerintahan Louis XIV, raja yang menyempurnakan praktik absolutisme kerajaan).[1][2] Ada juga yang mengeja namannya dengan Daumat.[3] Dia lahir pada tanggal 30 November 1625 di Clermont, Auvergne dan meninggal di Paris saat 14 Maret tahun 1696.[1] Le loix civiles dans leur ordre naturel, ed. 1723. Salah satu tulisannya yang terkenal adalah Les lois civiles dans leur ...

 

Nurfirmanwansyah

Nurfirmanwansyah Anggota DPRD Sumatera Barat Fraksi PKSPetahanaMulai menjabat 28 Agustus 2019Mayoritas34.341 suaraMasa jabatan28 Agustus 2004 – 2005Mayoritas8.104 suaraWakil Bupati Solok Selatan ke-1Masa jabatan20 Agustus 2005 – 20 Agustus 2010BupatiSyafrizal J PendahuluTidak ada, Jabatan baruPenggantiAbdul Rahman Informasi pribadiLahir1 Oktober 1964 (umur 59)Muara Labuh, Sumatera BaratKebangsaan IndonesiaPartai politikPKSSuami/istriDaslinarAnak8Alma ma...

 

Jacob Artist

Jacob ArtistArtist pada Desember 2013Lahir17 Oktober 1992 (umur 31)Buffalo, New York, Amerika SerikatPekerjaan Aktor Penyanyi Penari Tahun aktif2011–sekarang Jacob Artist (lahir 17 Oktober 1992) adalah aktor, penyanyi, dan penari Amerika Serikat. Ia paling dikenal untuk perannya sebagai Jake Puckerman dalam seri drama komedi musikal Fox Glee dan sebagai Brandon Fletcher dalam seri drama cerita seru ABC Quantico.[1][2] Referensi ^ Ausiello, Michael. Glee Scoop: Mee...

Rock on the Volga

Rock Festival in Samara, Russia This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Rock on the Volga – news · newspapers · books · scholar · JSTOR (May 2021) (Learn how and when to remove this template message) Rock over the VolgaGenreRock festivalLocation(s)Samara, Samara Oblast, RussiaYears active2009-2013, 2...

 

Nebettawy

NebettawyPermaisuri MesirIstri Kerajaan AgungNyonya Dua TanahNyonya Mesir Hulu dan Hilir, dll.Nebettawy di hadapan Dewa Horus seperti yang digambarkan di makamnyaAyahRamses IIIbuNefertari ?PasanganRamses IInama Mesir Agamaagama Mesir Kuno Nebettawy (nb.t-t3.wỉ; “Nyonya Dua Tanah”) merupakan seorang putri dan ratu Mesir Kuno, ia adalah putri kelima dan salah satu dari delapan Istri Kerajaan Agung Firaun Ramses II. Kehidupan Nebettawy mungkin adalah putri istri kesayangan Ramses...

 

Manapakkam

Neighbourhood in Chennai, Tamil Nadu, IndiaManapakkamNeighbourhoodView of Manapakkam and Nandambakkam from St. Thomas MountManapakkamManapakkam (Chennai)Show map of ChennaiManapakkamManapakkam (Tamil Nadu)Show map of Tamil NaduManapakkamManapakkam (India)Show map of IndiaCoordinates: 13°01′17″N 80°11′00″E / 13.021300°N 80.183200°E / 13.021300; 80.183200Country IndiaStateTamil NaduDistrictChennaiTalukAlandurMetroChennaiGovernment • BodyCMDA...

Leeds North (UK Parliament constituency)

Parliamentary constituency in the United Kingdom, 1885–1955 Leeds NorthFormer Borough constituencyfor the House of CommonsCountyWest Riding of Yorkshire(now West Yorkshire)1885–1955SeatsOneCreated fromLeedsReplaced byLeeds North East Leeds North was a borough constituency in the city of Leeds, West Yorkshire, which returned one Member of Parliament (MP) to the House of Commons of the Parliament of the United Kingdom, elected by the first past the post voting system. Boundaries 1885–1918...

 

Beth Joseph Synagogue

Former synagogue, now museum, in update New York, US Beth Joseph SynagogueThe synagogue, in 2008ReligionAffiliationOrthodox JudaismRiteNusach AshkenazEcclesiastical or organisational statusSynagogueJewish museumStatusActive (summer only)LocationLocation59 Lake Street, Tupper Lake, New York 12986CountryUnited StatesLocation in the Adirondacks, New YorkGeographic coordinates44°13′29″N 74°27′55″W / 44.22472°N 74.46528°W / 44.22472; -74.46528ArchitectureTypeSyn...

 

Ricky Tognazzi

Questa voce o sezione sugli argomenti attori italiani e registi italiani non cita le fonti necessarie o quelle presenti sono insufficienti. Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti dei progetti di riferimento 1, 2. Ricky Tognazzi sul set della miniserie Mia madre (2010) Ricky Tognazzi, all'anagrafe Riccardo Tognazzi (Milano, 1º maggio 1955), è un attore, regista, sceneggiatore e produttore ...

Kurtis Sport Car

Motor vehicle Kurtis Sport CarOverviewManufacturerKurtis KraftProductionc. 1949–1950AssemblyLos Angeles, California, United StatesDesignerFrank KurtisBody and chassisClassSports carBody styleHardtop convertible coupéLayoutFRPlatform1949 FordPowertrainEngineMultiple Ford V8 engines, ranging from 82 hp (61 kW) to 160 hp (120 kW)DimensionsWheelbase2,540 mm (100 in)Length4,293 mm (169 in)Width1,727 mm (68 in)Height1,295 mm (51 i...

 

Dropull i Sipërm

Municipal unit in Gjirokastër, AlbaniaDropull i Sipërm Άνω ΔρόποληMunicipal unitDropull i SipërmCoordinates: 39°55′N 20°18′E / 39.917°N 20.300°E / 39.917; 20.300Country AlbaniaCountyGjirokastërMunicipalityDropullPopulation (2011) • Municipal unit971Time zoneUTC+1 (CET) • Summer (DST)UTC+2 (CEST) Dropull i Sipërm (Greek: Άνω Δρόπολη, Ano Dropoli) is a former municipality in the Gjirokastër County, south...

 

Renata Sorrah

Brazilian actress In this Portuguese name, the first or maternal family name is Leonardo Pereira and the second or paternal family name is Sochaczewski. Renata SorrahSorrah in 2019.BornRenata Leonardo Pereira Sochaczewski (1947-02-21) 21 February 1947 (age 77)Rio de Janeiro, BrazilOccupationActressYears active1967–presentSpouses Carlos Vereza ​ ​(m. 1969; sep. 1971)​ Marcos Paulo ​ ​(m. 1981; div....

Втрати силових структур внаслідок російського вторгнення в Україну (жовтень — грудень 2018)

Докладніше: Втрати силових структур внаслідок російського вторгнення в Україну У статті наведено список втрат українських військовослужбовців у російсько-українській війні з жовтня по грудень 2018 року. Зміст 1 Усі списки 2 Список загиблих з 1 жовтня до 31 грудня 2018 року 2...

 

Zaman Perunggu

Bagian dari seri tentangSejarah dan PrasejarahUmat Manusia ↑ Masa sebelum Homo   (Kala Pliosen) Masa Prasejarah(sistem tiga zaman) Zaman Batu Paleolitikum Awal HomoHomo erectus Paleolitikum Madya Homo sapiens awal Paleotilikum Akhir Modernitas perilaku Epipaleolitikum Mesolitikum Neolitikum Tunas peradaban Protosejarah Kalkolitikum Zaman Perunggu Timur DekatEropaIndiaTiongkok Kebinasaan Akhir Zaman Perunggu Zaman Besi Timur DekatEropaIndiaAsia TimurAfrika Barat Masa Sejarah Abad K...

 

Внутренняя Монголия

У этого термина существуют и другие значения, см. Монголия (значения). Автономный районВнутренняя МонголияМонг.: Öbür Mongγul öbertegen jasaqu orunмонг. Өвөр Монголын Өөртөө Засах Орон[1]кит. упр. 内蒙古自治区, пиньинь Nèiménggǔ zìzhìqū 44° с. ш. 113° в. д.HGЯO Страна  Китай Адм. цент�...

2021 Myanmar coup d'état

2021 military coup in Myanmar 2021 Myanmar coup d'étatPart of the internal conflict and political crisis in MyanmarDeposed State Counsellor of Myanmar Aung San Suu Kyi (left) and Senior General Min Aung Hlaing (right)Date1 February 2021; 3 years ago (2021-02-01)LocationMyanmarResult Military coup d'état successful End of civilian rule and reimposition of military rule Win Myint and Aung San Suu Kyi detained and deposed Twenty-four ministers and deputies deposed[1] ...

 

Say So (lagu Doja Cat)

Say SoSampul resmi SpotifySingel oleh Doja Catdari album Hot PinkDirilis28 Januari 2020FormatDownload digitalstreamingDirekam2019Genre Pop-rap Disko Durasi3:58LabelKemosabeRCAPenciptaAmalaratna Zandile DlaminiLydia AsratLukasz GottwaldYeti BeatsProduserTyson TraxKronologi singel Doja Cat Cyber Sex (2019) Say So (2020) Like That (2020) Video musikSay So di YouTube Say So adalah lagu rapper asal Amerika Serikat, Doja Cat, ditampilkan di album studio keduanya Hot Pink (2019). Lagu ini dikirim ke...

 

Optical coherence tomography

Imaging technique This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details. (April 2020) (Learn how and when to remove this message) A high-resolution spectral-domain OCT scan (3×3 mm) of a dry age-related macular degeneration eye showing geographic atrophy and drusen in macula on both cross-sectional and en face fly-through. Optical coherence tomography (OCT) is an imaging techni...

Malabar District

Administrative district of Bombay and later Madras from 1792 to 1956 This article is about the administrative district of colonial British India. For similarly named places, see Malabar (disambiguation). Malabar districtDistrict of Madras Presidency1792–1956Malabar District with revenue divisions and taluksCapitalCalicutArea • 195115,027[1] km2 (5,802 sq mi)Population • 1951 4,758,842[1] GovernmentDistrict collector  History �...

 

Ian Holloway

English football player and manager Ian Holloway Holloway as Millwall manager in January 2015Personal informationFull name Ian Scott Holloway[1]Date of birth (1963-03-12) 12 March 1963 (age 61)[1]Place of birth Kingswood, Gloucestershire, England[1]Height 1.73 m (5 ft 8 in)[2]Position(s) MidfielderYouth career Bristol RoversSenior career*Years Team Apps (Gls)1980–1985 Bristol Rovers 111 (15)1985–1986 Wimbledon 19 (2)1986–1987 Brentford...