Kvaziodrůda

Kvazi -odrůda (z latinského quas (i) „jako“, „něco jako“) v univerzální algebře je třída algebraických systémů s pevným podpisem , axiomatizovaných sadou kvaziidentit ( Hornovy disjunkty ).

Na rozdíl od variety , což jsou třídy algebraických systémů axiomatizovaných identitami, modelově teoretické metody hrají v teorii kvazivariet zvláštní roli, zatímco variety jsou uvažovány především pro algebry (algebraické systémy bez vztahů v signaturách) a jsou studovány obecnými algebraickými metodami. [1] .

Definice

Pro algebraický systém se sadou operací a vztahů jsou formule tohoto tvaru považovány za kvaziatomické : ${\mathfrak {A}}=\langle A,F,R\rangle$ $F=\langle f_{1}:A^{n_{1}}\do A,\tečky f_{i}:A^{n_{i}}\do A,\tečky \rangle$ $R=\langle r_{1}\subseteq A^{m_{1}},\tečky r_{i}\subseteq A^{m_{i}},\tečky \rangle$

$r_{i}(f_{j1}(x_{1},\tečky ,x_{n_{j))),\tečky ,f_{km_{i))(x_{k1},\tečky ,x_ {n_{k}})))$ (nebo v zápisu vztahu: ), $(f_{j1}(x_{1},\tečky x_{n_{j))),\tečky ,f_{km_{i))(x_{k1},\tečky ,x_{n_{k} }))\v r_{i}$
$f_{j}(x_{1},\tečky ,x_{n_{j)))=f_{k}(x_{1},\tečky ,x_{n_{k))))$ ,

kde , , a jsou symboly proměnných. (Někdy je rovnost součástí signatury algebraického systému jako vztah, v takovém případě stačí formule prvního druhu.) $r_i \in R$ $f_i \in F$ $x_{i}$

Kvazi -identity jsou vzorce ve tvaru:

{\displaystyle \forall x_{1},\dots ,x_{k}\,{\big (}{\mathcal {F}}_{1}\land \dots \land {\mathcal {F}}_{ m}\Rightarrow {\mathcal {F}}_{m+1}{\big )))

kde jsou kvaziatomové vzorce s proměnnými . Kvazivarieta je třída algebraických systémů definovaných množinou kvaziidentit. $\mathcal F_i$ $x_1,\tečky x_k$

Charakteristické vlastnosti

Jakákoli rozmanitost algebraických systémů je kvaziodrůdou, protože jakákoli identita (z kvaziatomového vzorce) může být nahrazena například kvaziidentitou, která je jí ekvivalentní [2] . $\forall x_{1},\tečky ,x_{n}\,{\mathcal {F))(x_{1},\tečky x_{n})$ ${\displaystyle \forall x_{1},\dots ,x_{n}\,{\big (}x_{1}=x_{1}\Rightarrow {\mathcal {F))(x_{1},\tečky ,x_{n}){\big )))$

Pokud je kvazivarieta konečně axiomatizovatelná, pak je konečně definovatelná [3] .

Algebraický systém identity pro daný podpis , to znamená systém podporovaný jedním prvkem , jako je a , je kvazivarieta (a navíc varieta). Nejmenší kvazivarieta daného podpisu je varieta, je dána identitami a skládá se z jediného systému identity. Největší kvazivarietou zpětného podpisu je také varieta, třída všech systémů daného podpisu, definovaná identitou . [čtyři] $\langle F, R \rangle$ $E$ $\forall(f\in F)f(e, \tečky e_i, \tečky)=e$ $\forall(r\in R)(e, \tečky e_i, \tečky) \in r$ $\forall(x,y\in A)(x=y)$ $\forall(x_1, \tečky x_k \in A)(x_1, \tečky x_k)\v r$ $\forall(x)(x=x)$

Jakákoli kvaziodrůda zahrnuje libovolný filtrovaný produkt svých základních systémů [5] .

