Univerzális algebra

Az univerzális algebra (más néven általános algebra) a matematikának, pontosabban az algebrának egy olyan részterülete, amely általános algebrai struktúrákkal és azok homomorfizmusaival, valamint bizonyos általánosításokkal foglalkozik.

Míg az absztrakt algebra és annak különböző részterületei, például a csoportelmélet, a gyűrűelmélet és a testelmélet meghatározott műveletekkel és rögzített tulajdonságokkal rendelkező algebrai struktúrákat vizsgálnak, addig az univerzális algebra általánosságban foglalkozik a struktúrákkal, vagyis tetszőleges műveletekkel és tetszőlegesen rögzíthető tulajdonságokkal rendelkező struktúrákkal. A csoportelmélet például általánosan a csoportokról beszél, míg az univerzális algebra számára a csoportok csupán egy példát jelentenek az algebrai struktúrák egy típusára.^[1]

Az univerzális algebra kapcsolatban áll a modellelmélettel, amely a matematikai logika egy részterülete, és a struktúrák, valamint az ezeket leíró logikai formulák közötti összefüggésekkel foglalkozik. Központi jelentőségű ezen belül az egyenlőségi logika modellelmélete. Az univerzális algebrában alkalmazást nyer továbbá a hálóelmélet is. A kategóriaelmélet pedig egy még általánosabb megközelítést kínál, amelyből kiindulva az univerzális algebra vizsgálható. Ebben az esetben a struktúrák leírása kizárólag azok struktúramegőrző leképezéseinek összefűzés alatti viselkedésére redukálódik, az univerzális algebra esetében pedig konkrétan a homomorfizmusokra.^[2]

Az univerzális algebra alapvető fogalma az algebrai struktúra. Egy algebrai struktúra egy ${\displaystyle A}$ halmaz (amelyet hordozóhalmaznak nevezünk), amely egy műveletcsaláddal van ellátva:

${\displaystyle f_{i}:A^{n_{i}}\to A}$

ahol az ${\displaystyle n_{1},n_{2},\dots ,n_{i}}$ különböző aritású műveleteket jelöl, és ${\displaystyle n_{i}}$ tetszőleges természetes szám lehet. A konstansok formálisan nulláris műveletekként ábrázolhatók.

Például egy csoport egy olyan algebrai struktúra, amely egy bináris művelettel (a csoportszorzással) van ellátva. Egy gyűrű ezzel szemben két kétváltozós művelettel rendelkezik: az összeadással és a szorzással.

Egy csoport, egy gyűrű vagy más algebrai struktúra definíciójánál gyakran további követelményeket is előírunk a műveletekre nézve, például az asszociativitási törvényt. Az univerzális algebra természetes vizsgálati tárgyai ezért olyan algebrai struktúrák osztályai, amelyek adott logikai egyenletek által meghatározott tulajdonságokat elégítenek ki. Sok esetben az egyenlőségi logika elegendő ezek leírására.^[3]

Az egyenlőségi logikában, egyváltozós és nulláris műveletek (például az inverz és a neutrális elem) használatával, a csoportaxiómák például egyszerűen megfogalmazhatók. Az ilyen logikának az az előnyös tulajdonsága, hogy minden alstruktúra – vagyis egy algebrai struktúra olyan részhalmaza, amelyen a műveletek továbbra is jól definiáltak – ugyanazokat az egyenlőségi logikai formulákat elégíti ki. Az ilyen struktúrák osztályai egy speciális esetét képezik azoknak az elemi struktúraosztályoknak, amelyeket a klasszikus modellelmélet az elsőrendű predikátumlogika formulái által axiomatizál.^[4]

Egy homomorfizmus két algebrai struktúra, ${\displaystyle A}$ és ${\displaystyle B}$, között olyan leképezés

${\displaystyle p:A\to B}$

amely megőrzi a műveleteket. Ha az ${\displaystyle A}$ és ${\displaystyle B}$ struktúrák ${\displaystyle f_{i}}$ és ${\displaystyle g_{i}}$ műveletekkel rendelkeznek ugyanazon ${\displaystyle n_{i}}$ aritással, akkor a következő egyenlőség teljesül minden ${\displaystyle i}$-re, valamint minden ${\displaystyle a_{1},\dots ,a_{n}}$ elemre:

