Kvantor elimination

Kvantor elimination er et begreb om forenkling bruges i matematisk logik, model teori og teoretisk datalogi. En måde at klassificere formler er ved mængden af ​​kvantificering. Formler med mindre dybde kvantor vekslen er tænkt som værende enklere, med kvantor-fri formler som den enkleste. En teori har kvantifikator eliminering hvis for hver formel, der findes en anden formel uden kvantorer, der svarer til det.

Eksempler

Eksempler på teorier, der er blevet vist afgørbart bruge kvantor elimination er Presburger aritmetik, algebraisk lukkede felter, virkelige lukkede områder, atomless Boolean algebraer, langsigtede algebraer, tætte lineære ordrer, tilfældige grafer, Feature træer, samt mange af deres kombinationer, såsom boolsk Algebra med Presburger aritmetik, og Term algebraer med køer.

Kvantor eliminator for teorien om de reelle tal som et ordnet additiv gruppe er Fourier-Motzkin elimination; til teorien om området for reelle tal er det Tarski-Seidenberg teorem.

Kvantor elimination kan også bruges til at vise, at "kombinere" afgørbare teorier fører til nye afgørbare teorier. Sådanne konstruktioner omfatter Feferman-Vaught sætning og Term Powers.

Algoritmer og afgørbarhed

Hvis en teori har kvantor elimination, så et specifikt spørgsmål kan løses: Er der en metode til bestemmelse af hver? Hvis der er en sådan metode, vi kalder det en kvantifikator elimination algoritme. Hvis der er en sådan algoritme, så afgørbarhed for teorien reducerer til at beslutte sandheden af ​​kvantor-fri sætninger. Kvantor-fri sætninger har ingen variabler, så deres gyldighed i en given teori ofte kan beregnes, som gør det muligt at anvende kvantor eliminering algoritmer til at afgøre gyldigheden af ​​sætninger.

Relaterede begreber

Forskellige model teoretiske ideer er relateret til kvantor elimination, og der er forskellige tilsvarende betingelser.

Hver teori med kvantifikator elimination er model færdig.

En første ordens teori T har kvantor eliminering hvis og kun hvis en eller anden to modeller B og C i T og for enhver fælles underkonstruktion A i B og C, B og C er elementarily svarer på det sprog, T augmented med konstanter fra A. I virkeligheden er det tilstrækkeligt her for at vise, at enhver sætning med kun eksistentielle kvantorer har samme sandhedsværdi i B og C.

Grundlæggende ideer

For at vise konstruktivt at en teori har kvantor elimination, er det tilstrækkeligt at vise, at vi kan fjerne en eksistentiel kvantor anvendes til en forbindelse af litteraler, der er, viser, at hver formel af formen:

hvor hver er en bogstavelig, svarer til en kvantor-fri formel. Faktisk formoder, at vi ved, hvordan man kan fjerne kvantorer fra konjunktioner af formler, så hvis et kvantor-fri formel, kan vi skrive det i disjunktiv normalform

og bruge det faktum, at

svarer til

Endelig, for at fjerne en universel kvantor

hvor er kvantor-fri, vi forvandle disjunktiv normale form, og bruge det faktum, der svarer til

Historie

I begyndelsen af ​​model teori blev kvantor eliminering brugt til at vise, at forskellige teorier besidder visse model-teoretiske egenskaber som afgørbarhed og fuldstændighed. En almindelig teknik var at vise først, at en teori indrømmer eliminering af kvantorer og derefter bevise afgørbarhed eller fuldstændighed ved at overveje kun kvantor-fri formler. Denne teknik bruges til at vise, at Presburger aritmetik, dvs. teorien om de additive naturlige tal, er afgørbart.

Teorier kan være afgørbart endnu ikke indrømme kvantifikator elimination. Strengt taget, har teorien om de additive naturlige tal ikke indrømme kvantifikator elimination, men det var en udvidelse af de additive naturlige tal, der viste sig at være afgørbart. Når en teori i en tællelig sprog er afgørbart, er det muligt at udvide sit sprog med tælleligt mange relationer for at sikre, at det indrømmer kvantifikator elimination.

Eksempel: Nullstellensatz i ACF og DCF.

  0   0
Forrige artikel Drake af de 99 Dragons
Næste artikel AAA Northwest Region

Kommentarer - 0

Ingen kommentar

Tilføj en kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tegn tilbage: 3000
captcha