0-1 lait äärellisissä malleissa

PRO GRADU -TUTKIELMA

Satu Vahtera

0–1 lait äärellisissä malleissa

TAMPEREEN YLIOPISTO Informaatiotieteiden yksikkö

Matematiikka Tammikuu 2012

Tampereen yliopisto

Informaatiotieteiden yksikkö

VAHTERA, SATU: 0–1 lait äärellisissä malleissa Pro gradu -tutkielma, 33 s.

Matematiikka Tammikuu 2012

Tiivistelmä

Äärellisten mallien teoria on tietotekniikan kehityksen tarpeiden seuraukse- na kasvanut matemaattisen logiikan osa-alue. Teorian ensimmäisiä tuloksia oli Trakhtenbrotin tulos vuodelta 1950, jonka mukaan validius äärellisissä malleis- sa ei ole rekursiivisesti numeroituva. Nykyisin äärellisten mallien logiikat ovat usein perusta tietokantakyselyiden luomiseen ja äärellisten mallien teorian tek- niikoiden avulla todistetaan hakujärjestelmien ilmaisuvoimaa ja monimuotoi- suutta.

Äärellisissä malleissa, kuten suuntaamattomissa äärellisissä verkoissa, voi- daan tutkia tietyn ominaisuuden toteutuvuuden todennäköisyyttä. Kun verkon solmujen määrä lähenee ääretöntä, saadaan ominaisuudelle asymptoottinen to- dennäköisyys. Matemaattisessa logiikassa hyvin mielenkiintoinen ilmiö on 0–1 lait, jotka käsittelevät ominaisuuksien asymptoottista todennäköisyyttä eri lo- giikoissa. Jos logiikalla on 0–1 laki, kaikkien siinä määriteltävien ominaisuuk- sien asymptoottinen todennäköisyys on 0 tai 1. Tässä tutkielmassa esitellään muutamia logiikoita ja tutkitaan onko niillä 0–1 laki.

Työssä tutustutaan aluksi verkkojen ominaisuuksiin ja määritellään kiin- topisteen käsite, sekä muutama kiintopistelogiikka. Kiintopistelogiikoiden kä- sittelyä jatketaan määrittelemällä rajoitetun muuttujamäärän logiikat. Ehren- feucht-Fraïssén peleistä esitellään helmipelit, joiden avulla saadaan todistettua tärkeitä tuloksia liittyen asymptoottisiin todennäköisyyksiin ja kyselyihin eri logiikoissa. Työn lopussa määritellään vielä laajennusaksioomat, jotka ovat tar- peellinen apuväline 0–1 lain todistamisessa.

Viitekirjoina työssä ovat Libkin, Leonid: Elements of Finite Model Theory ja Ebbinghaus, Heinz-Dieter & Flum, Jorg: Finite Model Theory.

Asiasanat: satunnaisverkko, asymptoottinen todennäköisyys, laajennusaksioo- ma

Sisältö

Johdanto . . . 7

1 Valmistelevia tarkasteluja 8 1.1 Verkot . . . 9

1.2 Kiintopistelogiikat . . . 9

1.3 Rajoitetun muuttujamäärän logiikat . . . 14

1.4 Helmipelit . . . 16

2 Asymptoottinen todennäköisyys ja laajennusaksioomat 23 2.1 Asymptoottinen todennäköisyys . . . 23

2.2 Laajennusaksioomat . . . 25

3 0–1 lait 29 3.1 0–1 lakeja eri logiikoille . . . 29

3.2 Satunnaisverkko . . . 30

Lähdeluettelo 33

Johdanto

Tässä työssä käsitellään äärellisiä malleja ja eri logiikoita, sekä niiden ilmaisu- voimaa. Jos sen sijaan, että mietimme kaavan totuusarvon ratkeavuutta kai- kissa äärellisissä malleissa, mietimme onko se tosi lähes kaikissa äärellisissä malleissa, saamme lisättyä logiikan ilmaisuvoimaa. Jotkin ominaisuudet voivat olla ratkeamattomia niiden totuusarvon suhteen kaikissa logiikan äärellisissä malleissa, mutta voidaan todistaa ominaisuuden olevan esimerkiksi tosi lähes kaikissa logiikan äärellisissä malleissa. Tähän mielenkiintoiseen tulokseen pää- dytään tutustumalla ominaisuuksien asymptoottiseen todennäköisyyteen. Lu- kijan oletetaan hallitsevan melko laajat logiikan perustiedot. Usein tutkittavia äärellisiä malleja ovat äärelliset verkot, äärelliset merkkijonot ja muut äärelli- set relationaaliset mallit. Tässä työssä käsittelemme aiheita suuntaamattomien äärellisten verkkojen avulla.

Ensimmäisessä luvussa käydään läpi työn kannalta tärkeitä taustatietoja.

Aluksi määritellään verkko ja siihen liittyvät työn kannalta olennaiset ominai- suudet. Seuraavaksi määritellään kiintopiste, sekä siihen liittyvät kiintopiste- logiikat, jotka ovat keskeisessä asemassa tutkielmassa. Kiintopistelogiikoiden avulla saadaan määriteltyä rajoitetun muuttujamäärän logiikat, joista on apua tutkielman kannalta tärkeiden tulosten todistamisessa. Ensimmäisen luvun lo- pussa esitellään vielä helmipelit, joka on eräs Ehrenfeucht-Fraïssén pelien muo- to.

Työn toinen ja kolmas luku käsittelee äärellisiä malleja ja aiemmin määri- teltyjä logiikoita, tutkien millä todennäköisyydellä tietty ominaisuus mallissa toteutuu. Laajemmin, millä asymptoottisella todennäköisyydellä tietty omi- naisuus toteutuu logiikan äärellisissä malleissa. Luvussa kaksi määriteltävien laajennusaksioomien avulla tutkielmassa todistetaan luvussa kolme, onko tut- kielmassa esiin tuoduilla logiikoilla 0–1 laki. Kolmannen luvun lopussa määri- tellään vielä satunnaisverkko, jolla on mielenkiintoinen yhteys asymptoottiseen todennäköisyyteen.

1 Valmistelevia tarkasteluja

Määrittelemme aluksi aakkoston σ ensimmäisen kertaluvun logiikan termit ja kaavat seuraavasti:

• Jokainen muuttuja x on termi.

• Jokainen vakiosymboli c on termi.

• Jos t₀, . . . , tk−1 ovat termejä ja f on k-paikkainen funktiosymboli, niin f(t₀, . . . , tk−1) on termi.

• Jos t₀, t₁ ovat termejä, niin t₀ =t₁ on kaava.

• Jos t₀, . . . , tk−1 ovat termejä ja P on k-paikkainen relaatiosymboli, niin P(t₀, . . . , t_k−1) on kaava.

• Jos ϕ₀, ϕ₁ ovat kaavoja, niinϕ₀∧ϕ₁, ϕ₀∨ϕ₁ ja ¬ϕ₀ ovat kaavoja.

• Jos ϕon kaava, niin ∃xϕ ja ∀xϕ ovat kaavoja.

Käytämme yleiseen tapaan kaavasta ¬ϕ∨ψ lyhennemerkintää ϕ → ψ ja kaavasta (ϕ→ψ)∧(ψ →ϕ) lyhennemerkintää ϕ↔ψ.

Ensimmäisen kertaluvun logiikka FO = L_ωω on pienin logiikka, joka sisäl- tää atomikaavat ja on suljettu negaation (¬), konjunktion (∧) ja eksistenssi- kvantifionnin (∃) suhteen. Käsittelemme myöhemmin ensimmäisen kertaluvun logiikan, sekä sen laajennuksien ominaisuuksia. Tutkittavissa äärellisissä mal- leissa aakkosto on aina relationaalinen, eli aakkosto ei sisällä funktiosymboleita.

Kun σ on relationaalinen aakkosto, merkitsemme kaikkien äärellisten σ- mallien joukkoa STRUCT[σ].

