Kreativa och produktiva set

Inom beräkningsbarhetsteorin är produktiva mängder och kreativa mängder typer av mängder av naturliga tal som har viktiga tillämpningar inom matematisk logik . De är ett standardämne i läroböcker i matematisk logik som Soare (1987) och Rogers (1987) .

Definition och exempel

För resten av denna artikel, antag att $\varphi _{i}$ är en tillåten numrering av de beräkningsbara funktionerna och W _i motsvarande numrering av de rekursivt uppräknade mängderna.

En mängd A med naturliga tal kallas produktiv om det finns en total rekursiv (beräknbar) funktion $f$ så att för alla $i\in \mathbb {N}$ , om $A}$ $f(i)\in A\setminus W_{i}.$ sedan Funktionen $f$ kallas den produktiva funktionen för $A.$

En uppsättning A med naturliga tal kallas kreativ om A är rekursivt uppräknad och dess komplement $\mathbb {N} \setminus A$ är produktivt. Inte varje produktiv uppsättning har dock ett rekursivt uppräknat komplement, som illustreras nedan.

Den arketypiska kreativa uppsättningen är ${\displaystyle K=\{i\mid i\in W_{i}\}},$ som representerar stoppproblemet . Dess komplement ${\bar {K}}=\{i\mid i\not \in W_{i}\}$ produktiv med produktiv funktion f ( i ) = i (identitetsfunktionen).

För att se detta tillämpar vi definitionen av en produktiv funktion och visar separat att $i\in {\bar {K}}$ och $i\not \in W_{i }$ :

$i\in {\bar {K}}$ : anta att $i\in K$ , då $i\in W_{i}$ , nu givet att $W_{i}\subseteq {\bar {K}}$ vi har $i\in {\bar {K}}$ leder detta till en motsägelse . Så $i\in {\bar {K}}$ .
$i\not \in W_{i}$ : faktiskt om $i\in W_{i}$ så skulle det vara sant att $i \in K$ , men vi har visat motsatsen i föregående punkt. Så $i\not \in W_{i}$ .

Egenskaper

Ingen produktiv mängd A kan rekursivt räknas upp, för närhelst A innehåller varje tal i en återställning Wi _innehåller den andra tal, och dessutom finns det en effektiv procedur för att ta fram ett exempel på ett sådant tal från indexet i . På samma sätt kan ingen kreativ uppsättning vara avgörbar , eftersom detta skulle innebära att dess komplement, en produktiv uppsättning, är rekursivt uppräknad.

Varje produktiv uppsättning har en produktiv funktion som är injektiv och total .

Följande satser, på grund av Myhill (1955), visar att i en mening alla kreativa mängder är som $K$ och alla produktiva mängder är som ${\bar {K}}$ .

Sats. Låt P vara en uppsättning naturliga tal. Följande är likvärdiga:

P är produktivt.
${\bar {K}}$ är 1-reducerbar till P .
${\bar {K}}$ är m-reducerbar till P .

Sats. Låt C vara en uppsättning naturliga tal. Följande är likvärdiga:

C är kreativ.
C är 1-komplett
C är rekursivt isomorft till K , det vill säga det finns en total beräkningsbar bijektion f på de naturliga talen så att f ( C ) = K .

Tillämpningar i matematisk logik

Uppsättningen av alla bevisbara meningar i ett effektivt axiomatiskt system är alltid en rekursivt uppräknad uppsättning . Om systemet är lämpligt komplext, som första ordningens aritmetik , så kommer mängden T av Gödel-tal av sanna meningar i systemet att vara en produktiv mängd, vilket betyder att när W är en rekursivt uppräknad uppsättning sanna meningar, finns det minst en sann mening som inte finns i W . Detta kan användas för att ge ett rigoröst bevis på Gödels första ofullständighetsteorem , eftersom ingen rekursivt uppräknad mängd är produktiv. Komplementet av mängden T kommer inte att vara rekursivt uppräknad, och därför är T ett exempel på en produktiv mängd vars komplement inte är kreativt.

Historia

