Volné algebry

Struktury, s nimiž se studenti již setkali (relace, algebraické struktury, struktury spojitosti); specifické vlastnosti, srovnání. Různé konstrukce (podobjekty, ekvivalence a kongruence, součiny, sumy a pod.) a jejich společné rysy. Zvláštní pozornost bude věnována částečným uspořádáním, a to jak obecným záležitostem, tak i aspektům speciálního významu pro informatiku. Některá základní fakta teorie kategorií.
Germoe
Matfyz(ák|ačka) level I
Příspěvky: 34
Registrován: 28. 5. 2008 15:40
Typ studia: Informatika Ph.D.

Volné algebry

Příspěvek od Germoe »

Nenašel by se tu nějaký dobrovolník, který by mi vysvětlil, co to vlastně 'volná algebra' je? Definici ze skript vím, ale nějak se mi nedaří to uchopit a něco si pod tím představit...

Dík.
bujon
Matfyz(ák|ačka) level I
Příspěvky: 26
Registrován: 28. 1. 2007 12:22

Re: Volné algebry

Příspěvek od bujon »

Připojuji k dotazu Garmoe-a. Taky mám s tím problém si volné algebry rozumně představit. Hodil by se nějaký konkrétní příklad takové algebry. A když už je tady téma volných algeber - nenašla by se nějaké dobrá duše, která byla na přednášce na které se volné algebry braly a mohla by sem napsat věty a tvrzení ze skript, které náš "vládce a panovník množin a struktur" probral?
Uživatelský avatar
kolage
Matfyz(ák|ačka) level I
Příspěvky: 32
Registrován: 27. 1. 2011 18:10
Typ studia: Informatika Mgr.

Re: Volné algebry

Příspěvek od kolage »

no volnou algebru si taky nějak rozumně představit nedokážu, za to mám ve skriptech zakroužkované tvrzení... měli by to být 6.2.1-6.2.3 a samozřejmě oblíbená 6.4. :) Mě by ještě teda kdyžtak zajímalo, jestli se zkouší důkazy za Alexandrovým lemmatem (podle požadavků jsem pochopil že ne) - jsou tam ještě nejaká tvrzení o Hausdorffových prostorech... Spíš tak pro představu, učit se mi už stejně nechtějí :D
Ziman
Matfyz(ák|ačka) level I
Příspěvky: 8
Registrován: 9. 11. 2006 09:59
Typ studia: Informatika Mgr.
Bydliště: Kolej Otava, JM
Kontaktovat uživatele:

Re: Volné algebry

Příspěvek od Ziman »

Volna algebra je algebra nezviazana nijakymi (nadbytocnymi) rovnicami, iba nagenerovana z konstant a operacii co najrozlisujucejsim sposobom. (Nadbytocnymi mam na mysli irelevantnymi k triede algebier samotnej — ak chcem volnu algebru v triede komutativnych grup, tak zrejme obmedzeniu komutativnostou sa nevyhnem.)

Volnu algebru s nejakou signaturou/typom si ja osobne predstavujem ako mnozinu vsetkych "termov", ktore vzniknu, bez akejkolvek interpretacie/redukcie/zjednodusenia. Tj. ak mam signaturu (+, -, 0, 1), tak mnozina vsetkych termov obsahuje napriklad {1, 0, 0+1, 0+0, 0-1, 0-0, 0+(0-1), 1-(1-0), ...}. Je asi pomerne jednoduche intuitivne vidiet, ze toto je algebra s danou signaturou a ze z tejto algebry je jednoznacne zobrazenie do akejkolvek inej algebry s touto signaturou/typom (tym zobrazenim je redukcia/interpretacia termov).

Uvediem priklad. Majme signaturu Δ₁ = (S, 0) s jednou unarnou operaciou S a nulou, M = Ø. Potom volnou algebrou F₁(M) je tato algebra (konecnych) termov: F₁(M) = {0, S 0, S (S 0), S (S (S 0)), …}. Zrejme je vidiet, ze F₁(M) je izomorfna prirodzenym cislam.

