Mreža klonova kooperacija

Abstract

Cilj ovo rada je da obezbedi informacije o apstraktnim osobinama klonova ko-operacija, mrezi klonova operacija, ali i ostalim objektima koji prate pojam klona. U Uvodu je pokazano kako je nastao pojam ko-algebraske strukture. Kratko se razmatraju i dva pristupa ko-algebrama: Kleislijev, koji je potekao iz konteksta teorije kategorija [Kle 65], i Drbohlavov, koji je po osnovnoj ideji blizi univerzalnoj algebri, i koji je usvojen u ovom radu. Glava 0 sadrzi spisak osnovnih pojmova i oznaka vezanih za skupove, preslikavanja, relacije, mreze i particije koji se koriste u celom radu, dok se u Glavama 1 i 2 uvode standardni termini teorije klonova operacija i ko-operacija i daje pregled poznatih rezultata. Originalni rezultati rada sadrzani su u Glavama 3–7. Glava 3 sadrzi osnovni rezultat rada. Pomocu kontravarijantnog liftinga kooperacija uspostavlja se izomorfizam izmedju klona svih ko-operacija skupa X s jedne strane i jednog posebnog klona operacija skupa P(X) sa druge strane. Pokazuje se da je isto preslikavanje ujedno i potapanje algebre kooperacija skupa X u algebru operacija skupa P(X) koja je standardna u teoriji klonova. Takodje se pokazuje da je kontravarijantni lifting klonova ujedno i izomorfizam mreze klonova ko-operacija skupa X i jednog glavnog ideala u mrezi klonova na P(X). Nakon ispitivanja lokalno ko-zatvorenih klonova ko-operacija pokazujemo u u kakvom odnosu stoje reprezentacije klonova ko-operacija selektivnim operacijama s jedne strane [Cs´a 85], i operacijama na partitivnom skupu s druge strane. Reprezentaciju operacijama na partitivnom skupu, mada izomorfna jednom specijalnom slucaju reprezentacije selektivnim operacijama, smatramo bitnom, zato sto se njome klonovi ko-operacija smestaju u poznati ambijent skupovnih Booleovih algebri, umesto u prilicno opskuran prostor selektivnih operacija. U pretposlednjem odeljku se razmatra odnos klonova ko-operacija i klonova operacija kroz proces liftinga, sto je omoguceno cinjenicom da i kontravarijantni lifting klona svih ko-operacija i kovarijantni lifting klona svih operacija skupa X odredjuju klon operacija skupa P X. Na samom kraju ove pomalo dugacke glave se ispituju odnosi klonova ko-relacija i klonova relacija kroz prizmu monoida transformacija. U Glavi 4 se izlazu neke osobine mreze klonova ko-operacija kao parcijalno uredjenog skupa. Opisani su intervali Int(M) za neke posebne monoide transformacija M. Pokazano je da u slucaju M = TX u mrezi klonova ko-operacijane postoji “Burlova anomalija” (ispitivanja kolapsirajucih monoida su, medjutim, odlozena do Glave 5). Nakon toga je predlozena jedna konstrukcija skupa nezavisnih ko-operacija na osnovu koje je dobijena donja granica za broj klonova ko-operacija na konacnom skupu i tacan broj klonova ko-operacija na beskonacnom skupu. Iako je dobijena donja granica prilicno neprecizna, na osnovu nje se sasvim jasno uocava “veoma eksponencijalna priroda” ovog broja. Ispitivanja jednog posebnog glavnog filtera mreze klonova ko-operacija nam daju gornju granicu za visinu mreze. Glava 5 je posve´cena ispitivanjima maksimalnih klonova ko-operacija na kona-cnom skupu. Maksimalni klonovi ko-operacija su opisani u radu [Sz´ek 89] kao skupovi operacija koji slabo cuvaju regularne familije skupova. Prvo se daje interpretacija ovog rezultata u terminima ko-relacija i pokazuje se da je ovakav opis najbolji moguci kada se u obzir uzme arnost dobijenih ko-relacija. Nakon toga se pokazuje da nijedan maksimalan klon nema Shefferovu ko-operaciju i daje se opis U”¡1-maksimalnih klonova ko-operacija. Paznja se dalje prenosi na preseke maksimalnih klonova ko-operacija. Prvo se razmatraju preseci nekih parova maksimalnih klonova i pokazuje se da to ne mora uvek biti maksimalni klon, a kasnije se konstruiˇse potapanje mreze cLB1 £ : : : £ cLBk u mrezu cLX. Potom se pokazuje da je mreza cLX komplementirana, a na samom kraju se razmatraju kolapsirajuci klonovi ko-operacija i monoidi. Glava 6 je posvecena opisu minimalnih klonova ko-operacija i svih supminimalnih klonova ko-operacija koji nisu esencijalno unarni. Uvid u strukturu supminimalnih klonova omogucuje izvodjenje donje granice za visinu mreze klonova ko-operacija. Glava sadrzi i kratak komentar o asocijativnosti kooperacija. U Glavi 7 se razmatraju enumerativne osobine mreze klonova ko-operacija na troelementnom skupu, kao i nekih njenih pratecih objekata. Osim utvrdjivanja kardinalnosti mreze na skupu f0; 1; 2g, odredjena je njena visina, kao i svi submaksimalni klonovi. Poseban odeljak je posvecen enumeraciji baz¯a klona svih ko-operacija i svih maksimalnih klonova, klasicnoj temi u teoriji klonova. U dodacima su navedene tabele kojima se sumarizuju rezultati ove glave i dat je opis jednostavnog softverskog alata koji ima ulogu “raˇcunarskog atlasa” mreˇze cL3. S obzirom da mreza ima previse elemenata da bi se mogao dati njen Hasse dijagram, “racunarski atlas” se pokazao kao najjednostavniji i najefikasniji nacin da se dodje do informacija o mrezi. Napomenimo da su mnogi rezultati u ovom radu dobijeni uopstavanjem osobina mreze koje su otkrivene “prelistavanjem atlasa”. Navedimo kao primer strukturu U”¡1- maksimalnih klonova, gornju i donju granicu za visinu mreze, cinjenicu da je mreza komplementirana, kao i to da maksimalni klonovi nemaju Shefferovu ko-operaciju.