${\displaystyle p(f_{i}(a_{1},\dots ,a_{n_{i}}))=g_{i}(p(a_{1}),\dots ,p(a_{n_{i}}))}$

Egy bijektív homomorfizmus egy algebrai struktúrán izomorfizmusnak nevezhető. A homomorfizmusokat morfizmusoknak tekintve az algebrai struktúrák egy kategóriát alkotnak, így a kategóriaelmélet szokásos fogalmai is alkalmazhatók rájuk.^[5]

Az univerzális algebrában egy algebra (vagy algebrai struktúra) egy ${\displaystyle A}$ halmaz, amelyhez egy műveletgyűjtemény tartozik.

Bővebben: Aritás

Egy ${\displaystyle n}$-áris művelet egy ${\displaystyle A}$ halmazon olyan függvény, amely ${\displaystyle n}$ darab ${\displaystyle A}$-beli elemet vesz bemenetként, és egy ${\displaystyle A}$-beli elemet ad vissza kimenetként.

• 0-áris (nulláris) művelet: Egyszerűen egy ${\displaystyle A}$-beli elemként vagy konstansként értelmezhető, amelyet gyakran egy betű, például a jelöl.

• 1-áris (unáris) művelet: Egy olyan függvény ${\displaystyle A}$-ból ${\displaystyle A}$-ba, amelyet gyakran az érvek elé helyezett szimbólummal jelölünk, például .

• 2-áris (bináris) művelet: Egy olyan művelet, amelynek jelölése általában az argumentumok között helyezkedik el (infix notáció), például ${\displaystyle x\ast y}$.

• Magasabb fokú vagy nem meghatározott aritású műveletek: Ezeket általában függvényszimbólumokkal jelöljük, ahol az argumentumokat zárójelek között, vesszővel elválasztva tüntetjük fel, például ${\displaystyle f(x,y,z)}$.

Egy algebra egy adott ${\displaystyle \Omega }$ típusú algebra is lehet, ahol ${\displaystyle \Omega }$ egy természetes számokból álló sorozat, amely az algebra műveleteinek aritását jelöli. Néhány kutató azonban végtelen aritású műveleteket is megenged, például

${\displaystyle \bigwedge {\alpha \in J}x{\alpha }}$

ahol ${\displaystyle J}$ egy végtelen indexhalmaz. Ilyen műveletek például a teljes hálók algebrai elméletében fordulnak elő.

Miután az algebra műveleteit meghatároztuk, annak természetét további axiómák írják le, amelyek az univerzális algebrában gyakran identitásokként vagy egyenleti törvényekként jelennek meg.

Egy példa erre a bináris műveletekre vonatkozó asszociativitási axióma, amelyet az alábbi egyenlet fejez ki:

${\displaystyle x\ast (y\ast z)=(x\ast y)\ast z}$

Ez az axióma azt jelenti, hogy a bináris művelet asszociatív, vagyis bármely ${\displaystyle x,y,z}$ elemre az egyenlőség mindig fennáll az ${\displaystyle A}$ halmazban.

Az olyan algebrai struktúrák gyűjteményét, amelyeket identitások (egyenletek) határoznak meg, varietásnak vagy egyenletekkel meghatározott osztálynak nevezzük.

Az univerzális algebra tanulmányozása a varietásokra való korlátozással kizárja az alábbiakat:

• Mennyiségi kijelentések (kvantorok), beleértve az általános kvantifikációt (∀) – kivéve ha egy egyenlet előtt áll –, valamint az egzisztenciális kvantifikációt (∃).

• Logikai műveletek közül minden mást, kivéve a konjunkciót (∧).

• Egyenlőségen kívüli relációkat, különösen az egyenlőtlenségeket (például a ≠ b) és rendezési relációkat.

Az egyenletekkel meghatározott osztályok vizsgálata a modellelmélet egy speciális ágának tekinthető. Ez általában olyan struktúrákkal foglalkozik, amelyek csak műveletekkel rendelkeznek (azaz a típusa tartalmazhat függvényszimbólumokat, de egyéb relációkat – az egyenlőséget kivéve – nem). Az ilyen struktúrákat leíró nyelv kizárólag egyenletekből áll.

