Klon (algebra) - Clone (algebra) - Wikipedia

v univerzální algebra, a klon je soubor C konečných operace na setu A takhle

  • C obsahuje všechny projekce πkn: An → A, definován πkn(X1, …,Xn) = Xk,
  • C je uzavřen pod (finitární násobek) složení (nebo „superpozice“):[1] -li F, G1, …, Gm jsou členy C takhle F je m-ary, a Gj je n-ary pro všechny j, pak n-ary provoz h(X1, …,Xn) := F(G1(X1, …,Xn), …, Gm(X1, …,Xn)) je v C.

Otázka, zda by klony měly obsahovat operace s nullou nebo ne, není v literatuře zpracována jednotně. Klasický přístup, o čemž svědčí standardní monografie[2][3][4] teorie klonů považuje klony pouze za obsahující alespoň unární operace. Avšak pouze s malými úpravami (souvisejícími s prázdným invariantním vztahem) lze většinu obvyklé teorie pozvednout na klony umožňující operace s nullou.[5]:4–5 Obecnější pojem[6] zahrnuje všechny klony bez operací nullary jako subklony klonu všech alespoň unárních operací[5]:5 a je v souladu se zvykem povolit nullary a operace s nullary v univerzální algebře. Typicky publikace studující klony jako abstraktní klony, např. v kategorii teoretického nastavení Lawvereho algebraických teorií bude zahrnovat operace s nullou.[7][8]

Vzhledem k algebra v podpis σ, soubor operací na jeho nosiči definovatelný a σ-období (dále jen termínové funkce) je klon. Naopak každý klon lze realizovat jako klon termínových funkcí ve vhodné algebře pouhým převzetím samotného klonu jako zdroje podpisu σ takže algebra má jako základní operace celý klon.

Li A a B jsou algebry se stejným nosičem, takže každá základní funkce A je termín funkce v B a naopak A a B mít stejný klon. Z tohoto důvodu moderní univerzální algebra často zachází s klony jako s reprezentací algeber, která abstrahuje od jejich podpisu.

V sadě jednoho prvku je pouze jeden klon (jsou-li uvažovány operace s nullou, existují dva). Mřížka klonů na dvouprvkové sadě je spočítatelná,[9][10][3]:39 a byl zcela popsán uživatelem Emil Post[11][10] (vidět Postova mříž,[3]:37 který tradičně neukazuje klony s nullovými operacemi). Klony na větších sadách nepřipouští jednoduchou klasifikaci; existují kontinuum - mnoho klonů o konečné sadě velikostí nejméně tři,[12][3]:39 a 22κ (i jen maximální,[10][3]:39 tj. předkompletní) klony na nekonečné množině mohutnostiκ.[9][3]:39

Abstraktní klony

Philip Hall představil koncept abstraktní klon.[13] Abstraktní klon se liší od konkrétního klonu v dané sadě A abstraktní klon obvykle není

  • sada Cn pro každé přirozené číslo n,
  • elementy πk,n v Cn pro všechny k ≤ n, a
  • rodina funkcí ∗:Cm × (Cn)m → Cn pro všechny m a n

takhle

  • C * (π1,n,...,πn,n) = C
  • πk,m * (C1,...,Cm) = Ck
  • C * (d1 * (E1, ..., En), ..., dm * (E1, ..., En)) = (C * (d1,..., dm)) * (E1,...,En).

Jakýkoli konkrétní klon určuje zřejmým způsobem abstraktní klon.

Jakákoli algebraická teorie určuje abstraktní klon kde Cn je sada termínů v n proměnné, πk,n jsou proměnné a ∗ je substituce. Dvě teorie určují izomorfní klony právě tehdy, jsou-li odpovídající kategorie algeber izomorfní. Naopak každý abstraktní klon určuje algebraickou teorii s n-ary operace pro každý prvek Cn. To dává bijektivní korespondenci mezi abstraktními klony a algebraickými teoriemi.

Každý abstraktní klon C indukuje a Lawvereova teorie ve kterém jsou morfismy m → n jsou prvky (Cm)n. To vyvolává bijektivní korespondenci mezi Lawvereovými teoriemi a abstraktními klony.