Teoria on aakkoston σ lauseiden joukko. Löwenheimin ja Skolemin lause sanoo, että jos teorialla T on ääretön malli, sillä on myös numeroituva malli.

Tähän lauseeseen viitataan sivulla 31 teorianEAtäydellisyyden todistuksessa.

Trakhtenbrotin lause sanoo, että jokainen relationaalinen aakkostoσ, jossa on ainakin yksi kaksipaikkainen relaatiosymboli, on ratkeamaton sen ongelman suhteen onko aakkoston σ kaavalle Φ olemassa sellaista äärellistä mallia A ∈ STRUCT[σ], ettäAΦ. Tähän tulokseen viitataan sivulla 12 operaattorinF_ϕ monotonisuus-ongelman ratkeamattomuuden todistuksessa. Lauseen todistus löytyy kirjasta Elements of Finite Model Theory.

Olkoon σ aakkosto, jossa ei ole funktiosymboleita. Aakkoston σ mallien A ja Bvälinenhomomorfismi on sellainen kuvaush:A→B, että jokaiselle aak- kostonσvakiolle päteeh(c^A) = c^Bja jokaisellek-paikkaiselle relaatiosymbolille

R ja jonolle (a₀, . . . , ak−1)∈R^Apätee, että jono (h(a₀), . . . , h(ak−1)) kuuluu re- laatioonR^B. Merkitäänh(R^A) = {(h(x₀), . . . , h(xk−1))∈R^B |(x₀, . . . , xk−1)∈ R^A}. Bijektiivista homomorfismia h, jonka käänteiskuvaus on myös homomor- fismi, kutsutaan isomorfismiksi. Jos kahden mallin, A ja B, välillä on isomor- fismi, kutsumme malleja isomorfisiksi ja merkitsemme A∼=B.

σ-malleissam-paikkainenkysely on sellainen kuvausQ, joka yhdistää jokai- seen malliin A universumin A^m osajoukon niin, että jos A ∼=B isomorfismilla h : A →B, niin Q(B) =h(Q(A)). Sanomme, että kysely Q on määriteltävis- sä logiikassa Ljos on olemassa logiikanL kaava ϕ(x₀, . . . , x_m−1) aakkostollaσ siten, että jokaisella A

Q(A) ={(a₀, . . . , am−1)∈A^m |Aϕ(a₀, . . . , am−1)}.

1.1 Verkot

Verkko muodostuu joukosta objekteja, jossa jotkin objektiparit voivat olla yh- distetty toisiinsa. Kutsumme verkon G objekteja solmuiksi ja kahta solmua, u ja v, yhdistävää väylää särmäksi, (u, v) ∈ E^G. Käsittelemme suuntaamat- tomia verkkoja, joissa ei ole väliä särmän yhdistämien solmujen järjestyksellä.

Verkko G on siis järjestetty pari G = (V, E^G), missä V on joukko solmuja ja E^G ⊆ V² joukko särmiä. Verkon relaatio E^G on symmetrinen. Yksinkertai- nen verkko on suuntaamaton verkko, jossa ei ole särmiä solmusta itseensä, eikä enempää kuin yksi särmä kahden solmun välillä. Äärellinen verkko on sellai- nen verkko G = (V, E^G), jossa joukot V ja E^G ovat äärelliset. Äärettömässä verkossa solmuja tai solmuja ja särmiä on ääretön määrä. Tässä tutkielmassa keskitymme käsittelemään yksinkertaisia äärellisiä verkkoja.

Olkoot s,a₀, a₁, a₂, . . . , a_n−1, a_n ja u verkonG solmuja. Sanomme, että sol- musta s solmuun ukulkee polku, jos (s, a₀),(a₀, a₁),(a₁, a₂), . . . ,(an−1, a_n), (a_n, u)∈ E^G. Siispä jono solmujen välisiä särmiä muodostaa polun. Yksinker- tainen polku ei kulje saman solmun kautta kahdesti. Silmukka on yksinkertai- nen polku, jonka alku- ja loppusolmut ovat samat. Suuntaamattomassa verkos- sa kahden solmun sanotaan olevan yhdistetyt, jos niiden välillä on polku. Yhte- näisessä verkossa jokaisesta solmusta on polku kaikkiin muihin solmuihin. Ku- viossa 1.1 on yhtenäinen verkko G₁ = ({1,2,3,4,5},{(1,2),(1,5),(2,4),(2,5), (3,4)}). Täydellisessä verkossa jokaisen solmuparin välissä on särmä. Kuvios- sa 1.2 on täydellinen verkkoG₂ = ({a, b, c, d, e},{(a, b),(a, c),(a, d),(a, e),(b, c), (b, d),(b, e),(c, d),(c, e),(d, e)}).

1.2 Kiintopistelogiikat

Olkoonf :A →Afunktio. Kiintopiste on sellainenx∈A, jolle päteef(x) = x.

Graafisesti reaalilukuarvoisen funktion kiintopisteet (x, f(x)) sijaitsevat yhtä- lön f(x) =x kuvaajalla, suoralla. Esimerkiksi funktion f :R→R

f(x) =x³+ 2x−10

Kuvio 1.1.Yhtenäi- nen verkkoG1

Kuvio 1.2.Täydelli- nen verkkoG2

Kuvio 1.3. Funktioiden f(x) = x³ + 2x−10 ja f(x) = x kuvaajat ja kiintopiste (2,2)

yksi kiintopiste on luku 2, koska f(2) = 2³+ 2·2−10 = 2 (kuvio 1.3).

JoukonS potenssijoukko,℘(S), on joukonS kaikkien osajoukkojen joukko, johon kuuluvat myös tyhjä joukko ja joukko S itse.

Ensimmäisen kertaluvun logiikan lausein ei pystytä määrittelemään joita- kin laskennallisesti tärkeitä verkon ominaisuuksia, kuten verkon yhtenäisyyttä.

Logiikan FO ilmaisuvoiman riittämättömyys johtuu siitä, että sillä ei voi ilmais- ta kiintopisteitä. Käsittelemme seuraavaksi sellaisia logiikan FO laajennuksia, joilla pystymme ilmaisemaan kiintopisteongelmia.

Otetaan mielivaltainen joukko U. Joukon U operaattori on kuvaus F :

℘(U)→℘(U). Kutsumme operaattoriaF monotoniseksi jos X ⊆Y ⇒F(X)⊆F(Y)

ja inflatoriseksi jos

X ⊆F(X)

kaikilla X ∈℘(U).

Määritelmä 1.2.1. Olkoon operaattori F : ℘(U) → ℘(U). Joukko X ⊆ U on operaattorin F kiintopiste jos F(X) = X. Joukko X ⊆ U on operaattorin F pienin kiintopiste jos se on kiintopiste ja jos jokaiselle muulle operaatto- rin F kiintopisteelle Y pätee X ⊆ Y. Merkitsemme operaattorin F pienintä kiintopistettä lfp(F)

Lause 1.2.1 (Tarskin ja Knasterin lause). Jokaisella monotonisella operaatto- rilla F : ℘(U) → ℘(U) on pienin kiintopiste, lfp(F), joka voidaan määritellä seuraavasti

lfp(F) = ^\{Y |Y =F(Y)}.

Todistus. Olkoon W = {Y | F(Y) ⊆ Y}. W ei ole tyhjä joukko, sillä U ∈ W. Osoitamme ensin, että S = ^TW on operaattorin F kiintopiste. Jokaiselle joukolleY ∈W päteeS⊆Y ja siisF(S)⊆F(Y)⊆Y. Nyt siisF(S)⊆^TW = S. Toisaalta, koska F(S)⊆S, päteeF(F(S))⊆F(S) ja siisF(S)∈W. Täten S =^TW ⊆F(S), joka todistaa ettäS =F(S). OlkoonW⁰ ={Y |Y =F(Y)}