Nem minden algebrai struktúra tartozik ebbe a kategóriába. Például:

• Rendezett csoportok tartalmaznak egy rendezési relációt, így nem illeszkednek ebbe a keretbe.

• Testek osztálya nem képez varietást, mert nincs olyan típus (vagy „szignatúra”), amelyben az összes testtörvény egyenletekként írható fel (például az inverz művelet csak a nem nulla elemekre van definiálva, így nem adható hozzá az algebrai típushoz).

Ezen korlátozások előnye, hogy az univerzális algebra által vizsgált struktúrák bármely véges szorzatokat tartalmazó kategóriában definiálhatók. Például egy topológiai csoport egy egyszerű csoport a topologikus terek kategóriájában.

A matematikában megszokott algebrai rendszerek többsége varietások példája, bár ez nem mindig nyilvánvaló, mert a szokásos definíciók gyakran tartalmaznak kvantorokat vagy egyenlőtlenségeket.

Egy csoport definíciója általában egyetlen bináris művelet (∗) és az alábbi axiómák alapján történik:

• Asszociativitás:

${\displaystyle x\ast (y\ast z)=(x\ast y)\ast z}$

Formálisan: ${\displaystyle \forall x,y,z.\ x\ast (y\ast z)=(x\ast y)\ast z}$.

• Neutrális elem létezése:

${\displaystyle \exists e\forall x.\quad e\ast x=x=x\ast e}$

Azaz létezik egy e elem, amely minden x elemre identitásként működik.

• Inverz elem létezése:

${\displaystyle \forall x\exists i.\quad x\ast i=e=i\ast x}$

Minden ${\displaystyle x}$ elemhez létezik egy ${\displaystyle i}$ elem, amely az inverze.

Ez a csoportdefiníció nem teljesen illeszkedik az univerzális algebra nézőpontjába, mert az identitás és inverz axiómák nem tisztán egyenleti formában szerepelnek, hanem egzisztenciális kvantifikációval („létezik”).

Az egyenleti formában történő megfogalmazás érdekében a következő műveleteket definiáljuk:

• Nulláris művelet ${\displaystyle e}$ a neutrális elem számára,

• Unáris művelet ${\displaystyle \sim x}$ az inverz számára, amelyet gyakran ${\displaystyle x^{-1}}$-ként jelölnek.

Az axiómák így alakulnak:

• Asszociativitás:

${\displaystyle x\ast (y\ast z)=(x\ast y)\ast z}$

• Neutrális elem:

${\displaystyle e\ast x=x=x\ast e}$

• Inverz elem:

${\displaystyle x\ast (\sim x)=e=(\sim x)\ast x}$

Az átalakítás eredménye:

Fontos megjegyezni, hogy az extra műveletek (${\displaystyle e}$ és ~x) nem adnak hozzá új információt, mert a csoport szokásos definíciójából egyértelműen következnek.

Az univerzális algebra szemlélete különösen jól alkalmazható a kategóriaelméletben. Például amikor egy csoportobjektumot definiálunk egy kategóriában (ahol az objektum nem feltétlenül egy halmaz), egyenleti törvényeket kell használni (amelyek általános kategóriákban is értelmesek), nem pedig kvantifikált törvényeket (amelyek egyedi elemekre hivatkoznak).

A kategóriaelméletben például egy topológiai csoport esetén az inverz műveletnek folytonos leképezésnek kell lennie (azaz morfizmusnak kell maradnia a topológiai terek kategóriájában). Néhány szerző emellett megköveteli, hogy az identitásfüggvény zárt inklúzió (kofibráció) legyen.

A legtöbb algebrai struktúra univerzális algebra példája:

• Gyűrűk, félcsoportok, kvázicsoportok, grupoidok, hurkok stb.
• Vektorterek egy rögzített test felett és modulok egy rögzített gyűrű felett szintén univerzális algebrák. Ezek tartalmaznak egy bináris összeadási műveletet és egy unáris skalárszorzási műveletcsaládot.
• Relációs algebrák, például félhálók, hálók, Boole-algebrák.

Tegyük fel, hogy a típus (${\displaystyle \Omega }$) rögzített. Az univerzális algebrában három alapvető konstrukció létezik:

• Homomorf képe egy algebrának
• Részalgebra
• Direkt szorzat