Aby byla třída systémů kvazivarietou, je nutné a postačující, aby byla současně lokálně uzavřená, multiplikativně uzavřená (obsahovala jakýkoli kartézský součin svých systémů) a obsahovala systém identity. Lokální a multiplikativní uzávěr pro tuto vlastnost lze ekvivalentně nahradit uzávěrem pod filtrovanými produkty a dědičností[ upřesnit ] [6] .

Konstitutivní vztahy

Volné skladby

Svazky kvazivariet

Historie

Za první výsledek aplikace kvaziidentit v obecné algebře je považován výsledek Anatolije Malceva z roku 1939 [7] , ve kterém byla zkonstruována nekonečná řada kvaziidentit, která charakterizuje třídu pologrup vnořitelných do skupin . V článku z roku 1943 od Chena McKinsey [8] spojil některé algoritmické problémy algebry s kvazi-identitami a jeden z výsledků řešení Roberta Dilwortha v roce 1945 [9] problému existence nedistributivních svazů s jediným doplňkem byl důkazem toho, že kvazivariety mají volné systémy.

Novikovův teorém (1955) o nerozhodnutelnosti problému rovnosti slov ve skupinách ve skutečnosti znamená nerozhodnutelnost Hornovy teorie grup , tj. lze ji také připsat výsledkům souvisejícím s kvazivarietami.

Vznik teorie kvazivariet jako nezávislého odvětví univerzální algebry se týká prací Malceva, Tabaty a Fujiwary z konce 50. a počátku 60. let 20. století. K nárůstu zájmu matematiků o toto odvětví přispěla Malcevova zpráva na Mezinárodním kongresu matematiků v roce 1966 v Moskvě, ve které byly formulovány některé důležité problémy související s kvazivarietami [10] .

Zvláštní nárůst zájmu o teorii kvazivariet se projevil v 70. letech 20. století, kdy se Hornova logika začala široce používat v logickém programování (především v pracích souvisejících s programovacím jazykem Prolog ) a v teorii databází .

Poznámky

↑ Gorbunov, 1999 , Zásadní rozdíl je v tom, že algebry jsou studovány v teorii variet, zatímco libovolné algebraické systémy jsou studovány v teorii kvazivariet, str. viii.
↑ Maltsev, 1970 , s. 268.
↑ Maltsev, 1970 , s. 269-270.
↑ Maltsev, 1970 , s. 270.
↑ Maltsev, 1970 , s. 271.
↑ Maltsev, 1970 , Věta 2, Důsledek 3, str. 271-272.
↑ Maltsev A.I. O zahrnutí asociativních systémů do skupin // Matematická sbírka. - 1999. - T. 6 , č. 2 . - S. 331-336 .
↑ McKinsey J. Problém rozhodování pro některé třídy vět bez kvantifikátorů // Journal of Symbolic Logic. - 1943. - T. 8 . - S. 61-76 .
↑ R.P. Dilworth. Mříže s jedinečnými doplňky // Transactions of American Mathematics Society. - 1945. - T. 56 . - S. 123-154 .
↑ Gorbunov, 1999 , s. vii-viii.

Literatura

Gorbunov V. A. Algebraická teorie kvazivariet. - Novosibirsk : Vědecká kniha, 1999. - 368 s. — (Sibiřská škola algebry a logiky). - ISBN 5-88119-015-7 .
Aratmonov V. A.; Saliy V.N.; Skornyakov L. A.; Shevrin L. N.; Shulgeifer E. G. Univerzální algebry // Obecná algebra / pod generální redakcí Skornyakova L. A. . - M .: Nauka , 1991. - T. 2. - S. 295-367. — 480 s. — (Referenční matematická knihovna). — 25 500 výtisků. — ISBN 5-02-014427-4 .
Maltsev AI Algebraické systémy. — M .: Nauka , 1970. — 392 s. - 17 500 výtisků.