Tarskisův problém exponenciální funkce - Tarskis exponential function problem - Wikipedia

v teorie modelů, Tarskiho problém exponenciální funkce ptá se, zda teorie z reálná čísla společně s exponenciální funkce je rozhodnutelné. Alfred Tarski předtím prokázal, že teorie reálných čísel (bez exponenciální funkce) je rozhodná.

Problém

Objednané skutečné pole R je struktura nad jazykem objednané prsteny L_nebo = (+, ·, -, <, 0,1), s obvyklou interpretací danou každému symbolu. Tarski dokázal, že teorie skutečné pole, Th (R), je rozhodnutelný. To znamená, že existuje L_nebo-věta φ existuje účinný postup pro určení, zda

${ displaystyle mathbb {R} modely varphi.}$

Poté se zeptal, zda tomu tak stále je, pokud do jazyka, který byl interpretován jako, přidal unární funkci exp exponenciální funkce na R, získat strukturu R_exp.

Podmíněné a rovnocenné výsledky

Problém lze omezit na nalezení účinného postupu pro určení, zda je daný exponenciální polynom v n proměnné as koeficienty v% Z má řešení v Rⁿ. Macintyre & Wilkie (1995) to ukázal Schanuelův dohad znamená, že takový postup existuje, a proto poskytl podmínečné řešení Tarského problému. Schanuelova domněnka pojednává o všech složitých číslech, takže by se dalo očekávat, že bude silnějším výsledkem, než je rozhodnutelnost R_expMacintyre a Wilkie skutečně dokázali, že k prokázání rozhoditelnosti této teorie je nutná pouze skutečná verze Schanuelova domněnky.

Dokonce ani skutečná verze Schanuelova domněnky není nutná podmínka pro rozhodnutelnost teorie. Ve svém příspěvku Macintyre a Wilkie ukázali, že ekvivalentní výsledek k rozhodnutelnosti Th (R_exp) je to, čemu říkali dohad slabého Schanuela. Tato domněnka uvádí, že existuje účinný postup, který je dán n ≥ 1 a exponenciální polynomy v n proměnné s celočíselnými koeficienty F₁,..., F_n, G, vytvoří celé číslo η ≥ 1 podle toho n, F₁,..., F_n, G, a takové, že pokud α ∈ Rⁿ je ne singulární řešení systému

${ displaystyle f_ {1} (x_ {1}, ldots, x_ {n}, e ^ {x_ {1}}, ldots, e ^ {x_ {n}}) = ldots = f_ {n} (x_ {1}, ldots, x_ {n}, e ^ {x_ {1}}, ldots, e ^ {x_ {n}}) = 0}$

pak buď G(α) = 0 nebo |G(α)| > η⁻¹.

Řešení

V poslední době existují pokusy zvládnout teorii reálných čísel pomocí funkcí, jako je exp, sin, uvolněním rozhodovatelnosti k slabšímu pojetí kvazi-rozhodovatelnosti. Teorie je kvazi-rozhodnutelná, pokud existuje postup, který rozhoduje o uspokojivosti, ale který může běžet navždy pro vstupy, které nejsou robustní v určitém, dobře definovaném smyslu. Takový postup existuje pro systémy n rovnic v n proměnných (Franek, Ratschan & Zgliczynski (2011) ).

Reference

• Kuhlmann, S. (2001) [1994], "Teorie modelu reálné exponenciální funkce", Encyclopedia of Mathematics, Stiskněte EMS
• Macintyre, A.J .; Wilkie, A.J. (1995), „O rozhodovatelnosti reálného exponenciálního pole“, v Odifreddi, P.G. (vyd.), Kreisel, 70. narozeninový svazek, CLSI
• Franek, Peter; Ratschan, Stefan; Zgliczynski, Piotr (2011), „Splnitelnost systémů rovnic reálných analytických funkcí je kvazi rozhodovatelná“, Matematické základy informatiky 2011, LNCS, 6907Springer, doi:10.1007/978-3-642-22993-0_30