Ezek az alapfogalmak az algebrai struktúrák közötti kapcsolatokat írják le.

Homomorfizmus két algebra, ${\displaystyle A}$ és ${\displaystyle B}$, között egy olyan leképezés

${\displaystyle h:A\to B}$

amely megőrzi az összes algebrai műveletet. Formálisan: ha fᴬ egy A-ban definiált n-áris művelet, és fᴮ a neki megfelelő művelet B-ben, akkor minden ${\displaystyle x_{1},\dots ,x_{n}\in \mathbb {R} }$ A elemre igaz, hogy

${\displaystyle h(f_{A}(x_{1},\dots ,x_{n}))=f_{B}(h(x_{1}),\dots ,h(x_{n}))}$

(Az f alsó indexeit gyakran elhagyjuk, ha egyértelmű, hogy melyik algebrára vonatkoznak.)

Példák speciális aritásra:

• Nulláris művelet (konstans): ha e konstans, akkor

${\displaystyle h(e_{A})=e_{B}.}$

• Unáris művelet (~x):

${\displaystyle h(\sim x)=\sim h(x)}$.

• Bináris művelet (∗):

${\displaystyle h(x\ast y)=h(x)\ast h(y)}$.

A homomorfizmusokkal kapcsolatban számos további konstrukció és speciális definíció létezik. Különösen fontos az algebra homomorf képe, amelyet ${\displaystyle h(A)}$ jelöl.

Egy A algebra részalgebrája A egy részhalmaza, amely zárt az összes ${\displaystyle A}$-ban definiált műveletre nézve. Ez azt jelenti, hogy ha egy művelet ${\displaystyle A}$-ban van definiálva, akkor az adott részhalmazra korlátozva is egy művelet marad.

Egy algebrai struktúrák egy halmazának direkt szorzata az egyes hordozóhalmazok Descartes-szorzata, ahol a műveletek koordinátánként vannak definiálva. Ez azt jelenti, hogy az algebrai műveletek minden komponensre külön-külön hatnak.

Az univerzális algebra nemcsak egységes megközelítést biztosít a különböző algebrai struktúrák számára, hanem mély tételeket, valamint fontos példákat és ellenpéldákat is kínál. Hasznos keretet nyújt azok számára, akik új algebraosztályok tanulmányozásába kezdenek.

Ezen túlmenően lehetővé teszi, hogy bizonyos algebrai struktúrákra kidolgozott módszereket más struktúrákra is alkalmazzuk. Ha egy módszert univerzális algebrai nyelvre fordítunk (amennyiben ez lehetséges), akkor azt más algebraosztályokra is alkalmazhatjuk. Az univerzális algebra fogalmi tisztázást is hozott; ahogyan J.D.H. Smith megfogalmazta:

„ Ami egy adott keretben rendezetlennek és bonyolultnak tűnik, az egy megfelelően általános keretben egyszerűvé és nyilvánvalóvá válhat. ”

Különösen jelentős az univerzális algebra monoidok, gyűrűk és hálók vizsgálatában. Mielőtt az univerzális algebra megjelent, sok tételt (például az izomorfizmustételeket) külön-külön bizonyítottak meg minden egyes algebraosztályban. Az univerzális algebra lehetővé teszi, hogy ezeket egyszer s mindenkorra, általánosan igazolt tételekként bizonyítsuk az összes algebrai rendszerre.

A Higgins (1956) által publikált tanulmány jelentős hatást gyakorolt számos algebrai rendszer vizsgálatára. 1963-as munkája pedig az olyan csak részlegesen definiált műveletekkel rendelkező algebrák tanulmányozását segítette elő, mint például a kategóriák és grupoidok. Ez vezetett a magasabb dimenziós algebra kialakulásához, amely olyan algebrai elméletek vizsgálatával foglalkozik, amelyekben a műveletek csak részlegesen definiáltak, és geometriai feltételek határozzák meg a műveletek érvényességi tartományát. Fontos példák erre a különböző magasabb dimenziós kategóriák és grupoidok.^[6]

