Кіріспе
Жұптарында минимум және максимумдары бар жиын. Тор – реттік теория мен абстракт алгебра математикасының тармақтарында зерттелетін абстракт құрылым. Ол ішінара реттелген жиынтықтан тұрады, онда әрбір элемент жұбы үшін бірегей жоғарғы шек (ең кіші жоғарғы шек немесе біріктіру) және бірегей төменгі шек (ең үлкен төменгі шек немесе қиылысу) болады. Мысалы, жиынның қуаты жиынтығын қарастыруға болады, ол кіріктіру бойынша ішінара реттелген, онда жоғарғы шек – біріктіру, ал төменгі шек – қиылысу. Тағы бір мысал – бөлінгіштік бойынша ішінара реттелген натурал сандар, онда жоғарғы шек – ең кіші ортақ еселік, ал төменгі шек – ең үлкен ортақ бөлгіш. Торларды белгілі бір аксиоматикалық тепе-теңдіктерді қанағаттандыратын алгебралық құрылымдар ретінде де сипаттауға болады. Екі анықтама да сәйкес келетіндіктен, тор теориясы реттік теория мен жалпы алгебрадан қадам алады. Жартылай торлар торларды қамтиды, ал торлар өз кезегінде Хейтинг және Буль алгебраларын қамтиды. Бұл торға ұқсас құрылымдардың барлығы реттік теориялық және алгебралық сипаттамаларды қабылдайды. Абстракт алгебраның торларды зерттейтін саласы тор теориясы деп аталады.
A lattice is an abstract structure studied in the mathematical subdisciplines of order theory and abstract algebra. It consists of a partially ordered set in which every pair of elements has a unique supremum (also called a least upper bound or join) and a unique infimum (also called a greatest lower bound or meet). An example is given by the power set of a set, partially ordered by inclusion, for which the supremum is the union and the infimum is the intersection. Another example is given by the natural numbers, partially ordered by divisibility, for which the supremum is the least common multiple and the infimum is the greatest common divisor. Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities. Since the two definitions are equivalent, lattice theory draws on both order theory and universal algebra. Semilattices include lattices, which in turn include Heyting and Boolean algebras. These lattice like structures all admit order theoretic as well as algebraic descriptions. The sub field of abstract algebra that studies lattices is called lattice theory.
Анықтама
Тор жартылай реттелген жиын ретінде немесе алгебралық құрылым ретінде анықталуы мүмкін.
Ішінара реттелген жиынтық
Ішінара реттелген жиын (посет) егер ол бір уақытта қосылу және кездесу жартылай торлары болса, онда ол тор деп аталады, яғни кез келген екі элементтің кіші жиынында қосылу (яғни ең кіші жоғарғы шек, белгісімен ∨) және оған сәйкес кездесу (яғни ең үлкен төменгі шек, белгісімен ∧) болады. Бұл анықтама ∨ және ∧ операцияларын екілік операцияларға айналдырады. Екі операция да берілген тәртіпке қатысты монотонды: егер a ≤ b және c ≤ d болса, онда a ∨ c ≤ b ∨ d және a ∧ c ≥ b ∧ d.
Индукциялық аргумент арқылы, тордың бос емес кез келген шекті кіші жиынының ең кіші жоғарғы шегі және ең үлкен төменгі шегі бар екендігі көрінеді. Қосымша шарттар болған жағдайда, одан әрі қорытындылар жасау мүмкін; осы тақырыпты толығырақ талқылау үшін Толықтық (реттелу теориясы) мақаласын қараңыз. Бұл мақалада сондай-ақ жоғарыдағы анықтаманы байланысты ішінара реттелген жиындар арасындағы тиісті Галуа байланыстарының болуы тұрғысынан қалай қайта формулируге болатыны талқыланады – бұл жүйелер теориясының категориялық тәсілі үшін және формалды тұжырымдамалық талдау үшін ерекше қызығушылық тудыратын тәсіл. Тордың кіші жиынын қарастырғанда, кездесу және қосылу операциялары бөлшектік функцияларға дейін шектеледі – олардың нәтижесі кіші жиынға жатпаса, олар анықталмайды. Басқа алгебралық құрылымның (тордың) кіші жиыны ретіндегі осы сыртқы анықтамадан басқа, ішінара торды белгілі бір аксиомаларды қанағаттандыратын екі бөлшектік екілік операциялар жиыны ретінде де анықтауға болады.
Басқа алгебралық құрылымдармен байланыс
Торлар алгебралық құрылымдар секілді топтар отбасымен байланысты. Кездесу мен қосылу екі жаққа да ауысып, байланысқа түсетіндіктен, торды бірдей доменді екі коммутативті жартылай топтан тұратын деп қарастыруға болады. Шектелген тор үшін бұл жартылай топтар шын мәнінде коммутативті моноидтар болып табылады. Абсорбция заңы – тор теориясына тән жалғыз анықтамалық тепе-теңдік. Шектелген торды да тарату аксиомасы жоқ коммутативті сақина ретінде қарастыруға болады. Коммутативтілік, ассоциативтілік және идемпотенция арқасында қосылу мен кездесуді элементтер жұбы емес, бос емес шекті жиынға қолданылатын операциялар ретінде қарастыруға болады. Шектелген торда бос жиынның қосылуы мен кездесуі де анықталуы мүмкін (сәйкесінше және ). Бұл шектелген торларды жалпы торлардан гөрі табиғирақ етеді, сондықтан көптеген авторлар барлық торлардың шектеулі болуын талап етеді. Торлардың алгебралық интерпретациясы әмбебап алгебрада маңызды рөл атқарады.
Мысалдар
Кез келген жиын үшін, оның барлық қосалқы жиындарының жиынтығы (қуат жиыны деп аталады) қосалқы жиынды қамту арқылы реттелгенде, өзімен және бос жиынмен шектелген торды құрайды. Бұл торда, жоғарғы шек жиынтық біріктірілісімен, ал төменгі шек жиынтық қиылысымен анықталады (1-суретті қараңыз). Кез келген жиын үшін, қосу арқылы реттелген барлық шекті қосалқы жиындар жиынтығы да тор болып табылады және жиын шекті болса ғана шектелген болады. Кез келген жиын үшін, тазарту арқылы реттелген барлық бөлістер жиынтығы тор болып табылады (3-суретті қараңыз). Оң бүтін сандар әдеттегі ретпен "мин" және "макс" операциялары арқылы шексіз торды құрайды. 1 – төменгі шек; жоғарғы шек жоқ (4-суретті қараңыз). Егер жұп төменгі элемент болса, онда жоғарғы элемент жоқ (5-суретті қараңыз) деп реттелген натурал сандардың декарт квадраты. Натурал сандар да ең үлкен ортақ бөлгіш пен ең кіші ортақ еселік табу операциялары арқылы торды құрайды, бұл ретте: егер бөлінсе – төменгі шек; бөлетін болса – жоғарғы шек. 2-суретте шекті субтор көрсетілген. Кез келген толық тор (төменде де қараңыз) – шектелген тордың (нақтырақ) түрі. Бұл класс көптеген практикалық мысалдарға бастап әкеледі. Арифметикалық толық тордың ықшам элементтер жиынтығы ең кішкентай элементі бар тор болып табылады, онда тор операциялары арифметикалық тордың сәйкес операцияларын шектеу арқылы анықталады. Бұл арифметикалық торларды алгебралық торлардан ерекшелендіретін ерекше қасиет, себебі алгебралық торлардағы ықшам элементтер тек біріктіру жартылай торын құрайды. Бұл толық торлардың екі класы да домен теориясында зерттеледі. Төменде талқыланатын қосымша қасиеттердің әрқайсысы үшін торлардың қосымша мысалдары келтірілген.
Торлардың морфизмдері
Екі тор арасындағы морфизмнің тиісті түсінігі жоғарыда келтірілген алгебралық анықтамадан оңай шығады. Екі тор және L-ден M-ге дейінгі тор гомоморфизмі берілген болса, онда барлық үшін екі негізгі жартылай тордың гомоморфизмі болады. Құрылымы күрделі торлар қарастырылғанда, морфизмдер қосымша құрылымды да "сақтауы" керек. Атап айтқанда, екі шектелген тор арасындағы шектелген тор гомоморфизмі (әдетте "тор гомоморфизмі" деп аталады) келесі қасиетке де ие болуы керек:
Thus is a homomorphism of the two underlying semilattices. When lattices with more structure are considered, the morphisms should "respect" the extra structure, too. In particular, a bounded lattice homomorphism (usually called just "lattice homomorphism") between two bounded lattices and should also have the following property:
In the order theoretic formulation, these conditions just state that a homomorphism of lattices is a function preserving binary meets and joins. For bounded lattices, preservation of least and greatest elements is just preservation of join and meet of the empty set. Any homomorphism of lattices is necessarily monotone with respect to the associated ordering relation; see Limit preserving function. The converse is not true: monotonicity by no means implies the required preservation of meets and joins (see Pic. 9), although an order preserving bijection is a homomorphism if its inverse is also order preserving. Given the standard definition of isomorphisms as invertible morphisms, a is just a bijective lattice homomorphism. Similarly, a is a lattice homomorphism from a lattice to itself, and a is a bijective lattice endomorphism. Lattices and their homomorphisms form a category. Let and be two lattices with 0 and 1. A homomorphism from to is called 0,1 separating if and only if ( separates 0) and ( separates 1).
Тәртіптік теориялық тұжырымдамада бұл шарттар торлардың гомоморфизмі – екілік кездесетін және қосылатын операцияларды сақтайтын функция екенін көрсетеді. Шектелген торлар үшін ең кіші және ең үлкен элементтерді сақтау, бос жиынның қосылуы мен кездесуін сақтаумен бірдей. Кез келген тор гомоморфизмі, байланысты тәртіп қатынасына қатысты міндетті түрде монотонды болады; Лимит сақтау функциясына қараңыз. Керісінше, бұл дұрыс емес: монотондылық кездесетін және қосылатын элементтерді сақтауды міндетті түрде білдірмейді (9-суретті қараңыз), бірақ тәртіпті сақтайтын биекция, егер оның керісі де тәртіпті сақтайтын болса, гомоморфизм болып табылады. Изоморфизмдердің стандартты анықтамасына сәйкес, – тек біективті тор гомоморфизмі. Сол сияқты, – тордың өзіне гомоморфизмі, ал – биективті тор эндоморфизмі. Торлар және олардың гомоморфизмдері бір категория құрайды. және – 0 және 1 элементтері бар екі тор болсын. гомоморфизмі 0,1-ді бөліп тұратын болып аталады, егер және тек қана егер (0-ді бөліп тұрса) және (1-ді бөліп тұрса).
Thus is a homomorphism of the two underlying semilattices. When lattices with more structure are considered, the morphisms should "respect" the extra structure, too. In particular, a bounded lattice homomorphism (usually called just "lattice homomorphism") between two bounded lattices and should also have the following property:
In the order theoretic formulation, these conditions just state that a homomorphism of lattices is a function preserving binary meets and joins. For bounded lattices, preservation of least and greatest elements is just preservation of join and meet of the empty set. Any homomorphism of lattices is necessarily monotone with respect to the associated ordering relation; see Limit preserving function. The converse is not true: monotonicity by no means implies the required preservation of meets and joins (see Pic. 9), although an order preserving bijection is a homomorphism if its inverse is also order preserving. Given the standard definition of isomorphisms as invertible morphisms, a is just a bijective lattice homomorphism. Similarly, a is a lattice homomorphism from a lattice to itself, and a is a bijective lattice endomorphism. Lattices and their homomorphisms form a category. Let and be two lattices with 0 and 1. A homomorphism from to is called 0,1 separating if and only if ( separates 0) and ( separates 1).
Торлардың қасиеттері
Енді біз қызықты ерекше торлар кластарын тудыратын бірнеше маңызды қасиеттерді енгіземіз. Олардың бірі – шектелу, ол туралы бұрыннан мәлім.
Толықтығы
Егер оның барлық кіші жиынтықтарында қосылу және кездесу болса, онда ол деп аталады. Әсіресе, әрбір толық тор – шектелген тор. Шектелген торлы гомоморфизмдер әдетте тек шекті қосылуларды және кездесулерді сақтайды, ал толық торлы гомоморфизмдер кез келген қосылуларды және кездесулерді сақтауға тиіс. Толық жартылай тор болып табылатын әрбір позитивтік жиын толық тор болып табылады. Осы нәтижеге байланысты, осы кластағы позитивтік жиындар үшін гомоморфизмнің әртүрлі бәсекелес түсініктері бар, олар толық торлар, толық қосылу жартылай торлары, толық кездесу жартылай торлары немесе қосылу бойынша толық немесе кездесу бойынша толық торлар ретінде қарастырылады. "Ішінара тор" – "толық тордың" қарама-қарсысы емес, керісінше, "ішінара тор", "тор" және "толық тор" анықтамалары күшейе түсетін шектеулер болып табылады.
Шартты толықтығы
Шартты түрде толық тор – жоғарғы шегі бар кез келген бос емес ішкі жиынының біріктірілісі (яғни, ең кіші жоғарғы шегі) болатын тор. Мұндай торлар нақты сандардың толықтығы аксиомасын ең тікелей жалпылайды. Шартты түрде толық тор – толық тор, немесе оның ең үлкен элементі жоқ толық тор, немесе оның ең кіші элементі жоқ тор, немесе екеуі де жоқ тор.
Жалғастығы мен алгебралық
Домен теориясында ішінара реттелген жиынның элементтерін "әлдеқайда қарапайым" элементтермен жуықтауға ұмтылу табиғи. Бұл үздіксіз жинақтар класына алып келеді, онда әрбір элемент элементтен қатаң төмен орналасқан элементтердің бағытталған жиынының жоғарғы шегі ретінде алынуы мүмкін. Егер осы бағытталған жиындарды алу үшін оларды жинақтың ықшам элементтерімен шектеуге болатын болса, онда жинақ тіпті алгебралық болады. Екі ұғымды да торларға келесідей қолдануға болады: Үздіксіз тор – бұл посет ретінде үздіксіз толық тор. Алгебралық тор – бұл посет ретінде алгебралық толық тор. Бұл екі класс та қызықты қасиеттерге ие. Мысалы, үздіксіз торларды белгілі бір өрнектерді қанағаттандыратын алгебралық құрылымдар (шекті емес операциялармен) ретінде сипаттауға болады. Алгебралық торлар үшін мұндай сипаттама белгісіз болғанымен, оларды Скотт ақпараттық жүйелері арқылы "синтаксистік" тұрғысынан сипаттауға болады.
A continuous lattice is a complete lattice that is continuous as a poset. An algebraic lattice is a complete lattice that is algebraic as a poset. Both of these classes have interesting properties. For example, continuous lattices can be characterized as algebraic structures (with infinitary operations) satisfying certain identities. While such a characterization is not known for algebraic lattices, they can be described "syntactically" via Scott information systems.
Қосымшалар мен псевдододақтамалар
Ең үлкен элементі 1 және ең кіші элементі 0 бар шектелген тор болсын. Екі элемент x және y бір-бірінің толықтырғышы болады, егер және тек егер:
Жалпы, шектелген тордың кейбір элементтері толықтырғышқа ие болмауы мүмкін, ал кейбіреулері бірнеше толықтырғышқа ие болуы мүмкін. Мысалы, әдеттегі ретпен жиналған {0, 1} жиыны шектелген тор болып табылады, және 0-дың толықтырғышы жоқ. N5 шектелген торында, элемент 2-нің екі толықтырғышы бар, атап айтқанда 3 және 4 (Көр. сурет 11). Әрбір элементі толықтырғышқа ие шектелген тор толықтырылған тор деп аталады. Толықтырылған және таратушы тор Буль алгебрасы болып табылады. Таратушы тор үшін, егер ол бар болса, элементтің толықтырғышы бірегей болады. Егер толықтырғыш бірегей болса, онда біз x' деп жазамыз және баламалы түрде, x ∨ x' = 1 және x ∧ x' = 0. Сәйкес келетін бірлік операциясы, толықтыру деп аталады, тор теориясына логикалық терістеудің аналогын енгізеді. Хейтинг алгебралары – кейбір элементтері толықтырғыштан мүресіз болатын таратушы торлардың мысалы. Керісінше, Хейтинг алгебрасының әрбір элементі псевдо толықтырғышқа ие, ол да x' деп белгіленеді. Псевдо толықтырғыш – бұл x ∧ x' = 0 шартын қанағаттандыратын ең үлкен элемент. Егер Хейтинг алгебрасының әрбір элементінің псевдо толықтырғышы іс жүзінде толықтырғыш болса, онда Хейтинг алгебрасы іс жүзінде Буль алгебрасы болады.
Бос торлар
Кез келген жиын еркін жартыторды жасау үшін қолданылуы мүмкін. Еркін жартытор, жиынның барлық шекті кіші жиынтықтарынан тұрады, ал жартытор операциясы – қарапайым жиынтықтардың біріктірілуі арқылы анықталады. Еркін жартытордың әмбебап қасиеттері бар. Жиын үстіндегі еркін тор үшін Уитман s элементтері бойынша көпмүшелерге негізделген құрылым ұсынды.