Felsorolt halmaz

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. május 26-án felülvizsgált verziótól ; az ellenőrzések 7 szerkesztést igényelnek .

A felsorolható halmaz ( effektíve felsorolható , rekurzívan felsorolható , félig eldönthető halmaz [1] ) olyan konstruktív objektumok halmaza (például természetes számok ), amelyek összes eleme valamilyen algoritmus segítségével megszerezhető . Egy felsorolható halmaz komplementerét corekurzívan felsorolhatónak nevezzük [2] . Minden felsorolható halmaz aritmetikai . A magkurzívan felsorolható halmaz nem feltétlenül megszámlálható, de mindig aritmetikus. halmazok megfelelnek hierarchia szintjének $\Sigma _{1}^{0}$ $\Pi _{1}^{0}.$

Minden megoldható halmaz megszámlálható. Egy felsorolható halmaz akkor és csak akkor határozható meg, ha a komplementere is felsorolható. Más szóval, egy halmaz akkor és csak akkor dönthető el, ha egyszerre felsorolható és magkurzívan felsorolható. Egy felsorolható halmaz részhalmaza nem feltétlenül megszámlálható (és még csak nem is aritmetikai).

Az összes megszámlálható részhalmaz halmaza megszámlálható halmaz , a nem megszámlálható részhalmazok halmaza pedig megszámlálhatatlan . $\mathbb {N}$ $\mathbb {N}$

A meghatározás változatai

Az algoritmus fogalmának különböző formalizálásai megfelelnek a felsorolható halmaz fogalmának különböző formális definícióinak, amelyek ekvivalensnek bizonyulnak. Így a rekurzív függvény koncepciója alapján a természetes számok megszámlálható halmazai egy változó részlegesen rekurzív függvényeinek képeiként definiálhatók (ezért a természetes számok megszámlálható halmazait néha "rekurzívan felsorolható halmazoknak" is nevezik). Hasonlóképpen, néhány A ábécé megszámlálható szókészletei bevezethetők Turing -gépek kimeneti halmazaiként külső A ábécével, vagy szavak halmazaiként az A ábécé normál algoritmusainak kimenetei A ábécéjében .

Az algoritmusok elméletében bebizonyosodott az az állítás, hogy a felsorolható halmazok, és csak a felsorolható halmazok, szolgálhatnak az algoritmusok tartományaként. Ez lehetővé teszi számunkra, hogy egy másik ekvivalens módszert vezessünk be a felsorolható halmaz fogalmának meghatározására. Így a természetes számok megszámlálható halmazait tekinthetjük a rekurzív függvények tartományainak, a szavak halmazainak - a Turing-gépek vagy a normál algoritmusok alkalmazhatósági területeinek a megfelelő ábécével.

Példák

Az üres készlet megszámlálható.
Minden eldönthető halmaz (különösen minden véges halmaz ) megszámlálható.
Az üres bemenetnél megálló Turing-gépek számhalmaza is megszámlálható (bár nem eldönthető , mivel komplementere nem megszámlálható).
Egy megszámlálható halmaz vetülete megszámlálható.
Véges számú megszámlálható halmaz egyesülése és metszéspontja is megszámlálható.
A természetes számok azon halmaza, amelyek decimális jelölése részkarakterláncként fordul elő a π szám decimális jelölésében , megszámlálható , és ha π normál , még triviálisan is megoldható (a természetes számok teljes halmaza).
A Khaitin-féle Ω állandónál kisebb racionális számok halmaza megszámlálható, de nem eldönthető.
De a Khaitin-féle Ω állandónál nagyobb racionális számok halmaza nem megszámlálható (bár aritmetikailag és korkurzívan megszámlálható).
Az elsőrendű aritmetikában a bizonyítható állítások halmaza megszámlálható.
De az igaz állítások halmaza az elsőrendű aritmetikában sem nem megszámlálható, sem nem korkurzívan felsorolható (és még csak nem is aritmetika, ami Tarski tételének az igazság aritmetikában való kimondhatatlanságára vonatkozó állítása).

Diophantine

Az egész számok bármely megszámlálható halmaza (vagy egész számok sora) rendelkezik diofantin reprezentációval , azaz valamely algebrai diofantin egyenlet összes megoldásának halmazának vetülete.

Ez különösen azt jelenti, hogy bármely felsorolható halmaz egybeesik azon pozitív értékek halmazával, amelyeket valamilyen egész együtthatós polinom egész számok paramétereihez vett. Ezt az eredményt Jurij Matiyasevics állapította meg .

Lásd még

Immun készlet

Jegyzetek

↑ A. E. Pentus, M. R. Pentus, Formális nyelvek matematikai elmélete, 14. előadás: Algoritmikus problémák // Intuit.ru, 2007.09.07.
↑ Barwise, Kenneth John. Útmutató a matematikai logikáról. 3. rész: rekurzióelmélet. - M .: Nauka, 1982.

Irodalom

Rogers H. A rekurzív függvények elmélete és a hatékony kiszámíthatóság : [ford. angolból . ] / szerk. V. A. Uspensky: per. angolról. V. A. Dushsky, M. I. Kanovich, E. Yu. Nogina. - M .: Mir, 1972.

Felsorolt ​​halmaz