Az univerzális algebra természetes nyelvezetet biztosít a korlátos kielégítési probléma ${\displaystyle (CSP)}$ leírására. A ${\displaystyle CSP}$ olyan fontos számításelméleti problémák egy osztályát jelenti, amelyekben egy adott relációs algebra (A) és egy egzisztenciális mondat (φ) adott, és azt kell eldönteni, hogy φ teljesíthető-e A-ban.

Ebben a megközelítésben az algebra A általában rögzített, így a ${\displaystyle CSP(A)}$ azt a problémát jelenti, ahol az egyetlen változó tényező maga az egzisztenciális mondat φ.

Bizonyított, hogy minden számítási probléma megfogalmazható egy megfelelő algebra A esetén ${\displaystyle CSP(A)}$ formájában.

Példa erre az ${\displaystyle n}$-színezési probléma, amely megfogalmazható a következő módon:

• A színezési probléma ${\displaystyle {\text{CSP}}(\{0,1,\dots ,n-1\},\neq )}$ alakban írható le, ahol az algebra n elemű, és egyetlen relációt tartalmaz: az egyenlőtlenséget (≠).

Az osztályozási sejtés (dichotomy conjecture) – amelyet 2017 áprilisában bizonyítottak – kimondja, hogy ha ${\displaystyle A}$ véges algebra, akkor ${\displaystyle CSP(A)}$ vagy ${\displaystyle P}$-beli, vagy ${\displaystyle NP}$-teljes.^[7]