Ak si vezmeme signaturu Δ₂ = (+, -), M = {1}, potom F₂(M) ≃ {1, 1-1, 1+1, 1-(1-1), 1-(1+1), 1-1-1, …}, proste mnozina vsetkych termov nagenerovanych z M, ktore zliepas dokopy operaciami z Δ₂. Tato mnozina je pribuzna celym cislam, ale rozhodne s nimi nie je izomorfna — 1 plus (1 minus 1) sa rovna 1 v celych cislach, ale termy "1+(1-1)" a "1" si rovne nie su.

Kazdopadne z F₂(M) do Z existuje homomorfizmus (dokonca jednoznacny). Tym homomorfizmom je denotacia/redukcia/vyhodnotenie vyrazu a termom z F₂(M) priraduje prvky zo Z nasledovne:
  • 1 → 1
  • 1-1 → 0
  • 1+1 → 2
  • 1-(1-1) → 1
  • 1-(1+1) → -1
  • 1-1-1 → -1
Po kratkej uvahe si clovek asi uvedomi, ze toto je asi jediny sposob, ako zostrojit homomorfizmus F₂(M) → Z, ze to plati pre vsetky taketo cielove algebry, a teda F₂(M) je volnou algebrou. Volne okruhy (ak odlozime tuto hrackarsku signaturu a uvazujeme aj nasobenie, jednotku, nulu etc.) su uzko spate s algebraickymi (v zmysle stredoskolskej algebry) vyrazmi.

Rovnako sa da zostrojit homomorfizmus F₂(M) → Z₂, kde Z₂ je klasicka scitacia grupa s dvoma prvkami. Pointou tuna je to, ze
  • Volna algebra je uplne nezviazana ziadnymi rovnicami (asociativnost +, symetria +, 1+1 = 2, …) a pozostava z termov, ktore v celej uplnosti zachytavaju svoju vlastnu podstatu a cely vznik, nic "nezabudaju" ani neskryvaju (naproti tomu ak mam 2-ku v celych cislach, tak to v skutocnosti moze byt prezlecena 1+1-tka alebo nieco ine, ale ja to nemam ako zistit).
  • Cele cisla su zviazane rovnicami ako je (a + b = b + a, a + (b + c) = (a + b) + c, 1+1 = 2, …), co v povodnej volnej algebre vobec nebolo. Prvkov v Z je teda istym sposobom "menej roznych" (aj ked Z ma rovnaku mohutnost), pretoze viacero roznych termov z F₂(M) sa zredukuje na jedno rovnake cislo zo Z.
  • Z₂ je takmer extremnym (uplnym extremom je jednoprvkova grupa) prikladom, ktory je rovnicami zviazany az tak strasne, ze mu stacia len dva prvky v nosnej mnozine.
Podobne majme algebru monoidov s neutralnym prvkom ε, operaciou konkatenacie ∘: Δ₃ = (∘, ε), mnozinu M = {a,…,z}. Potom F₃(M) = {a, ε∘m, z, a∘b, a∘(z∘n), (h∘(e∘l))∘(l∘o), …}. Odtialto je jednoznacny homomorfizmus do mnoziny konecnych postupnosti prvkov z M, efektivne teda do mnoziny M∗. Volne monoidy su teda uzko spate so zoznamami.

Nuz a Pultrova konstrukcia volnej algebry je teda mnozina termov Gen(Ψ[M]), kde zrejme odbocka cez mnozinu R hra ulohu "filtra", aby F(M) zbytocne nerozlisovala prvky, ktore nejdu rozlisit ziadnou algebrou z triedy A (tj. aby nebola volnejsia nez treba, lebo inak by nam vypadla z triedy algebier A).
Odpovědět

Zpět na „MAI064 Matematické struktury“