The aim of this thesis is to provide information on abstract properties of clones of co- operations, the lattice of clones of co-operations and other accompanying objects. Introduction to the thesis demonstrates in short the genesis of concepts of co-operation and co-algebra and presents two approaches to the topic: the Kleisli approach which originated in the category theory, and the approach of Drbohlav which is more in the spirit of universal algebra and which is adopted in the thesis. Chapter 0 is a short display of standard set-theoretic terminology and notation which is used in the thesis. Chapters 1 and 2 present standard notions of theory of clones of operations and co-operations, respectively. They contain lists of the most important known results. The original contribution of this thesis is contained in Chapters 3–7. Chapter 3 contains the basic result of the thesis. By means of contravariant lifting of co-operations we establish an isomorphism between the clone of all co-operations on a set X and one special clone of operations on the set P(X). This isomorphism is not only the abstract clone isomorphism, but also a lattice isomorphism between the lattice of all clones of co-operations on X and a principal ideal in the lattice of all clones of operations on P(X). The same mapping is an embedding of the algebra of co-operations on X into the algebra of operations on P(X). Locally co-closed clones of operations are also characterised via this most useful mapping. Representation of clones of co-operations by operations on the powerset is compared to the representation by selective operations. Although isomorphic to a special case of the representation by selective operations, representation by operations on the powerset is highly important because it places clones of co-operations into a familiar setting of set-theoretic Boolean algebras, rather then in the quite obscure setting of selective algebras. At the end of this lengthy chapter, we investigate the relationship of corresponding liftings of the clone of all operations and the clone of all co-operations, and ellaborate the lifting proces and the interplay between description of transformation monoids by relations and co-relations. Chapter 4 exibits some order-theoretic properties of the lattice of clones of co-operations. Intervals of the form Int(M) are described for some special transformation monoids M. In case M = TX it is demonstrated that the socalled “Burle anomaly” does not occur in the lattice of clones of co-operations. The investigation of collapsing clones and monoids is, however, deferred until Chapter 5. After that a construction of an independent set of co-operations is presented, based on which a lower bound for the number of clones of cooperations is obtained. Although pretty rough, this lower bound shows that the number of clones of co-operations on a finite set is of a “very exponental nature”. The number of clones of operations on an infinite set is also obtained. The investigations of a particular principal filter of the lattice provide an upper bound for the height of the lattice. Chapter 5 is devoted to the investigation of maximal clones of co-operations on a finite set. All the maximal clones of co-operations are described in [Sz´ek 89] in terms of regular families. We first reinterpret that result in terms of co-relations and show that the description is the best possible as far as arities of co-relations involved are considered. After that we supply some more information on the maximal clones. We show that no maximal clone of co-operations has a Sheffer co-operation and describe clones covered by U”¡1. Then we turn to intersections of maximal clones of co-operations. First we consider intersections of some special pairs of maximal clones and show that in some cases this is not a maximal clone. As for the intersection of several maximal clones of co-operations, we show how to embed cLB1 £ : : : £ cLBk in cLX. Using results on the structure of maximal clones we show that the lattice cLX is complemented. The chaptr ends with a note on collapsing clones of co-operations. Chapter 6 provides the description of minimal clones of co-operations and those supminimal clones of co-operations which are not essentially unary. The structure of supminimal clones of co-operations provides a lower bound for the height of the lattice of clones of co-operations. As a spin-off, there is a brief discussion on associativity. Chapter 7 is devoted to enumerations of various objects connected to the lattice of clones of co-operations on a three element set. Besides the enumeration of the lattice itself, the submaximal clones have been listed and the height of the lattice on a three element set is determined. A separate section deals with a classical clone-theoretic topic of enumerating the bases for the clone of all co-operations and for the maximal clones of co-operations. The Appendices to this chapter contain some tables that summarize various enumerations, as well as a description of a modest software tool that palys the role of the “computer atlas” of cL3. Since the lattice has too many elements to be drawn explicitely, this was the simplest and the most efficient way to handle it. Let us remark that many results of this thesis were obtained by gathering the information on the particular case from the “computer atlas” and by generalisation, such as: the structure of U”¡1 maximal clones, the bounds for the height of the lattice, the fact that maximal clones have noSheffer co-operation and the fact that cLX is complemented.