Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Модель теориясында, математикалық логиканың бір саласы, элементарлық сынып (немесе аксиомалық сынып) — белгілі бір бірінші реттік теорияны қанағаттандыратын барлық құрылымдар жиыны.
In model theory, a branch of mathematical logic, an elementary class (or axiomatizable class) is a class consisting of all structures satisfying a fixed first order theory.
Анықтама
σ қолтаңбасының K класы элементарлық класс деп аталады, егер σ қолтаңбасының бірінші реттік теориясы T болса, және K, T-нің барлық модельдерінен, яғни T-ні қанағаттандыратын барлық σ құрылымдарынан тұрады. Егер T бір ғана бірінші реттік сөйлемнен тұратын теория ретінде таңдалына алатын болса, онда K негізгі элементарлық класс деп аталады. Көбірек жалпылап айтқанда, K псевдоэлементарлық класс болады, егер σ қолтаңбасын кеңейтетін қолтаңбаның бірінші реттік теориясы T болса, және K, T модельдерінің σ-ға тоғысуынан алынған барлық σ құрылымдарынан тұрады. Басқаша айтқанда, σ құрылымдарының K класы псевдоэлементарлық болады, егер және тек қана егер K'-дегі құрылымдардың σ-ға тоғысуынан алынған K' элементарлық класы болса. Нақты себептерге байланысты, элементарлық класстар бірінші реттік логикада аксиоматизацияланатын деп аталады, ал негізгі элементарлық класстар бірінші реттік логикада шекті аксиоматизацияланатын деп аталады. Бұл анықтамалар басқа логикаларға да оңай кеңейтіледі, бірақ бірінші реттік жағдай ең маңызды болғандықтан, егер басқа логика көрсетілмесе, аксиоматизацияланатындығы бірінші реттік жағдайға сілтеме жасайды.
A class K of structures of a signature σ is called an elementary class if there is a first order theory T of signature σ, such that K consists of all models of T, i. e., of all σ structures that satisfy T. If T can be chosen as a theory consisting of a single first order sentence, then K is called a basic elementary class. More generally, K is a pseudo elementary class if there is a first order theory T of a signature that extends σ, such that K consists of all σ structures that are reducts to σ of models of T. In other words, a class K of σ structures is pseudo elementary if and only if there is an elementary class K' such that K consists of precisely the reducts to σ of the structures in K'. For obvious reasons, elementary classes are also called axiomatizable in first order logic, and basic elementary classes are called finitely axiomatizable in first order logic. These definitions extend to other logics in the obvious way, but since the first order case is by far the most important, axiomatizable implicitly refers to this case when no other logic is specified.
Қарсы келетін және баламалы терминология
Жоғарыда айтылғандар қазіргі кезде "шексіз" модель теориясындағы стандартты терминология болғанымен, сәл өзгеше бұрынғы анықтамалар әлі де шекті модель теориясында қолданылады, онда элементарлық сыныпты Δ-элементарлық сынып деп атауға болады, ал элементарлық сынып және бірінші реттік аксиомаға ие сынып терминдері негізгі элементарлық сыныптар үшін резервтелген (Ebbinghaus және басқалар, 1994; Ebbinghaus және Flum, 2005). Ходжес элементарлық сыныптарды аксиомаға келтірілетін сыныптар деп атайды, ал негізгі элементарлық сыныптарды анықталатын сыныптар деп атайды. Ол сонымен қатар EC сыныбы және EC сыныбы деген синонимдерді де қолданады (Hodges, 1993). Бұл терминологияның әртүрлі болуына нақты себептер бар. Жалпы модель теориясында қарастырылатын қолтаңбалар көбінесе шексіз, ал бір бірінші реттік сөйлемде тек шекті сандағы символдар ғана болады. Сондықтан, негізгі элементарлық сыныптар шексіз модель теориясында ерекше жағдай болып табылады. Ал шекті модель теориясы көбінесе тек шекті қолтаңбалармен ғана айналысады. Кез келген шекті σ қолтаңбасы үшін және изоморфизм бойынша жабық σ құрылымдарының кез келген К класы үшін, K және дәл сол шекті құрылымдарды қамтитын σ құрылымдарының элементарлық класы бар екенін көру оңай. Осыдан келіп, элементарлық сыныптар шекті модель теориясы үшін аса қызығушылық тудырмайды.
While the above is nowadays standard terminology in "infinite" model theory, the slightly different earlier definitions are still in use in finite model theory, where an elementary class may be called a Δ elementary class, and the terms elementary class and first order axiomatizable class are reserved for basic elementary classes (Ebbinghaus et al. 1994, Ebbinghaus and Flum 2005). Hodges calls elementary classes axiomatizable classes, and he refers to basic elementary classes as definable classes. He also uses the respective synonyms EC class and EC class (Hodges, 1993). There are good reasons for this diverging terminology. The signatures that are considered in general model theory are often infinite, while a single first order sentence contains only finitely many symbols. Therefore, basic elementary classes are atypical in infinite model theory. Finite model theory, on the other hand, deals almost exclusively with finite signatures. It is easy to see that for every finite signature σ and for every class K of σ structures closed under isomorphism there is an elementary class of σ structures such that K and contain precisely the same finite structures. Hence, elementary classes are not very interesting for finite model theorists.
Ұғымдар арасындағы оңай қатынастар
Әрине, әрбір негізгі элементарлық сынып – элементарлық сынып, ал әрбір элементарлық сынып – псевдоэлементарлық сынып. Бұған қоса, тығыздық теоремасының тікелей салдары ретінде, σ-құрылымдар класы негізгі элементарлық болады, егер және тек қана егер ол элементарлық болса және оның толықтырғышы да элементарлық болса.
Clearly every basic elementary class is an elementary class, and every elementary class is a pseudo elementary class. Moreover, as an easy consequence of the compactness theorem, a class of σ structures is basic elementary if and only if it is elementary and its complement is also elementary.
Негізгі бастауыш сынып
σ тек бірлік функция символы f-тан тұратын қолтаңба болсын. f бір-бірге сәйкестікке ие σ құрылымдарының K класы – негізгі элементарлық класс. Бұл Т теориясымен куәландырылады, ол тек бір ғана сөйлемден тұрады.
Let σ be a signature consisting only of a unary function symbol f. The class K of σ structures in which f is one to one is a basic elementary class. This is witnessed by the theory T, which consists only of the single sentence
.
Элементар емес псевдоэлементарлық сынып
Ақырында, тек бір унарлық қатынас символы P-ден тұратын σ белгісін қарастырайық. Кез келген σ құрылымы екі кіші жиынға бөлінеді: P орындалатын элементтер және қалғандары. K классын осы екі кіші жиынның бірдей кардиналдығы бар барлық σ құрылымдарының жиыны деп атайық, яғни олардың арасында биекция бар. Бұл класс элементар емес, себебі P-нің және оның толықтыруының іске асырылу жиыны санаулы шексіз болатын σ құрылымы, санаулы шексіз және санаусыз жиындары бар σ құрылымымен дәл сол бірінші реттік сөйлемдерді қанағаттандырады. Енді P және f унарлық функция символынан тұратын белгіні қарастырайық. классын f биекция болатын және P, x үшін орындалса, P, f(x) үшін орындалмаса, барлық құрылымдардың жиыны деп атайық. - бұл элементар класс, сондықтан K элементар емес, бірақ псевдоэлементар классқа берілген мысал.
Finally, consider the signature σ consisting of a single unary relation symbol P. Every σ structure is partitioned into two subsets: Those elements for which P holds, and the rest. Let K be the class of all σ structures for which these two subsets have the same cardinality, i. e., there is a bijection between them. This class is not elementary, because a σ structure in which both the set of realisations of P and its complement are countably infinite satisfies precisely the same first order sentences as a σ structure in which one of the sets is countably infinite and the other is uncountable. Now consider the signature , which consists of P along with a unary function symbol f. Let be the class of all structures such that f is a bijection and P holds for x iff P does not hold for f(x). is clearly an elementary class, and therefore K is an example of a pseudo elementary class that is not elementary.
Псевдобазалық емес сынып
σ кездейсоқ қолтаңба болсын. Барлық шекті σ-құрылымдарының K класы элементар емес, себебі (жоғарыда көрсетілгендей) оның толықтыруы элементар, бірақ негізгі элементар емес. Бұл σ-ны кеңейтетін кез келген қолтаңба үшін де осы дұрыс болғандықтан, K тіпті псевдоэлементарлық класс емес. Бұл мысал бірінші реттік логиканың туа табиғатымен келетін экспрессивті күшінің шектерін көрсетеді, ал екінші реттік логика одан әлдеқайда экспрессивті. Дегенмен, екінші реттік логика бірінші реттік логиканың толықтық және ықшамдық теоремалары сияқты көптеген қажетті қасиеттерін сақтап қала алмайды.
Let σ be an arbitrary signature. The class K of all finite σ structures is not elementary, because (as shown above) its complement is elementary but not basic elementary. Since this is also true for every signature extending σ, K is not even a pseudo elementary class. This example demonstrates the limits of expressive power inherent in first order logic as opposed to the far more expressive second order logic. Second order logic, however, fails to retain many desirable properties of first order logic, such as the completeness and compactness theorems.