ja S⁰ =^TW⁰. Nyt S ∈W⁰ ja siisS⁰ ⊆S. Toisaalta W⁰ ⊆W, jotenS =^TW ⊆

TW⁰ =S⁰. Nyt siis S =S⁰. Täten S = ^T{Y | Y = F(Y)} on operaattorin F kiintopiste. Koska se on operaattorinF kaikkien kiintopisteiden leikkaus, se on operaattorin F pienin kiintopiste. Tämä osoittaa, että

lfp(F) =^\{Y |Y =F(Y)}=^\{Y |F(Y)⊆Y}.

Kaikki operaattorit eivät ole monotonisia. Esittelemme seuraavaksi kuinka voimme etsiä kiintopisteen ei-monotoniselle operaattorille.

Oletetaan, että G on mielivaltainen operaattori. Operaattorin G inflatori- nen kiintopiste, ifp(G), on kaikkien niiden joukkojenXⁱ yhdiste, missä X⁰ =∅ ja Xⁱ⁺¹ =Xⁱ∪G(Xⁱ).

ifp(G) =

∞

[

i=0

Xⁱ , kunX⁰ =∅ ja Xⁱ⁺¹ =Xⁱ∪G(Xⁱ).

Olkoon F : ℘(U) → ℘(U) mielivaltainen operaattori ja X⁰ = ∅, Xⁱ⁺¹ = Xⁱ∪G(Xⁱ). Jos jono X⁰ =∅, Xⁱ⁺¹ =Xⁱ∪G(Xⁱ) saavuttaa kiintopisteen, niin jollain luvulla n∈NpäteeXⁿ=Xⁿ⁺¹ ja siis kaikillam > n,X^m =Xⁿ. Koska joukollaU on vain 2^|U| osajoukkoa,n≤2^|U|. Voi myös olla, ettei tällaista lukua n ole, eikä jono saavuta kiintopistettä. Operaattorin F osittainen kiintopiste määritellään seuraavasti

pfp(F) =

( Xⁿ jos Xⁿ=Xⁿ⁺¹ jollakinn∈N

∅ jos Xⁿ6=Xⁿ⁺¹ kaikillan≤2^|U|.

Seuraavaksi näytämme kuinka kiintopiste-operaattoreita saadaan lisättyä logiikkaan FO. Inflatorisen kiintopisteen logiikka, IFP, ja osittaisen kiintopis- teen logiikka, PFP, saadaan määriteltyä suoraan logiikan FO laajennuksina.

Sen sijaan pienimmän kiintopisteen logiikan, LFP, määrittelemistä varten täy- tyy ensin tutkia operaattorin monotonisuutta, sillä pienin kiintopiste on var- masti olemassa vain monotonisilla operaattoreilla.

Olkoon σ relationaalinen aakkosto ja lisäksi olkoon R /∈ σ paikkaluvun k relaatio. Olkoon ϕ(R, x₀, . . . , xk−1) aakkoston σ∪ {R} kaava. Jokaiselle mal- lille A ∈ STRUCT[σ] kaavasta ϕ(R, ~x) muodostuu operaattori F_ϕ : ℘(A^k) →

℘(A^k), joka määritellään seuraavasti:

F_ϕ(X) ={~a |Aϕ[X/R,{~a}/{~x}]}.

Tässä merkintäX/Rtarkoittaa, että relaatiosymboliRtulkitaan relaatioksi X kaavassa ϕ. Siis jos aakkoston σ ∪ {R} malli A⁰ on mallin A ekspansio ja R tulkitaan relaatioksi X, niin A⁰ ϕ(~a).

Merkitään kaavan ϕvapaita muuttujia Fv(ϕ).

Määritelmä 1.2.2. Logiikat IFP ja PFP määritellään logiikan FO laajennuk- sina seuraavin säännöin:

• (IFP): Jos ϕ(R, ~x) on kaava missä relaation R paikkaluku on k ja~ton jono termejä ja |~x|=~t=k, niin

[ifp_R,~xϕ(R, ~x)](~t)

on kaava, jolla Fv([ifp_R,~xϕ(R, ~x)]) = Fv(~t)∪Fv(ϕ)\ {~x}.

• (PFP): Jos ϕ(R, ~x) on kaava missä relaation R paikkaluku on k ja~ton jono termejä ja |~x|=~t=k, niin

[pfp_R,~xϕ(R, ~x)](~t)

on kaava, jolla Fv([pfp_R,~xϕ(R, ~x)]) = Fv(~t)∪Fv(ϕ)\ {~x}.

Toteutuvuus määritellään seuraavasti:

• (IFP): A[ifp_R,~xϕ(R, ~x)](~a) jos ja vain jos~a∈ifp(F_ϕ).

• (PFP): A[pfp_R,~xϕ(R, ~x)](~a) jos ja vain jos~a∈pfp(F_ϕ).

Seuraavaksi lähdemme määrittelemään logiikkaa LFP. Operaattorin mono- tonisuuden toteaminen on kuitenkin hankalaa.

Lemma 1.2.2. Ongelma operaattorinF_ϕmonotonisuudesta äärellisten mallien luokassa on ratkeamaton.

Todistus. Olkoon Φ mielivaltainen lause ja ϕ(S, x) ≡ (S(x) → Φ). Oletetaan, että lause Φ on validi. Nyt ϕ(S, x) on aina tosi ja siten operaattoriF_ϕ monoto- ninen jokaisessa mallissa. Oletetaan sitten, että A ¬Φ jossakin epätyhjässä mallissa A. Nyt ϕ(S, x) ja ¬S(x) ovat ekvivalentit mallissa A joten operaat- tori F_ϕ ei ole monotoninen. Täten F_ϕ on monotoninen jos ja vain jos lause Φ on tosi jokaisessa epätyhjässä mallissa. Tämä lauseen totuusarvo-ongelma on Trakhtenbrotin lauseen mukaan ratkeamaton.

Jotta ongelma monotonisuudesta vältetään, rajoitamme kaavoja seuraavas- ti. Otetaan kaava ϕ, joka saattaa sisältää relaatiosymbolinR. Sanomme relaa- tion R esiintymää kaavassa negatiiviseksi jos siihen vaikuttaa pariton määrä negaatioita ja positiiviseksi jos siihen vaikuttaa parillinen määrä negaatioita.

Esimerkiksi kaavassa ¬∀x∀y(¬R(x)∧R(y))∨ ∃z¬R(z) relaation R ensimmäi- nen esiintymä, R(x), on positiivinen koska se on kahden negaation vaikutusa- lueella. Esiintymät R(y) ja R(z) ovat negatiiviset. Kaavassa R(x) → R(y) relaation ensimmäinen esiintymä, R(x), on negatiivinen ja toinen, R(y), posi- tiivinen, sillä kaava R(x)→R(y) on lyhennemerkintä kaavasta¬R(x)∨R(y).

Kaavassa R(x) ↔ R(y) relaation R neljästä esiintymästä kaksi on positiivisia ja kaksi negatiivisia, sillä kaava R(x) ↔ R(y) on lyhennemerkintä kaavasta R(x)→R(y)∧R(y)→R(x). Jos jossakin kaavassa kaikki relaationR esiinty- mät ovat positiivisia, tai esiintymiä ei ole, sanomme kaavan olevanpositiivinen relaation R suhteen.

Lemma 1.2.3. Jos ϕ(R, ~x) on positiivinen relaation R suhteen, niin F_ϕ on monotoninen.

Todistus. Todistetaan samanaikaisella induktiolla positiivisille ja negatiivisil- le kaavoille. Negatiivisilla kaavoilla väite on, että jos X ⊆ Y, niin F_ϕ(Y) ⊆ F_ϕ(X). OlkootX ja Y joukot siten, että X ⊆Y.

Olkoonϕ(R, ~x) atomikaava. Kaikki mahdolliset relaationResiintymät ovat positiivisia. Nyt mille tahansa alkiojonolle ~a ∈ X pätee myös ~a ∈ Y ja mille tahansa vakiolle c∈X pätee myös c∈Y, joten F_ϕ(X)⊆F_ϕ(Y).

Olkoon kaava ϕ sitten muotoa ϕ = ¬ψ, jossa ψ(R, ~x) on positiivinen re- laation R suhteen. Nyt kaavassa ψ(R, ~x) kaikki relaation R mahdolliset esiin- tymät ovat positiivisia. Jos relaatiolla R on siis esiintymiä kaavassa ψ(R, ~x), ovat ne kaavassa ϕ(R, ~x) negatiivisia ja kaava ϕ(R, ~x) on siis negatiivinen re- laationR suhteen. Tällöin, koska pätee F_ψ(X)⊆F_ψ(Y), niin F_ϕ(Y)⊆F_ϕ(X).

Josψ(R, ~x) on negatiivinen relaationR suhteen, on kaavanϕ(R, ~x) esiintymät positiivisia, sillä ¬¬σ =σ. Näin ollen F_ϕ(X)⊆F_ϕ(Y).

Olkoon kaavaϕsitten muotoaσ∧ψ. Nyt jos kaavat σ(R, ~x) jaψ(R, ~x) ovat positiivisia relaation R suhteen, on myös kaava ϕ(R, ~x) positiivinen relaation R suhteen. Tällöin pätee F_σ(X) ⊆ F_σ(Y) ja F_ψ(X) ⊆ F_ψ(Y) ja siis myös F_ϕ(X)⊆F_ϕ(Y), silläF_σ(X)∪F_ψ(X) =F_ϕ(X) jaF_σ(Y)∪F_ψ(Y) =F_ϕ(Y). Jos taas kaavat σ(R, ~x) ja ψ(R, ~x) ovat negatiivisia relaation R suhteen, on myös kaava ϕ(R, ~x) negatiivinen relaation R suhteen. Tällöin pätee F_σ(Y)⊆F_σ(X) ja F_ψ(Y)⊆F_ψ(X) ja siis myösF_ϕ(Y)⊆F_ϕ(X).

Viimeiseksi, olkoon kaavaϕmuotoa∃xψ. Jos kaavaψ(R, ~x) on positiivinen relaation R suhteen, kaikki relaation R esiintymät ovat positiivisia. Tällöin jos relaatiolla R ei ole esiintymiä, jolloin myöskään kaavassa ∃xψ ei ole relaatiol- la R esiintymiä ja F_ϕ(X) ⊆ F_ϕ(Y). Jos esiintymiä on, on kaava ∃xψ(R, ~x) positiivinen ja ~a ∈ F_ϕ(X) → ~a ∈ F_ϕ(Y). Siis F_ϕ(X) ⊆ F_ϕ(Y). Jos taas ψ(R, ~x) on negatiivinen relaation R suhteen, kaikki relaation R esiintymät ovat negatiivisia. Nyt kaikki ne ~a, joilla A ∃xψ[Y /R,{~a}/{~x}], pätee myös A∃xψ[X/R,{~a}/{~x}], joten Fσ(Y)⊆Fσ(X).

Siispä F_ϕ on monotoninen jos ϕ(R, ~x) on positiivinen relaation R suhteen.

Määritelmä 1.2.3. Logiikka LFP määritellään logiikan FO laajennuksena seuraavalla muodostussäännöllä:

• Jos ϕ(R, ~x) on kaava, joka on positiivinen relaation R suhteen, missä relaation R paikkaluku onk ja~ton jono termejä ja |~x|=~t=k, niin

[lfp_R,~xϕ(R, ~x)](~t)

on kaava, jolla Fv([lfp_R,~xϕ(R, ~x)]) = Fv(~t)∪Fv(ϕ)\ {~x}.

Toteutuvuus määritellään seuraavasti:

A[lfp_R,~xϕ(R, ~x)](~a) jos ja vain jos~a∈lfp(F_ϕ).

Ongelmia jaotellaan sen mukaan, kuinka nopeasti ratkeavia ne ovat. Merkit- semme polynomisessa ajassa ratkeavien ongelmien luokkaaPtime. Seuraavas- sa lauseessa todetaan logiikoiden LFP ja IFP olevan äärellisten, järjestettyjen mallien osalta yhtäläiset luokanPtimekanssa. Lauseen todistus pohjautuu yh- distettyihin kiintopisteisiin, joiden käsittely jää tämän tutkielman ulkopuolelle [1 s.192].

Lause 1.2.4 (Immermanin ja Vardin lause).

LFP_< ≡IFP_< ≡Ptime.

1.3 Rajoitetun muuttujamäärän logiikat

Tässä luvussa esitetään logiikka, jossa rajoitetaan kaavoissa käytettyjen muut- tujien määrää. Osoitamme, että kiintopistelogiikat LFP, IFP ja PFP voidaan sisällyttää tällaiseen rajoitetun muuttujamäärän logiikkaan. Tästä on hyötyä kiintopistelogiikoiden myöhemmässä käsittelyssä.

Logiikan FO kaavanϕ_n(x, y), joka sanoo verkossaGolevannpituisen polun solmusta xsolmuun y, voi ilmaista monella tavalla. Kaava ϕ₁(x, y) sanoo, että (x, y)∈E^G. Pidempää polkua∃x₁. . .∃xn−1((x, x₁)∈E^G∧. . .∧(xn−1, y)∈E^G) vastaava kaava on ϕ_n(x, y), n > 1. Voimme myös ilmaista kaavan induktiivi- sesti:

ϕ₁(x, y)≡(x, y)∈E^G, ϕ_n+1(x, y)≡ ∃z_n((x, z_n)∈E^G∧ϕ_n(z_n, y)), jossaz_non uusi muuttuja. Molemmissa ilmaisutavoissa on käytössä suuri määrä muuttujia. Voimme kuitenkin muuttaa induktiolla määritellyn jonon muotoon, jossa muuttujien määrä saadaan rajoitettua kolmeen:

ϕ₁(x, y)≡(x, y)∈E^G, ϕ_n+1(x, y)≡ ∃z((x, z)∈E^G∧∃x(z =x∧ϕ_n(x, y))).

Nyt muuttuja, jota ei enää tarvita, otetaan käyttöön uudestaan ja saamme kaavan muuttujamäärän rajattua.

L∞ω laajentaa logiikan FO äärettömällä konjunktiolla ^V ja disjunktiolla^W.

Määritelmä 1.3.1. Niiden logiikan FO kaavojen, joissa muuttujat ovat x₀, . . . , xk−1, joukkoa merkitään FO^k. Samoin niidenL∞ω-kaavojen, joissa muut- tujat ovat x₀, . . . , x_k−1, joukkoa merkitäänL^k_∞ω. Lopuksi määrittelemme rajoi- tetun muuttujamäärän äärettömän logiikan L^ω_∞ω seuraavasti

L^ω_∞ω = ^[

k∈N

L^k_∞ω

Näin ollen L^ω_∞ω koostuu niistä L∞ω-kaavoista, joissa on käytössä äärellinen määrä muuttujia.

L^ω_∞ω-kaavan ϕ kvanttoriaste qr(ϕ) määritellään induktiolla kaavan raken- teen suhteen:

1. qr(ϕ) = 0, kun ϕon atomikaava.

2. Kun ϕ=¬ψ , niin qr(ϕ) = qr(ψ).

3. Kun ϕon muotoa σ∧ψ, niin qr(ϕ) = max{qr(σ),qr(ψ)}.

4. Kun ϕon muotoa ∃xψ, niin qr(ϕ) = qr(ψ) + 1.

Äärettömille konnektiiveille määrittelemme qr(^_

i∈I

ϕ_i) = qr(^{^}

i∈I

ϕ_i) = sup

i∈I

qr(ϕ_i),

jossa merkintä sup_i∈Iqr(ϕi) tarkoittaa kvanttoriasteiden qr(ϕi),i∈I pienintä ylärajaa.

Ordinaaliluku tai lyhyemminordinaali on joukkoα, jonka jokaiselle alkiolle β ∈αpäteeβ ⊂αja alkiorelaatio∈on joukonαhyvinjärjestys. Ordinaalien ja luonnollisten lukujen erona on, että ordinaaleissa on seuraajalukujen lisäksi niin sanottuja rajaordinaaleja. Ensimmäinen rajaordinaali on luonnollisten lukujen mahtavuutta vastaava ω, jonka alkioita ovat kaikki luonnolliset luvut. Tälle on jälleen seuraajaordinaaleja, kunnes saavutetaan seuraava rajaordinaali ω·2.

Äärettömän kaavan kvanttoriaste voi olla rajaordinaali. Esimerkiksi jos kaavat ϕ_n ovat sellaisia logiikan FO kaavoja joille qr(ϕ_n) = n, niin qr(^W_n<ωϕ_n) = ω ja qr(∃x^W_n<ωϕ_n) = ω+ 1.

Malliluokka on kokoelma äärellisiä malleja. Merkinnällä L ≤ L^∗ tarkoite- taan, että kaikki malliluokat jotka voidaan määritellä logiikassa L, voidaan määritellä myös logiikassaL^∗. Käytämme merkintää~x=~y lyhenteenä kaavalle ((x₀ =y₀)∧. . .∧(xk−1 =yk−1)).

Oletetaan, että logiikan FO kaava ϕ(R, ~x) on joko monotoninen relaatios- sa R, tai kiintopiste on inflatorinen. Oletetaan, että kaava ϕ muuttujien ~x = (x₀, . . . , xk−1) lisäksi käyttää muuttujiaz₀, . . . , z_l. Otamme käyttöön lisämuut- tujat~y= (y₀, . . . , y_k−1) ja määrittelemmeepätodenkaavanϕ⁰(~x) =¬(x₀ =x₀), sekä induktiivisesti ϕⁿ⁺¹(~x) sellaisena kaavana ϕ(R, ~x), missä jokainen relaa- tion esiintymä R(u₀, . . . , uk−1), missä u₀, . . . , uk−1 ovat muuttujia joukoista ~x ja ~z, korvataan kaavalla

∃~y((~y=~u)∧(∃~x((~x=~y)∧ϕⁿ(~x)))).

Huomaamme, että saadussa kaavassa joukon ~y muuttujat eivät voi esiintyä missään muotoaR(·) olevassa kaavan osassa. Nyt koska relaationR esiintymät kaavassa ϕⁿ⁺¹ on ilmaistu käyttäen kaavaaϕⁿ, niin^W_nϕⁿ(~x) määrittää kiinto- pisteen. Koska enimmillään kaksinkertaistimme kaavan ϕ muuttujien määrän, niin jos ϕ ∈ FO^m, niin molemmat lfp_R,~xϕ ja ifp_R,~xϕ ovat ilmaistavissa logii- kassaL^2m_∞ω. Koska kiintopistettä määritettäessä muuttujien määrä korkeintaan kaksinkertaistuu, jokaiselle logiikan LFP tai IFP kaavalle on olemassa ekviva- lentti logiikan L^ω_∞ω kaava. Nyt siis LFP≤L^ω_∞ω ja IFP≤L^ω_∞ω.

Lause 1.3.1. PFP≤L^ω_∞ω.

Todistus. Logiikalle PFP muutamme kaavan rakennetta hieman. Sen sijaan, että ottaisimme disjunktion kaikista kaavoista ϕⁿ, määrittelemme merkinnän kp_n lauseelle∀~x(ϕⁿ(~x)↔ϕⁿ⁺¹(~x)) osoittamaan, että kiintopiste on saavutettu.

Nyt [pfp_R,~xϕ](~y) voidaan ilmaista kaavalla ψ(~y)≡ ^_

n∈N

(kp_n∧ϕⁿ(~x)).

Jos ei ole olemassa lukua n jollakp_n pätee, niin osittainen kiintopiste on tyhjä joukko ja kaava ψ(~y) on ekvivalentti epätoden kaavan kanssa. Muussa tapauk- sessa, olkoon n₀ se pienin luonnollinen luku n jolla kp_n on tosi. Nyt, kaikilla m ≥ n₀ pätee ∀~x(ϕⁿ⁰(~x) ↔ϕ^m(~x)) ja siis ψ(~y) määrittää osittaisen kiintopis- teen. Täten kaava ψ määrittää kiintopisteen pfp_R,~xϕ ja se enimmillään kak- sinkertaistaa muuttujien määrän. Käyttäen tätä määritelmää induktiivisesti näemme, että PFP≤L^ω_∞ω.

1.4 Helmipelit

Tässä luvussa esittelemme helmipelin, joka on eräs Ehrenfeucht-Fraïssé-pelin muunnelma. Tässä pelissä pelaajilla, spoilerilla ja duplikaattorilla, on käytös- sään joukko helmipareja. Jokaisella vuorolla helmi joko asetetaan mallin jolle- kin alkiolle, tai siirretään alkiolta toiselle. Helmipelin voittaja voidaan määri- tellä siitä huolimatta, ettei pelin tarvitse päättyä tietyn siirtomäärän jälkeen.

Määritelmä 1.4.1. Olkoot AjaBsaman relationaalisen aakkostonσmalleja ja jonot ~a = (a₁, . . . , a_n) ∈ A ja ~b = (b₁, . . . , b_n) ∈ B. Nyt (~a,~b) määrittää osittaisen isomorfismin mallistaA malliin Bjos seuraavat ehdot toteutuvat:

• Jokaiselle lukuparille i, j ≤n pätee

ai =aj jos ja vain jos bi =bj.

• Jokaiselle aakkostonσ vakiosymbolillecja jokaiselle luvullei≤n pätee a_i =c^A jos ja vain josb_i =c^B.

• Jokaiselle aakkoston σ k-paikkaiselle relaatiosymbolille R ja jokaiselle jonolle (ei välttämättä toisistaan eroavia) numeroita (i₁, . . . , i_k), i_m ≤ n kaikilla m, pätee

(a_i1, . . . , a_ik)∈R^A jos ja vain jos (b_i1, . . . , b_ik)∈R^B.

Määritelmä 1.4.2. Olkoot A, B ∈ STRUCT[σ]. Spoileri ja duplikaattori pelaavat k-helmipelin malleilla AjaB seuraavalla tavalla. Pelaajilla on joukko helmipareja (p¹_A, p¹_B), . . . ,(p^k_A, p^k_B). Siirrot tehdään seuraavasti:

• Spoileri valitsee mallin, Atai B, ja numeron 1≤i≤k.

Oletamme spoilerin valitsevan mallin A. Tapaus, jossa spoileri valitsee mallin B, on täysin symmetrinen.

• Spoileri sijoittaa helmenpⁱ_A jollekin mallinA alkiolle. Jos pⁱ_A on jo sijoi- tettuna malliinA, voi spoileri jättää sen paikoilleen tai siirtää sen mallin A toiselle alkiolle. Jos helmeä pⁱ_A ei ole vielä käytetty, ottaa spoileri sen käyttöön ja sijoittaa mallin A alkiolle.

• Duplikaattori vastaa tähän sijoittamalla helmen pⁱ_B jollekin mallin B alkiolle.

Käytämme n:n kierroksen pituisesta helmipelistä merkintää PGⁿ_k(A,B) ja äärettömän monen kierroksen helmipelistä merkintää PG^∞_k (A,B). Jokaisen kierroksen jälkeen malleille A ja B sijoitetut helmet määrittävät relaation F ⊆ A× B: pari (a, b) kuuluu relaatioon F jos ja vain jos helmi pⁱ_A, jolla- kin i≤k, on sijoitettu alkiolle a∈A ja helmi pⁱ_B on sijoitettu alkiolle b∈B.

Duplikaattorilla on voittostrategia pelissä PGⁿ_k(A,B) jos hän pystyy var- mistamaan, että jokaisen kierroksen, j ≤n, jälkeen relaatioF määrittää osit- taisen isomorfismin. Tällöin kirjoitamme A'^k,n_∞ω B.

Duplikaattorilla on voittostrategia pelissä PG^∞_k (A,B) jos hän pystyy var- mistamaan, että jokaisen kierroksen jälkeen relaatioF määrittää osittaisen iso- morfismin. Siispä mille tahansa spoilerin siirtojonolle on löydyttävä vastaava duplikaattorin siirtojono niin, että kun helmet on sijoitettu mallien alkioille, relaatioF määrittää osittaisen isomorfismin ja mihin tahansa spoilerin helmien asetteluun mallien alkioilla on mahdollista vastata duplikaattorin helmien aset- telulla, joka säilyttää isomorfismin. Tällöin kirjoitamme A'^k_∞ω B.

Esimerkki 1.4.1. OlkootJ_n ja J_m kaksi mielivaltaista lineaarijärjestystä, joi- den pituudet ovat (vastaavasti) n ja m,n 6=m. Voimme osoittaa, että spoileri voittaa 2-helmipelin PG^∞₂ (J_n, J_m).

Spoileri valitsee pidemmän lineaarijärjestyksen ja asettaa helmen ensim- mäisestä helmiparista tämän järjestyksen ensimmäiselle alkiolle. Jotta spoile- ri ei voita peliä, täytyy duplikaattorin tehdä samoin ja asettaa vastaava hel- mi lyhyemmän lineaarijärjestyksen ensimmäiselle alkiolle. Seuraavaksi spoileri asettaa toisen helmiparin helmen pidemmän järjestyksen seuraavalle alkiolle.

Duplikaattorin on jälleen tehtävä samoin (duplikaattorin asettaessa toisen hel- men jollekin muulle alkiolle peli etenee vastaavasti, mutta spoileri voittaa no- peammin).

Nyt spoileri siirtää ensimmäisen helmiparin helmen pidemmässä lineaarijärjes- tyksessä kolmannelle alkiolle. Duplikaattorin täytyy tehdä samoin, jotta järjes- tysrelaatio säilyy. Näin jatkuu spoilerin siirtäen aina järjestyksessä aiempana olevan helmen kaksi alkiota eteenpäin ja duplikaattorin tehden samoin.

Lopulta, kun duplikaattori on asettanut helmet lyhyemmän lineaarijärjestyksen kahteen viimeiseen alkioon, hän häviää pelin seuraavalla kierroksella.

Kun spoileri siirtää helmen kaksi alkiota eteenpäin, duplikaattorilla ei ole vas- taavaa paikkaa helmelle.

Otetaan kaksi mallia A,B ∈ STRUCT[σ], jotka ovat ekvivalentit niiden logiikan L^k_∞ω kaavojen suhteen, joiden kvanttoriaste on korkeintaan n. Nyt jo- kaisen logiikassa L^k_∞ω määriteltävän kaavan, jonka kvanttoriaste on korkein- taan n, totuusarvo mallissa A on sama, kuin mallissa B. Merkitsemme tällöin A≡^k,n_∞ω B.

Vastaavasti, jos kaksi malliaA,B∈STRUCT[σ] ovat ekvivalentit kaikkien logiikan L^k_∞ω lauseiden suhteen, merkitsemme tällöin A ≡^k_∞ω B. Jos kaksi mallia A,B ∈ STRUCT[σ] ovat ekvivalentit kaikkien logiikan FO^k lauseiden suhteen, merkitsemme tällöin A≡^kB.

Lause 1.4.1. (a) A≡^k,n_∞ω B jos ja vain jos A'^k,n_∞ω B.

(b) A≡^k_∞ω B jos ja vain jos A'^k_∞ω B.

Lauseen todistusta varten tutkimme kahden mallin välistä ekvivalenssia lisää ja määritämme tietyn osittaisten isomorfismien edestakais-ominaisuuden todistusta varten.

Esimerkissä 1.4.1 saatu tulos on edellisen lauseen nojalla luonnollinen, sillä kaikki äärellisiä lineaarijärjestyksiä koskevat kyselyt ovat ilmaistavissa logiikas- saL²_∞ω. Duplikaattorin ei siis tulisi voittaa 2-helmipeliä PG^∞₂ (J_n, J_m) paitsi jos n =m.

Esimerkki 1.4.2. Otetaan kaksi mielivaltaista tyhjän aakkoston mallia (puh- taita joukkoja), A ja B ja luku k. Jos |A|,|B| ≥k, niin duplikaattori voittaa k-helmipelin PG^∞_k (A, B).

Duplikaattorin täytyy säilyttää sellainen asetelma, että millä tahansa lu- vuilla i ja j, helmet pⁱ_A ja p^j_A ovat asetettu samalle alkiolle jos ja vain jos hel- met pⁱ_B ja p^j_B ovat asetettu samalle alkiolle. Tämä on helppo toteuttaa, sillä kummassakin mallissa on vähintään k alkiota ja helmet mahtuvat tarvittaessa jokainen omalle alkiollensa. Duplikaattori voittaa siis päättymättömän pelin.

Eräs mielenkiintoinen ominaisuus äärellisissä malleissa on universumin mah- tavuuden parillisuus. Määritämme tämän selvittämiseen kyselyn EVEN seuraa- vasti:

EVEN(A) on tosi jos ja vain jos |A| ≡0 (mod 2).

Esimerkistä 1.4.2 saamme seuraavaksi esitellyn tuloksen.

Seuraus 1.4.2. Kysely EVEN ei ole määriteltävissä logiikassa L^ω_∞ω.

Todistus. Tehdään vastaoletus, että kysely EVEN on ilmaistavissa logiikan L^ω_∞ω lauseella Φ. Olkoon k sellainen luku, että Φ ∈ L^k_∞ω. Valitaan malli A, jonka mahtavuus on k, ja malli B, jonka mahtavuus on k+ 1. Esimerkin 1.4.2 perusteellaA '^k_∞ω B ja edelleen lauseen 1.4.1 perusteellaA≡^k_∞ω B. NytAΦ jaB Φ, joka on ristiriidassa oletuksen kanssa, että lause Φ määrittää kyselyn EVEN, koska vain toinen mallien mahtavuuksista,k jak+ 1, on parillinen.

Olkoon ϕääretön disjunktio ϕ≡^W_i∈Iϕ_i, jossa kaikki kaavat ϕ_i ovat logii- kan FO kaavoja, ja oletetaan että qr(ϕ)≤n. Tämä tarkoittaa, että qr(ϕ_i)≤n kaikilla i ∈I. Kun aakkosto on kiinnitetty ja äärellinen, on olemassa vain ää- rellinen määrä ei-ekvivalentteja logiikan FO kaavoja, joiden kvanttoriaste on n. Siispä on olemassa sellainen äärellinen osajoukko I₀ ⊂ I, että ϕ≡^W_i∈I0ϕ_i, eli siis ekvivalentti jonkin logiikan FO kaavan kanssa. Käyttäen tätä tulosta in- duktiivisesti logiikan L^ω_∞ω kaavojen rakenteelle, voimme todeta että jokaisella luvulla k jokainen logiikan L^k_∞ω kvanttoriasteenn kaava on ekvivalentti logii- kan FO^k saman kvanttoriasteen kaavan kanssa. Siispä jos mallit A ja B ovat ekvivalentit kaikkien logiikan FO^k lauseiden, joiden kvanttoriaste on enintään n, totuusarvojen suhteen, niin A≡^k,n_∞ω B.

Lemma 1.4.3. Jokaiselle malliparille A,B seuraavat ominaisuudet ovat yh- täpitäviä:

1. A≡^k B.

2. A≡^k_∞ω B.

Todistus. Olkoot A ja B sellaiset mallit, jotka ovat ekvivalentit kaikkien lo- giikan FO^k kaavojen totuusarvojen suhteen. Siispä jokaisella luvulla n pätee A ≡^k,n_∞ω B. Koska mallit A ja B ovat äärelliset, on äärellinen määrä kuvauk- sia joukolta A^k joukolle B^k. Täten jokainen ääretön strategia k-helmipelissä PG^∞_k (A,B) on täydellisesti määritelty äärellisen strategian perusteella, jossa

luku n on riittävän suuri, eli sellainen jolla kaikki mahdolliset pelin tilanteet tulevat esiin. Täten, tarpeeksi suurella luvulla n (riippuu malleista A ja B), k-helmipelin PGⁿ_k(A,B) voittaminen johtaa k-helmipelin PG^∞_k (A,B) voitta- miseen.

Seuraavaksi käsittelemme kaavoja, joissa on vapaita muuttujia. Jos dupli- kaattori voittaak-helmipelin PGⁿ_k(A,B) asetelmasta, jossa ensimmäisetmhel- meä on asetettu jonojen ~a ja~b, jossa |~a| =~b= m≤ k, alkioille, niin merkit- semme (A, ~a)≡^k,n_∞ω (B,~b) vastaavasti. Samalla tavoin merkitsemme (A, ~a)≡^k_∞ω (B,~b) koskien peliä PG^∞_k (A,B).

Seuraus 1.4.4. OlkootAjaBkaksi mallia ja~a∈A^m,~b∈B^m, m≤k. Tällöin (a) (A, ~a) ≡^k,n_∞ω (B,~b) jos ja vain jos A ϕ[~a/~x] ⇔ B ϕ[~b/~x] kaikilla

ϕ(~x)∈L^k_∞ω joillaqr(ϕ)≤n.

(b) (A, ~a) ≡^k_∞ω (B,~b) jos ja vain jos A ϕ[~a/~x] ⇔ B ϕ[~b/~x] kaikilla ϕ(~x)∈L^k_∞ω.

Esittelemme seuraavaksi ominaisuuden, jonka avulla saamme todistettua lauseen 1.4.1. Tarvitsemme aluksi muutaman määritelmän.

Olkoon f :A→B osittainen kuvaus. Sen lähtöjoukkoa merkitään dom(f) ja maalijoukkoa rg(f). Osittainen kuvausf on siis määritelty joukossa dom(f)⊆ A ja f(dom(f)) = rg(f)⊆B.

Merkitsemme symboleinα jaβ lukuja, jotka voivat olla äärellisiä tai ääret- tömiä ordinaaleja. Olkoot AjaBkaksi mallia jaβ ordinaali. Olkoon I_β joukko osittaisia isomorfismeja joukkojen A ja B välillä ja olkoon I_α ={I_β |β < α}.

Sanomme, että joukolla I_α on k-edestakais-ominaisuus jos seuraavat ehdot täyttyvät:

• Jokainen joukko I_β on epätyhjä.

• I_β⁰ ⊆I_β, kunβ < β⁰ < α.

• Jokainen joukkoI_β on alaspäin suljettu, eli josg ∈I_β jaf ⊆g(dom(f)⊆ dom(g) ja g dom(f) = f), niin f ∈Iβ.

• Jos f ∈I_β+1 ja |dom(f)|< k, niin

eteen: jokaiselle alkiollea ∈A on olemassa sellainen g ∈ I_β, että f ⊆ g ja a∈dom(g);

taakse: jokaiselle alkiolleb ∈B on olemassa sellainen g ∈I_β, ettäf ⊆g ja b ∈rg(g).

Kuten aiemmin huomasimme, ekvivalenssistaA≡^k,n_∞ω Bseuraa ekvivalenssi A≡^k_∞ω Bmillä tahansa malliparillaAjaBja tarpeeksi suurella luvullan. Jos meillä siis on tarpeeksi pitkä äärellinen jono I_α, jotkin joukotI_β toistuvat, sillä on vain äärellinen määrä osittaisia isomorfismeja mallienA jaB välillä. Siispä tällainen jono voidaan laajentaa mielivaltaisen ordinaalin pituiseksi.

Lemma 1.4.5. Olkoot A ja B kaksi mallia. Mallit A ja B ovat ekvivalentit kaikkien logiikan L^k_∞ω lauseiden suhteen, joiden kvanttoriaste on pienempi kuin α jos ja vain jos on olemassa joukkoI_α ={I_β |β < α}osittaisia isomorfismeja mallien A ja B välillä, joilla on k-edestakais-ominaisuus.

Todistus. Oletetaan, että mallitAjaBovat ekvivalentit kaikkien logiikanL^k_∞ω lauseiden suhteen, joiden kvanttoriaste on pienempi kuin α. Olkoon β < α.

Määritellään I_β siten, että se on niiden osittaisten isomorfismien f joukko, joille pätee |dom(f)| ≤ k ja jokaiselle kaavalle ϕ ∈ L^k_∞ω, jolla qr(ϕ) ≤ β ja jokaiselle jonolle ~a joukossa dom(f) pätee

Aϕ(~a) ⇔ Bϕ(f(~a)).

Osoitamme, että joukolla I_α ={I_β |β < α} on k-edestakais-ominaisuus.

Koska mallitAjaBovat ekvivalentit kaikkien logiikan L^k_∞ω lauseiden suh- teen, joiden kvanttoriaste on pienempi kuin α, niin jokainen joukko I_β on epä- tyhjä, sisältäen ainakin tyhjän osittaisen isomorfismin. Ehto I_β⁰ ⊆ I_β, kun β < β⁰ seuraa suoraan määritelmästä, kuten myös alaspäin sulkeutuvuus. To- distettavaksi jää edestakais-ominaisuus.

Tehdään vastaoletus, että löytyy sellainen f ∈ I_β+1, β + 1 < α, jolle pä- tee |dom(f)| = m < k ja joka ei toteuta ehtoa eteen. Nyt siis on olemassa sellainen alkio a ∈ A, että ei ole olemassa osittaista isomorfismia g ∈ I_β, jo- ka laajentaa osittaisen isomorfismin f alkiolla a ∈ dom(g). Näin ollen, jou- kon I_β määritelmän mukaan, jokaiselle alkiolle b ∈ B voimme löytää sellai- sen kaavan ϕ_b(x₀, x₁, . . . , x_m), jonka kvanttoriaste on enintään β ja että jol- lekin alkiojoukolle a₁, . . . , a_m ∈ dom(f) pätee A ϕ_b(a, a₁, . . . , a_m) ja B

¬ϕ_b(b, f(a₁), . . . , f(a_m)).

Olkoon nyt

ϕ(x₁, . . . , x_m) ≡ ∃x₀ ^{^}

b∈B

ϕ_b(x₀, x₁, . . . , x_m).

Selvästi, A ϕ(a₁, . . . , am), mutta B ¬ϕ(f(a₁), . . . , f(a_m)), joka on ristirii- dassa oletuksen f ∈I_β+1 kanssa koska qr(ϕ)≤β+ 1. Tapaus, jossa osittainen isomorfismi f ei toteuta ehtoa taakse saadaan vastaavasti.

Oletetaan sitten, että on olemassa joukko Iα, jolla on k-edestakais-ominai- suus. Osoitamme induktiolla ordinaalinβsuhteen, että kaikillaϕ(x₁, . . . , x_m)∈ L^k_∞ω, m≤k, joiden qr(ϕ)≤β < α,

kaikillaf ∈I_β,a₁, . . . , a_m ∈dom(f):

Aϕ(a₁, . . . , am) ⇔ Bϕ(f(a₁), . . . , f(a_m)).

(1.4.1)

Tämän todistaminen riittää, sillä kaavasta (1.4.1) seuraa, että mallit A ja B ovat ekvivalentit kaikkien logiikan L^k_∞ω lauseiden suhteen, joiden kvanttoriaste on pienempi kuin α.

Perusaskel:β = 0 pätee, sillä tällöinϕon Boolen kombinaatio atomikaavoja.

Koska f on osittainen isomorfismi, A a_i ⇔ B f(a_i), kaikilla a₁, . . . , a_m ∈ dom(f), joten kaava (1.4.1) pätee.

Induktioaskel: Jos ϕ≡ ^W_iϕ_i, missä qr(ϕ) >qr(ϕ_i) kaikilla i, niin β on ra- jaordinaali. Nyt käyttäen oletusta jokaiseenϕ_i, huomaamme, että kaava (1.4.1) pätee lauseelle ϕ.

Jää tutkittavaksi tapaus ϕ(x₁, . . . , x_m) ≡ ∃x₀ψ(x₀, . . . , x_m), jossa qr(ϕ) = β+ 1 ja qr(ψ) =β jollakin ordinaalilla β, jolla β+ 1 < α. Yleisyyttä rajoitta- matta voimme olettaa, että x₀ ei kuulu muuttujajoukkoon {x₁, . . . , x_m} ja siis m < k.

Olkoonf ∈I_β+1 jaa₁, . . . , a_m ∈dom(f). Oletetaan, ettäAϕ(a₁, . . . , a_m), siis että jollakin alkiolla a₀ ∈ A, A ψ(a₀, a₁, . . . , a_m). Koska joukko I_β+1 on alaspäin suljettu, voimme olettaa jatkossa että dom(f) = {a₁, . . . , a_m}.

Koska |dom(f)| = m < k, on k-edestakais-ominaisuuden perusteella olemas- sa g ∈ I_β joka on osittaisen isomorfismin f sellainen laajennus, että a₀ ∈ dom(g). Käyttämällä kaavaa (1.4.1) induktiivisesti lauseeseenψ, saamme B ψ(g(a₀), g(a₁), . . . , g(a_m)). Koska f ja g ovat ekvivalentit alkioiden a₁, . . . , a_m suhteen, Bψ(g(a₀), f(a₁), . . . , f(a_m)) ja siis Bϕ(f(a₁), . . . , f(a_m)).

Suunta, jossa toteutuvuudesta Bϕ(f(a₁), . . . , f(a_m)) seuraa

A ϕ(a₁, . . . , a_m), on täysin vastaava. Tämä päättää kaavan (1.4.1), lem- man 1.4.5, sekä lauseen 1.4.1 todistuksen.

2 Asymptoottinen todennäköisyys ja laajennusaksioomat

Asymptootti on se suora, jota käyrä lähestyy jatkuessaan äärettömyyksiin. Sa- na asymptootti tulee kreikankielen sanasta asymptotos. Asymptotos tarkoittaa

”ei yhteen kaatumista” (Oxford English Dictionary, second edition, 1989). Ter- min esitteli Apollonius Pergalainen kartioleikkauksiin liittyvien töidensä yh- teydessä. Verraten sanan nykyiseen merkitykseen, hän kuitenkin tarkoitti sillä mitä tahansa suoraa, joka ei leikkaa annettua käyrää (D.E. Smith, History of Mathematics, vol 2 Dover (1958) p. 318).

Käsittelemme tässä luvussa suuntaamattomien verkkojen ominaisuuksien asymptoottista todennäköisyyttä. Samoin, kuin käyrä joka jatkuessaan ääret- tömyyksiin lähestyy raja-arvoa, asymptoottia, saadaan joillekin verkon omi- naisuuksille asymptoottinen todennäköisyys kun solmujen määrää kasvatetaan rajatta.

2.1 Asymptoottinen todennäköisyys

Kun tarkastelemme äärellisten mallien ominaisuuksien asymptoottista toden- näköisyyttä, mallin A, jossa |A| = n, universumi on joukko {0, . . . , n −1}.

Aloitetaan käsittelemällä suuntaamattomia verkkoja. Merkitsemmen:n solmun verkkojen joukkoa Grn ={G = (V, E^G) | |V| =n}. Suuntaamattomien verk- kojen määrä solmuilla {0, . . . , n−1} on

|Grn| = 2(ⁿ²).

Olkoon P verkkojen ominaisuus. Todennäköisyys sille, että satunnaisesti valitulla solmujen{0, . . . , n−1}verkolla on ominaisuusP,µ_n(P), määritellään seuraavasti:

µ_n(P) = |{G∈Grn |verkollaG on ominaisuus P}|

|Grⁿ| .

Satunnaisesti valittu tarkoittaa tässä sitä, että verkoista otetaan tasainen ja- kauma.

Määrittelemme ominaisuudenP asymptoottisen todennäköisyyden

(2.1.1) µ(P) = lim

n→∞µ_n(P),

jos raja-arvo on olemassa. Jos ominaisuus P on määritelty jonkin logiikan lauseella Φ, niin käytämme merkintöjä µ_n(Φ) ja µ(Φ).

Voimme yleistää tarkastelun mielivaltaisiinσ-malleihin. Tällöin merkitsem- me universumin {0, . . . , n−1} erilaisten σ-mallien määrää sⁿ_σ, ja universumin {0, . . . , n−1} erilaisten σ-mallien, joilla ominaisuus P, määrää sⁿ_σ(P). Osa- määrällä saamme todennäköisyyden

µ_n(P) = sⁿ_σ(P) sⁿ_σ .

Asymptoottisen todennäköisyyden saamme taas kaavalla (2.1.1).

Esimerkki 2.1.1. Olkoon P ominaisuus ”verkossa ei ole eristettyjä solmuja”.

Väitämme, että µ(P) = 1. Yhtäläisesti, osoitamme että µ( ¯P) = 0, missä ¯P on:

”on olemassa eristetty solmu”. Laskeaksemme todennäköisyyden µ_n( ¯P), huo- maamme olevan n tapaa valita eristetty solmu ja 2(ⁿ⁻¹² ) tapaa asettaa särmät jäljellä oleviin solmuihin. Verkko, jossa on enemmän kuin yksi eristetty solmu, toteuttaa useamman kuin yhden tällaisen tilanteen. Nyt

µ_n( ¯P) ≤ n·2(ⁿ⁻¹² )

2(ⁿ²) = n·2(ⁿ⁻¹² )

2⁽ⁿ⁻¹⁾⁺(ⁿ⁻¹2 ) = n·2(ⁿ⁻¹² )

2ⁿ⁻¹ ·2(ⁿ⁻¹² ) = n 2ⁿ⁻¹, ja siis asymptoottinen todennäköisyys µ( ¯P) = 0.

Esimerkki 2.1.2. Olkoon ominaisuus P verkon yhtenäisyys. Osoitamme jäl- leen, ettäµ( ¯P) = 0 ja siten verkon yhtenäisyyden asymptoottinen todennäköi- syys on 1. Laskeaksemme asymptoottisen todennäköisyyden µ( ¯P), täytyy tie- tää niiden verkkojen määrä, joissa on ainakin kaksi yhtenäistä osaa. Olettaen yhden osan kooksi k,

• on ⁿ_k tapaa valita osajoukko X ⊆ {0, . . . , n−1},

• on 2(^k2) tapaa asettaa särmät osajoukkoon X ja

• on 2(^n−k2 ) tapaa asettaa särmät osajoukonX komplementtijoukkoon.

Nyt

µ_n( ¯P) ≤

n−1

X

k=1

_n

k

·2(^k2)·2(^n−k2 ) 2(ⁿ²) =

n−1

X

k=1

n k

!

·2(^k2)⁺(^n−k₂ )⁻(ⁿ₂)

=

n−1

X

k=1

n k

!

·2^k2−kn →0, kun n kasvaa rajatta.

Eksponenttien yhdistäminen ja sievennys saadaan seuraavasti:

k 2

!

+ n−k 2

!

− n 2

!

= k!

2(k−2)! + (n−k)!

2(n−k−2)! − n!

2(n−2)!

= k(k−1)

2 + (n−k)(n−k−1)

2 − n(n−1)

2 =k²−kn Verkon yhtenäisyyden asymptoottinen todennäköisyys on siis 1.