Postens (1944) banbrytande tidning definierade konceptet som han kallade en kreativ uppsättning. Upprepa, uppsättningen $K$ som refereras till ovan och definieras som domänen för funktionen $d(x)=[[x]](x )+1$ som tar diagonalen för alla uppräknade 1-plats beräkningsbara delfunktioner och lägger till 1 till dem är ett exempel på en kreativ uppsättning. Post gav en version av Gödels ofullständighetsteorem med hjälp av hans kreativa uppsättningar, där Gödel ursprungligen i någon mening hade konstruerat en mening som fritt kunde översättas med att säga "Jag är obevisbar i denna axiomatiska teori." Gödels bevis fungerade dock inte utifrån begreppet sanna meningar, utan använde snarare begreppet en konsekvent teori, vilket ledde till den andra ofullständighetssatsen . Efter att Post slutfört sin version av ofullständighet lade han till följande:

"Slutsatsen är oundviklig att även för en sådan fast, väldefinierad mängd matematiska propositioner, är och måste matematiskt tänkande i huvudsak vara kreativt."

Den vanliga kreativa uppsättningen $K$ definierad med diagonalfunktionen $d(x)$ har sin egen historiska utveckling. Alan Turing visade i en artikel från 1936 om Turing-maskinen förekomsten av en universell dator som beräknar funktionen ${\displaystyle \Phi } .$ Funktionen $\Phi$ är definierad så att ${\displaystyle \Phi (w,x)=} ($ resultatet av att tillämpa instruktionerna kodade av $w$ på ingången $x$ ), och är universell i den meningen att varje beräkningsbar delfunktion $f$ ges av $f(x)=\Phi ( e,x)$ för alla $x$ där $e$ kodar instruktionerna för $f$ . Med ovanstående notation $\Phi (e,x)=[[e]](x)$ , och diagonalfunktionen uppstår ganska naturligt som $d(x)=[[x]](x)+1$ . I slutändan är dessa idéer kopplade till kyrkans tes som säger att den matematiska föreställningen om beräkningsbara delfunktioner är den korrekta formaliseringen av en effektivt beräkningsbar delfunktion, som varken kan bevisas eller motbevisas. Church använde lambdakalkyl , Turing en idealiserad dator och senare Emil Post i sitt tillvägagångssätt, som alla är likvärdiga.

Deborah Joseph och Paul Young ( 1985 ) formulerade ett analogt koncept, polynomisk kreativitet , i beräkningskomplexitetsteori och använde det för att ge potentiella motexempel till Berman-Hartmanis-förmodan om isomorfism av NP-kompletta uppsättningar.

Anteckningar

Davis, Martin (1958), Beräkningsbarhet och olöslighet , Series in Information Processing and Computers, New York: McGraw-Hill, MR 0124208 . Omtryckt 1982 av Dover Publications.
Enderton, Herbert B. (2010), Computability Theory: An Introduction to Recursion Theory , Academic Press, ISBN 978-0-12-384958-8 .
Joseph, Deborah ; Young, Paul (1985), "Some remarks on witness functions for nonpolynomial and noncomplete sets in NP", Theoretical Computer Science , 39 (2–3): 225–237, doi : 10.1016/0304-3975(85)90140-9 MR 0821203 _
Kleene, Stephen Cole (2002), Mathematical logic , Mineola, NY: Dover Publications Inc., ISBN 0-486-42533-9 , MR 1950307 . Omtryck av originalet från 1967, Wiley, MR 0216930 .
Myhill, John (1955), "Creative sets", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik , 1 (2): 97–108, doi : 10.1002/malq.19550010205 , MR 0071379 .
Post, Emil L. (1944), "Rekursivt uppräknade uppsättningar av positiva heltal och deras beslutsproblem", Bulletin of the American Mathematical Society , 50 ( 5): 284–316, doi : 10.1090/S0002-9904-1944-08111- 1 , MR 0010514
Rogers, Hartley, Jr. (1987), Theory of rekursiva funktioner och effektiv beräkningsbarhet (2:a upplagan), Cambridge, MA: MIT Press, ISBN 0-262-68052-1 , MR 0886890 .
Soare, Robert I. (1987), Recursively enumerable sets and degrees: A study of computable functions and computably generated sets , Perspectives in Mathematical Logic, Berlin: Springer-Verlag, ISBN 3-540-15299-7 , MR 0882921 .