Viz také

Poznámky

  1. ^ Denecke, Klaus (2003). „Mengerovy algebry a klony výrazů“. East-West Journal of Mathematics. 5 (2): 179. ISSN  1513-489X.
  2. ^ Pöschel, Reinhard; Kalužnin, Lev A. (1979). Funktionen- und Relationenalgebren. Ein Kapitel der diskreten Mathematik. Mathematische Monographien (v němčině). 15. Berlín: VEB Deutscher Verlag der Wissenschaften.
  3. ^ A b C d E F Szendrei, Ágnes (1986). Klony v univerzální algebře. Séminaire de Mathématiques Supérieures. 99. Montréal, QC: Presses de l'Université de Montréal. ISBN  978-2-7606-0770-5.
  4. ^ Lau, Dietlinde (2006). Funkční algebry na konečných množinách. Základní kurz o mnohocenné logice a klonové teorii. Springer Monografie z matematiky. Berlín: Springer. doi:10.1007/3-540-36023-9. ISBN  978-3-540-36022-3.
  5. ^ A b Behrisch, Mike (2014). Moc, John; Wingfield, Cai (eds.). „Klony s Nullary Operations“. Elektronické poznámky v teoretické informatice. 303: 3–35. doi:10.1016 / j.entcs.2014.02.002. ISSN  1571-0661.
  6. ^ McKenzie, Ralph N.; McNulty, George F .; Taylor, Walter F. (1987). Algebry, mřížky, odrůdy. Já. Monterey, CA: Wadsworth & Brooks / Cole Advanced Books & Software. p. 143. ISBN  978-0-534-07651-1.
  7. ^ Trnková, Věra; Sichler, Jiří (2009). "Všechny klony jsou klony centralizátoru". Algebra Universalis. 61 (1): 77–95. CiteSeerX  10.1.1.525.167. doi:10.1007 / s00012-009-0004-4. ISSN  0002-5240.
  8. ^ Trnková, Věra; Sichler, Jiří (2008). „Na klonech určených jejich počátečními segmenty“. Cahiers de Topologie et Géométrie Différentielle Catégoriques. 49 (3). ISSN  1245-530X.
  9. ^ A b Rosenberg, Ivo G. (1974). "Některé maximální uzavřené třídy operací na nekonečných množinách". Mathematische Annalen. Berlín / Heidelberg: Springer. 212 (2): 158. doi:10.1007 / BF01350783. ISSN  0025-5831. PAN  0351964. Zbl  0281.08001.
  10. ^ A b C Rosenberg, Ivo G. (1976). "Sada maximálních uzavřených tříd operací na nekonečné množině." A má mohutnost 22| A |". Archiv der Mathematik. Basilej: Springer (Birkhäuser). 27 (6): 562. doi:10.1007 / BF01224718. ISSN  0003-889X. PAN  0429700. Zbl  0345.02010.
  11. ^ Post, Emil Leon (1941). Dvouhodnotové iterační systémy matematické logiky. Annals of Mathematics Studies. 5. Princeton, N. J .: Princeton University Press. str. viii + 122. PAN  0004195.
  12. ^ Юрий Иванович Янов (Jurij Ivanovič Janov); Альберт Абрамович Мучник (Aľbert Abramovič Mučnik) (1959). „O suščestvovanii k-značnyx zamknutyx klassov, ne imejuščix konečnogo bazisa " О существовании k-zначных замкнутых классов, не имеющих конечного базиса [O existenci k-hodnota uzavřených tříd bez konečného základu]. Doklady Akademii Nauk SSSR (v Rusku). 127 (1): 44–46. ISSN  0002-3264. PAN  0108458. Zbl  0100.01001.
  13. ^ Cohn, Paul Moritz (1981). Univerzální algebra. Matematika a její aplikace. 6 (2. vyd.). Dordrecht-Boston, Mass.: D. Reidel Publishing Co. str. 127. ISBN  978-90-277-1254-7.

Reference