Alfred North Whitehead A ,,Treatise on Universal Algebra''' (Az univerzális algebra értekezete) című könyvében, amely 1898-ban jelent meg, az univerzális algebra kifejezés lényegében ugyanazt a jelentést hordozta, mint ma. Whitehead William Rowan Hamiltont és Augustus De Morgant tekinti a téma megalapítóinak, míg magát a kifejezést James Joseph Sylvesternek tulajdonítja.

Abban az időben olyan struktúrák, mint a Lie-algebrák és a hiperbolikus kvaterniók, rámutattak az algebrai struktúrák kiterjesztésének szükségességére az asszociatív szorzású osztályon túlra. Egy recenziójában Alexander Macfarlane így ír:

„ A mű fő gondolata nem a különböző módszerek egységesítése, sem a közönséges algebra általánosítása annak érdekében, hogy ezeket magába foglalja, hanem inkább az egyes struktúrák összehasonlító vizsgálata.” Akkoriban George Boole logikai algebrája erőteljes ellenpontot jelentett a számok szokásos algebrájával szemben, így az „univerzális” kifejezés a feszültségek enyhítésére szolgált. ”

Whitehead korai munkássága a kvaterniók (Hamilton munkája), Grassmann Ausdehnungslehre-je (kiterjesztési elmélete) és Boole logikai algebrájának egyesítésére irányult. Könyvében Whitehead így ír:

„ Az ilyen algebráknak önmagukban is értéket ad a részletes tanulmányozás; ugyanakkor érdemes összehasonlító vizsgálatot végezni rajtuk, mert ezáltal fény derül a szimbolikus érvelés általános elméletére és az algebrai szimbolizmusra különösen. Az összehasonlító vizsgálat szükségszerűen feltételez némi előzetes önálló tanulmányozást, mivel az összehasonlítás lehetetlen előzetes ismeretek nélkül. ”

Whitehead azonban nem ért el általános érvényű eredményeket. A témában minimális munka folyt egészen az 1930-as évek elejéig, amikor Garrett Birkhoff és Øystein Ore publikálni kezdett az univerzális algebrákról. A metamatematika és a kategóriaelmélet fejlődése az 1940-es és 1950-es években tovább fejlesztette a területet, különösen Abraham Robinson, Alfred Tarski, Andrzej Mostowski és tanítványaik munkájának köszönhetően.

Az 1935 és 1950 közötti időszakban a legtöbb tanulmány Birkhoff munkásságának vonalát követte, és olyan témákkal foglalkozott, mint a szabad algebrák, a kongruenciák és részalgebra-hálók, valamint a homomorfizmusok tételei. Bár a matematikai logika fejlődése lehetővé tette az algebrai alkalmazásokat, ezek lassan terjedtek el; Anatolij Maltsev 1940-es évekbeli eredményeit a háború miatt szinte észre sem vették. Tarski előadása az 1950-es cambridge-i Nemzetközi Matematikai Kongresszuson egy új korszakot indított el, amelyben a modellelméleti szempontok kerültek előtérbe. Ezt a vonalat Tarski mellett C.C. Chang, Leon Henkin, Bjarni Jónsson, Roger Lyndon és mások is követték.

Az 1950-es évek végén Edward Marczewski kiemelte a szabad algebrák fontosságát, amely több mint 50 tanulmány megjelenéséhez vezetett az algebrai szabad algebraelmélet témájában. Ezeket Marczewski maga, valamint Jan Mycielski, Władysław Narkiewicz, Witold Nitka, J. Płonka, S. Świerczkowski, K. Urbanik és mások publikálták.

1963-ban William Lawvere doktori disszertációjától kezdve a kategóriaelmélet technikái egyre fontosabbá váltak az univerzális algebra területén.^[8]

További információ: kategóriaelmélet, operádelmélet, részleges algebra és modellelmélet

Az univerzális algebrát a kategóriaelmélet technikáival is vizsgálták. Ebben a megközelítésben az algebrai struktúra leírására nem egy műveletlista és az azokat kielégítő egyenletek szolgálnak, hanem egy speciális típusú kategória, amelyet Lawvere-elméleteknek vagy általánosabban algebrai elméleteknek nevezünk. Alternatív megoldásként az algebrai struktúrák monádok segítségével is leírhatók. A két megközelítés szorosan összefügg, és mindkettőnek megvannak a maga előnyei. Különösen fontos, hogy minden Lawvere-elmélet egy monádot határoz meg a halmazok kategóriáján, míg minden „végességi” monád ezen a kategórián egy Lawvere-elméletből származtatható. Ugyanakkor egy monád egy adott kategórián belül írja le az algebrai struktúrákat (például a halmazok kategóriájában), míg az algebrai elméletek tágabb kategóriák osztályán belül is alkalmazhatók (konkrétan azokon, amelyek rendelkeznek véges szorzatokkal).^[9]

A kategóriaelmélet egyik újabb fejleménye az operádelmélet. Az operád egy műveletegyüttes, amely hasonló az univerzális algebrához, de azzal a megszorítással, hogy az egyenletek kizárólag változókat tartalmazó kifejezések között engedélyezettek, azaz változók sem ismétlődhetnek, sem kihagyhatók. Például a gyűrűk leírhatók bizonyos operádok úgynevezett „algebráiként”, de a csoportok nem, mivel a ${\displaystyle gg^{-1}=1}$ egyenletben a  g  változó a bal oldalon megismétlődik, míg a jobb oldalon kimarad. Elsőre ez korlátozásnak tűnhet, de előnyei is vannak: például a gyűrű és a vektortér fogalmai kombinálhatók, hogy megkapjuk az asszociatív algebra fogalmát, viszont a csoport és a vektortér fogalmainak hasonló egyesítése nem lehetséges.^[10]

Egy másik általánosítás a részleges algebra, ahol a műveletek részleges függvények is lehetnek. Bizonyos részleges függvények kezelhetők a Lawvere-elméletek egy általánosításával, amelyet lényegében algebrai elméleteknek nevezünk.^[11]

Az univerzális algebra egy további általánosítása a modellelmélet, amelyet néha úgy írnak le, mint az „univerzális algebra + logika”.

• Taylor, Walter: Equational Logic. Houston, Texas: Houston Journal of Mathematics. 1979.  
• Bodirky, Manuel – Grohe, Martin: Non-dichotomies in constraint satisfaction complexity. (hely nélkül): Proceedings of ICALP 2008. 2008.  
• Lawvere, William F: Functorial Semantics of Algebraic Theories (PhD Thesis). (hely nélkül): University of Denver. 1964.  

• Burris, Stanley N – Sankappanavar, H.P: A Course in Universal Algebra. (hely nélkül): Springer-Verlag. 2012.  
• Freese, Ralph – McKenzie, Ralph: Commutator Theory for Congruence Modular Varieties. (hely nélkül): Cambridge University Press. 1987.  
• Cohn, Paul Moritz: Universal Algebra. Dordrecht: Reidel. 1981.  
• Hobby, David – McKenzie, Ralph: The Structure of Finite Algebras. (hely nélkül): American Mathematical Society. 1988.