Richardsons teorem

I matematik fastställer Richardsons teorem obestämbarheten av likheten mellan reella tal definierade av uttryck som involverar heltal , $π$ , ${\displaystyle \ln 2,$ } och exponential- och sinusfunktioner . Det bevisades 1968 av matematikern och datavetaren Daniel Richardson från University of Bath .

Specifikt är den klass av uttryck som satsen gäller den som genereras av rationella tal, talet π , talet ln 2 , variabeln x , operationerna addition, subtraktion, multiplikation, komposition och sin , exp och abs funktioner.

För vissa klasser av uttryck (genererade av andra primitiver än i Richardsons teorem) finns det algoritmer som kan avgöra om ett uttryck är noll.

Uttalande av satsen

Richardsons sats kan anges på följande sätt: Låt E vara en uppsättning uttryck som representerar $\mathbb {R} \to \mathbb {R}$ funktioner. Antag att E inkluderar dessa uttryck:

x (representerar identitetsfunktionen)
e ^x (representerar exponentialfunktionerna)
sin x (representerar sin funktion)
alla rationella tal, ln 2 och π (representerar konstantfunktioner som ignorerar deras inmatning och producerar det givna talet som utdata)

Anta att E också stängs under några standardoperationer. Anta specifikt att om A och B är i E , så är alla följande också i E :

A + B (representerar den punktvisa additionen av funktionerna som A och B representerar)
A − B (representerar punktvis subtraktion)
AB (representerar punktvis multiplikation)
A ∘ B (representerar sammansättningen av funktionerna representerade av A och B )

Då är följande beslutsproblem olösliga:

Besluta om ett uttryck A i E representerar en funktion som är icke-negativ överallt
Om E även inkluderar uttrycket | x | (representerar absolutvärdesfunktionen), bestämma om ett uttryck A i E representerar en funktion som är noll överallt
Om E inkluderar ett uttryck B som representerar en funktion vars antiderivat inte har någon representant i E , avgör om ett uttryck A i E representerar en funktion vars antiderivata kan representeras i E . (Exempel: $e^{ax^{2}}$ har en antiderivata i de elementära funktionerna om och endast om $a = 0$ .)

Tillägg

Efter att Hilberts tionde problem löstes 1970, observerade BF Caviness att användningen av e ^x och ln 2 kunde tas bort. Wang noterade senare att under samma antaganden under vilka frågan om det fanns x med A ( x ) < 0 var olöslig, var frågan om det fanns x med A ( x ) = 0 också olöslig.

Miklós Laczkovich tog också bort behovet av π och minskade användningen av sammansättning. I synnerhet, givet ett uttryck A ( x ) i ringen som genereras av heltal, x , sin x ⁿ och sin( x sin x ⁿ ) (för n som sträcker sig över positiva heltal), båda frågan om A ( x ) > 0 för vissa x och om A ( x ) = 0 för vissa x är olösliga.

Däremot säger Tarski-Seidenberg-satsen att första ordningens teori för det reella fältet är avgörbar, så det är inte möjligt att ta bort sinusfunktionen helt.

Se även

Konstant problem – Problem med att avgöra om ett uttryck är lika med noll
Elementär funktion – Matematisk funktion
Tarskis gymnasiealgebraproblem – Matematiskt problem

Vidare läsning

Petkovšek, Marko ; Wilf, Herbert S .; Zeilberger, Doron (1996). A = B. AK Peters . sid. 212. ISBN 1-56881-063-6 . Arkiverad från originalet 2006-01-29.

externa länkar

Weisstein, Eric W. "Richardsons teorem" . MathWorld .