Abstrakt

V předložené práci formulujeme problematiku oboru peanovských součinů (na daném modelu Presburgerovy aritmetiky (Pr)) jakožto potenciálně možného základu pro konstrukci modelů Peanovy aritmetiky (PA). Tato problematika je speciálním případem fenoménu prezentace, který úzce souvisí s pojmem bohaté teorie.

Dále se zabýváme jednou ze základních otázek o oboru peanovských součinů, totiž problémem, zda na daném modelu M teorie Pr mohou existovat dva peanovské součiny (·,°) shodující se na nějakém slicu a ∈ M: (∀x) (a·x = a°x) a přitom různé pod a: (∃c,d < a) (c·d ≠ c °d). Tento problém převedeme na otázku, zda eliminační množina lineární aritmetiky (LA) je podmnožinou množiny existenčních formulí.

Úplnou odpověď na tuto otázku v práci nepodáme, dokážeme pouze, že formule tvaru (∀x) (∃z₁, z₂)ψ, kde ψ je konjunkce rovností termů, je ekvivalentní s existenční. Naznačíme, že otázka eliminace v LA je podstatně těžší než v Pr či v teorii modulů a ukážeme, že souvisí s problémem popisu konečně generovaných podmonoidů Z. Přitom zavedeme pojmy (regulární množina, standardní racionalita, zubatice, ...) a metody, které, jak věříme, budou podstatné pro případné budoucí rozřešení tohoto problému.

Klíčová slova

Peanova aritmetika, součiny, lineární aritmetika, eliminace v aritmetice, potkavší se dvojice