УНИВЕРЗИТЕТ У КРАГУЈЕВЦУ ПРИРОДНО-МАТЕМАТИЧКИ ФАКУЛТЕТ Владимир Ристић ЛОГИКЕ СА ИНТЕГРАЛИМА И УСЛОВНИМ ОЧЕКИВАЊИМА Докторска дисертација Крагујевац, 2013. ИДЕНТИФИКАЦИОНА СТРАНИЦА ДОКТОРСКЕ ДИСЕРТАЦИЈЕ I Аутор Име и презиме: Владимир Т. Ристић Датум и место рођења: 29. јун 1974. године у Јагодини Садашње запослење: Асистент на Факултету педагошких наука у Јагодини Универзитета у Кра- гујевцу II Докторска дисертација Наслов: Логике са интегралима и условним очекивањима Број страница: 93 Број слика: Број библиографских података: 54 Установа и место где је рад израђен: Природно-математички факултет Универзитета у Крагујевцу, Крагујевац Научна област (УДК): Математичка логика Ментор: Доц. др Небојша Икодиновић III Оцена и одбрана Датум пријаве теме: 29. август 2012. године Број одлуке и датум прихватања докторске дисертације: Комисија за оцену подобности теме и кандидата: 1. Др Миодраг Рашковић, научни саветник, Математички институт САНУ, председник, 2. Др Радосав Ђорђевић, ванредни професор Природно-математичког факултета у Крагујевцу, члан, 3. Др Небојша Икодиновић, доцент Математичког факултета у Београду, члан, Комисија за оцену докторске дисертације: 1. Др Миодраг Рашковић, научни саветник, Математички институт САНУ, председник, 2. Др Радосав Ђорђевић, ванредни професор Природно-математичког факултета у Крагујевцу, члан, 3. Др Небојша Икодиновић, доцент Математичког факултета у Београду, члан, Датум одбране дисертације: Садржај Предговор 1 Увод 3 1. Нестандардна анализа 7 1.1. Нестандардни универзум ∗V (S) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2. Лебова мера . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.3. Лебова конструкција Данијеловог интеграла . . . . . . . . . . . . . . . . . . . . . . . 11 2. Допустиви скупови 13 2.1. Аксиоме теорије KPU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2. Елементарни појмови теорије скупова KPU . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3. Дефинициона екстензија језика L∗ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.4. Дефиниција Σ рекурзијом . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.5. „Collapsing” лема . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.6. Преносиви и апсолутни предикати . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.7. Дефиниција допустивог скупа и допустивог ординала . . . . . . . . . . . . . . . . 24 2.8. Хередитарно коначни скупови . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3. Пребројиви фрагменти инфинитарне логике L∞ω 29 3.1. Формализовање синтаксе и семантике у KPU теорији . . . . . . . . . . . . . . . . 29 3.2. Својство конзистентности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.3. Теорема слабе комплетности за пребројиве фрагменте . . . . . . . . . . . . . . . . 33 3.4. Комплетност и компактност за пребројиве допустиве фрагменте . . . . . . . . 35 4. Средњи модел 38 5. Логике са интегралима 43 5.1. Логике L AP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 5.1.1. Вероватносни модели . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 5.1.2. Аксиоматски систем и правила извођења . . . . . . . . . . . . . . . . . . . . 44 5.1.3. Слаби модели . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 5.1.4. Градирани вероватносни модели . . . . . . . . . . . . . . . . . . . . . . . . . . 46 5.1.5. Сагласност и комплетност . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 5.1.6. Случајне променљиве . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 5.2. Логика L A ∫ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 5.3. Теорема комплетности за вероватносне моделе са коначно вредносним ме- рама у логици са интегралима Lfin A ∫ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 5.4. Двовероватносне логике . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 5.4.1. Логика La AP1P2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 i 5.4.2. Логика La A ∫ 1 ∫ 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 6. Логике са операторима условног очекивања 57 6.1. Случајне променљиве и интеграли . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 6.2. Условно очекивање . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 6.3. Двовероватносне логике са условним очекивањем . . . . . . . . . . . . . . . . . . . 59 6.3.1. Двовероватносне логике са случајним променљивим и интегралима 59 6.3.2. Логика La AE1E2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 7. Тополошке логике 68 7.1. Логика са квантификатором „постоји непребројиво много” . . . . . . . . . . . . 68 7.2. Тополошки простори . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 7.3. Топологије на класама . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 7.4. Тополошка логика L(O) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 7.5. Тополошка класа-логика L A (O,C ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 7.6. Теорема комплетности за непрекидне функције и тополошки производ . . . 79 7.7. Логика Lcont A (On ,C n )n∈ω . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 Литература 88 Додатак 91 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 Биографија . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 Предговор Математичка логика, као део математике и логике уопште, данас представља неза- обилазни метод за решавање велике групе математичких проблема. С једне стране, пред- ставља средство за прецизно излагање математичких теорија, с друге стране, једну од математичких теорија у чијем оквиру је развијен један број математичких метода које се по природи не разликују битно од метода алгебре, анализе итд., односно, који су по својој природи математички и служе за решавање математичких проблема. С тим у вези, фор- малне логике заузимају важно место у формализацији многих теорија. Могло би се рећи да проучавање логичких система, у овом раду, иде у два правца: један је у вези са теори- јом вероватноће, односно теоријом мере, док је други везан за топологију. Предмет рада је, свакако у првом реду, проширивање класичне логике до формалних система који ће бити прикладни за описивање и закључивање у наведеним математичким окружењима. Место и значај топологије и теорије мере у математици у потпуности оправдавају про- учавање везе између фрагмената математичке логике којима ћемо се овде бавити и ових математичких дисциплина. Организација рада Поред уводног поглавља, у коме је дат историјат и значај вероватносних и тополо- шких логика, као и краћи приказ инфинитарне логике Lω1ω и логика са уопштеним кван- тификаторима L(Q), излагање је подељено у седам следећих поглавља: (1) Нестандардна анализа, (2) Допустиви скупови, (3) Пребројиви фрагменти инфинитарне логике L∞ω, (4) Средњи модел, (5) Логике са интегралима, (6) Логике са операторима условног очекивања и (7) Тополошке логике. У првом поглављу Нестандардна анализа изложени су основни појмови нестан- дардне анализе и описане су две технике које имају важну улогу у конструкцији очекива- них модела представљених логичких система: конструкција Лебове мере и Лебова кон- струкција Данијеловог интеграла. У другом поглављу Допустиви скупови су изложени елементарни појмови везани за Крипке-Платекову теорију скупова, као и за њене тран- зитивне моделе – допустиве скупове. Описане су и неке специјалне врсте допустивих скупова које ће бити кључне у грађењу синтаксе вероватносних и тополошких логика и приказана је веза са класичном теоријом израчунљивости. Треће поглавље Пребројиви фрагменти инфинитарне логике L∞ω је приказ пребројивог фрагмента LA. Описан је на- чин формализовања синтаксе и семантике у KPU теорији, својство конзистентности и до- казана је комплетност и компактност (Барвајзова) за пребројиве допустиве фрагменте. Све нове логике које ће бити дате у овом раду биће инфинитарне логике над одговарају- ћим допустивим скуповима. Четврто поглавље Средњи модел је један оригинални приказ Н. Икодиновића познате конструкције средњег модела Миодрага Рашковића. С обзиром да је техника средњег модела коришћена у свим резултатима у овом раду, издвојена је као засебно поглавље. У петом поглављу Логике са интегралима најпре је представљена вероватносна логика L AP , а затим и логика са интегралним оператором L A ∫ , при чему је 1 Предговор приказана веза између ових логичких система. Затим су представљене две нове вероват- носне логике Lfin A ∫ и La A ∫ 1 ∫ 2 . У првој су описани модели чије мере имају коначне рангове, док друга представља еквивалент Рашковићеве двовероватносне логике La AP1P2 међу логи- кама са интегралним операторима. У оба случаја је доказана потпуност аксиоматизације у односу на класу дефинисаних модела. На почетку шестог поглавља Логике са опера- торима условног очекивања представљена је Кислерова логика L A ∫ (R) са интегралним операторима и случајним променљивим, а затим и логика L AE са оператором условног очекивања. У наставку је изложена нова двовероватносна логика са случајним промен- љивим La A ∫ 1 ∫ 2 (R), као и двовероватносна логика са условним очекивањем у логици La AE1E2 . Дефинисана су два различита оператора условног очекивања у односу на две мере µ1 и µ2 респективно, које се налазе у апсолутно непрекидном односу. У седмом поглављу Топо- лошке логике дата је најпре Кислерова логика са квантификатором „постоји непребројиво много”, која на неки начин представља основу за тополошке логике које су представљене у овом поглављу. Затим су наведени неки елементарни појмови везани за, најпре класичне тополошке просторе, а онда и за тополошке класа просторе које су проучавали Ж. Мијај- ловић и Д. Ћирић у [11] и [12]. Такође су представљене две Сгроове тополошке логике L(O) и L(Onn∈ω), од којих је друга екстензија логике L(O) и погодна је за проучавање тополо- шког производа и непрекидних пресликавања на класичним тополошким просторима. У следећем одељку је изложена тополошка класа логика L A (O,C ), која представља инфини- тарни допустиви еквивалент Сгроове логике L(O), у односу на тополошке класа просторе. На крају је описана нова тополошка класа логика Lcont A (On ,C n )n∈ω у којој централно место заузимају појмови тополошког производа и непрекидних пресликавања на тополошким класа просторима. Публиковани и излагани делови рада Делови овог рада који се односе на вероватносне логике објављени су у научним часописима: [47, 48]. Резултат из поглавља 6. је такође изложен на научном скупу Pro- babilistic logics and applications у Београду 2011, док је преглед резултата из поглавља 7. изложен на Семинару из вероватносних логика Математичког института САНУ. Два рада, који су такође резултат ових истраживања, налазе се на рецензији. Захвалност Велику захвалност дугујем професорима др Радосаву Ђорђевићу и др НебојшиИко- диновићу, ментору овог рада. Својим идејама, којима је инициран највећи део истражи- вања, и залагањем кроз дискусије, дали су велики допринос овом раду. Посебно сам за- хвалан професору др Миодрагу Рашковићу на корисним сугестијама које су ми биле од велике помоћи током рада. 2 Увод Настанак вероватносних логика се може везати за име Џерома Кислера. Замишљене најпре као логике прилагођене проучавању једноставнијих структура на пољу теорије ве- роватноће, развијају се ка логичким системима погодним за описивање и сложенијих пој- мова, као што су мартингали, Марков процес, Брауново кретање итд. Кислер свој рад започиње логиком L AP , тј. разматрањем структура првог реда у којима је вероватноћа дефинисана на домену. Логика L AP је слична инфинитарној логици LA (A је допустив подскуп од допустивог скупа HC који садржи ординал ω, видети поглавље 2); уобича- јени квантификатори ∀x и ∃x су замењени вероватносним квантификатором Px ≥ r , при чему формула (Px ≥ r )<(x ) значи да је вероватноћа скупа {x | <(x )} већа или једнака r . Разрађујући Кислерове идеје, Хувер је проучавао логике LωP , Lω1P , као и логику LAP . С обзиром на не тако велику изражајну моћ логике L AP , јавља се потреба за логиком у којој ће многа својства случајних променљивих бити описива. Тако настаје логика L A ∫ у којој уместо вероватносних квантификатора Px ≥ r фигуришу квантификатори облика ∫ . . . dx . Такође, Хувер уводи логику L A ( ∫ ) која је модификација логике L A ∫ . Уведеним логикама ипак није могуће описати појмове који су у вези са условним очекивањем случајних про- менљивих. Овај проблем Кислер решава увођењем логике L AE која проширује логику са интегралима L A ∫ додавањем новог оператора E [· | ·] којим се изражава условно очекивање случајне променљиве у односу на σ-алгебру мерљивих скупова. Проучавање логика са условним очекивањима даље настављају С. Фахардо и Х. Роденхаусен који даје адапти- рану вероватносну логику Lad , погодну за проучавање стохастичких процеса, односно неких специјалних вероватносних простора. Целокупан приказ ових вероватносних логика може се наћи у [6], где такође Кислер даје низ сугестија за правце даљег истраживања на пољу вероватносних логика. Један од постављених проблема је био и теорема комплетности за класу двовероватносних модела, специјално за структуре са две вероватносне мере µ1 и µ2 такве да је µ1 апсолутно непре- кидна у односу на µ2. Радећи на овом проблему, Рашковић у [46] уводи врло корисну технику средњег модела која ће дати пуно нових резултата на овом пољу. Ова техника је коришћена за доказивање комплетности многих логика везаних за двовероватносне струк- туре. У првом реду треба истаћи и радове Р. Ђорђевића, који поред логика са апсолутно непрекидним односом мера у двовероватносним структурама, изучава и логике код којих се мере налазе у сингуларном односу. Техника средњег модела је заједнички именитељ свих логика које су изложене у овом раду, а корак даље у проучавању двовероватносних логика је и логика са условним очекивањима изложена у поглављу 6. Развој тополошких логика би могао бити подељен у два правца. С једне стране су Флум и Зајглер који су најзаслужнији за развој тополошких логика. Поред класичних тополошких простора, они су разматрали и логике разних специјалних тополошких про- стора, као што су униформни простори, инфинитезимални простори итд. С друге стране су Сгроове тополошке логике које представљају, на неки начин, наставак Кислеровог рада на логикама са уопштеним квантификаторима. Логике које ће бити представљене у овом раду су модификације Сгроових тополошких логика, најпре логике L(O), а затим и логике 3 Увод L(Onn∈ω) која је погодна за проучавање појма тополошког производа и непрекидних пре- сликавања. Као резултат проучавања тополошких логика овог типа на неким специјалним тополошким просторима, Р. Ђорђевић, Н. Икодиновић и Ж. Мијајловић излажу тополо- шку класа логику L A (O,C ) где су описани тополошки класа простори, које су проучавали Ж. Мијајловић и З. Ћирић у [11, 12]. Нова тополошка класа логика Lcont A (On ,C n )n∈ω, која је изложена у поглављу 7, синтетише све претходне резултате, представљајући логику погодну за резоновање о тополошком производу и непрекидним пресликавањима тополо- шких класа простора. У наредним одељцима биће описане логике које играју велику улогу у проучавању логика у овом раду: инфинитарна логика Lω1ω и логика са уопштеним квантификаторима L(Q). Инфинитарне логике. Логика Lω1ω Поред логике другог реда, која се добија увођењем релацијских променљивих, про- ширења предикатског рачуна првог реда могу се добити уопштавањем њихових логичких везника. Уколико се у језику L допусте дисјункције и конјункције бесконачне дужине, до- бијају се инфинитарне логике. Најједноставнији случај инфинитарне логике јесте логика Lω1ω у којој су дозвољене пребројиве конјункције и дисјункције. Ова логика, у ствари, представља један фрагмент логике L∞ω у којој су допуштене дисјункције и конјункције преко скупа формула произвољних кардиналности. Формално, формуле логике L∞ω де- финишемо као најмању класу затворену за уобичајене везнике и квантификаторе логике Lωω и затворену за конјункције произвољних скупова формула. Према томе, ако је Φ скуп формула логике L∞ω, онда је и ∧ Φ формуле логике L∞ω. Аналогно се дефинише и скуп формула логике Lω1ω. У оба случаја, релацију задовољења проширујемо следећим усло- вом: M |=∧Φ акко M |=< за свако < из Φ . Користећи де Морганове законе, дисјункцију ∨ Φ можемо дефинисати као скраћење формуле ¬∧{¬< |< ∈Φ}. У општем случају, фрагмент инфинитарне логике је дефинисан као фрагмент логике L∞ω (видети поглавље 3), међутим, како ћемо надаље радити ис- кључиво са пребројивим (допустивим) фрагментима, детаљније ће бити описана логика Lω1ω. Постоје формуле језике Lω1ω са бесконачно много слободних променљивих. Од сада ће наша пажња бити усмерена само на оне формуле које имају само коначно много сло- бодних променљивих. Уколико формула има коначно много слободних променљивих, онда свака њена потформула такође садржи коначан број слободних променљивих. Ако је < реченица језика Lω1ω, онда свака потформула формуле < има коначан број слободних променљивих. Иначе, језик Lω1ω има непребројиво много формула, што представља један од разлога увођења фрагмената ове логике. Многе структуре, које се не могу описати у предикатском рачуну првог реда, могу бити описане формулама логике Lω1ω: класа свих коначних модела, класа свих група са торзијом, класа поља карактеристике нула, класа архимедски уређених поља итд. На пример, класа свих група са торзијом окарактери- сана је конјункцијом уобичајених аксиома за групе заједно са: ∀x∨{x ∗ · · · ∗x︸ ︷︷ ︸ n = e | n ∈N}. 4 Увод Такође, ако за природан број n већи од 1, са <≥n означимо формулу ∃v0 . . .∃vn−1(¬v0 = v1 ∧ . . .∧¬v0 = vn−1 ∧ . . .∧¬vn−2 = vn−1) , имамо да важи: M |= ∨{¬<≥n | n > 1}, ако „M је коначан скуп”. Ако се дозволе докази бесконачне дужине, логика Lω1ω има аксиоматски систем који је потпун у односу на уве- дену семантику. Прецизније, у логици Lω1ω може се дефинисати појам доказа тако да за сваки скуп реченица Σ и сваку реченицу < језика Lω1ω, Σ ⊢<⇔Σ |=<. Прву теорему потпуности за ову логику доказао је Карп (1964). Аксиоматски систем предикатског рачуна првог реда проширен је на следећи начин: за сваку реченицу ∧ Φ и < ∈ Φ додаје се аксиома (i ) ∧Φ→ <; и правило извођења (i i ) из ψ→ <, за свако < из Φ, закључује сеψ→∧Φ. Нека је даље< =∧{¬<≥n | n ≥ 2}. Реченица< важи умоделуA акко је скуп A коначан. Закључује се да скуп реченица {<}∪{¬<≥n | n ≥ 2} нема модел и притом, сваки његов коначан подскуп има модел, тј. у логици Lω1ω не важи став компактности. Све у свему, прелазећи од предикатског рачуна првог реда Lωω на логику L∞ω, по- стиже се знатно већа изражајна моћ, али се, с друге стране, многа добра својства логике Lωω нарушавају, у првом реду компактност. На пример, уколико се посматра само Lω1ω као фрагмент логике L∞ω, нека својства попут компактности и интерполације рецимо, остају сачувана. Увођење појма допустивог фрагмента инфинитарне логике L∞ω, који је детаљно описан у поглављу 3, у ствари је концепт враћања компактности и других добрих особина логике првог реда уз задржавање, штавише појачавање, изражајне моћи инфини- тарних логика. Логике са уопштеним квантификаторима L(Q) Поред уопштавања логичких везника, у логици првог реда могу се уопштавати и квантификатори. Идеја уопштавања квантификатора потиче од Мостовског [1957]. Ње- гова идеја била је да се додају квантификатори који експлицитно представљају појмове „коначно много” и „пребројиво много” који нису дефинабилни у логици првог реда, а имају велики значај у математици. Међутим, прва систематична студија ових логика појављује се у Кислеровим радовима [1970], где проучава логику L(Q1) која настаје до- давањем квантификатора Q1 (постоји непребројиво много) логици првог реда. Доказом комплетности, за једноставан и експлицитан скуп аксиома, и других својстава, као што је теорема о испуштању типова са последицама, Кислер отвара поље за проучавање разних екстензија ове логике, које ће задржати нека добра својства логике првог реда. Сгроове то- полошке логике, којима ћемо се бавити у последњем поглављу, представљају последицу ових Кислерових радова на логикама са уопштеним квантификаторима. У логикама са уопштеним квантификаторима L(Q) квантификаторQ може бити ин- терпретиран на различите начине. Наиме, за сваки ординал α, језик првог реда L може се проширити квантификаторомQα и одговарајућа логика је L(Qα). Скуп формула језика LQα генерисан је правилима која поред стандардних садрже правило: ако је < формула и x променљива, израз облика Qαx< је формула језика LQα , при чему је x везана промен- љива у овој формули. Интерпретација формуле облика Qαx< у моделу A за валуацију ν : Var→ A дефинисана је тако да: A |=Qαx< акко кардиналност скупа {b ∈ A |A |=<[ν (b/x )]} је већа или једнака од ωα , 5 Увод где је ν (b/x ) валуација која свим променљивим додељује исте вредности као и валуација ν , осим променљивој x , којој додељује вредност b . Као што је већ наведено, од великог значаја је логика L(Q1) која је на неки начин из- грађена на разликовању пребројиво–непребројиво. Она је погодна за дефинисање појмова као што су пребројиво генерисане групе, разне непребројиве структуре итд. Логика L(Q0) истиче однос коначно–бесконачно и у њој можемо дефинисати појмове као што су групе са торзијом, коначно генерисане групе, коначно-димензионе векторске просторе, а могу се дефинисати и природни бројеви. За разлику од логике L(Q1), за логику L(Q0) не може се доказати теорема потпуности. Такође, не важи ни теорема компактности, али важи Ловенхајм-Сколемова теорема. У L(Q1) не важи теорема компактности, а ни Ловенхајм- Сколемова теорема, будући да формула Q1x (x = x ) нема пребројив модел. Међутим, ло- гика L(Q1) је занимљива и због тога што у њој, бар у пребројивом случају, важи став ком- пактности, тј. важи: сваки пребројив скуп L(Q1)-реченица је задовољив акко је сваки ње- гов коначан подскуп задовољив. Да теорема компактности не важи (за непребројиве ску- пове реченица) показује следећи пример: ако језик садржи непребројив скуп симбола кон- станти {cα | α <ω1}, сваки коначан подскуп од {¬cα = cβ | 0≤ α < β <ω1} ∪ {¬Q1x (x = x )} је задовољив, док читав скуп то није. Уколико се квантификаторQ интерпретира са „бити отворен скуп”, модификовањем аксиоматског система логике L(Q1), добија се логички систем погодан за описивање појма топологије, који као појам „вишег реда” није био описив у логици првог реда. 6 1. Нестандардна анализа Још крајем 17. века, Лајбниц је увео метод актуелних инфинитезимала у диферен- цијални и интегрални рачун, али тек Абрахам Робинсон (1918–1974) шездесетих година прошлог века ове идеје поставља на строге математичке основе. Његов оригинални при- ступ је био базиран на нестандардним моделима поља реалних бројева. Наиме, Робинсон је нашао пут да сваку математичку структуру A, на пример, стандардни мерљив простор (A,F,µ) утопи у екстензију ∗A, која садржи „идеалне” (нове) елементе. Тражена екстен- зија ∗A се може добити алгебарским путем узимајући ултрастепен ∗A = AI /U , где је U ултрафилтер на подскуповима индексног скупа. Нестандардна анализа је грана математике која формулише анализу користећи строги појам инфинитезимале, где је елемент уређеног поља F инфинитезимала ако и само ако је његова апсолутна вредност мања од било ког елемента поља F облика 1 n , за природан број n . Уређена поља која имају инфинитезимале названа су неархимедовским пољима. Нестандардна анализа користи методе теорије модела, дисциплине математичке логике, проширујући универзум класичне анализе до такозваног нестандардног универзума који садржи бесконачно мале (инфинитезимале) и бесконачно велике елементе. Уопштеније, нестандардна анализа је било која форма математике која се односи на нестандардне мо- деле и принцип трансфера, који је описан у наредном поглављу (видети [44], [53]). 1.1. Нестандардни универзум ∗V (S) Нека је S ̸=∅ скуп праелемената тако да елементи од S нису скупови. Претпоставља се да S садржи скуп R реалних бројева јер је уобичајено да се математичке теорије изгра- ђују у вези са реалним бројевима. Уколико је у питању реална анализа (чак и комплексна), довољно је да се узме S =R. Суперструктуру V (S) изграђујемо индукцијом, и то: V0(S) =S, Vn+1(S) =Vn (S)∪P(Vn (S)), V (S) = ⋃ n∈N Vn (S) Уочава се да се сви жељени објекти над S могу сместити у V (S). На пример, ако x ,y ∈ V (S), тада {x ,y } ∈ V (S), па тиме и (x ,y ) ∈ V (S), због (x ,y ) = {x },{x ,y } . Одатле и свака функција f са доменом и рангом у V (S) такође припада V (S). Даље, ако је (X ,F,µ) мерљив простор тако да X ⊆ S, F ⊆ P(X ) и µ: F → R+, види се да X ∈ V1(S), F ∈ V2(S), µ ∈ V5(S) и (X ,F,µ)∈V9(S). Уобичајено је да све потребне структуре „упадну” у, на пример, V20(S). Структура ∗S и пресликавање ∗: V (S)→V (∗S) је стандардни модел за S уколико задо- вољава следеће: (1) ∗S је права екстензија од S и ∗ ↾ s је идентично пресликавање, тј. ∗s = s , за s ∈S, ово је принцип екстензије. (2) За сваки A1, . . . ,An ∈V (S) и сваку ограничену формулу <(x1, . . . ,xn ) (тј. формулу која је изграђена само помоћу ∈, =, ∧, ∨, ¬,→ и ограничених квантификатора ∀x ∈ y , ∃x ∈ y ) важи: V (S) |=<(A1, . . . ,Ar ) акко V (∗S) |=<(∗A1, . . . , ∗An ) 7 1. Нестандардна анализа Ово је Лајбницов принцип или принцип трансфера. (3) Ако су A1 ⊇ A2 ⊇ . . . непразни скупови из ∗V (S), тада је ⋂n∈NAn ̸=∅, и ово је принцип ω1-засићености, који допушта конструкцију „идеалних” елемената. Размотримо случај када је S = R. По принципу трансфера, алгебарске аксиоме и аксиоме за уређена поља важе и у суперструктури ∗R. На пример, познато је да важи (∀x ∈ R)(∀y ∈ R)(∀z ∈ R)x < y → (x + z )< (y + z ) и зато је (∀x ∈ ∗R)(∀y ∈ ∗R)(∀z ∈ ∗R)x ∗< y → (x ∗+ z ) ∗< (y ∗+ z ), будући да <∈V3(R) и +∈V5(R). Такође, ако x ,y ∈R и x < y , онда је и x ∗=x ∗ n за свако n ∈N). По принципу екстензије ∗R\R ̸=∅, тако да можемо узети x ∈ ∗R\R. Ако је x бесконачан, онда је x−1 ненула инфинитезимала (x је инфинитезимала ако је |x |< 1 n за свако n ∈N). Уколико је x коначан, онда постоји јединствени st(x ) = sup{α∈R |α< x } назван стандардним делом од x , где је x −st(x ) ненула инфинитезимала. Уколико је x ∈ ∗R бесконачан, онда постоји јединствени H ∈ ∗N \N, тако да важи H ≤ x ω већи је одω+ω,ω ·ω, ωω,ωωω , . . . ,ε0, . . . Такође, допустив ординал је увек граничан и једнак је скупу свих орди- нала који су елементи одговарајућег допустивог скупа. Дефиниција 2.7.7. Нека је A= AM = (M;A,∈, . . .). Објекат x је у A уколико је x ∈M ∪A и означава се са x ∈ A. Релација на A је релација на скупу M ∪A. Релација S дужине n на A је Σ1 на A уколико постоји Σ1 формула < тако да је (1) S(x1, . . . ,xn ) акко A |=<[x1, . . . ,xn ] за све x1, . . . ,xn ∈A . 25 2. Допустиви скупови Релација S је Π1 на A ако (1) важи за неку Π1 формулу < и S је ∆1 на A уколико је и Σ1 и Π1 на A. Функција F на A је функција чији је домен подскуп од (M ∪A)n за неко n , а скуп вредности је подскуп од M ∪A. Рећи ћемо да је F Σ1 на A уколико је њен график Σ1 на A. Став 2.7.8. Нека је A допустив скуп. (i) Ако a ∈A, онда a је ∆1 на A, (ii) Ако x ∈A, онда {x } је ∆1 на A, (iii) Σ1 релације на A су затворене за ∧,∨,∃x ∈ a ,∀x ∈ a ,∃x . 2.8. Хередитарно коначни скупови Скуп a ∈VM је хередитарно коначан уколико је TC (a ) коначан. Нека је HFM (0) = 0; HFM (n+1) = скуп свих коначних подскупова скупаM ∪HFM (n ); HFM = ⋃ n<ωHFM (n ). Теорема 2.8.1. HFM је најмањи допустив скуп надM. Прецизније, нека је L∗ = L(∈, . . .) и нека HFM = (M;HFM ,∈, . . .) буде L∗-структура. (i) HFM је допустив скуп. (ii) Ако је AM = (M;A,∈, . . .) допустив, онда је HFM ⊆AM. Доказ. Индукцијом по n лако се доказује (ii) будући да A мора бити затворен за пар и унију. Докажимо да је HFM допустив скуп. Како је HFM транзитиван у VM, аксиоме ек- стензионалности и регуларности су задовољене. Такође је и сваки HFM(n ) транзитиван. Уколико x ,y ∈HFM(n ), онда {x ,y } ∈HFM(n +1), тако да је задовољена аксиома пара. Ако је a ∈ HFM(n ), онда је ⋃a коначни подскуп од HFM(n ) тако да је елемент од HFM(n + 1), тако да је задовољена и аксиома уније. Уколико је a ⊆b ∈HFM(n ), тада је a ∈HFM(n ) бу- дући да је подскуп коначног скупа коначан, отуда је задовољена пуна сепарација, па према томе и ∆0 сепарација. Слично важи и пуна колекција, јер ако a ∈ HFM и има, рецимо, k елемената y1, . . . ,yk , и за сваки од ових yi постоји неки x i тако да <(x i ,yi ) важи, онда се сви x1, . . . ,xk појављују у неком HFM(n ), па је, према томе, {x1, . . . ,xk } ∈HFM(n +1). Последица 2.8.2. Најмањи допустив скуп је HF = {a ∈ V | a је чист хередитарно коначан скуп}. Најмањи допустив ординал је ω. Доказ. HF је чист део било ког HFM и o(HF ) =ω. Допустив скуп HF одговара класичној теорији израчунљивости, што је предста- вљено следећом теоремом. Теорема 2.8.3. Нека је S релација на скупу природних бројева. (i) S је рекурзивно набројив акко S је Σ1 на HF . (ii) S је рекурзиван акко S је ∆1 на HF . Доказ. (⇒) Примећује се да (i) имплицира (ii) будући да је S рекурзиван акко су S и ¬S рекурзивно набројиви предикати. Најпре ћемо доказати (⇒) дела под (ii) јер ће нам по- служити за доказивање одговарајућег дела под (i). Довољно ће бити да покажемо да свака рекурзивна тотална функција на целим бројевима f , може бити проширена доΣ1 функције fˆ наHF следећом дефиницијом: fˆ (x ) = f (x ), за x ∈ω и fˆ (x ) = 0, за x /∈ω. Да бисмо ово до- казали за све рекурзивне функције користићемо дефиницију класе рекурзивних функција 26 2. Допустиви скупови као најмање класе која садржи основне тоталне функције и затворена је за неке операције које од тоталних функција „праве” тоталне функције. Постоје различити приступи теорији израчунљивости, и због најлакшег доказивања изабран је Шенфилдов приступ дат у [51]. Класа (тоталних) рекурзивних функција је најмања класа која садржи +, ·,K< (карактеристична функција релације <), F (x1, . . . ,xn ) = x i (пројекције), затворена је за композицију и µ-операцију (ако јеG рекурзивна функција таква да ∀n⃗ ∃m [G (n⃗ ,m ) = 0] и за све n⃗ ,F (n⃗ ) = µm [G (n⃗ ,m ) = 0], најмање m за које је G (n⃗ ,m ) = 0, онда је F рекурзивна). Већ имамо дефинисане Σ1 операције + и · као и ∆0 релацију α < β (видети табелу 2.2). Композиција тоталних Σ1 функција је тотална Σ1 функција, зато нам преостаје да докажемо да је класа функција f које имају одговарајућу Σ1 функцију fˆ , затворена у односу на µ-оператор. Претпоставимо да је ∀n⃗ ∃mG (n⃗ ,m ) = 0  , да је G рекурзивна и да је Gˆ Σ1 на HF по индукцијској претпоставци и да је F (n⃗ ) = µm [G (n⃗ ,m ) = 0]. Тада, Fˆ (x⃗ ) = y акко неко x i није природан број и y = 0; или свако x i и y су природни бројеви и G (x⃗ ,y ) = 0 и ∀z < y ∃n[n ̸= 0∧G (x⃗ ,z ) = n ]. Како је G Σ1, ово је Σ па је према томе и Σ1. Закључујемо да је свака рекурзивна функција и предикат на ω, ∆1 на HF . Како сваки рекурзивно набројиви предикат S(x⃗ ) може бити представљен у облику ∃n R(x⃗ ,n ), где је R рекурзиван (стандардни резултат из теорије израчунљивости), добијамо да је сваки рекурзивно набројиви предикат Σ1 на HF . Да бисмо доказали други смер, потребна нам је следећа лема. Лема 2.8.4. Постоји функција e :ω→HF са следећим особинама: (i) e је бијекција, (ii) e је Σ1 на HF , (iii) n = e (m ) је рекурзивна релација елеменатаm и n , (iv) за било коју∆0 формулу<(x1, . . . ,xk ), релација (HF,∈) |=<e (n1), . . . ,e (nk ) елемената n1, . . . ,nk је рекурзивна. Доказ. Дефинишимо пресликавање e на следећи начин: e (0) = 0 e (1) = {e (0)}= {0} (1= 20) e (2) = {e (1)} (2= 21) ... ... e (5) = {e (2),e (0)} (5= 22+20) ... ... e (2n1 +2n2 + · · ·+2nk ) = {e (n1), . . . ,e (nk )} (n1 > n2 > · · ·> nk ) . Коришћена је бинарна експанзија броја n и e (n ) је дефинисано за свако n помоћу Σ рекурзије. Како је график функције e Σ на HF , онда је он и Σ1 на HF . Индукцијом се једноставно показује да је пресликавање e бијекција. Уколико је e (k ) = n , тада је e (k +2k ) = n+1, одакле се добија (iii). Како је e (n )∈ e (m ) акко n је експонент у бинарној експанзији 2k1 + · · ·+ 2k l броја m , закључујемо да (iv) важи када је < облика x ∈ y . Ин- дукцијом по сложености ∆0 формула и користећи особине рекурзивних предиката, лако се доказује да важи (iv) и у осталим случајевима. 27 2. Допустиви скупови Доказ теореме 2.8.3. (⇐) Претпоставимо да је S Σ1 на HF и рецимо да је S(n ) акко HF |= ∃y <(n ,y ), где је < нека ∆0 формула. Тада је S(n ) акко ∃k ∃m e (k ) = n ∧<(e (k ),e (m )). Део у загради је рекурзиван на основу претходне леме, па је зато S рекурзивно набројив. (Случај када S има више од једног аргумента се доказује слично). На основу до сада изложеног може се доказати да важи: – HFM ⊆VM(ω), HFM =VM(ω) аккоM је коначан. – Ако је A чист допустив скуп и A ̸=HF , онда ω∈A. – Ако је AM допустив и o(AM) =ω, онда је HF чист део од AM. – HF је ∆1 подскуп било ког допустивог скупа. – Ако је X Σ1 на HF , онда је X Σ1 на сваком допустивом скупу. Елементи скупаHFM су били сви они скупови из VM чије је транзитивнио затворење коначан скуп. С тим у вези, ако је k било који бесконачан кардинални број, дефинишимо H (k )M = {a ∈VM | TC (a ) има кардиналност мању од k }. Закључујемо да је H (ω)M = HFM . Уколико је M празан, писаћемо H (k ) за H (k )M . Ако је k регуларан кардинал, H (k )M се може представити једначинама: G (0) = 0; G (α+1) = {a ⊆M ∪G (α) | card(a )< k } ; G (λ) = ⋃ α<λ G (α), ако је λ гранични ординал ; H (k )M = ⋃ α G (α) = ⋃ α card(M ). Од посебног значаја за наш даљи рад ће бити скуп H (ω1) који ће другачије бити обележен са HC , односно H (ω1)M, уколико јеM непразно. 28 3. Пребројиви фрагменти инфинитарне логике L∞ω Метатеорија на којој ће бити засновано излагање у овом поглављу је KPU теорија скупова. Биће уведена инфинитарна логика L∞ω, као и њени пребројиви фрагменти чије ће особине бити изложене (видети [4]). Једна од тих особина је и Барвајзов став компакт- ности за пребројиве фрагменте (теорема 3.4.6), чија ће једна од примена бити и техника средњег модела, која је детаљно описана у наредном поглављу. 3.1. Формализовање синтаксе и семантике у KPU теорији У претходном поглављу су формализовани неки од основних математичких појмова, као што су „функција”, „природан број”, „ординал” итд. Сада је наш циљ изградња ло- гичког система радећи у KPU теорији и најпре ћемо формализовати појмове као што су „језик”, „структура”, „формула”. Претпоставимо најпре да су међу атомичним предикатима метајезика L∗, следећи предикати: релацијски симбол (x ), функцијски симбол (x ), симбол константе (x ), променљива (x ). Међу операцијским симболима метајезика L∗ се налазе две унарне операције var и ar. Користићемо /,/1,/2, . . . за означавање објеката x који задовољавају релацијски сим- бол (x ). Слично h,h1,h2, . . . за функцијске симболе и c ,c1,d , . . . за симболе константи. Такође ћемо претпоставити да су међу симболима константи метајезика L∗ и симболи ¬,∧,∨,∀,∃,≡. Претпоставићемо, затим, следеће аксиоме за синтаксу: (1) Аксиома која тврди да су класе променљивих, функцијских симбола, релацијских симбола и симбола константи, дисјунктне и да ни један од симбола ¬,∧,∨,∀,∃,≡ не припада ни једној од ових класа. (2) Аксиома за променљиве, где је vα у ствари var(α), α ̸= β ⇒ vα ̸= vβ , променљива (x )⇔∃α(x = vα). (3) Аксиома за ar, која даје дужину или „арност” релацијских и функцијских симбола. Скуп L је језик уколико је L скуп релацијских, функцијских и симбола константи. Предикати „t је терм” и „t је терм језика L” су дефинисани рекурзијом на TC (t ): Дефиниција 3.1.1. t је терм (језика L) акко је t променљива или симбол константе (језика L), или је t = (h,y ), где је h функцијски симбол (језика L), y = (y1, . . . ,yar(h)) и сваки yi је терм (језика L). На основу теореме 2.4.4 може се закључити да су дефинисани предикати уствари ∆ предикати. Дефиниција 3.1.2. Атомичнаформула (језика L) је скуп који има један од следећих облика: (i) (≡, t1, t2) где су t1, t2 терми (језика L); у ознаци (t1 ≡ t2) или (t1 = t2) . (ii) (/, t1, . . . , tn ) где је / релацијски симбол (језика L), n = ar(/) и t1, . . . , tn су терми (је- зика L); у ознаци /(t1, . . . , tn ) за (/, t1, . . . , tn ) . 29 3. Пребројиви фрагменти инфинитарне логике L∞ω Дефиниција 3.1.3. Скуп < је коначна формула (језика L) акко: < је атомична формула (језика L), или < је (¬,ψ) и ψ је коначна формула (језика L), или < је (∧,{ψ,θ }) или (∨,{ψ,θ }) где су ψ,θ коначне формуле (језика L), или < је (∃,v,ψ) или (∀,v,<) где је v променљива и ψ је коначна формула (језика L). Писаћемо ¬ψ за (¬,ψ),ψ∧θ за (∧,{ψ,θ }) и ∃vψ за (∃,v,ψ). Сви наведени предикати су дефинисани рекурзивно и представљају ∆ предикате. У циљу формирања скупова облика a = ⋃ n<ω bn , где је bn дефинисано рекурзијом по n , теорији KPU додаћемо аксиому бесконачности: ∃α Lim (α), где је Lim (α) дефинисано као у табели 2.2 из претходног поглавља. Аксиома бесконачности обезбеђује егзистенцију бесконачних ординала и користићемо симбол ω за први гранични ординал. Став 3.1.4. Уколико аксиома бесконачности важи, онда за било који језик L постоји скуп Lωω = {< |< је коначна формула језика L са променљивим облика vn , n <ω}. Доказ. Показаћемо да јеTerm= {t | t је терм језика L у коме је свака променљива облика vn , n < ω} скуп. Дефинишимо Term(0) = {c ∈ L | c је симбол константе} ∪ {var(n ) | n < ω}, Term(n + 1) = {(h, t1, . . . , tk ) ∈ L | h ∈ L, h је функцијски симбол, k = ar (h), t1, . . . , tk ∈ Term(n )}∪Term(n ), индукцијом по n . Тада је Term= ⋃ n<ω Term(n ). Слично се показује да је и Lωω скуп. Дефиниција 3.1.5. Скуп < је инфинитарна формула уколико важи један од следећих ис- каза: < је коначна формула < је ¬ψ, где је ψ инфинитарна формула, < је ∃vψ или ∀vψ, где је v променљива и ψ је инфинитарна формула, < је (∧,Φ) или < је (∨,Φ), где је Φ непразан скуп инфинитарних формула. Писаћемо ∧Φ за (∧,Φ), односно ∨Φ за (∨,Φ). Појам инфинитарне формуле над јези- ком L се дефинише аналогно. Дефиниције слободне и везане променљиве се једноставно могу извести. (Замена слободне променљиве термом t у формули <, мора бити дефини- сана помоћу рекурзије на TC (<)). Уобичајено, реченица је формула која нема слободних променљивих. Скуп подформула формуле <, у ознаци sub(<), дефинисан је рекурзијом на TC (<), на следећи начин: sub(<) = {<}, ако је < атомична формула, = {<}∪ sub(ψ), ако је < облика ¬ψ, ∃vψ или ∀vψ, = {<}∪⋃ ψ∈Φ sub(ψ), ако је < облика ∧Φ или ∨Φ. Права инфинитарна формула је формула која има коначно много слободних промен- љивих. Појам „права инфинитарна формула” је ∆ појам, с обзиром да важи < је права акко {v | v је слободна променљива у <} је коначан, акко {α | vα је слободно у <} је коначан, 30 3. Пребројиви фрагменти инфинитарне логике L∞ω и да се може доказати да је појам „a је коначан скуп ординала” описив ∆ формулом. За означавање класе свих (правих) инфинитарних формула језика L, кориситићемо симбол L∞ω. Дефиниција 3.1.6. СтруктураM за језик L је парM= (M , f ), где ћемо за f (x ) писати xM, тако да важи: (i) M је непразан скуп, (ii) f је функција чији је домен dom ( f ) = L, (iii) / ∈ L имплицира /M је подскуп одM ar(/), (iv) h ∈ L имплицира hM је функција чији је доменM ar(h) и ранг је подскуп одM , (v) ако c ∈ L, онда cM ∈M . Ово је такође ∆ предикат од M и L. Валуација у M је функција s чији је домен dom (s ) коначан скуп променљивих и rng (s ) ⊆M . За дату структуру M језика L, терм t језика L и валуацију s уM, где су променљиве из терма t садржане у dom (s ), дефинишимо рекурзијом tM(s ) вредност терма t уM за валуацију s : tM(s ) = cM, уколико је t симбол константе c , = s (v ), уколико је t променљива v , = hM(tM1 (s ), . . . , t M k (s )), уколико је t облика h(t1, . . . , tk ). Остаје да се формализује појам релације задовољењаM |=<[s ], где јеM структура језика L, < формула језика L и s је валуација за слободне променљиве у <. Будући да не постоји скуп свих променљивих, не постоји ни скуп свих валуација. Зато узимамо Σ опе- рацијуG тако да за било које L,M и< ∈ L∞ω,G (M,<) = {s | s је валуација уM са dom (s ) = слободне променљиве формуле <}. Дефинишимо тада: SatL(M,<) = {s ∈G (M,<) |M |=<[s ]} рекурзијом на TC (<), SatL(M,/(t1, . . . , tn )) = {s ∈G (M,/(t1, . . . , tn )) | (tM1 (s ), . . . , tMn (s ))∈/M}, SatL(M,¬<) = {s ∈G (M,¬<) | s /∈ SatL(M,<)}, SatL(M,∧Φ) = {s ∈G (M,∧Φ) | за свако < ∈Φ, s ↾Free−Var(<)∈ SatL(M,<)}, SatL(M,∃v<) = {s ∈G (M,∃v<) | за неко x ∈M , s ∪{(v,x )} ∈ SatL(M,<)}, ако је v слободно у <, = SatL(M,<), ако v није слободно у <. За L-структуреM, формуле < језика L и валуације s предикатM |=<[s ] је дат са: M |=<[s ] акко s ↾Free−Var(<)∈ SatL(M,<). За реченице < имамо да јеM |=< уколико је празна функција 0 у SatL(M,<). Како је SatL(M,<) једна Σ операција, на основу теореме Σ рекурзије, закључује се да јеM |=<[s ] један ∆ предикат одM,<,s и језика L. Уколико су слободне променљиве формуле < међу променљивим v1, . . . ,vn , писаћемо M |=<[a 1, . . . ,a n ] за M |=<[s ] где је s = {(v1,a 1), . . . , (vn ,a n )}. 31 3. Пребројиви фрагменти инфинитарне логике L∞ω 3.2. Својство конзистентности Сама техника конструкције модела је врло слична Кислеровој конструкцији у [26]. С обзиром да ћемо све резултате доказивати у теорији KPU+Аксиома бесконачности, по- стоје места у раду која ће се разликовати, тј. треба избећи коришћење аксиоме партитивног скупа и аксиоме избора. Колекција инфинитарних формула језика L никада није скуп и, како је уобичајено радити са скупом формула, имамо следећу дефиницију. Дефиниција 3.2.1. Нека је L језик. Фрагмент од L∞ω је скуп LA инфинитарних формула и променљивих, тако да је: (i) свака коначна формула из Lωω је у LA , (ii) ако < ∈ LA , онда свака подформула и променљива из < је у LA , (iii) ако је <(v )∈ LA и t је терм језика L са променљивим из LA , онда је и <(t /v ) такође у LA , и (iv) ако су <,ψ,v у LA , онда су и ¬<,∼<,∃v<,∀v<,< ∨ψ,< ∧ψ. (Симбол ∼ је дефинисан као у [26], овде је уместо <¬ коришћено ∼<; такође, ∼ има експлицитну Σ дефиницију). Нека је K језик и C = {cn | n <ω} пребројиви скуп симбола константи које се не на- лазе у K . Нека је L = K ∪C фиксирани језик до краја овог одељка. Ако је KA фрагмент од K∞ω, онда постоји природни фрагмент LA = KA(C ) од L∞ω, као скуп свих формула облика <(c i 1, . . . ,c i n ) које су настале заменом коначног броја слободних променљивих констан- тама из C . Терм t из LA је основни уколико је из скупа C или је облика h(c i 1, . . . ,c i n ) за h ∈ K , и c i -ове из C . Дефиниција 3.2.2. Својство конзистентности за LA је скуп S скупова s тако да је сваки s ∈S скуп реченица из LA и следеће важи за свако s ∈S: (C0) 0∈S; ако s ⊆ s ′ ⊆S, онда s ∪{<} ∈S за свако < ∈ s ′ ; (C1) (Правило конзистентности) Ако < ∈ s , онда ¬< /∈ s ; (C2) (¬-правило) Ако ¬< ∈ s , онда s ∪{∼<} ∈S ; (C3) (∧-правило) Ако ∧Φ∈ s , онда за све < ∈Φ, s ∪{<} ∈S ; (C4) (∀-правило) Ако ∀v<(v )∈ s , онда за свако c ∈C , s ∪{<(c/v )} ∈S ; (C5) (∨-правило) Ако ∨Φ∈ s , онда за неко < ∈Φ, s ∪{<} ∈S ; (C6) (∃-правило) Ако ∃v<(v )∈ s , онда за неко c ∈C , s ∪{<(c/v )} ∈S ; (C7) (Правило једнакости) Нека је t основни терм из LA и c ,d ∈C : (i) Ако (c ≡ d )∈ s , онда s ∪{(d ≡ c )} ∈S; (ii) Ако <(t ), (c ≡ t )∈ s , онда s ∪{<(c )} ∈S; (iii) За неко e ∈C , s ∪{e ≡ t } ∈S. Лема 3.2.3. Уколико S задовољава све услове из претходне дефиниције, изузев услова (C0), онда постоји најмање својство конзистентности S′, тако да је S ⊆S′. Доказ. Дефинишимо f (0) = S ∪ {0}, f (n + 1) = f (n ) ∪ {s ∪ {<} | s ∈ f (n ) ∧ ∃s ′ ∈ f (n )[s ⊆ s ′ ∧< ∈ s ′]}, S′ = ⋃ n<ω f (n ). S′ је својство конзистентности и ако је S ⊆ S′′ и S′′ својство конзистентности, онда је f (n )⊆S′′ индукцијом по n . Лема 3.2.4. Нека је S својство конзистентности, s ∈S. (i) <, (<→ψ)∈ s имплицира s ∪{ψ} ∈S. (ii) c ∈C имплицира s ∪{(c ≡ c )} ∈S. 32 3. Пребројиви фрагменти инфинитарне логике L∞ω (iii) c ,d ,e ∈C , (c ≡ d )∈ s , (d ≡ e )∈ s имплицира s ∪{(c ≡ e )} ∈S. СтруктураM језика L је канонска структура уколико је сваки елемент изM облика cM за неко c ∈C . Теорема 3.2.5 (Егзистенција модела). Нека је LA пребројивифрагмент и нека јеS својство конзистентности за LA . За свако s ∈S постоји канонска структураM језика L тако да јеM модел за s , тј за свако < ∈ s ,M |=<. Доказ. Како је LA пребројив, можемо набројити све реченице из LA : <0,<1, . . . , 0 постоји δ > 0 тако да за сваки скуп B из одговарајуће алгебре мерљивих скупова F, µ2(B )< δ имплицира µ1(B )< ϵ. Другим речима, ако је F<ϵi = {B ∈F |µi (B )< ϵ}, i = 1,2, ϵ > 0, тада је свака F<ϵ1 финија колекција од F<δ2 за неко δ > 0. Аксиома апсолутне непрекидности је ∧ ϵ∈Q+ ∨ δ∈Q+ ∧ n∈ω ∧ <∈Φn ((P2x⃗ < δ)<(x⃗ )→ (P1x⃗ < ϵ)<(x⃗ )), где је Φ= ⋃ n Φn , Φn = {< ∈Φ |< има n +1 слободну променљиву}. 41 4. Средњи модел Напомена 4.9. (1) Аксиома апсолутне непрекидности неће имплицирати да у слабом мо- делу (A,µ1,µ2) важи µ1 ≪ µ2, с обзиром да је дозвољено правити конјункције само по елементима допустивог скупа, тј. ∧ <∈Φ <, Φ ∈ A, али ће обезбедити трансформацију слабог модела у модел у коме ће бити задовољено тражено својство. Изложеном тех- ником средњег модела добијамо модел у коме ће аксиома апсолутне непрекидности важити униформно за сваку формулу <, тј. важиће за свако ϵ > 0, постоји δ > 0 тако да за сваку формулу < логике L AP1P2 важи (P2x⃗ < δ)<(x⃗ ) → (P1x⃗ < ϵ)<(x⃗ ), тј. важиће µ1≪µ2. (2) Напоменимо још да је слаб модел (A,q1,q2) логике L f A (Q1,Q2) такође и f -модел, тј. при- мена изложене технике није била неопходна, али је због погодног методичког при- ступа излагању ове технике изабран управо тај логички систем са наведеним свој- ствима између колекција q1 и q2 (исто важи и за логику Lu A (Q1,Q2)). Пример 4.10 (Теорема комплетности за тополошке класа моделе). Тополошка класа ло- гика L A (O,C ) (инфинитарна логика са два нова квантификатораO и C ) погодна је за проу- чавање топологије на правим класама, где су класе отворених и класе затворених скупова дефинисане одвојено. Тополошки класа модел за L A (O,C ) је структура (K,O,C ) тако да је тројка (K ,O,C ) тополошки класа простор где је O класа отворених подскупова и C класа затворених подскупова од K . Релација задовољења је дефинисана уобичајено: (K,O,C ) |=Ox<[⃗b ] акко a | (K,O,C ) |=<[a , b⃗ ] ∈O ; (K,O,C ) |=Cx<[⃗b ] акко a | (K,O,C ) |=<[a , b⃗ ] ∈C . Од описаних својстава тополошког класа простора, у аксиоматском систему логике L A (O,C ), издвојићемо оно због којег је неопходна примена технике средњег модела: За сваки подскуп X од K постоји F ∈ C тако да је X ⊆ F . Примећује се да је наве- дено својство типа „уписан у”. Одговарајућа аксиома је ∧ n ∧ <∈Φn ∀x⃗ ∨ m ∨ ψ∈Φm ∃y⃗ Czψ(z , y⃗ )∧ ∀z (<(z , x⃗ )→ψ(z , y⃗ )), где је Φ=⋃ n Φn , Φn = {< ∈Φ |< је формула са n +1 слободном про- менљивом} и Φ, Φn ∈ A. Дакле, наведено својство мора да важи за све подскупове од K , а не само за дефинабилне подскупове од K , па је зато неопходна конструкција средњег модела. У даљем раду су изложени разни логички системи у којима је техника конструкције средњег модела кључна у доказивању комплетности аксиоматизација у односу на дефи- нисане класе модела. (Видети поглавља 5, 6 и 7). 42 5. Логике са интегралима 5.1. Логике LAP У овом поглављу је представљена логика L AP која је слична инфинитарној логици L A и која, уместо уобичајених квантификатора (∀x ) и (∃x ), поседује вероватносне кван- тификаторе (Px ≥ r ). Структура ове логике је структура првог реда са вероватносном (пребројиво адитивном) мером на универзуму, тако да је свака релација мерљива. Фор- мула (Px ≥ r )<(x ) подразумева да скуп {x | <(x )} има меру најмање r . Претпоставља се да је A допустив скуп тако да је ω ∈ A и сваки елемент a ∈ A је пребројив (тј. A⊆HC, где је HC скуп наследно пребројивих скупова, видети [4] и поглавље 2). Дефиниција 5.1.1. Уз претпоставку да је L пребројивA-рекурзиван скуп релацијских сим- бола и симбола константи (без функцијских симбола), логика L AP има следеће логичке симболе: (а) Пребројиво много променљивих vn , n ∈N; (б) Везнике ¬ и∧; (в) Квантификаторе (Px⃗ ≥ r ), где је x⃗ = (x1, . . . ,xn ) n-торка различитих променљивих и r ∈A∩ [0,1]; (г) Симбол једнакости = (опционо). Дефиниција 5.1.2. Скуп формула логике L AP је најмањи скуп тако да: (а) Свака атомична формула логике првог реда је формула из L AP ; (б) Ако је < формула из L AP , онда је и ¬< формула логике LAP ; (в) Ако је Φ ∈ A скуп формула логике L AP са коначно много слободних променљивих, онда је и ∧ Φ формула логике L AP ; (г) Ако је < формула из L AP и (Px⃗ ≥ r ) је квантификатор логике LAP , онда је и (Px⃗ ≥ r )< формула из L AP . Формуле се могу посматрати у скуповном смислу, тј. као елементи допустивог скупа A тако да је L AP ⊆ A. Како је LAP одређена логиком Lω1P (видети [23]), имамо да је LAP = A∩ Lω1P . Дефиниција 5.1.3. У логици L AP се користе следеће скраћенице: (i) (Px⃗ < r )< за ¬(Px⃗ ≥ r )<; (ii) (Px⃗ ≤ r )< за (Px⃗ ≥ 1− r )¬<; (iii) (Px⃗ > r )< за ¬(Px⃗ ≥ 1− r )¬<; (iv) ∨ <∈Φ< за ¬ ∧ <∈Φ¬<; (v) Коначни везници ∧,∨→,↔ су дефинисани уобичајено. 5.1.1. Вероватносни модели Коначно адитиван вероватносни простор је уређена тројка (A,S,µ) где је S поље под- скупова од A и µ: S→ [0,1], µ(A) = 1 и за X ,Y ∈ S, µ(X ∪Y ) =µ(X \Y )+µ(Y \X )+µ(X ∩Y ). Скупови X ∈ S су µ-мерљиви, а µ је коначно адитивна вероватносна мера на A. 43 5. Логике са интегралима Вероватносни простор је тројка (A,S,µ), где је S σ-поље и µ је пребројиво адитивна мера; тј. за X0 ⊆ X1 ⊆ . . . из S имамо да је µ(⋃ n Xn ) = lim n µ(Xn ). У том случају, за µ ћемо једноставније рећи „вероватносна мера”. Скуп X је нула скуп мере µ уколико постоји Y ⊇ X тако да је µ(Y ) = 0. Производ два вероватносна простора (A,S,µ) и (B ,F,ν ) је вероватносни простор (A×B ,S⊗F,µ⊗ν ), где је S⊗F σ-алгебра генерисана помоћу скупа мерљивих правоугаоника X×Y , где X ∈ S, Y ∈F и важи (µ⊗ν )(X×Y ) =µ(X )·ν (Y ); n-ти производ простор је означен са (An ,Sn ,µn ). У општем случају, дијагонала, тј. скуп {(x ,x ) | x ∈M } није µ2-мерљив. Међутим, уколико је сваки синглтон мерљив, постоји начин да се мера µ2 прошири и на дијагоналне супове. Дефиниција 5.1.4. Нека је (A,S,µ) вероватносни простор такав да је сваки синглтон мер- љив. Тада, за свако n ∈N, (An ,S(n ),µ(n )) је вероватносни простор где је S(n ) σ-алгебра гене- рисана помоћу мерљивих правоугаоника и дијагоналних скупова Di j = {x⃗ ∈ An | x i = x j } и µ(n ) је јединствена екстензија од µn на S(n ) таква да је µ(n )(Di j ) = ∑ x∈M µ({x })2. Став 5.1.5. Уколико је (A,S,µ) вероватносни простор такав да је сваки синглтон мерљив, тада мера µ(n ) на S(n ), дата у претходној дефиницији, постоји и јединствена је. Штавише, за сваки скуп X ∈ S(n ) постоји µn -мерљив скупU тако да је µ(n )(X∆U ) = 0. Дефиниција 5.1.6. Вероватносни модел за L је структура A= (A,RAi ,cAj ,µ)i∈I ,j∈J , где је µ (пребројиво адитивна) вероватносна мера на A тако да је сваки синглтон мерљив, свака релација RAi је µ(n i )-мерљива и сваки cAj ∈ A. Теорема 5.1.7. Нека је A вероватносни модел за L. Релација задовољења A |= <[a⃗ ], за <(x⃗ ) ∈ L AP и a⃗ за A, је дефинисана рекурзивно као у случају логике LA уз додатни услов за вероватносни квантификатор: A |= (Py⃗ ≥ r )<(x⃗ , y⃗ )[a⃗ ] акко {⃗b ∈ An | A |= <[a⃗ , b⃗ ]} је µ(n )-мерљив и има меру најмање r . Штавише, A је модел реченице < ако је A |=<. Теорема 5.1.8. За сваки вероватносни модел A , формулу <(x⃗ , y⃗ ) ∈ L AP и a⃗ из A, скуп {⃗b ∈ An |A |=<[a⃗ , b⃗ ]} је µ(n )-мерљив. Претходна теорема, на неки начин, оправдава дефинисаност релације задовољења за случај са вероватносним квантификаторима и последица је „дијагоналне” форме Фу- бинијеве теореме (видети [22]). Теорема 5.1.9 (Фубини). Нека је µ вероватносна мера тако да је сваки синглтон мерљив и нека је B ⊆ Am+n µ(m+n )-мерљив. Тада је: (i) Сваки засек Bx⃗ = {y⃗ ∈ An | x⃗ y⃗ ∈ B} је µ(n )-мерљив; (ii) Функција f (x⃗ ) =µ(n )(Bx⃗ ) је µ(m )-мерљива; (iii) Важи да је µ(m+n )(B ) = ∫ f (x⃗ )dµ(m ). (Функција f : A→R је µ-мерљива ако је f −1(−∞,r ) µ-мерљив скуп за свако r ∈R). 5.1.2. Аксиоматски систем и правила извођења Следећим дефницијама је дат аксиоматски систем логике L AP ; < иψ су произвољне формуле из L AP , Φ∈A је произвољан скуп формула из LAP и r,s ∈A∩ [0,1]. Дефиниција 5.1.10. Аксиоме слабе L AP су следеће: (А1) Све аксиоме за LA без квантификатора; (А2) Монотоност: (Px⃗ ≥ r )<→ (Px⃗ ≥ s )<, где је r ≥ s ; 44 5. Логике са интегралима (А3) (Px⃗ ≥ r )<(x⃗ )→ (Py⃗ ≥ r )<(y⃗ ); (А4) (Px⃗ ≥ 0)<; (А5) Коначна адитивност: (i) (Px⃗ ≤ r )< ∧ (Px⃗ ≤ s )ψ→ (Px⃗ ≤ r + s )(< ∨ψ); (ii) (Px⃗ ≥ r )< ∧ (Px⃗ ≥ s )ψ∧ (Px⃗ ≤ 0)(< ∧ψ)→ (Px⃗ ≥ r + s )(< ∨ψ); (А6) Архимедовско својство: (Px⃗ > r )<↔ ∨ n∈N (Px⃗ ≥ r + 1 n )<. Дефиниција 5.1.11. Аксиоме за (пуну) L AP су аксиоме за слабу LAP плус следећа листа аксиома: (B1) Пребројива адитивност: ∧ Ψ⊆Φ (Px⃗ ≥ r )∧Ψ→ (Px⃗ ≥ r )∧Φ, где Ψ иде преко скупа свих коначних подскупова од Φ; (B2) Симетрија: (Px1, . . . ,xn ≥ r )<↔ (Px u¯ (1), . . . ,x u¯ (n ) ≥ r )<, где је u¯ пермутација скупа {1,2, . . . ,n}. (B3) (Px⃗ ≥ r )(Py⃗ ≥ s )<→ (Px⃗ y⃗ ≥ r · s )<, где су све променљиве у x⃗ и y⃗ различите. (B4) За свако r < 1, (Px⃗ ≥ 1)(Py⃗ > 0)(Pz⃗ ≥ r )(<(x⃗ , z⃗ )↔<(y⃗ , z⃗ )), где су све променљиве у x⃗ , y⃗ и z⃗ различите. (Аксиома (B4) обезбеђује да <(x⃗ , y⃗ ) може бити апроксимиран коначном унијом мер- љивих правоугаоника). Дефиниција 5.1.12. Правила извођења за L AP су следеће: (R1) Модус поненс: <, <→ψ ⊢ψ; (R2) Конјункција: {<→ψ |ψ∈Ψ} ⊢<→∧Ψ; (R3) Генерализација: <→ψ(x⃗ ) ⊢<→ (Px⃗ ≥ 1)ψ(x⃗ ), где x⃗ није слободно у <. 5.1.3. Слаби модели Дефиниција 5.1.13. Слаб модел за L AP је структура A= (A,RAi ,cAj ,µn )i∈I ,j∈J ,n∈N, тако да је µn коначно адитивна вероватносна мера на An , сваки синглтон је мерљив и скуп {⃗b ∈ An | A |=<[a⃗ , b⃗ ]} је µn мерљив за сваку формулу <(x⃗ , y⃗ )∈ LAP и a⃗ из A. Теорема 5.1.14 (Теорема слабе комплетности). Нека је A пребројив. Уколико је Φ конзи- стентно у слабој L AP , онда Φ има слаб модел. Скица доказа: Нека је C пребројив скуп нових симбола константи и нека је K = L ∪C . Помоћу Хенкинове конструкције, [44], Φ може бити проширено до маскимално конзи- стентног скупа реченица Γ (у слабој K AP) са следећим својствима: (1) Ако је Φ⊆ Γ и∧Φ∈ K AP , онда је ∧ Φ∈ Γ; (2) Ако је <(c⃗ )∈ Γ за свако c⃗ из C , онда (Px⃗ ≥ 1)<(x⃗ )∈ Γ. Нека је C ′ скуп симбола константи језика K . Γ индукује структуру првог реда A0 = (A,RAj ,cA)i∈I ,c∈C ′ за K на уобичајен начин и A = {cA | c ∈ C ′}. Мера µn је дефинисана по- моћу µn{c⃗ A | <(c⃗ , d⃗ ) ∈ Γ} = sup{r | (Px⃗ ≥ r )<(x⃗ , d⃗ ) ∈ Γ} за свако <(x⃗ , y⃗ ) и d⃗ . На основу аксиома (А1)–(А5) мера µn ће бити добро дефинисана и коначно адитивна. Овим је доби- јен слаб модел A. На основу аксиоме (А6), обезбеђена је коректност дефинисања мере µn . Индукцијом се доказује да је A |=Γ, па је према томе A модел за Φ. 45 5. Логике са интегралима 5.1.4. Градирани вероватносни модели Дефиниција 5.1.15. Градирани вероватносни модел за L је структура A= (A,RAi ,cAj , µn )i∈I ,j∈J ,n∈N, тако да: (а) свако µn је (пребројиво адитивна) вероватносна мера на An ; (б) свака n-арна релација RAi је µn -мерљива и релација једнакости је µ2-мерљива; (в) ако је скуп B µm -мерљив, онда је B ×An µm+n -мерљив; (г) свака µn је инваријантна за пермутације; уколико је u¯ пермутација скупа {1,2, . . . ,n} и B ∈ dom(µn ), ако је u¯ B = {(a u¯ (1), . . . ,a u¯ (n )) | (a 1, . . . ,a n ) ∈ B}, онда u¯ B ∈ dom(µn ) и µn (u¯ B ) =µn (B ); (д) 〈µn | n ∈N〉 има Фубинијево својство: ако је B µm+n -мерљив, онда: (1) за свако x⃗ ∈ Am , секција Bx⃗ = {y⃗ | B (x⃗ , y⃗ )} је µn -мерљив; (2) функција f (x⃗ ) =µn (Bx⃗ ) је µm -мерљива; (3) ∫ f (x⃗ )dµm =µm+n (B ). Дефиниција 5.1.16. Под градираном логиком L AP подразумевамо логику LAP са свим ак- сиомама, изузев аксиоме (B4). Теорема 5.1.17 (Теорема градиране комплетности). Сваки пребројиви скуп реченица Φ који је конзистентан у градираној L AP , има градиран модел. Скица доказа: Нека је A пребројив и нека L има пребројиво много симбола константи које се не појављују у Φ. Тада, Φ има слаб модел A = (A,Ri ,c j ,µn )i∈I ,j∈J ,n∈N такав да за- довољава све теореме градиране L AP , A = {c j | j ∈ J } и домен сваке мере µn је скуп LAP- дефинабилних подскупова од An . Нека је ∗A= (∗A, ∗Ri , ∗c j , ∗µn )i∈∗I ,j∈∗J ,n∈∗N интернална струк- тура и нека је Aˆ= (∗A, ∗Ri , ∗c j ,L(µn ))i∈I ,j∈J ,n∈N, где је L(µn ) Лебова мера од µn . Из чињенице да сваки L(µn )-мерљив скуп може бити апроксимиран одозго и одоздо интерналним ску- повима, као и из аксиома (B2) и (B3), следи да је Aˆ градирана вероватносна структура. Индукцијом по сложености формуле може се показати да је Aˆ L AP-еквивалентно са A, па је према томе Aˆ |=Φ. 5.1.5. Сагласност и комплетност Од кључног значаја у доказу теореме комплетности је следећа лема која се доказује применом аксиоме (B4) n пута. Лема 5.1.18 (Апроксимација правоугаоницима). Нека јеA градирана вероватносна струк- тура која задовољава сваку теорему из L AP . Тада, за свако ϵ > 0 и формулу <(y⃗ ) из LAP постоји коначно много формула ψi j (x⃗ ,y j ), ге је i = 1, . . . ,m и j = 1, . . . ,n , тако да важи A |= (Px⃗ > 0)(Py⃗ > 1− ϵ)<(y⃗ )↔ m∨ i=1 n∧ j=1 ψi j (x⃗ ,y j )  . Лемом се тврди да било који дефинабилан скуп <(y⃗ ) у A може бити апсоксимиран до на ϵ помоћу коначне уније дефинабилних правоугаоника. Дефиниција 5.1.19. Нека су A и B градиране вероватносне структуре. Каже се да је A= B скоро сигурно (с.с.) ако A и B имају исте универзуме, константе и мере, и за сваку атомичну формулу <(x⃗ ) из L AP важи: A |=<[a⃗ ] акко B |=<[a⃗ ] за µn -скоро све a⃗ . 46 5. Логике са интегралима Лема 5.1.20. Ако је A = B с.с., онда су A и B L AP-еквивалентне структуре. Такође, за сваку формулу <(x⃗ ) из L AP , A |=<[a⃗ ] акко B |=<[a⃗ ] за µn -скоро све a⃗ . Доказ се изводи индукцијом по сложености формуле <. Теорема 5.1.21. Нека је A градирана вероватносна структура која задовољава сваку те- орему логике L AP и нека је µ = µ1. Тада, постоји градирана вероватносна структура B таква да је A = B с.с., и свака релација RBi је µ(n )-мерљива. Према томе, B индукује уобичајену вероватносну структуру. Теорема 5.1.22 (Теорема сагласности). Било који скуп Φ реченица из L AP , који има модел, је конзистентан. Једина потешкоћа је проверити ваљаност аксиоме (B4). (Видети [27]). Теорема 5.1.23 (Теорема комплетности). Сваки пребројив конзистентан скуп Φ реченица логике L AP има модел. Теорема комплетности је последица градиране комплетности, теореме 5.1.21 и леме 5.1.20. На основу следећег примера се лако закључује да теорема компактности за L AP не важи. Пример 5.1.24. Нека је T скуп реченица који садржи реченице (Px > 0)R(x ) и (Px ≤ 1 n )R(x ) за n = 1,2,3, . . . Док сваки коначан подскуп од T има модел, цео скуп T нема модел. 5.1.6. Случајне променљиве Дефиниција 5.1.25. Случајна променљива n-тог степена на вероватносном простору (A,F,µ) је µ(n )-мерљива функција X : An →R. Нека је L = {X i ,c j ,Rk | i ∈ I , j ∈ J ,k ∈ K }. Дефиниција 5.1.26. Помоћни језик од L је језик LX који има исте симболе константи c j и релацијске симболе Rk из L, али и нове релацијске симболе [X i (x⃗ ) ≥ r ] и [X i (x⃗ ) ≤ r ] за свако i ∈ I и r ∈Q. Користе се следећа скраћења: [X i (x⃗ )< r ] за ¬[X i (x⃗ )≥ r ] и [X i (x⃗ )> r ] за ¬[X i (x⃗ )≤ r ]. Језик L AP (R) има исти скуп формула као и LXAP . Аксиоме и правила извођења су као у LXAP , плус четири нове аксиоме где су r,s ∈Q: (RV1) [X i (x⃗ )≥ r ]→ [X i (x⃗ )≥ s ], где је r ≥ s ; (RV2) [X i (x⃗ )> r ]↔∨ n [X i (x⃗ )≥ r + 1n ]; (RV3) [X i (x⃗ )≥ r ]↔∧ n [X i (x⃗ )≥ r − 1n ]; (RV4) ∨ n ([X i (x⃗ )≥−n ]∧ [X i (x⃗ )≤ n ]). Дефиниција 5.1.27. Модел са случајним променљивим за L је структура (A,µ), где је A= (A,XAi ,c A j ,R A k )i∈I ,j∈J ,k∈K структура првог реда, µ је вероватносна мера на A, XAi је случајна променљива n i -тог степена, cAj ∈ A, RAk је µ(n i )-мерљива и сваки синглтон је мерљив. 47 5. Логике са интегралима Важи да је (A,µ) |= [X i (x⃗ )≥ r ][a⃗ ] акко XAi (a⃗ )≥ r . Теорема 5.1.28. Пребројив скуп реченица из L AP (R) има модел са случајним променљивим акко је конзистентан у L AP (R). 5.2. Логика LA ∫ Индикатор формула 1(R(x⃗ )) за дату релацију R(x⃗ ) је дефинисана са 1(R(x⃗ )) = ( 1, ако R(x⃗ ) је тачно, 0, ако R(x⃗ ) није тачно. Језик L A ∫ ће имати атомичне терме који ће бити интерпретирани као индикатор функције атомичних формула на језику L, а сложенији терми ће бити изграђени из ато- мичних коришћењем непрекидних реалних функција као и коришћењем интеграције. Нека је L Σ-дефинабилан скуп који садржи релацијске симболе, симболе константи, пребројиво много променљивих ν1,ν2,ν3, . . ., n-арне везнике F за сваку непрекидну функ- цију F : Rn →R, n ≥ 0, тако да је F ↾ Q n∈A, и квантификаторе ∫ . . .dx . Дефиниција 5.2.1. Скуп термова логике L A ∫ је најмањи скуп, тако да: (1) сваки атомични терм 1(R(x⃗ )) или 1(x = y ) за сваку атомичну формулу логике првог реда L A , је терм; (2) сваки реални број r ∈A∩R је терм; (3) ако је τ терм и x је променљива, онда је ∫ τdx терм; (4) ако су τ1, . . . ,τn терми, тада је и F(τ1, . . . ,τn ) терм. Променљива x је везана у терму ∫ τdx . Затворен терм је терм без слободних про- менљивих. Дефиниција 5.2.2. Скуп формула логике L A ∫ је најмањи скуп такав да: (1) свака атомична формула τ≥ 0, за сваки терм τ из L A ∫ , је формула; (2) ако је < формула, онда је и ¬< формула; (3) ако је Φ скуп формула са коначно много слободних променљивих и Φ∈A, онда је∧Φ формула. Дефиниција 5.2.3. Интерпретација за L A ∫ у вероватносној структури (A,µ) је функција која додељује сваком терму τ(x⃗ ), где је x⃗ = (x1, . . . ,xn ) n-торка различитих променљивих, функцију τA : An →R, тако да је: (1) 1(R(x⃗ ))A(a⃗ ) = ( 1, ако је RA[a⃗ ], 0, ако је ¬RA[a⃗ ], 1(x = y )A(a ,b ) = ( 1, ако је a =b , 0, ако је a ̸=b ; (2) rA = r ; (3) ∫ τ(x , y⃗ )dx A(a⃗ ) = ∫ τA(b , a⃗ )dµ(b ); (4) F(τ1, . . . ,τm )A(a⃗ ) = F (τA1 (a⃗ ), . . . ,τAm (a⃗ )). Релација задовољења A |= <[a⃗ ] за формулу <(x⃗ ) из L A ∫ и a⃗ ∈ An је дефинисана ре- курзивно као у логици првог реда, изузев услова за атомичне формуле: ако је τ(x⃗ ) ≥ 0 атомична формула, онда је A |= (τ(x⃗ )≥ 0)[a⃗ ] акко τA(a⃗ )≥ 0. Аксиоме логике L A ∫ , где су σ,τ терми и r,s ∈A∩R, су: 48 5. Логике са интегралима (E1) све схема аксиоме за LA без квантификатора, где атомична формула 1(x = y ) = 1 игра улогу формуле x = y ; (E2) τ= 0∨τ= 1, за сваки атомични терм τ; (E3) аксиоме уређења: (1) r ≥ r ; (2) τ≥ r →τ≥ s за r ≥ s ; (E4) (τ1, . . . ,τm ) ∈ S → F(τ1, . . . ,τm ) ∈ [a ,b ], за сваки рационални затворени правоугаоник S ⊆Rm , где је F (S) = [a ,b ]; (E5) аксиоме за интеграл: (i) ∫ r dx = r ; (ii) ∫ τ(x )dx = ∫ τ(y )d y ; (iii) ∫∫ τ(x ,y )dx d y = ∫∫ τ(x ,y )d y dx ; (iv) ∫ (r ·σ+ s ·τ)dx = r ∫ σdx + s ∫ τdx ; (E6) Архимедова аксиома τ> r ↔∨ n (τ≥ r + 1 n ); (E7) за свакоm ∈N,∨ k ∫ Fk  1−∫ Fk ∫ |τ(x⃗ , z⃗ )−τ(y⃗ , z⃗ )|d z⃗ d y⃗ d x⃗ ≥ 1− 1m , где је Fk (a ) = 0, ако је a ≤ 1 k , линеарно, ако је 1 k ≤ a ≤ 2 k , 1, ако је a ≥ 2 k . Аксиома (E7) је транслација аксиоме (B4) за LAP . Правила извођења за логику L A ∫ су: (F1) <,<→ψ ⊢ψ (Modus Ponens) ; (F2) {<→ψ |ψ∈Ψ} ⊢<→∧Ψ (Правило конјункције) ; (F3) <→ (τ(x , y⃗ )≥ 0) ⊢<→ ∫ τ(x , y⃗ )dx ≥ 0, где x није слободно у < (Генерализација) . Нека је T пребројив и конзистентан скуп реченица из L A ∫ . Најпре се помоћу Хенки- нове конструкције добија слаб интегрални модел (A, I ) за T , где је A модел првог реда, а I је A-Данијелов интеграл на A; тј. I је функција на скупу термова из L A ∫ са највише једном слободном променљивом и параметрима из A, тако да је: (1) I (r ) = r ; (2) I (r ·σ+ s ·τ) = r · I (σ)+ s · I (τ); (3) ако је τA(b , a⃗ )≥ 0 за свако b ∈ A, онда је и I (τ(x , a⃗ ))≥ 0. Рекурзивна дефиниција за τ(a⃗ )(A,I ) је иста као и за уобичајену вероватносну струк- туру, изузев услова за интеграл∫ τ(x , a⃗ )dx (A,I ) = I (τ(x , a⃗ )). Од слабог интегралног модела, преласком на нестандардни универзум, добија се интер- нална слаба интегрална структура (∗A, ∗I ). Лебова конструкција Данијеловог интеграла (видети поглавље 1) даје вероватносну меру µ на ∗A, тако да за сваки терм τ(x ) са параметрима из ∗A, стандардни део од ∗I (τ) је интеграл стандардног дела од τ∗A у односу на меру µ. На сличан начин конструишу се вероватносне мере µn на ∗An коришћењем итери- саних интеграла. На крају, аксиома (E7) је задовољена скоро свуда у градираном моделу (∗A,µn ), тако да на сличан начин као у логици LAP , добијамо вероватносни модел за T . 49 5. Логике са интегралима Теорема 5.2.4. Пребројив скуп реченица из L A ∫ има вероватносни модел ако и само ако је конзистентан. 5.3. Теорема комплетности за вероватносне моделе са коначно вредносним мерама у логици са интегралима Lfin A ∫ У наредном излагању радићемо са мерама чији ће скупови вредности бити коначни. С друге стране, постоје многе структуре чији подскупови могу бити врло занимљиви као скупови вредности мера, односно погодни за изражавање вероватноћа. Поред стандард- ног примера архимедског поља рационалних бројева Q, тј. интервала [0,1] Q , важан је и пример неархимедског поља, као што је, рецимо, Q[ϵ], тј. најмањег поља које се добија додавањем једне позитивне инфинитезимале ϵ пољу рационалних бројева. Такође су ин- тересантни и примери производа уређених поља, који су уређени прстени, као што су Q×Q, Qn итд. Ови примери оправдавају важност рангова мера, а ми ћемо у овом погла- вљу издвојити оне чији су рангови коначни скупови реалних бројева из интервала [0,1]. На самом почетку издвојићемо интересантну теорему на којој ће бити утемељена аксиоматизација логике Lfin A ∫ . Теорема 5.3.1. Нека је F поље подскупова скупа Ω. Мера µ је коначно вредносна вероват- носна мера на F ако и само ако постоји реалан број c > 0 такав да је µ(A) > c кад год је A ∈F и µ(A)> 0. Будући да су, на неки начин, мере у логици L AP експлицитније изражене у синтакси, ово својство мере може бити добијено помоћу аксиоме (FV )P ∨ c∈Q+ ∧ <∈Φn ((Px⃗ > 0)<(x⃗ )→ (Px⃗ > c )<(x⃗ )), где је Φn ∈ A и Φn = {< | < има n слободних променљивих} (видети [15]). За налажење аксиоме која ће имплицирати исто својство мера у логици L A ∫ , искоришћен је следећи резултат: индукцијом по сложености терма може се доказати да за сваки терм τ(x⃗ ) из L A ∫ и за свако r ∈R∩A постоји формула<τ,r из LAP тако да је у свакој вероватносној структури (A,µ) за свако a⃗ ∈ An испуњено следеће: τA(a⃗ )> r акко A |=<τ,r [a⃗ ], (видети [44]). Штавише, логике L AP и L A ∫ су еквивалентне (видети [27]) што омогућава да сваку теорему логике L AP можемо конвертовати у сличну теорему логике L A ∫ , и обратно. Нека јеA пребројив допустив скуп такав да јеA⊆HC иω∈A и нека је L Σ-дефинаби- лан скуп симбола релација и константи, који има пребројиво много променљивих v1,v2, . . ., n-арне везнике F за сваку непрекидну функцију F : Rn → R, n ≥ 0 и F ↾ Q n∈ A и квантифи- каторе ∫ . . .dx . Логика Lfin A ∫ је слична логици L A ∫ ; листи аксиома логике L A ∫ је додата аксиома која је у ствари транслација аксиоме (FV )P у L A ∫ : (FV )∫ ∨ c∈Q+ ∧ τ∈D ∧ r∈Q ∨ k h∫ Fk ,r (τ(x⃗ ))d x⃗ > 0→ ∫ Fk ,r (τ(x⃗ ))d x⃗ > ci, 50 5. Логике са интегралима где је Fk ,r (a ) = 1, ако је a ≥ r,0, ако је a ≤ r − 1k , линеарно, иначе, и D је скуп термова са коначно много слободних променљивих и D ∈ A. Како конјунк- ција у претходној аксиоми може да се посматра само преко елемената допустивог скупа A, тј. ∧ τ∈D где D ∈A, применићемо конструкцију средњег модела (видети поглавље 4). Вероватносна структура за Lfin A ∫ је структура (A,µ) тако да је A структура првог реда и µ је вероватносна мера на A таква да је сваки синглтон мерљив, свака релација RAi је µ(n i )-мерљива и µ је коначно вредносна вероватносна мера. Градиран модел је дефинисан као у логици L AP уз додатни услов да су мере µn коначно вредносне. Доказаћемо да је ова аксиоматизација комплетна за Σ1-дефинабилне теорије у од- носу на класу вероватносних модела са коначно вредносним мерама, комбинујући Хенки- нову конструкцију и конструкцију средњег модела. Увешћемо две врсте помоћних струк- тура, тј. дефинисаћемо слаб и средњи модел. Дефиниција 5.3.2. (i) Слаб модел логике Lfin A ∫ је структура (A, I ), где је A структура пр- вог реда за језик L и I је позитивна реална функција дефинисана на скупу термова са највише једном слободном променљивом x и параметрима из A. (ii) Средњи модел у Lfin A ∫ је слаб модел (A, I ), такав да аксиома (FV )∫ важи униформно за сваки терм τ, тј. постоји c ∈Q+ тако да за сваки терм τ и a⃗ ∈ An , и за свако r ∈Q, постоји k , ако I (Fk ,r (τ(x , a⃗ )))> 0, онда I (Fk ,r (τ(x , a⃗ )))> c где је Fk ,r (a ) = 1, ако је a ≥ r ,0, ако је a ≤ r − 1k , линеарно, иначе . У оба случаја, за терм τ дефинишемо τA индуктивно као за вероватносне моделе, изузев случаја за интеграл ∫ τ(x , y⃗ )dx A(a⃗ ) = I (τ(x , a⃗ )). Помоћу Хенкинове конструкције, слично као у претходном поглављу, доказујемо да је Σ1-дефинабилна теорија у Lfin A ∫ конзистентна ако и само ако има слаб модел у коме важи свака теорема логике Lfin A ∫ . Нека је C ∈ A скуп нових симбола константи уведен Хенкино- вом конструкцијом и нека је K = L ∪C . Конструкција средњег модела из слабог модела је кључни део доказа главног резул- тата и изложићемо је следећом теоремом. Теорема 5.3.3 (Средња комплетност). Σ1-дефинабилна теорија T из K fin A ∫ је конзистентна ако и само ако има средњи модел у коме важи свака теорема из K fin A ∫ . Доказ. Уведимо језик M који има четири врсте променљивих: X ,Y ,Z , . . . променљиве за скупове, x ,y ,z , . . . променљиве за урелементе, r,s , t , . . . за реалне бројеве и P,Q ,R , . . . променљиве за терме који представљају функције An → R, n ≥ 0. Предикати су ≤ за ре- алне бројеве, E sn (x⃗ ,X )(n ≥ 1 и x⃗ = x1, . . . ,xn ) за скупове, E tn+1(x⃗ ,r,T ), n ≥ 0 (са значењем T (x1, . . . ,xn ) = r ), и I (T,r ) (T : A0 → R или T : A1 → R и I (T ) = r акко I (T,r )). Функциј- ски симболи су +, · и скуп функцијских симбола F за терме и реалне бројеве, тако да је 51 5. Логике са интегралима F ∈ C A (Rn ). Симболи константи су X< за сваку формулу < из K fin A ∫ , Tτ за сваки терм τ и r¯ за сваки реалан број r ∈R∩A. Нека је S теорија изM A , која садржи следећу листу формула: 1. Аксиоме добре дефинисаности (а) (∀X ) ∧ n 0)→ I (Fk ,r (T )> c )) где је Fk ,r (a ) = 1, ако је a ≥ r,0, ако је a ≤ r − 1k , линеарно, иначе, 7. Аксиома за архимедовско поље и све теореме теорије поља реалних бројева 8. Аксиоме које су трансформација аксиома логике K fin A ∫ (∀x⃗ )E sn (x⃗ ,X<). 9. Аксиоме реализације свих реченица < из T (∀x )E s1 (x ,X<). Слаба структура (A, I )може бити трансформисана у стандардну структуруB= (B ,P,Q , F,E sn B,E t B n+1, I B,≤,+, ·,Fn ,XB< ,TBτ , r¯ ) за MA где је B = A, P ⊆ ⋃ n≥1P(An ),Q ⊆ ⋃ n≥0P(An ×R), F ⊆ R је поље, XB< ∈ P за формулу < и TBτ ∈ Q за терм τ. Узећемо да је XB< = {a⃗ ∈ An | A |= <[a⃗ ]}, P = nXB< | < ∈ K fin A ∫ o , TBτ (a⃗ ) = τA(a⃗ ) за a⃗ ∈ An , Q = n TBτ | τ је терм из K fin A ∫ o и IBk (T B τ ) = I (τ) за терм τ са највише једном слободном променљивом. Теорија S је Σ1 дефи- 52 5. Логике са интегралима набилна на A и S0 ⊆S, S0 ∈A има стандардни модел зато што аксиома (FV )∫ важи у слабом моделу. На основу Барвајзове компактности (видети [4]) следи да S има стандардни модел B који може бити трансформисан у средњи модел B теорије T стављањем да је: τB(x⃗ ) = r акко E tBm+1(x⃗ ,1,Tτ) (R B(a⃗ ) важи акко E tBm+1(a⃗ ,r,T1(R(x⃗ )))) и IB(τ(a⃗ ,y )) = IB(Tτ(a⃗ ,y )) за a⃗ ∈Bn . Овим је доказ комплетиран. Сада ћемо доказати теорему комплетности за логику Lfin A ∫ . Као и у доказу комплет- ности за логику L A ∫ , биће коришћена Лебова конструкција која одговара Данијеловом интегралу (видети поглавље 1). Теорема 5.3.4 (Теорема комплетности за Lfin A ∫ ). Σ1-дефинабилна теорија T из Lfin A ∫ је кон- зистентна ако и само ако T има вероватносни модел са коначно вредносном мером. Доказ. Сагласност је једноставно доказати. Да бисмо доказали тежи део, нека је C пре- бројив скуп нових симбола константи. Користимо Хенкинову конструкцију да добијемо максимално конзистентан скуп Φ реченица из K fin A ∫ , где је K = L ∪C , тако да је: (1) ако је Γ⊆Φ, и∧Γ∈ K fin A ∫ , онда је ∧ Γ∈Φ, (2) ако је ∫ τ(x )dx > 0 ∈Φ, онда (τ(c )> 0)∈Φ, за неко c ∈C . Како је теорија Φ комплетна и садржи све аксиоме логике K fin A ∫ , она индукује слабу структуру (A, I ) са универзумом A =C , тако да свака реченица из Φ важи у моделу (A, I ). Следећи корак је конструкција средњег модела за теорију T из Lfin A ∫ . На основу тео- реме 5.3.3 добијамо средњи модел у коме важи аксиома (FV )∫ униформно за сваки терм τ. Преласком на ω1-засићени нестандардни универзум формирамо интернални средњи интегрални модел (∗A, ∗I ). Лебова конструкција даје вероватносну меру µ на ∗A тако да за сваки терм τ(x ) са параметрима из ∗A, стандардни део од ∗I (τ) је интеграл стандардног дела од τ∗A у односу на µ. Мере µn конструишемо као у случају градираног модела за логику L A ∫ . Из Лебове конструкције и аксиоме (FV )∫ закључујемо да ће мере µn имати коначне рангове. На основу аксиоме (E7) (видети [27]) коначно добијамо вероватносни модел (B,µ) за T , где је B= ∗A и µ=µ1. На потпуно исти начин се може доказати исти резултат и за логику Lfin AP , која је на- стала додавањем аксиоме (FV )P листи аксиома логике LAP . Слаб и средњи модел су дефинисани на следећи начин. Дефиниција 5.3.5. (i) Слаба структура за Lfin AP је структура (A,µn ) таква да је свака µn коначно адитивна вероватносна мера на An , сваки синглтон је мерљив и скуп {⃗b ∈ An | (A,µn ) |=<[a⃗ , b⃗ ]} је µn -мерљив за сваку формулу <(x⃗ , y⃗ )∈ Lfin AP и a⃗ ∈ Am . (ii) Средња структура за Lfin AP је слаба структура (A,µn ), таква да важи следеће: постоји c > 0 тако да је за сваку формулу <(x⃗ , y⃗ )∈ Lfin AP и свако a⃗ ∈ Am , ако је µn ( 0, онда је µn ( c , где је 0)(S1(x )∧ · · · ∧Sn (x )) | n ∈ω} ∪ {(Px < 12n )Sn (x ) | n ∈ω} нема вероватносни модел са коначно вредносном мером. Остаје да се докаже да је T конзи- стентно у Lfin AP . Нека је A јединични интервал [0,1] и нека је µ Лебегова мера на [0,1]. За скупове Bn = [0, 12n+1 ) имамо да је 0 < µ(Bn ) < 1 2n . Нека је A i 1,...,i kn1,...,nk = B i 1 n1 ∩ · · · ∩ B i knk Булов атом, где је B in = Bn за i = 1 и B in = A \ Bn за i =−1. Интерпретираћемо предикате узимајући да је R (A,µ)n = ( Bn , ако је Rn =Sm за некоm , B1, иначе. Будући да се само коначно много предиката Sn (x ) могу појавити у неком елементу скупа A, следи да је скуп n A i 1,...,i kn1,...,nk | µ A i 1,...,i kn1,...,nk  > 0 o коначан. Теорија T , као и све аксиоме логике Lfin AP су задовољене, изузев евентуално аксиоме (FV )P . Међутим, како је за c = min n µ A i 1,...,i kn1,...,nk  | µA i 1,...,i kn1,...,nk  > 0o задовољена и ова аксиома, закључује се да је T конзи- стентно у Lfin AP . 5.4. Двовероватносне логике Апсолутно непрекидни двовероватносни простор је структура (A,F,µ1,µ2) са две вероватносне мере µ1 и µ2 на A дефинисане на истој σ-алгебри F мерљивих скупова који задовољавају следећи услов: за сваки B ∈F, ако је µ2(B ) = 0, онда је µ1(B ) = 0. Мера µ1 је апсолутно непрекидна у односу на µ2, у ознаци µ1≪µ2, уколико је испуњено да за свако ϵ > 0 постоји δ> 0 тако да за сваки B ∈F, ако је µ2(B )<δ, онда је µ1(B )< ϵ. Предмет нашег проучавања ће бити структуре са две мере које се налазе у апсо- лутно непрекидном односу. Логике погодне за проучавање структура са две мере, које су у сингуларном односу (видети [44]), дате су у [17], [44]. 5.4.1. Логика La AP1P2 Нека је A пребројив допустив скуп ω∈A. Логика La AP1P2 је слична стандардној веро- ватносној логици, разлика је у томе што се квантификација у логици La AP1P2 врши у односу на две мере µ1 и µ2, тј. постоје две врсте квантификатора (P1x⃗ ≥ r ) и (P2x⃗ ≥ r ). Апсолутно непрекидни двовероватносни модел за L је структура (A,µ1,µ2) где је A класична структура без операција за L = {Ri ,c j | i ∈ I , j ∈ J } и µ1 и µ2 су вероватносне мере такве да важи µ1≪µ2. Релација задовољења је дефинисана рекурзивно као у случају L AP и квантификатори су интерпретирани на уобичајен начин; (A,µ1,µ2) |= (Pi x⃗ ≥ r )<[x⃗ , y⃗ ][c⃗ ] акко µ(n )i {a⃗ ∈ An | (A,µ1,µ2) |=<[a⃗ , c⃗ ]} ≥ r . Аксиоме, и правила извођења, су све аксиоме као у логици L AP , које допуштају да квантификатори P1 и P2 играју улогу квантификатора P, заједно са следећим аксиомама: 54 5. Логике са интегралима (U1) Аксиоме непрекидности вероватносних квантификатора (i) ∧ n ∨ m (Pi y⃗ < 1 n )(Pj x⃗ ∈ [r − 1m ,r ))<(x⃗ , y⃗ ), i , j = 1,2, (ii) ∧ n ∨ m (Pi y⃗ < 1 n )(Pj x⃗ ∈ (r,r + 1m ])<(x⃗ , y⃗ ). (U2) Аксиома апсолутне непрекидности∧ ϵ∈Q+ ∨ δ∈Q+ ∧ n ∧ <∈Φn ((P2x⃗ <δ)<(x⃗ )→ (P1x⃗ < ϵ)<(x⃗ )), где је Φ= ⋃ n Φn , Φn = {< ∈Φ |< има n слободних променљивих} и Φ, Φn ∈A. У циљу доказивања теореме комплетности логике La AP1P2 уведене су две врсте помоћ- них модела. Дефиниција 5.4.1. (i) Слаб двовероватноснимодел за La AP1P2 је структура (A,µ1n ,µ2n ) тако да је свака µin коначно адитивна вероватносна мера на An , где је сваки синглтон мер- љив и скуп {a⃗ ∈ An | (A,µ1n ,µ2n ) |= <[a⃗ , c⃗ ]} је µin -мерљив за сваку формулу <(x⃗ , y⃗ ) из La AP1P2 и c⃗ из A. (ii) Средњи двовероватносни модел за La AP1P2 је слаб модел (A,µ1n ,µ2n ) у ком аксиома ап- солутне непрекидности важи униформно за сваку формулу <, тј. за свако ϵ > 0 по- стоји δ > 0 тако да је за сваку формулу <(x⃗ , y⃗ ) из La AP1P2 и c⃗ ∈ Am испуњено, ако је µ2n{a⃗ ∈ An |A |=<[a⃗ , c⃗ ]}<δ, онда је µ1n{a⃗ ∈An |A |=<[a⃗ , c⃗ ]}< ϵ. С обзиром да све аксиоме представљају особине мера које се налазе у апсолутно непрекидном односу, теорема сагласности важи. Аксиоматизација је комплетна за Σ1- дефинабилне теорије у односу на класу апсолутно непрекидних двовероватносних мо- дела; у доказу је коришћена слаб-средњи-јак модел конструкција (видети [46]). 5.4.2. Логика La A ∫ 1 ∫ 2 Двовероватносна логика La A ∫ 1 ∫ 2 са два типа интегралних оператора је уведена слич- ном конструкцијом из претходног одељка и представља екстензију логике L A ∫ погодну за проучавање особина случајних променљивих у апсолутно непрекидном двовероватно- сном простору. Еквиваленција између логика L AP и L A ∫ је проширена и на двовероватно- сне логике La AP1P2 и La A ∫ 1 ∫ 2 . Апсолутно непрекидни двовероватносни модел за L је дефинисан као и за логику La AP1P2 . Релација задовољења је дефинисана рекурзивно као за логику L A ∫ , где су кванти- фикатори ∫ 1 и ∫ 2 интерпретирани на уобичајен начин. Аксиоме су све аксиоме за L A ∫ , где квантификатори ∫ 1 и ∫ 2 играју улогу квантификатора ∫ плус следеће аксиоме. (V1) Аксиоме непрекидности интегралних оператора (i , j = 1,2). (а) ∧ n ∨ m ∨ k ∫ i Gk ∫ j τ(x⃗ , y⃗ )d x⃗  d y⃗ < 1 n , где је Gk (a ) = 1, ако је r − 1 m + 1 k ≤ a ≤ r − 2 k , 0, ако је a ≤ r − 1 m или a ≥ r − 1 k , линеарно, иначе. (б) ∧ n ∨ m ∨ k ∫ i Hk ∫ j τ(x⃗ , y⃗ )d x⃗  d y⃗ < 1 n , где је Hk (a ) = 1, ако је r + 2 k ≤ a ≤ r + 1 m − 1 k , 0, ако је a ≤ r + 1 k или a ≥ r + 1 m , линеарно, иначе. 55 5. Логике са интегралима Ове аксиоме представљају транслацију аксиома (U1) логике La AP1P2 (видети претходни одељак). (V2) Аксиома апсолутне непрекидности∧ ϵ∈Q+ ∨ δ∈Q+ ∧ τ∈D ∧ r∈Q ∨ k ∫ 2 Fk ,r (τ(x⃗ ))d x⃗ <δ→ ∫ 1 Fk ,r (τ(x⃗ ))d x⃗ < ϵ  где је Fk ,r (a ) = 1, ако је a ≥ r,0, ако је a ≤ r − 1k , линеарно, иначе. Слаб и средњи модел дефинисани су на следећи начин: Дефиниција 5.4.2. (i) Слаб модел за La A ∫ 1 ∫ 2 је структура (A, I1, I2), где је A структура пр- вог реда и I1, I2 су позитивне линеарне функције дефинисане на скупу термова са нај- више једном слободном променљивом x и параметрима из A. (I1, I2 су A-Данијелови интеграли на A). (ii) Средњи модел за La A ∫ 1 ∫ 2 је слаб модел (A, I1, I2) такав да је аксиома апсолутне непре- кидности задовољена униформно за сваки терм τ(x⃗ ), тј. за свако ϵ > 0 постоји δ> 0, тако да за сваки терм τ(x⃗ ) и a⃗ из A и за свако r ∈Q, постоји k тако да је задовољено: Уколико је I2(Fk ,r (τ(x , a⃗ )))<δ, онда је I1(Fk ,r (τ(x , a⃗ )))< ϵ, где је Fk ,r (a ) = 1, ако је a ≥ r,0, ако је a ≤ r − 1k , линеарно, иначе. За обе структуре, за термτ, дефинишемо τA индуктивно као за вероватносне моделе, (слично као у логици L A ∫ ) изузев услова за интеграле∫ i τ(x , y⃗ )dx A (a⃗ ) = I i (τ(x , a⃗ )), за i = 1,2. За Σ1-дефинабилну теорију T из La A ∫ 1 ∫ 2 конструкција вероватносног модела је врло слична одговарајућој конструкцији у логици Lfin A ∫ (видети одељак 5.3). Постоје и други примери двовероватносних логика са интегралима где се мере на- лазе у апсолутно непрекидном односу; у њиховим моделима фигуришу случајне промен- љиве. Тада се веза између мера може аксиоматизовати уз помоћ случајне променљиве која ће бити интерпретирана као Радон–Никодимов извод. Једна таква логика ће бити описана у поглављу 6. Интересантна је и двовероватносна логика са интегралима, описана у [13], где је доказана проширена комплетност. 56 6. Логике са операторима условног очекивања 6.1. Случајне променљиве и интеграли Главни циљ је увођење случајних променљивих у логику L A ∫ , тако да добијена ло- гика L A ∫ (R), која ће бити описана у овом поглављу, буде еквивалентна логици L AP (R) са случајним променљивим, видети [27], [44]. За разлику од логике L A ∫ , где атомични терми могу узимати вредности из скупа {0,1}, у логици L A ∫ (R) са случајним променљивим, до- пуштено је да атомични терми могу имати вредности у скупу R. Нека је L A-рекурзиван скуп {X i ,c j | i ∈ I , j ∈ J } симбола случајних променљивих и симбола константи. Дефиниција 6.1.1. Атомични терми логике L A ∫ (R) су [X i (x⃗ )↾r ] и 1(x = y ) где је x⃗ уређена n-торка променљивих или константи и r ∈ Q+. Скуп термова и формула из L A ∫ (R) је де- финисан као у случају логике L A ∫ . Структура са случајним променљивим је структура A= (A,XAi ,c A j ,µ) која је већ описана у поглављу 5. Дефиниција 6.1.2. Вредност τ(a⃗ )A терма τ(x⃗ ) логике L A ∫ (R) у структури са случајним променљивим A је дефинисана као у L A ∫ , изузев следећег правила за атомичне терме: [X i (a⃗ )↾r ]A = r, акко X A i (a⃗ )≥ r, −r, акко XAi (a⃗ )≤−r, XAi (a⃗ ), иначе. Закључује се да [X i (a⃗ ) ↾r ]A представља засек од X i (a⃗ ), ограничен бројем r . Главни разлог засецања је да сваки терм буде интерпретиран као ограничена и, према томе, инте- грабилна случајна променљива. Аксиоме и правила извођења од L A ∫ (R) су иста као код логике L A ∫ уз једину разлику аксиома о термима. Тачније, аксиома „τ = 0∨τ = 1, за сваки атомични терм τ” из L A ∫ је замењена следећом листом аксиома, где је x⃗ n-торка променљивих или константи. (1) 1(x = y ) = 0∨1(x = y ) = 1. (2) [X i (x⃗ )↾r ] =min s ,max (−s , [X i (x⃗ )↾r ]), где је 0≤ s ≤ r . (3) ∨ k (|[X i (x⃗ )↾k+1]| ≤ k ) (X i (x⃗ ) је коначно). (4) За свако m ∈ N , ∨ k ∫ |[X i (x⃗ )↾k+1]− [X i (x⃗ )↾k ]|d x⃗ ≤ 1m . (Вероватноћа да је [X i (x⃗ )] ≥ k тежи нули кад k →∞). Теорема 6.1.3 (Теорема сагласности и потпуности). Пребројив скуп Φ реченица логике L A ∫ (R) има модел акко је конзистентан. 6.2. Условно очекивање Дефиниција 6.2.1. Нека је (A,S,µ) вероватносни простор и нека је F σ-подалгебра од S и нека је g : A→R ограничена и мерљива функција. Условно очекивање од g у односу на 57 6. Логике са операторима условног очекивања алгебру F је F-мерљива функција h : A→ R тако да важи ∫ B g dµ= ∫ B h dµ, за свако B ∈ F. Уобичајена ознака је h = E [g |F] или h(x ) = E [g (·) |F](x ). Став 6.2.2. Условно очекивање h(x ) = E [g (·) | F](x ) постоји и јединствено је у смислу да су било које две такве функције једнаке скоро свуда (са разликом на скупу мере нула). Ово је последица Радон-Никодимове теореме (видети [36], [22]). У случају условног очекивања, h је Радон-Никодимов извод мере ν (B ) = ∫ B g dµ, за B ∈ F у односу на меру µ ↾F. Логика L AE је екстензија логике L A ∫ (R) настала додавањем новог оператора E [· | ·] чија је улога да се опишу многи основни појмови у теорији вероватноће, пре свега, појам условног очекивања случајне променљиве у односу на неку σ-алгебру. Дефиниција 6.2.3. Скуп термова и формула логике L AE је дефинисан као у случају за L A ∫ (R), изузев следећег правила за грађење термова: ако је τ(x⃗ ,y ) терм, где y није у x⃗ и z је променљива, тада је E [τ(x⃗ ,y ) | y ](z ) такође терм. Појам слободног појављивања променљиве у терму τ логике L AE се уводи индук- цијом по сложености терма τ на исти начин као у логици L A ∫ , изузев случаја за термове са оператором условног очекивања. Променљива v је слободна у E [σ(x⃗ ,y ) | y ](z ) акко v је z или v није y и слободно је у σ. Затим је скуп слободних променљивих логике L AE подељен на два дела: E -слободне и E -везане променљиве. Дефиниција 6.2.4. (а) Променљива v је E -слободна у [X i (x⃗ )↾r ] акко v је у x⃗ ; (б) v је E -слободна у 1(x = y ) акко v је x или v је y ; (в) v је E -слободна у F(τ1, . . . ,τn ) акко v је E -слободно у τi , за неко i ; (г) v је E -слободна у ∫ τdx акко v није x и v је E -слободно у τ; (д) v је E -слободна у E [τ(x⃗ ,y ) | y ](z ) акко v није z и v је у x⃗ ∪{y }; (ђ) Променљива v је E -везана у τ акко v је слободна у τ и није E -слободна у τ. У наставку ћемо видети да је интерпретација термова са операторима условног оче- кивања таква, да интерпретација преко E -слободних променљивих даје F-мерљиву слу- чајну променљиву, док интерпретација преко E -везаних даје случајну променљиву која није F-мерљива. Дефиниција 6.2.5. Модел са условним очекивањем за L је структура A= (A,XAi ,µ,F), где јеµ вероватносна мера наA таква да је сваки синглтонмерљив,F јеσ-алгебраµ-мерљивих скупова и случајна променљива XAi : An → R је реално вредносна µ(n ) | B-мерљива функ- ција, тј. за сваки Борелов подскуп B од R, (XAi )−1 (B ) је µ(n )-мерљив скуп. Дефиниција 6.2.6. Интерпретација у структури са условним очекивањем (A,µ,F) је функ- ција која сваком терму τ(x1, . . . ,xn ) из LAE додељује функцију τA : An →R и дефинисана је као у случају за L A ∫ (R), уз услов за терм са оператором условног очекивања: E [τ(x⃗ ,y ) | y ](z ) A(a⃗ ,b ) = E [τA(a⃗ ,y ) | y ](b ) за свако a⃗ ∈An и заµ-скоро свеb ∈ A, где E [τA(a⃗ , ·) |F]: A→ R представља условно очекивање за τA(a⃗ , ·): A→R у односу на алгебру F. С обзиром да су сви терми ограничени, може се дефинисати униформна граница ‖τ‖. При интерпретацији у произвољном моделу A, важиће |τA(a⃗ )| ≤ ‖τ‖, за свако a⃗ ∈ An . 58 6. Логике са операторима условног очекивања Дефинише се индуктивно на следећи начин: ‖X i (x⃗ )↾r ‖= r, ‖1(x = y )‖= 1, ‖r ‖= r, ‖∫ τdx‖= ‖τ‖, ‖E [τ | y ](z )‖= ‖τ‖, ‖F(τ1, . . . ,τn )‖= sup|s i |≤‖τi ‖|F (s1, . . . ,sn )|. Аксиоматски систем логике L AE је добијен тако што су аксиомама логике L A ∫ (R) додате аксиоме које формализују дефиницију условног очекивања: E [τ(x⃗ ,y ) | y ](z ) = E [τ(x⃗ ,u ) | u ](z ) где се y и u не појављују у x⃗ ;(5) ∫ E [τ(x⃗ ,y ) | y ](y ) ·σ(y )d y = ∫ E [τ(x⃗ ,y ) | y ](y ) ·E [σ(y ) | y ](y )d y .(6) Теорема 6.2.7 (Теорема сагласности и потпуности). Пребројиви скуп реченица логике L AE има модел ако и само ако је конзистентан. Доказ. Нека је Φ конзистентан скуп L AE реченица и нека је K језик настао додавањем нових симбола случајне променљиве Xτ(x⃗ ) за сваки терм τ(x⃗ ) из LAE облика E [σ(x⃗ ,y ) | y ](z ), језику L. Сваки такав терм је транслиран у атомични терм [X i (x⃗ ,z )↾n ], где је n ≥ ‖τ‖. Закључује се да сваки терм и реченица из L AE имају своју транслацију у K A ∫ (R). Нека је Ψ теорија у K A ∫ (R), која се састоји из свих транслација реченица из Φ, свих транслација теорема из L AE и реченица (Px⃗ ≥ 1)[Xτ(x⃗ )↾r ] = [Xτ(x⃗ )↾s ], r,s ≥ ‖τ‖. Ψ је тада конзистентно у K A ∫ (R) и има модел са случајним променљивим A. Нека је F σ-алгебра на A генерисана скуповима {d ∈ A | XAτ (a⃗ ,d ) ≥ r }, где је τ(x⃗ ,z ) облика E [σ(x⃗ ,y ) | y ](z ) и a⃗ је из A. Редукт модела A на језик L је модел са условним очекивањем за скуп реченица Φ. Сличан концепт се може направити и за два или више оператора условних очеки- вања. Интересантан је случај са два оператора E1 и E2, где је једна σ-алгебра садржана у другој. Теорема 6.2.8. Нека је Φ пребројив скуп реченица у L AE са два оператора условног очеки- вања. Φ има модел A= (A0,F1,F2), где је F1 ⊆ F2 ако и само ако је Φ конзистентно у LAE заједно са схема аксиомом E1[τ(x⃗ ,y ) | y ] = E2E1[τ(x⃗ ,y ) | y ] | y  . 6.3. Двовероватносне логике са условним очекивањем 6.3.1. Двовероватносне логике са случајним променљивим и интегралима Као што је већ описано у поглављу 5, апсолутно непрекидни двовероватносни мо- дел је структура (A,µ1,µ2), где је A структура првог реда (без операција) и µ1,µ2 су две вероватносне мере у односу µ1 ≪ µ2. Одговарајућа логика LAP1P2 је врло слична стан- дардној вероватносној логици L AP ; две врсте квантификатора се користе, Pi x⃗ > r , i = 1,2, r ∈A∩ [0,1], који су интерпретирани на уобичајен начин: (A,µ1,µ2) |= (Pi x⃗ > r )<(x⃗ ) акко µia⃗ ∈ An | (A,µ1,µ2) |=<[a⃗ ] > r, i = 1,2. 59 6. Логике са операторима условног очекивања Од аксиома и правила извођења за L AP1P2 издвојићемо аксиому која описује апсо- лутну непрекидност мера µ1 и µ2.∧ ϵ∈Q+ ∨ δ∈Q+ ∧ n∈ω ∧ <∈Φn (P2x⃗ <δ)<(x⃗ )→ (P1x⃗ < ϵ)<(x⃗ ), где је Φ= ⋃ n Φn , Φn = {< ∈Φ |< има n +1 слободних променљивих} и Φ, Φn ∈A. Двовероватносна логика La A ∫ 1 ∫ 2 са два типа интегралних оператора је уведена на при- родан начин као екстензија логике L A ∫ , погодна за проучавање особина случајних промен- љивх у апсолутно непрекидном двовероватносном простору. У овом поглављу, модифи- коваћемо логику La A ∫ 1 ∫ 2 додавањем нових атомичних термова који узимају вредности у R, слично као у случају логике L A ∫ (R). Добијена логика La A ∫ 1 ∫ 2 (R) представља основу на којој ће бити утемељена логика La AE1E2 . Логички симболи логике La A ∫ 1 ∫ 2 (R) обухватају пребројиво много променљивих v0, v1, . . .; везнике ¬ и ∧; симболе функција f за свако f ∈ CA(Rn ), где је CA(Rn ) скуп свих непрекидних функција f : Rn → R, n ≥ 0, таквих да је f ↾ Qn ∈ A; симбол једнакости =; и интегралне квантификаторе ∫ 1 . . .dx и ∫ 2 . . .dx . С обзиром да су структуре са случајним променљивим од интереса за наше истраживање, користићемо језик L = {X } ∪ {X i | i ∈ I } ∪ {c j | j ∈ J } са симболима случајних променљивих X ,X i , i ∈ I и симболима константи c j , j ∈ J . Претпоставимо да је A⊆HC и A је пребројив допустив скуп. Дефиниција 6.3.1. Двовероватносни модел (апсолутно непрекидни) са случајним про- менљивим за L је структура облика A= (A,XAi ,XA,µ1,µ2), где су µ1,µ2 вероватносне мере на A такве да је µ1 ≪ µ2 и сваки синглтон је мерљив, скуп {⃗b ∈ An | A |= <[a⃗ , b⃗ ]} је µ(n )i мерљив за сваку формулу <(x⃗ , y⃗ ) и a⃗ из A, XAi : An → R је n-та случајна променљива, XA : A→R+ је Радон-Никодимов извод од µ1 у односу на меру µ2 и cAj ∈ A. Дефинишимо сада скуп термова и формула логике La A ∫ 1 ∫ 2 (R). Дефиниција 6.3.2. Скуп термова за La A ∫ 1 ∫ 2 (R) је најмањи скуп, тако да је: (i) сваки атомични терм 1(x = y ) или [Y (x⃗ )↾ r ], где је Y симбол случајне променљиве и r ∈Q+, је терм; (ii) сваки реални број r ∈A је терм; (iii) ако су τ1, . . . ,τn терми и f ∈CA(Rn ), онда је f (τ1, . . . ,τn) терм; (iv) ако је τ терм и x је променљива, онда је ∫ i τdx терм, за i = 1,2; (v) ако је τ(x⃗ ,y ) терм и y није у x⃗ , онда је 1(τ(x⃗ ,y )> r ) терм, r ∈Q. Дефиниција 6.3.3. Скуп формула логике La A ∫ 1 ∫ 2 (R) је најмањи скуп, тако да важи: (i) свака атомична формула τ≥ 0, за сваки терм τ, је формула; (ii) ако је < формула, онда је и ¬< формула; (iii) ако је Φ скуп формула са коначно много слободних променљивих и Φ ∈ A, онда је и∧ Φ формула. Дефиниција 6.3.4. (а) Интерпретација за La A ∫ 1 ∫ 2 (R) у двовероватносном моделу са слу- чајним променљивим је дефинисана слично као у L A ∫ (R), уз додатне услове за нове 60 6. Логике са операторима условног очекивања терме: ∫ i τ(x⃗ ,y )d y A (a⃗ ) = ∫ A τA(a⃗ ,y )dµi (y ), i = 1,2;(1)  1(τ(x⃗ ,y )> r ) A(a⃗ ,b ) =(1, τA(a⃗ ,b )> r, 0, τA(a⃗ ,b )≤ r. ,(2) (б) Релација задовољењаA |=<[a⃗ ], за формулу<(x⃗ ) и a⃗ ∈An , је дефинисана рекурзивно на исти начин као у логици L A уз услов A |= (τ(x⃗ )≥ 0)[a⃗ ] акко τA(a⃗ )≥ 0. Као и у логици L A ∫ (R) и овде су атомични терми засечени, тако да су сви терми интерпретирани помоћу ограничене и интеграбилне случајне променљиве. Униформна граница терма ‖τ‖ је дефинисана као у L A ∫ (R), и очигледно је ‖1(τ(x⃗ ,y )> r )‖= 1. Аксиоме логике La A ∫ 1 ∫ 2 (R) су све аксиоме од L A ∫ , где интеграли ∫ 1 и ∫ 2 играју улогу интеграла ∫ , сем аксиоме за атомичне терме, која је, слично као у логици L A ∫ (R), замењена следећом листом аксиома: Терм аксиоме [Y (x⃗ )↾r ] =min r,max (−r [Y (x⃗ )↾s ]), 0≤ r ≤ s ;(Т1) ∨ k |[Y (x⃗ )↾(k+1)]| ≤ k ;(Т2) ∨ k ∫ i |[Y (x⃗ )↾(k+1)]− [Y (x⃗ )↾k ]|d x⃗ ≤ 1 m , за свакоm ∈N;(Т3) ∧ r 1(τ(x⃗ ,y )> r ) = 1∨1(τ(x⃗ ,y )> r ) = 0,(Т4) (где Y може бити X i , i ∈ I или X ); заједно са: Аксиоме непрекидности интегралних оператора i , j = 1,2∧ n ∨ m ∨ k ∫ i gk ∫ j τ(x⃗ , y⃗ )d x⃗  d y⃗ < 1 n ,(C1) где је g k (a ) = 1, ако је r − 1 m + 1 k ≤ a ≤ r − 2 k , 0, ако је a ≤ r − 1 m или a ≥ r − 1 k , линеарно, иначе;∧ n ∨ m ∨ k ∫ i hk ∫ j τ(x⃗ , y⃗ )d x⃗  d y⃗ < 1 n ,(C2) где је hk (a ) = 1, ако је r + 2 k ≤ a ≤ r + 1 m − 1 k , 0, ако је a ≤ r + 1 k или a ≥ r + 1 m , линеарно, иначе;∫ 1 ∫ 2 τd y  dx = ∫ 2 ∫ 1 τdx  d y(I) 61 6. Логике са операторима условног очекивања Радон–Никодимова аксиома∨ k ∧ τ∈D ∫ 1 τ(x⃗ ,y )d y = ∫ 2 τ(x⃗ ,y ) · [X (y )↾ k ]d y ,(RN) где је D скуп термова са коначно много слободних променљивих и D ∈A. Правила извођења за La A ∫ 1 ∫ 2 (R) су: <,<→ψ ⊢ψ (модус поненс);(R1) {<→ψ |ψ∈Ψ} ⊢<→∧Ψ (конјункција);(R2) <→ (τ(x⃗ ,y )≥ 0) ⊢<→ ∫ k τ(x⃗ ,y )d y ≥ 0, где y није слободно у <(R3) (генерализација). Теорема сагласности важи, с обзиром да све аксиоме представљају добро позната својства. Теорема 6.3.5 (Теорема сагласности). Свака реченица логике La A ∫ 1 ∫ 2 (R) која има двоверо- ватносни модел са случајним променљивим је конзистентна. Лако се може доказати да је ова аксиоматизација комплетна за Σ1 дефинабилне те- орије у односу на класу двовероватносних модела са случајним променљивим, комби- нујући технику својства конзистентности и слаб-средњи-јак модел конструкцију М. Ра- шковића у [46]. Иста техника биће примењена и за доказивање главног резултата у овом поглављу. Теорема 6.3.6 (Теорема комплетности за La A ∫ 1 ∫ 2 (R)). Нека је T скуп реченица из La A ∫ 1 ∫ 2 (R) који је Σ1 дефинабилан на A и конзистентан са аксиомама логике La A ∫ 1 ∫ 2 (R). Тада постоји двовероватносни модел са случајним променљивим за T . У конструкцији модела користе се две врсте уобичајених модела који се у случају логике La A ∫ 1 ∫ 2 (R) дефинишу на следећи начин: Дефиниција 6.3.7. Слаб модел за La A ∫ 1 ∫ 2 (R) је структура AW = (A,XAi ,XA, I1, I2), где је Ik (k = 1,2) позитивна линеарна реална функција дефинисана на скупу термова са највише једном слободном променљивом x и параметрима из A (Ik је A-Данијелов интеграл). У слабом моделу, дефинисаћемо интерпретацију τAw терма τ индуктивно као за двовероватносне моделе, изузев случаја за терм са интегралом: ∫ i τ(x⃗ ,y )d y AW (a⃗ ) = I i τA W (a⃗ ,y )  , i = 1,2. Дефиниција 6.3.8. Средњи модел за La A ∫ 1 ∫ 2 (R) је структура Am = (A,XAi ,XA, I1, I2) која је слаб модел такав да Радон-Никодимова аксиома важи униформно за сваки терм τ, тј. по- стоји k тако да за сваки τ(x⃗ ,y ) и a⃗ ∈ A важи I1τAW (a⃗ ,y )= I2τAW (a⃗ ,y ) · [X (y )↾k ]AW . Ове моделе ћемо користити и у доказу теореме комплетности за логику La AE1E2 . 62 6. Логике са операторима условног очекивања 6.3.2. Логика La AE1E2 Логика La AE1E2 је настала додавањем два оператора условног очекивања E1 и E2 ло- гици La A ∫ 1 ∫ 2 (R). Дефиниција 6.3.9. Структура са условним очекивањем за језик L је пар (A,F), где је A двовероватносна структура са случајним променљивим и F је σ-алгебра подскупова од A таквих да је F⊆ dom(µ1)∩dom(µ2). Оператори условног очекивања E1[· | ·] и E2[· | ·] су детерминисани на следећи начин: ако је Y : A→ R случајна променљива, дефинисаћемо Ek [Y |F] као условно очекивање од Y на σ-алгебри F у односу на меру µk , k = 1,2. Дефиниција 6.3.10. Скуп термова логике La AE1E2 је дефинисан истим правилима за гра- ђење термова као у логици La A ∫ 1 ∫ 2 (R), уз додатак правила са оператором условног очеки- вања: (v i ) ако је τ(x⃗ ,y ) терм, где y није у x⃗ и z је променљива, онда је E i [τ(x⃗ ,y ) | y ](z ) терм у коме је појављивање променљиве y везано и појављивање променљиве z слободно, за i = 1,2. У даљем раду користићемо скраћеницу E i [τ(x⃗ ,y ) | y ] за E i [τ(x⃗ ,y ) | y ](y ), па је према томе, y слободна променљива у E i [τ(x⃗ ,y ) | y ]. Дефиниција 6.3.11. Интерпретација за логику La AE1E2 у двовероватносној структури са условним очекивањем (A,F) је дефинисана као за логику La A ∫ 1 ∫ 2 (R), са додатим следећим условом: E i [τ(x⃗ ,y ) | y ](z )A(a⃗ ,b ) = E i [τA(a⃗ , ·) |F](b ), за свако a⃗ ∈ An и µi -скоро све b ∈ A, где E i [τA(a⃗ , ·) |F]: A→R представља условно очеки- вање од τA(a⃗ , ·): A→R у односу на F, тј. F-мерљиву функцију g : A→R, такву да важи:∫ B τA(a⃗ , ·)dµi = ∫ B g dµi , за свако B ∈F. Ставимо да је ‖E i [τ(x⃗ ,y ) | y ](z )‖= ‖τ‖. Логика La AE1E2 има све схема аксиоме и правила извођења као и логика La A ∫ 1 ∫ 2 (R), из- узев аксиоме (RN), која је замењена следећим схема аксиомама: (Е1) Ek [τ(x⃗ ,y ) | y ](z ) = Ek [τ(x⃗ ,u ) | u ](z ), где y и u се не појављују у x⃗ ; (Е2) ∫ k Ek [τ(x⃗ ,y ) | y ](y )σ(y )d y = ∫ k Ek [τ(x⃗ ,y ) | y ](y )Ek [σ(y ) | y ](y )d y ; (Е3) E i [τ(x⃗ ,y ) | y ](y ) = E j [E i [τ(x⃗ ,y ) | y ](y ) | y ](y ), i , j = 1,2; (Е4) ∨ k ∧ τ∈D ∫ 1 E1[τ(x⃗ ,y ) | y ](y )d y = ∫ 2 E2[τ(x⃗ ,y ) · [X (y )↾k ] | y ](y )d y , где је D скуп термова са коначно много слободних променљивих и D ∈A . Напомена 6.3.12. Чињеница да су условна очекивања у односу на мере µ1 и µ2 дефини- сана над истом σ-подалгебром F имплицира интересантну релацију између њих и дата је следећом лемом. У почетку истраживања очекивано је да ће лема 6.3.13 бити иско- ришћена у аксиоматизацији логике La AE1E2 . С обзиром да није добијен погодан резултат, аксиома (Е4) је уврштена у систем аксиома. 63 6. Логике са операторима условног очекивања Лема 6.3.13. Нека је S σ-алгебра мерљивих подскупова од A, и µ1 и µ2 су мере на S, такве да важи µ1 ≪ µ2. Ако је F σ-подалгебра од S и Ek [Y | F] је условно очекивање случајне променљиве Y : A→R у односу на меру µk , k = 1,2, онда је E1[Y |F] ·E2[X |F] = E2[Y X |F], где је X Радон-Никодимов извод од µ1 у односу на µ2. Доказ. Најпре, имамо да је ∫ E Y dµ1 = ∫ E Y X dµ2, где E ∈F. Према томе, можемо закључити да је ∫ E E1[Y | F]dµ1 = ∫ E E2[Y X | F]dµ2. Преласком на једну меру можемо елиминисати интеграл на следећи начин. Како је ∫ E E1[Y |F]X dµ2 = ∫ E E2[Y X |F]dµ2 и функција E2[Y X | F] је F-мерљива, док E1[Y | F]X није нужно F-мерљива, закључујемо да важи E2[E1[Y | F] ·X |F] = E2[Y X |F] и будући да је функција E1[X |F] F-мерљива, имамо да је коначно E1[Y |F] ·E2[X |F] = E2[Y X |F] Сада ћемо доказати да је аксиоматизација за La AE1E2 комплетна за Σ1 дефинабилне теорије у односу на класу двовероватносних модела са условним очекивањима, следећи исти концепт који је представљен у претходном поглављу. Теорема 6.3.14 (Теорема сагласности). Свака реченица из La AE1E2 која има двовероватно- сни модел са условним очекивањем је конзистентна. Теорема 6.3.15 (Теорема комплетности за La AE1E2 ). Нека је T скуп реченица логике La AE1E2 који је Σ1 дефинбилан на A и конзистентан са аксиомама од La AE1E2 . Тада, постоји двове- роватносни модел са условним очекивањем за скуп T . Доказ. Нека је L¯ екстензија од L добијена додавањем нових симбола случајних промен- љивих XE i [σ(x⃗ ,y )|y ] за сваки термσ(x⃗ ,y ), i = 1,2. Због једноставнијег записивања, писаћемо X iσ(x⃗ ,y ), уместо XE i [σ(x⃗ ,y )|y ]. Терм τ логике LaAE1E2 може бити транслиран у терм T(τ) логике L¯a A ∫ 1 ∫ 2 (R) на следећи начин: (1) ако је τ атомични терм, онда је T(τ) =τ; (2) ако је τ терм облика E i [σ(x⃗ ,y ) | y ], онда је T(τ) терм [XE i [σ(x⃗ ,y )|y ](x⃗ ,y ) ↾k ], где је k ≥ ‖σ‖; (3) транслација T комутира са интегралним квантификаторима и са сваким функцијским симболом f; (4) ако је τ терм 1(σ(x⃗ ,y )> r ), онда је T(τ) терм 1(T(σ(x⃗ ,y ))> r ). Транслација формуле< логике La AE1E2 у формулу T(<) логике L¯a A ∫ 1 ∫ 2 (R) је дефинисана тако даT комутира са¬ и∧. Нека јеT ∗ теорија која се састоји од свих транслација реченица из T , свих транслација теорема логике La AE1E2 и реченице∫ j |[X iτ(x⃗ )↾k ]− [X iτ(x⃗ )↾l ]|d x⃗ = 0, k , l ≥ ‖τ‖, i , j = 1,2. Закључује се да је теорија T ∗ конзистентна у L¯a A ∫ 1 ∫ 2 (R). Користећи Хенкинову кон- струкцију, добијамо слаб модел са случајним променљивим Aw = (A,XA w ,XA w i ,X 1Aw i ,X 2Aw i , I Aw 1 , I Aw 2 ) 64 6. Логике са операторима условног очекивања за T∗. Нека је = L = L¯ ∪C језик уведен у Хенкиновој конструкцији, где је C скуп нових сим- бола константи иC ∈A. Следићемо идеју М. Рашковића из [46]. Нека јеM језик са четири врсте променљивих: – U ,V,W, . . . променљиве за скупове; – x ,y ,z , . . . променљиве за урелементе; – променљиве r,s , t ,u ,v, . . . за реалне бројеве; и – F,G ,H , . . . променљиве за n-арне реално вредносне функције (које представљају ин- терпретације термова, тј. функције An →R). Релацијски симболи језика су: – ≤ за реалне бројеве; – ϵn (x1, . . . ,xn ,U ), n ≥ 1 (са значењем да је (x1, . . . ,xn )∈U ); – νn+1(x⃗ ,r,F ), n ≥ 0 (са значењем да је F (x1, . . . ,xn ) = r ); – Intk (F,r ), k = 1,2 (са значењем да је Intk (F,r ) акко Ik (F ) = r за F : A◦→R или F : A1→ R); и – Expk (F,G ), k = 1,2 (са значењем да је Expk (F,G ) акко Ek (F ) =G за F : An →R). Бинарни функцијски симболи су +, ·,max,min са уобичајеним значењем. Симболи константи су: – U< за сваку = La A ∫ 1 ∫ 2 (R)-формулу <; – Fτ за сваки = La A ∫ 1 ∫ 2 (R)-терм τ; и – r¯ за сваки реални број r ∈R∩A. Нека је S следећа теорија логикеM A : (1) Аксиоме добре дефинисаности (а) (∀U ) ∧ nr ))∨νn+2(x⃗ ,y ,0,F1(τ(x⃗ ,y )>r )) ∧νn+2(x⃗ ,y ,1,F1(τ(x⃗ ,y )>r ))↔ νn+2(x⃗ ,y ,s ,Fτ(x⃗ ,y ))∧ s > r  ∧νn+2(x⃗ ,y ,0,F1(τ(x⃗ ,y )>r ))↔ νn+2(x⃗ ,y ,s ,Fτ(x⃗ ,y ))∧¬(s > r )i; (3) (∀x⃗ ,y )hνn+2(x⃗ ,y ,r,Fτ)↔ (∃G ,H )(∀z ,s )(ν2(z ,s ,G )↔ νn+2(x⃗ ,z ,s ,Fσ′)) ∧Expk (G ,H )∧ ν2(y ,r,H )i, где је τ транслација терма облика Ek [σ(x⃗ ,y ) | y ], k = 1,2, и σ′ је T(σ). (4) Аксиоме задовољења (а) (∀x⃗ )ϵn (x⃗ ,Uτ≥0)↔ νn+1(x⃗ ,r,Fτ)∧ r ≥ 0; (б) (∀x⃗ )ϵn (x⃗ ,U¬<)↔¬ϵn (x⃗ ,U<); (в) (∀x⃗ )ϵn (x⃗ ,U∧<)↔∧ < ϵn (x⃗ ,U<)  . (5) Аксиоме интегралних оператора (а) (∀F ) ∧ n≥2 ¬(∃x⃗ ,r )νn+1(x⃗ ,r,F )↔ (∃1s ) Intk (F,s ); (б) (∀r ) Intk (Fr ,r ); (в) (∀F,G ,r,s , t ,u )Intk (r · F + s ·G , t )∧ Intk (F,u )∧ Intk (G ,v )→ t = r ·u + s ·v , i = 1,2; (г) (∀F )(∀x )(∃r ≥ 0)ν2(x ,r,F )→ (∃s ≥ 0) Intk (F,s ) . (6) Аксиоме оператора са условним очекивањем (а) (∀x⃗ )(∃F )(∀y ,s )ν2(y ,s ,F )↔ νn+1(x⃗ ,y ,s ,Fτ)→ (∃1G )Expk (F,G ), k = 1,2; (б) (∀F,G ,H ,G1)Expk (F,G )∧Expk (H ,G1)→ (Intk (G ·H ,r )↔ Intk (G ·G1,r )); (в) ∨ k (∀F )(∀G ,H )Exp1(F,G )∧Exp2(F · F[X ↾k ],H )→ (Int1(G ,r )↔ Int2(H ,r )) . (7) Аксиоме за Архимедовско поље и све теореме теорије затвореног поља реалних бро- јева саmin иmax (за реалне бројеве). (8) Аксиоме које су трансформације свих аксиома < логике = La A ∫ 1 ∫ 2 (R) (∀x⃗ )ϵn (x⃗ ,U<) . (9) Аксиоме остваривости свих реченица < из T ∗ (∀x )ϵ1(x ,U<) . Теорија S је Σ1 дефинабилна на A. Нека је S0 допустив подскуп од S (S0 ⊆ S,S0 ∈ A). На основу Барвајзове теореме компактности [4], S има модел B јер S0 има стандардни модел који се може добити трансформацијом слабог модела AW : B= 〈B ,U,F,F,ϵBn ,νBm+1, IntBk ,ExpkB ,≤,+, ·,min,max,XB< ,UBτ ,r 〉 , где је: – B = A; – U⊆ ⋃ n≥1 P(An ); – F⊆ ⋃ n≥0 P(An ×R); – F⊆R је поље; – ϵBn ⊆ An ×U; – νBm+1 ⊆ Am ×F×F; 66 6. Логике са операторима условног очекивања – IntBk : F→F, k = 1,2; – ExpkB ⊆F×F, k = 1,2; – +, ·,min,max: F×F→F,≤⊆F×F; – UB< = {a⃗ ∈ An |AW |=<[a⃗ ]}, U= {UB< |< је формула из = La A ∫ 1 ∫ 2 (R)}; – FBτ =τA W , F= {FBτ |τ је терм из скупа D}. Модел B се може трансформисати у средњи модел Am за T ∗, тако да је: τA m = r акко νBm+1(x⃗ ,r,Fτ); XA m Ek [τ(a⃗ ,y )|y ](b ) = c акко FB(b ) = c ∧ExpkB[Fτ(a⃗ ,y ),F ], за неко F ; I A m k (τ(a⃗ ,y )) = r акко IntBk (Fτ(a⃗ ,y ),r ) за a⃗ ∈ Bn , и k = 1,2. На основу Лебове конструкције Данијеловог интеграла закључујемо да интернални средњи модел са случајним променљивим ∗Am даје вероватносни модел са случајним про- менљивим A= (∗A,XAi ,X 1 A τ ,X 2A τ ,X A,µ1,µ2) за теорију T ∗, где је XAi (a⃗ ) = sup{r | [X i (x⃗ ) ↾r ]∗A(a⃗ )≥ r } и X kAτ , k = 1,2, и XA су дефинисани исто као и XAi . Нека је Fk σ-алгебра на ∗A генерисана скуповима {b ∈ ∗A | X kAτ (a⃗ ,b )≥ r }, где је терм τ облика Ek [σ(x⃗ ,y ) | y ], k = 1,2. Аксиоме за условна очекивања имплицирају да је F1 = F2 = F. На основу аксиоме (E4), прецизније, на основу њене транслације, следи да постоји k ∈ Q+ тако да је ∫ E dµ1 = ∫ E [X (x ) ↾k ]Adµ2, за сваки мерљив скуп E . Из саме конструкције закључујемо да је [X (x ) ↾k ]A ненегативна ограничена функција и зато је µ1 ≪ µ2. Нека је A редукт модела A на L. Користећи ак- сиоме, може се показати индукцијом по сложености термова и формула да реченица < из La AE1E2 важи у A акко T(<) важи у A, па је због тога A модел за T . 67 7. Тополошке логике 7.1. Логика са квантификатором „постоји непребројиво много” Нека је L предикатска логика првог реда са једнакошћу и пребројивом листом сим- бола релација, функција и симбола константи. Језик логике L(Q) настаје додавањем кван- тификатора Qx са значењем „постоји непребројиво много”, језику L. Скуп формула ове логике је најмањи скупΦ који садржи све атомичне формуле из L и има следеће својство: ако је <,ψ∈Φ и y је променљива, онда су и < ∧ψ, ¬<, ∃y<, ∀y < иQy< ∈Φ. Под слабим моделом логике L(Q) подразумевамо пар (A,q ) такав да јеA модел језика првог реда L и q је скуп подскупова универзума A модела A, тј. q ⊆ P(A). Чињеницу да n-торка a 1, . . . ,a n ∈ A задовољава формулу <(v1, . . . ,vn ) у моделу (A,q ) дефинишемо на уобичајен начин индукцијом по сложености формуле <. Уколико је формула обликаQx<, онда важи (A,q ) |=Qvm<[a 1, . . . ,a n ] акко {b ∈ A | (A,q ) |=<[a 1, . . . ,am−1,b ,am+1, . . . ,a n ]} ∈q , где је <(v1, . . . ,vn ) формула из L(Q) иm ≤ n . Индукцијом по сложености формуле < могу се доказати две једноставне леме. Лема 7.1.1. Ако су све слободне променљиве формуле <(v1, . . . ,vn ) међу променљивим vi 1 , . . . ,vim и ако је a i 1 =b i 1 , . . . ,a im =b im , онда (A,q ) |=<[a 1, . . . ,a n ] акко (A,q ) |=<[b1, . . . ,bn ] . Лема 7.1.2. Нека је (A,q ) слаб модел и нека је <(x1, . . . ,xm ,y1, . . . ,yn ) формула на језику L(Q) и нека је ψ формула настала помоћу замене сваке слободне променљиве из y1, . . . ,yn формуле <, константама c1, . . . ,cn . Ако су d 1, . . . ,d n интерпретације за c1, . . . ,cn у моделу A, онда за све a 1, . . . ,am ∈ A важи (A,q ) |=<[a 1, . . . ,am ,d 1, . . . ,d n ] акко (A,q ) |=ψ[a 1, . . . ,am ] . Нека је A модел језика L. Модел A је стандардни модел реченице < уколико важи да је A |= < акко (A,q ) |= <, где је q скуп свих непребројивих подскупова од A. (A |= <[a 1, . . . ,a n ] акко (A,q ) |=<[a 1, . . . ,a n ], за случај када је < формула). Уколико је < формула језика L(Q), чије су слободне променљиве u1, . . . ,un , онда (A,q ) |=< подразумева (A,q ) |=∀u1, . . . ,un<, и A |=< подразумева A |=∀u1, . . . ,un<. Аксиоматски систем логике L(Q) представља проширење аксиоматског система кла- сичног предикатског рачуна следећим схема-аксиомама: A1. ¬Qx (x ≡ y ∨x ≡ z ) ; A2. ∀x (<→ψ)→ (Qx<→Qxψ) ; A3. Qx<(x , . . .)↔Qy<(y , . . .), уколико y није слободно у <, и формула <(y , . . .) је настала заменом сваког слободног појављивања променљиве x променљивом y ; A4. Qy ∃x<→∃xQy< ∨Qx∃y< . 68 7. Тополошке логике Све аксиоме су интуитивно јасне и имају следећа значења: Аксиома A1 је „Сваки скуп кардиналности ≤ 2 је пребројив”, док аксиома A2 говори да сваки скуп који има непребројиви подскуп је и сам непребројив. „Ако је ⋃ x∈X a x непребројив скуп, онда је a x непребројив за неко x ∈X или је скуп X непребројив” је значење аксиоме A4. Лема 7.1.3. Сваки модел A језика L је стандардни модел сваке од наведених аксиома. Примећује се да A |=Qx x ≡ x акко је универзум A непребројив. РеченицаQx x ≡ x није на листи аксиома, тако да су допуштени и пребројиви стандардни модели. Уколико би сеQx x ≡ x уврстила у листу аксиома, дефиниција стандардног модела би морала бити појачана чињеницом да је A непребројив скуп. Такође, није тешко наћи слабе моделе који не задовољавају аксиоме од L(Q). С друге стране, постоје слаби модели који задовољавају аксиоме од L(Q) и разликују се од стан- дардних модела. На пример, ако је q скуп свих бесконачних подскупова од A, онда је (A,q ) слаб модел који задовољава сваку аксиому логике L(Q). Правила извођења су иста као у класичном предикатском рачуну. Многе теореме предикатског рачуна могу бити доказане на сличан начин и у L(Q). Лема 7.1.4. Нека је Σ скуп реченица из L(Q), као и реченица <. Ако је Σ∪ {<} ⊢ ψ, онда Σ ⊢<→ψ. Лема 7.1.5. Нека је Σ максимално конзистентан скуп реченица из L(Q). Тада, за све ре- ченице <,ψ из L(Q) имамо ¬< ∈Σ акко < /∈Σ и < ∧ψ∈Σ акко < ∈Σ и ψ∈Σ . Лема 7.1.6. Ако је L′ екстензија језика L добијена додавањем произвољног скупа симбола константи, онда за било који скуп Σ реченица из L(Q), Σ је конзистентно у L(Q) акко Σ је конзистентно у L′(Q). Следећом лемом су дате неке теореме логике L(Q), које су важне за доказ става пот- пуности. Лема 7.1.7. Следеће формуле су теореме логике L(Q): (i) Qx<→∃x< . (ii) ∃xQy<→Qy ∃x< . (iii) Qx (< ∧ψ)→< ∧Qxψ, где x није слободна променљива у < . (iv) Qx (< ∨ψ)↔Qx< ∨Qxψ . (v) Qx< ∧¬Qxψ→Qx (< ∧¬ψ). Од велике важности за даљи рад са тополошким логикама је управо теорема слабе комплетности, чији ће доказ бити детаљно изложен. Дефиниција 7.1.8. Нека је Γ скуп реченица из L(Q) и C је скуп симбола константи језика L. C је скуп сведока за Γ акко за сваку реченицу облика ∃x<(x ) постоји c ∈C тако да важи Γ ⊢ ∃x<(x )→<(c ). Лема 7.1.9. Уколико је Γ максимално конзистентан скуп реченица из L(Q) и C је скуп сведока за Γ, онда Γ има слаб модел (A,q )такав да је сваки елемент из A интерпретација неког c ∈C . 69 7. Тополошке логике Доказ. Нека је Γ0 скуп свих реченица језика L које припадају скупу Γ. На основу леме 7.1.5, Γ0 је максимално конзистентан скуп реченица језика L, штавише, C је скуп сведока за скуп Γ0. Из логике првог реда имамо да Γ0 има модел A, тако да је сваки елемент из A интерпретација неког c ∈C . Нека је c¯ интерпретација c ∈C , тј. A = {c¯ | c ∈C }. Следећи део доказа је трансформација моделаA у слаб модел (A,q ) скупа Γ. За сваку формулу <(x ) из L(Q) са највише једном слободном променљивом, нека је S< = {c¯ | c ∈C и Γ ⊢<(c )}. Тада, q = {S< | < има највише једну слободну променљиву, рецимо x , и Γ ⊢Qx<}. Очи- гледно, q је скуп подскупова од A. Треба доказати, индукцијом по сложености реченице <, да за све реченице < из L(Q) важи (1) (A,q ) |=< акко Γ ⊢< Ако је < атомична реченица, онда (1) важи јер је < из L. Уколико (1) важи за < и ψ, онда важи и за ¬< и за < ∧ψ, на основу леме 7.1.5. За < облика ∃xψ(x ) еквиваленција (1) се доказује као у логици првог реда [9]. Нека је сада< обликаQxψ(x ) и претпоставља се да (1) важи за све реченицеψ(c ), c ∈ C . Тада, (2) Sψ = {c¯ | Γ ⊢ψ(c )}= {c¯ | (A,q ) |=ψ(c )}, на основу леме 7.1.2. Ако је Γ ⊢ Qxψ, онда Sψ ∈ q на основу дефиниције од q , па је и (A,q ) |=Qxψ на основу (2). Претпоставка да је (A,q ) |=Qxψ повлачи, на основу (2), да Sψ ∈ q . Из дефиниције од q , за сада се може само закључити да постоји формула θ (y ) таква да је Sψ = Sθ и Γ ⊢ Qy θ (y ). Из (2) и леме 7.1.2 добија се да c¯ ∈ Sψ имплицира Γ ⊢ψ(c ), c ∈C , и слично важи и за θ . Одатле следи да је Γ ⊢ψ(c ) акко Γ ⊢ θ (c ) за свако c ∈ C , па важи Γ ⊢ψ(c )↔ θ (c ), за свако c ∈ C . Будући да је C скуп сведока за Γ, важиће Γ ⊢ ∀u ψ(u )↔ θ (u ), где је u променљива која се није појављивала у ψ и θ . На основу аксиоме 2, Γ ⊢Quψ(u )↔ Quθ (u ), а аксиома 3. повлачи Γ ⊢Qxψ(x )↔Quθ (u ) и Γ ⊢Qy θ (y )↔Quθ (u ). Добија се из исказне логике да је Γ ⊢Qxψ(x )↔Qy θ (y ) и како је Γ ⊢Qy θ (y ), следи да важи Γ ⊢Qxψ(x ). На основу (1) следи да је (A,q ) модел скупа реченица Γ. Теорема 7.1.10 (Теорема слабе комплетности). Нека је Σ скуп реченица из L(Q). Σ је кон- зистентно акко Σ има пребројив слаб модел у коме све аксиоме логике L(Q) важе. Доказ. Ток доказа је суштински врло сличан Хенкиновом доказу теореме комплетности за логику првог реда. Нека је Σ конзистентно и нека је L∗ проширење језика L преброји- вим скупом нових симбола константи C . На основу леме 7.1.6, Σ остаје конзистентан у L∗(Q). Хенкиновом методом, Σ може бити проширен до максимално конзистентног скупа Γ реченица из L∗(Q) тако да је C скуп сведока за Γ. На основу претходне леме, Γ има слаб модел (A∗,q ) у коме је сваки елемент интерпретација неког c ∈ C . Пребројивост скупа C повлачи пребројивост од A∗. Како је Γ максимално конзистентан у L∗(Q), све аксиоме из L∗(Q) припадају скупу Γ и зато важе у моделу (A∗,q ). Ако је A редукт од A∗ на L, онда је (A,q ) пребројиви слаб модел од Σ који задовољава све аксиоме из L(Q). 70 7. Тополошке логике Доказ другог смера се добија из чињенице да ако је Σ ⊢< и (A,q ) је слаб модел за Σ, онда је и (A,q ) |=<. Напомена 7.1.11. 1) Претходни резултат такође важи и за непребројиви језик L са једином разликом што се реч „пребројив” у теореми 7.1.10 брише. 2) Горњи резултат би се могао добити уколико се аксиома A2 замени аксиомом ∀x <(x )↔ ψ(x )→ Qx<(x )↔Qxψ(x ), која ће бити уврштена у листу аксиома тополо- шких логика из нашег даљег проучавања. 3) У досадашњем доказу коришћене су само аксиоме A2 и A3. Стандардни модел за конзистентан скуп реченица Σ је конструисан као унија еле- ментарног ланцаω1 слабих модела [29]. Ако је (A,q ) слаб модел за Σ, циљ је да се скупови из q „увећају” до непребројивих скупова коришћењем елементарних ланаца. Следећа лема је кључна у доказу комплетности. Лема 7.1.12. Нека је (A,q ) пребројиви слаб модел у коме све аксиоме логике L(Q) важе и нека је L∗ језик моделаA∗, настао додавањем нових симбола константи ca , за свако a ∈ A, језику L. Формула <(x ) је формула из L∗(Q)таква да важи (A∗,q ) |=Qx<(x ). Тада постоји пребројива елементарна екстензија (B,r ) од (A,q ) тако да важи: (i) за неко b ∈ B \A, (B∗,r ) |=<[b ] . (ii) за сваку формулу ψ(y ) из L∗(Q) такву да је (A∗,q ) |= ¬Qyψ(y ) важи {a ∈ B | (B∗,r ) |= ψ[a ]} ⊂ A . Пребројивим понављањем претходне леме и коришћењем методе елементарних ла- наца добија се исти резултат који важи сада за сваку формулу <(x ) из L∗(Q). Лема 7.1.13. Нека је (A,q ) пребројив слаб модел у коме све аксиоме из L(Q) важе и нека је L∗ језик модела A∗ дефинисан као у претходној леми. Тада, (A,q ) има пребројиву елемен- тарну екстензију (B,r ) такву да је за све формуле <(x ) из L∗(Q): (A∗,q ) |=Qx<(x ) акко постоји b ∈ B \A тако да је (B∗,r ) |=<[b ]. На крају, ако је (A0,q0) пребројиви слаб модел заΣ, применом последње лемеω1 пута добија се елементарни ланац (Aα,qα), α<ω1, пребројивих слабих модела, унија добијеног ланца ће бити стандардни модел за Σ. Последица 7.1.14 (Теорема компактности). Нека је Σ скуп реченица из L(Q). Ако сваки коначан подскуп од Σ има стандардни модел, онда Σ има стандардни модел. Лако се уочава да комплетност и компактност не важе за L(Q) уколико L има не- пребројиво много симбола константи, посматрајући скуп Σ = ¬QxP(x ) ∪ P(cα) | α < ω1 ∪ ¬cα ≡ cβ |α<β <ω1 . КвантификаторQx се може интерпретирати на различите начине, о чему говори сле- дећи низ последица слабе комплетности за логику L(Q). Претпоставка да је језик L пре- бројив може бити одбачена. Теорема 7.1.15. Следеће чињенице су еквивалентне: (i) Σ је конзистентно у односу на аксиому A3 и схема аксиому ∀x (<↔ψ)→ Qx<↔ Qxψ  ; (ii) Σ има слаб модел. Теорема 7.1.16. Следеће чињенице су еквивалентне: (i) Σ је конзистентно у односу на аксиоме A2 и A3 и схема аксиомуQx (< ∧ψ)↔Qx< ∧ Qxψ; 71 7. Тополошке логике (ii) Σ има слаб модел (A,q ) такав да је q филтер на скупу A. 7.2. Тополошки простори Концепт метричког простора, као скупа за чија је свака два елемента одређено ра- стојање, уведен је почетком 20. века као природна генерализација разних простора који су до тада проучавани у математичкој анализи. Обједињујући резултате класичне анализе везане за непрекидност, конвергенцију и разне особине простора, теорија метричких про- стора је убрзала даљи развој математичке анализе ка функционалној анализи у којој тачке простора нису више само бројеви или уређене n-торке бројева. Заснивање теорије топо- лошких простора долази као природна последица развоја функционалне анализе, тј. ја- вила се потреба да се уместо метричких посматрају још апстрактнији простори; данас представља најопштији оквир у коме се изучавају непрекидност и сродни појмови. Дефиниција 7.2.1. Колекција O подскупова неког непразног скупа X је колекција отво- рених скупова, или топологија, ако и само ако важе следећа три услова: (O1) ∅, X ∈O ; (O2) акоU ,V ∈O онда иU ∩V ∈O ; (O3) за сваку фамилију {Ui | i ∈ I } ⊆O, важи⋃i∈IUi ∈O . Тополошки простор је пар (X ,O). Елементе колекције O називамо отвореним скуповима. Затворени скупови су ком- плементи отворених. Теорема 7.2.2. Колекција C свих затворених скупова неког тополошког простора (X ,O) задовољава следеће услове: (C1) ∅, X ∈C , ; (C2) ако F,H ∈C онда и F ∪H ∈C ; (C3) за сваку фамилију {Fi | i ∈ I } ⊆C, важи⋂i∈I Fi ∈C . Тополошка структура на неком скупу X може се дефинисати тако што се прво зада колекција C подскупова од X која задовољава услове (C1), (C2), (C3) и чије елементе зовемо затворени скупови, а онда се отворени скупови дефинишу као комплементи затворених. Теорема 7.2.3. Дати су тополошки простори X1 = (X ,O), колекција отворених скупова O на X и X2 = (X ,C), колекцијом C затворених скупова на X . Ако за сваки U ∈ O и сваки F ∈ C важиU \ F ∈O и F \U ∈ C, тада је O колекција отворених скупова простора X2, а C колекција затворених скупова простора X1. Према претходној теореми, тополошки простор се може дефинисати и као тројка (X ,O,C), тако да колекција O задовољава услове (O1), (O2), (O3) за отворене скупове, а C услове (C1), (C2), (C3) за затворене скупове, уз додатни услов ако U ∈O и F ∈C, тада U \ F ∈O и F \U ∈C . Дефиниција 7.2.4. Нека је (X ,O) тополошки простор. Скуп A ⊂ X је околина тачке x ∈ X акко постоји отворен скупO ∈O такав да је x ∈O ⊂ A. Чињеница да је скуп отворен може да се изрази помоћу појма околине тачке, о чему говори следећа теорема. 72 7. Тополошке логике Теорема 7.2.5. Нека је (X ,O) тополошки простор. Тада важи: скуп A ⊂ X је отворен акко је околина сваке своје тачке. Дефиниција 7.2.6. Нека су (X ,Ox ) и (Y ,Oy ) тополошки простори и x0 ∈ X произвољна тачка. Функција f : X → Y је – непрекидна у тачки x0 акко за сваку околину V тачке f (x0) постоји околинаU тачке x0 тако да је f [U ]⊂V ; – непрекидна акко је непрекидна у свакој тачки x ∈X . Услов непрекидности функције може да се искаже и коришћењем појмова отвореног и затвореног скупа. Теорема 7.2.7. Нека су (X ,Ox ) и (Y ,Oy ) тополошки простори и f : X → Y произвољно пресликавање . Тада су следећи услови еквивалентни: (i) Пресликавање f је непрекидно . (ii) За сваки отворен скупO ⊆ Y , скуп f −1[O]⊆X је отворен . (iii) За сваки затворен скуп F ⊆ Y , скуп f −1[F ]⊆X је затворен . Дефиниција 7.2.8. Нека је (X ,O) тополошки простор. 1) Фамилија B⊆P(X ) је база топо- логије O акко важе следећи услови: (B1) Елементи колекције B су oтворени скупови, тј. B⊆O; (B2) Сваки отворен скупO ∈O може да се прикаже као унија неке подфамилије фамилије B. 2) Колекција P⊆P(X ) је подбаза топологије O акко важе следећи услови: (PB1) Елементи колекције P су отворени скупови, тј. P⊆O; (PB2) Фамилија свих коначних пресека елемената P представља неку базу топологије O. Производ тополошких простора се уводи на основу следеће једноставне теореме. Теорема 7.2.9. Нека је I непразан скуп, а  (X i ,Oi ) | i ∈ I фамилијатополошких простора. Тада важи: a1) Колекција P свих подскупова скупа ∏ X i облика u¯ −1i [Oi ], где је i ∈ I произвољан ин- декс, аOi ∈Oi отворен скуп у простору X i , је подбаза неке топологије на скупу∏X i . Означимо ту топологију са O. a2) Фамилија свих коначних пресека елемената колекције P B= ⋂ i∈K u¯ −1i [Oi ] | K ⊆ I ∧ |K |<ℵ0 ∧ (∀i ∈ K )Oi ∈Oi  је база топологије O. (За j ∈ I , пресликавање u¯ j :∏i∈I X i → X j дато са u¯ j (x i | i ∈ I ) = x j је пројекција производа на простор X j .) Дефиниција 7.2.10. Топологију O на скупу ∏ X i уведену у претходној теореми зовемо топологија Тихонова. За простор ( ∏ X i ,O) кажемо да је производ фамилије простора (X i ,Oi ) | i ∈ I . 7.3. Топологије на класама Код дефинисања многих појмова везаних за класа-просторе, није могуће пренети на једноставан начин дефиниције и конструкције одговарајућих појмова из класичне топо- логије. Главни разлог је одсуство операције комплементирања. Овај проблем у многим 73 7. Тополошке логике случајевима може бити отклоњен дефинисањем посебно класе отворених скупова и по- себно класе затворених скупова. Слично се може извести и на стандардним тополошким просторима (теорема 7.2.3). У овом одељку ћемо великим појачаним словима: X,Y,Z, . . . означавати класе, а обичним (малим и великим словима): x ,y ,z , . . . ,X ,Y ,Z , . . . скупове. Користићемо и стан- дардне ознаке: V за класу свих скупова, ORD за класу свих ординала, CARD за класу свих кардинала итд. Метатеорија на којој ће бити засновано излагање у овом одељку јеNBG те- орија скупова у којој се разматрају класе, а која је заправо екстензија ZF теорије скупова. Мијајловић и Ћирић у [11], [12] уводе појам тополошке структуре на правим класама сле- дећом дефиницијом. Дефиниција 7.3.1. Нека су X, T и C класе. Тројка (X,T,C) је тополошки класа-простор акко важе следећи услови: (KT1) ако u ,v ∈T, онда и u ∩v ∈T; (KT2) за сваки скуп i и сваку фамилију {u j | j ∈ i }, ако за сваки j ∈ i , u j ∈ T онда и⋃ j∈i u j ∈T; (KT3) за сваки x ∈X постоји u ∈T, такав да је x ∈ u ; (KT4) ако u ∈T и a ∈C, онда u \a ∈T; (KC1) ако a ,b ∈C, онда a ∪b ∈C; (KC2) за сваки скуп i и сваку фамилију {a j | j ∈ i }, ако за сваки j ∈ i , a j ∈ C онда и⋂ j∈i a j ∈C; (KC3) за сваки скуп x , такав да је x ⊂X, постоји a ∈C, такав да је x ⊆ a ; (KC4) ако u ∈T и a ∈C, онда и a \u ∈C. Примери: 1) Дискретан класа-простор на V: (V,V,V). 2) За сваки ординал α, нека је τα скуп свих отворених, аσα свих затворених подскупова од α у односу на топологију уређења на α. Како је за α<β , τα ⊆ τβ и σα ⊆σβ , лако се види да је за T= ⋃ α∈ORDτα и C= ⋃ α∈ORDσα, (ORD,T,C) тополошки класа-простор. Тополошки класа-простор на класи CARD, дефинише се потпуно аналогно. 3) Нека је на скупу x дефинисан обичан тополошки простор, у коме је τx колекција свих отворених, а σx колекција свих затворених скупова. За произвољну класу X, нека је T = {u | u ⊆ X, x ∩ u ∈ τx } и C = {a | a ⊆ X, x ∩ a ∈ σx }. Тада је (X,T,C) тополошки класа-простор. С друге стране, може се доказати да је, за сваки тополошки класа-простор (X,T,C) и сваки скуп x ∈ X, (x ,T ↾x ,C ↾x ), обичан тополошки простор, при чему је T ↾x= {y ∩x | y ∈T} и C ↾x= {y ∩x | y ∈C}; важи и T=⋃x∈XT ↾x , C=⋃x∈XC ↾x . Следећи резултати су од значаја за рад са тополошким логикама који ће бити изложен у наредном одељку. Теорема 7.3.2. Нека је K права класа и  и  су класе подскупова од K тако да је (1) ∀x ∈K ∃s ∈ x ∈ s . (2) За сваки подскупm ⊆K постоји f ∈ тако да јеm ⊆ f . (3) ∀s ∈∀ f ∈ (s − f ∈∧ f − s ∈) . Онда постоји најмања класа-топологија (K,τ(),σ())тако да важи ⊆τ() и ⊆σ(). Теорема 7.3.3. Нека је (X,T,C) класа-простор и f ⊆ X. Тада, f је затворен акко (∀y /∈ f ) (∃v ∈T) (y ∈ v ∧v ∩ f =∅). 74 7. Тополошке логике Напоменимо да ако су X и Y класе, пресликавање из X у Y је свака класа F ⊆ X×Y тако да важи ∀x ∈X ∃1y ∈Y (x ,y )∈F. Дефиниција 7.3.4. Нека су X и Y класа-простори. Пресликавање F: X→Y је непрекидно акко је рестрикција F ↾ u за свако u ∈TX непрекидна функција. Теорема 7.3.5. Нека су X и Y класа простори и F: X→ Y пресликавање. Следећи услови су еквивалентни: (1) F је непрекидно . (2) За све u ∈TX и све w ∈TY , u ∩F−1(w )∈TX . (3) За све v ∈CX и све w ∈CY , v ∩F−1(w )∈CX . Производ два класа-простораXi = (Xi ,Ti ,Ci ), 1≤ i ≤ 2, је класа-просторX= (X,T,C), где је X=X1 × X2 и основе за T и C су класе T0 = u¯ −11 (u ) ∩ u¯ −12 (v ) | u ∈ T1,v ∈ T2 , C0 =  u¯ −11 (u ) ∩ u¯ −12 (v ) | u ∈ C1,v ∈ C2 . Овде су u¯1 и u¯2 су пројекције из K у K1 и K2 респективно. Класе T0 и C0 очигледно не задовољавају услове теореме 7.3.2, зато нека је T′ класа свих коначних унија елемената класе T0, и C′ нека је класа свих коначних унија елеме- ната класе C0. (Лако се уочава да су класе T′ и C′ затворене и за коначне пресеке). Очи- гледно је T0 ⊆ T′ и C0 ⊆ C′ и класе T′ и C′ задовољавају услове теореме 7.3.2, па тада постоји најмањи класа простор (X,T,C) такав да је T′ ⊆ T и C′ ⊆ C. Није тешко ви- дети да је класа T = {∪x | x је конaчан пресек елемената из T′} управо класа отворених скупова T из горње „дефиниције” производа класа простора. Слично, класа C = {∩x | x је конaчна унија елемената из C′} је класа затворених скупова C. Све у свему, може се закључити да је сваки отворен скуп O ∈ T униjа скупова облика O1 ×O2 где је O1 ∈ T1 и O2 ∈ T2 и ова чињеница је од великог значаја за конструкцију аксиоматског система наше логике која ће бити изложена у наредном одељку. (Класe T′ и C′ иначе образују базу класа простора (X,T,C), видети дефиницију базе у [12]). 7.4. Тополошка логика L(O) Све тополошке логике које ће бити изложене у наредним одељцима су утемељене на Сгроовој логици L(O) [50], која је доста слична логици L(Q) са уопштеним квантификато- ром „постоји непребројиво много”. Скуп формула логике L(O) генерисан је као у логици L(Q), с једином разликомшто сада квантификаторOx игра улогу квантификатораQx ; слаб модел (A,q ) је дефинисан на исти начин. Слаб модел (A,q ) језика L(O) је тополошки уко- лико је q топологија на A. Интерпретација формуле Ox < у тополошкој структури (A,q ) за валуацију ν : Var→ A дефинисана је тако да: (A,q ) |=Ox <[ν ] акко b ∈A | (A,q ) |=<[ν (b | x )] ∈q . Аксиоматски систем у односу на који је доказана комплетност је дат као проширење аксиоматског система класичног предикатског рачуна следећим схема аксиомама: (A0) Ox<(x )↔Oy<(y ); (A1) ∀x (<↔ψ)→ (Ox<↔Oxψ); (A2) Ox x = x ,Ox x ̸= x ; (A3) Ox< ∧Oxψ→Ox (< ∧ψ); (A4) ∀y Ox<→Ox∃y <; 75 7. Тополошке логике Пре самог доказа потпуности треба истаћи да је доказ базиран на једноставном твр- ђењу, које гласи: ако је Y ⊆ X и Y није отворен скуп простора (X ,τ), тада постоји тачка a ∈ Y таква да за сваки отворен скупU ⊆ Y имамо да a /∈U . На основу слабе комплетно- сти логике L(Q) закључује се да сваки конзистентан скуп реченица у L(O) има слаб модел (A,q ) у коме важе све аксиоме логике L(O) (видети напомену 7.1.11 и теорему 7.1.15). Теорема 7.4.1. Нека је T теорија у L(O). Тада, T је конзистентно у L(O) акко T има тополошки модел. Доказ. Уколико T има тополошки модел (A,q ), онда је T конзистентно у L(O), будући да све аксиоме (A0)-(A4) важе у сваком тополошком простору. Претпоставимо да је T конзистентно у L(O). Конструкција тополошког модела је следећи задатак. За свакуформулу<(x ,y1, . . . ,yn ) логике L(O) додаје се нови симболфункције f <(y1, . . . ,yn ) и за било коју дату формулу ψ(x ,z 1, . . . ,zm ) нека ψ< буде следећа формула ∀y1, . . . ,yn ,z 1, . . . ,zm  Oxψ(x ,z 1, . . . ,zm )∧¬Ox<(x ,y1, . . . ,yn )∧ ∧∀x ψ(x ,z 1, . . . ,zm )→<(x ,y1, . . . ,yn )→ →< f <(y1, . . . ,yn ),y1, . . . ,yn∧¬ψ f <(y1, . . . ,yn ),z 1, . . . ,z n. Ово значи да, ако < дефинише скуп који није отворен, онда f < одређује тачку из тог скупа која није ни у једном подскупу од < који је дефинабилан помоћу ψ. Нека је L′ = L ∪ { f < | < ∈ L(O)}. Треба показати да је T ′ = T ∪ {ψ< | <,ψ ∈ L(O)} конзистентан у L′(O). Довољно ће бити да се покаже да је сваки коначан подскуп конзистентан. Нека јеψ