Paris-Harrington tétel

Csirmaz László

Sokáig nyitott kérdés volt, hogy van-e értelmes matematikai állítás (hogy az “értelmes” pontosan mit is jelent, azzal most nem foglalkozunk), melyről meg tudjuk mutatni, hogy a Peano axiómarendszertől független. Az első példát 1977-ben találta Jeff Paris és Leo Harrington. Példájuk a (véges) Ramsey tételnek egy ártatlannak látszó erősítése, mely végül is függetlennek bizonyult a szokásos Peano axiómarendszertől.

Definíció Azt mondjuk, hogy a természetes számok H részhalmaza ∗ tulajdonságú, ha H-ban több elem van, mint H minimális eleme: |H| > min(H). Adott e, r és M természetes számok esetén a

M → (∗)_{r}^{e}

partícióreláció jelentése: akárhogyan is szinezzük ki az M = {0, 1,…, M − 1} halmaz e-eseit r színnel, mindig van legalább e + 1 elemű H ⊂ M ∗-homogén.

Legyen 𝔑 a természetes számok szokásos struktúrája, aminek alaphalmaza ω, a jelek pedig +, ∗, ≤, 0 és 1. Ezen kívül még bevezetjük a 2^{x} (a többi jellel egyébként a Peano axiómarendszerben definiálható) egyváltozós függvényjelet a kettőhatványok jelölésére. A Peano formulák közül fontosak lesznek számunkra az úgy nevezett Δ_{0}^{∗} formulák. Ezekben minden kvantor egy (összeadás, szorzás és hatványozásból összeállított) kifejezéssel van korlátozva. A szokásos Δ_{0} formulákban a kvantorokat más változókkal kell korlátozni.

1. Tétel 𝔑 ⊧ ∀e ∀r ∃M M → (∗)_{r}^{e} .

Bizonyítás. Rögzítsük e és r értékeit, és tegyük fel, hogy hozzájuk egyetlen M sem megfelelő. Ez azt jelenti, hogy minden M-re az M halmaz e-eseit ki lehet szinezni r színnel úgy, hogy M-nek nincs ∗-homogén része. Tekintsük az összes lehetséges ellenpéldát adó szinezést. Ezeket egy fába rendezzük el úgy, hogy a P_{1} szinezés kisebb a P_{2} szinezésnél, ha a P_{1}-hez tartozó M_{1} kisebb a P_{2}-höz tartozó M_{2}-nél, és P_{1} éppen P_{2}-nek M_{1}]-re való megszorítása. Most ha P_{1} < P_{2}, akkor minden M_{1} < M < M_{2}-re P_{2}- nek M-re való megszorítása is ellenpélda, így az P_{1} és P_{2} között van. Ezért az előállott fának minden szinten csak véges sok rákövetkezője lehet (az M halmaz e-eseit ugyanis csak véges sok féleképpen szinezhetjük), ugyanakkor a fa nem véges magasságú. Ezért a König-lemma értelmében van benne végtelen ág, ami azt jelenti, hogy van [ω]^{e}-nek olyan r színnel való szinezése, amit tetszőleges M-ra megszorítva ellenpéldát kapunk.

Most alkalmazzuk a végtelen Ramsey tételt, ami szerint van H ⊂ ω végtelen homogén. Legyen M akkora, hogy M ∩H-ban több mint min (H) elem található. Ekkor M ∩H ∗-homogén, ellentmondásban azzal, hogy a szinezést erre az M-re megszorítva is ellenpéldát kell kapnunk.

A bizonyításban a végtelen Ramseyre való hivatkozást nem lehet kikerülni, amit az alábbi tétel mutat:

2. Tétel (Paris-Harrington) A fenti kombinatorikus elv nem bizonyítható a Peano Aritmetika szokásos axiómarendszerében.

Bizonyítás. Konstruálunk egy 𝔄 modellt, amiről a következőket fogjuk megmutatni:

(i) 𝔄 Peano modell;

(ii) 𝔄-ban a ∀e ∀r ∃M M → (∗)_{r}^{e} egy (Peano-beli) következménye nem igaz.

Mielőtt a konstrukcióra rátérnénk, először a ∗ partíció reláció néhány erősítéséről megmutatjuk, hogy (a Peano aritmetikában) ekvivalens az eredeti állítással.

1. Lemma Előírhatjuk, hogy a H ∗-homogén minimális eleme legalább egy előre adott k szám legyen.

Bizonyítás. Ezt k-ra vonatkozó indukcióval bizonyítjuk. Az k = 0-ra ez éppen az eredeti állítás, úgy hogy tegyük fel, hogy az állítást k-ra már tudjuk: legyen adva e és r, és legyen M akkora, hogy [M]^{e}-et (r+1) színnel színezve mindig kapunk olyan H ∗-homogént, melynek minimális eleme legalább k. Legyen most adva [M]^{e} egy r színű partíciója, és definiáljunk egy (r + 1) színű partíciót a következőképpen: A ∈ [M]^{e} színe legyen a megadott ha k nem az A minimális eleme, egyébként legyen az (r + 1)-edik szín. Indukciós feltevésünk szerint van H ⊂ M ∗-homogén, melynek minimális eleme legalább k. H-ban legalább e + 1 elem van, így van olyan A ∈ [H]^{e} is, melyben a minimális elem nem k, vagyis A színe nem r + 1. Ezért H egyetlen e-esének a színe sem lehet r + 1, vagyis k ∉ H, tehát H minimális eleme legalább k + 1, ahogyan kívántuk.

2. Lemma Egyetlen szinezés helyett megkövetelhetjük, hogy H legyen homogén előre megadott j szinezés mindegyikére.

Bizonyítás. Legyenek a szinezések f_{1}, …, f_{s}, és mondjuk f_{i} az [M]^{e}-t r_{i} színnel szinezi. Definiáljuk [M]^{e} egyetlen, ∏_{i<s} r_{i} színnel való f szinezését úgy, hogy A ∈ [M]^{e} színe legyen éppen ⟨f_{1}(A),…, f_{s}(A)⟩. Ha H ∗-homogén az f szinezésre, akkor persze homogén lesz az f_{1}, …, f_{s} szinezések mindegyikére is.

3. Lemma Tegyük fel, hogy ∀e ∀r ∃M M → (∗)_{r}^{e}. Akárhogyan is adunk meg s darab (nem feltétlenül ugyanannyi argumentumú) szinezést és egy k számot, létezik olyan ∗-tulajdonságú H halmaz, melynek minimális eleme nagyobb k-nál, és amely homogén az összes szinezésre.

Bizonyítás. Legyen az i-edik szinezés e_{i} argumentumú, és legyen e = max {e_{i}}. Minden i-re szinezzük ki [M]^{e} egy A elemét a következőképpen. Soroljuk fel [A]^{e_{i}} elemeit mondjuk lexikografikusan növő sorrendben és mindegyikhez írjuk fel annak az i-edik szinezés szerinti színét. Így egy szín 1 és r_{i} közötti

számok \binom{e}{e_{i}} hosszú sorozata. Ezt minden i-re tegyük meg. Az előző két lemma szerint ha M elég nagy

volt, akkor található olyan H ⊂ M, ami ∗-homogén az összes így definiált e-es szinezésekre, továbbá minimális eleme nagyobb mint k és nagyobb mint 2e.

Állítjuk, hogy ekkor H megfelelő homogén lesz. Világos, hogy ∗-tulajdonságú és hogy minimális eleme legalább k. Az kell, hogy a megadott szinezések mindegyikére homogén. H minimális eleme legalább 2e, így H-ban van több mint 2e elem. Vegyünk egy A ∈ [H]^{e} halmazt, és abban két különböző e_{i}-set, B_{1}-et és B_{2}-t. Mivel H-nak van elég sok különböző eleme, azért biztosan találunk olyan A_{1} és A_{2} ∈ [H]^{e} halmazokat, hogy A_{1}-ben B_{1} és A_{2}-ben B_{2} a fenti felsorolás szerint ugyanannyiadik (azt mondjuk, hogy B_{1} és B_{2} ikrek). De A_{1}-nek és A_{2}-nek az i-edik szinezésből kapott (vektor)színe ugyanaz, tehát B_{1}-nek és B_{2}-nek mint ikreknek az i-edik szinezés szerint is ugyanolyan színűeknek kell lenniük. Ha pedig B_{1} és B_{2} nem esne ugyanabba az e-esbe, akkor fedjük le mindkettőt egy-egy e-essel, mondjuk B_{1} ⊂ A_{1} és B_{2} ⊂ A_{2}. Most B_{1}-nek van egy ikre A_{2}-ben, aminek (megintcsak H homogenitása miatt) ugyanaz az i szerinti színe mint B_{1}-nek, s az iker színe az előek szerint megegyezik B_{2} színével.

Az eddigiekben a partícióreláció következményeivel foglalkoztunk. Most azt vizsgáljuk meg, hogyan lehet a Peano aritmetikában formalizálni a fenti gondolatmenetet. Nekünk egy kicsit többre lesz szükségünk, nevezetesen arra, hogy a fenti formulák felírhatók úgy is, hogy a bennük szereplő kvantorokat tudjuk felülről korlátozni a szabad változók (2^{x}-et is használó) kifejezéseivel.

4. Lemma Legyen M ≥ n > 10, és u_{1}, u_{2}, …, u_{n} mindegyike kisebb M-nél. Ekkor az ⟨u_{1},…, u_{n}⟩ sorozat kódja (Gödel-száma) kisebb mint M^{n^{3}}.

Bizonyítás. Emlékeztetőül az ⟨u_{1},…, u_{n}⟩ sorozat kódja u = π(x, b), ahol π a párzófüggvény, és rem(x, 1 + (i + 1)b) = u_{i}, ahol u_{0} = n. Ilyen b-nek megfelel például az a szám, amelyik az összes u_{i}-nél nagyobb és osztható (n + 1)!-sal. Az x is biztosan kisebb mint a megfelelő 1 + (i + 1)b értékek szorzata, így

b ≤ max {M, (n + 1)!} < M·n^{n},
x ≤ (n + 1)!(b + 1)^{n},
u < x^{2}b^{2} ≤ M^{2n}·(b + 1)^{2+2n} ≤ M^{2+4n}·n^{2n+2n^{2}} < M^{n^{3}},

ahogyan állítottuk.

Legyen Θ(\overline{u}, \overline{z}) egy kvantormentes, csak összeadás- és szorzásjelet tartalmazó Peano formula, ahol Θ-ban csak a felírt szabad változók szerepelnek, és azokat két részre osztottuk: \overline{u} ℓ-es, \overline{z} pedig s-es.

Definíció Legyenek \overline{x} és \overline{y} elemei [ω]^{s}-nek és legyen r ∈ ω. Azt mondjuk, hogy \overline{x} ≡_{r} \overline{y} (mod Θ), ha minden \overline{u} < r esetén

𝔑 ⊧ (∃z_{1} < x_{1}) (∀z_{2} < x_{2}) … Θ(\overline{u}, \overline{z}) ↔ (∃z_{1} < y_{1}) (∀z_{2} < y_{2}) … Θ(\overline{u}, \overline{z}).

Definiáljuk még az F_{Θ} szinezést ω (1 + 2s)-esein a következőképpen:

F_{Θ}(a, \overline{x}, \overline{y}) = \{ \begin{matrix}1 & ha \overline{x} ≡_{r} \overline{y} (mod Θ) \\ 0 & egyébként, \end{matrix}

ahol r a legnagyobb olyan egész, amire még s·(2^{r^{ℓ}} + 1) ≤ a.

5. Lemma Ha H ∗-homogén F_{Θ}-ra, akkor minden (2s + 1)-ese 1 színű.

Bizonyítás. Legyen H = {z_{1}, z_{2},…, z_{n}} nagyság szerint. Legyen a = z_{1}, osszuk H-t s hosszúságú blokkokra. Ezek száma \frac{n−1}{s} ≥ \frac{a}{s} hiszen n > z_{1} = a. Válasszuk az x_{1}, …, x_{s} értékeket egy blokkból. Egy rögzített \overline{x} mellett minden lehetséges \overline{u} értékre (ebből összesen r^{ℓ} darab van) írjuk fel, hogy

(∃z_{1} < x_{1}) (∀z_{2} < x_{2}) … Θ(\overline{u}, \overline{z})

igaz, vagy hamis. Mivel ez r^{ℓ} hosszú igaz/hamis sorozat, belőle összesen 2^{r^{ℓ}} féle képzelhető el. Blokkból viszont 2^{r^{ℓ}} + 1 ≤ a/s miatt ennél több van, így lesz két olyan \overline{x} és \overline{y} blokk, amikre minden lehetséges \overline{u} mellett a megfelelő formulák egyszerre igazak illetve hamisak. Ez pedig azt jelenti, hogy \overline{x} ≡_{r} \overline{y} (mod Θ), vagyis az ⟨a, \overline{x}, \overline{y}⟩ színe 1. S mivel H homogén volt, az összes (2s + 1)-ese ugyanolyan színű, tehát 1-es.

6. Lemma Az alábbi k és z szabad változókkal rendelkező állítás felírható Δ_{0}^{∗} formulaként: “ha k éppen az ⟨ℓ, s, ⌜Θ⌝⟩ sorozat Gödel-száma, akkor z egy F_{Θ} szinezésre nézve ∗-homogén sorozat kódja.”

Bizonyítás. Emlékeztetünk arra, hogy Δ_{0}^{∗} formulákban a kvantorokat valamilyen (hatványozást is megengedő) kifejezéssel kell korlátoznunk. Először is, mivel Θ kvantormentes, az a háromváltozós állítás, melynek argumentumai Θ, \overline{u} és \overline{z} Gödel-számai, és megmondja, hogy, Θ a megadott értékelés mellett igaz-e vagy hamis, Δ_{0}^{∗}. Ez a formula ugyanis úgy írható fel, hogy “van olyan sorozat, melynek tagjai (formula,érték) párok, az utolsó tagjában a formula éppen Θ, a párja a Θ értéke; minden tagja az előzőekből a (kvantormentes) formula felépítésének szabályai szerint áll elő (például ha egy formula φ ∨ ψ, akkor φ és ψ a sorozatban korábban előfordul, és az értéke pontosan akkor igaz, ha vagy φ vagy ψ értéke igaz volt), a változók értéke pedig az \overline{u} és \overline{z} szerint van megadva.” Az egyetlen korlátozandó érték a sorozat kódja. Mivel Θ részformuláinak száma legfeljebb ⌜Θ⌝, azért a sorozatnak legfeljebb ⌜Θ⌝ < k eleme van, mindegyik elem Θ egy részformulája plusz egy igaz/hamis érték, így kisebb mint ⌜Θ⌝^{2} < k^{2}. A 4. lemma szerint tehát a sorozat kódja kisebb (k^{2})^{k^{3}} = k^{2k^{3}} < 2^{2k^{4}}.

Másodszor az, ami ⟨ℓ, s, ⌜Θ⌝⟩ és \overline{x} Gödel-számaiból valamint r-ből megmondja, hogy (∀\overline{u} < r) (∃z_{1} < x_{1}) (∀z_{2} < x_{2}) … Θ(\overline{u}, \overline{z}) igaz-e vagy sem, szintén Δ_{0}^{∗}. Ehhez vegyük azt a sorozatot, melynek elemei az összes lehetséges ℓ + s hosszúságú sorozatok, melyekben az első ℓ elem mindegyike kisebb mint r, a második s elem közül a j-edik kisebb mint x_{j}. Az elemek értéke így legfeljebb (⌜\overline{x}⌝ + r)^{(ℓ+s)^{3}}, s mivel ez egyúttal a sorozat hosszára is korlát, megintcsak kaptunk egy hatványfüggvénnyel kifejezhető korlátot. Vegyünk még egy ugyanilyen hosszúságú sorozatot, melynek elemei igaz–hamis értékek s + 1 hosszú sorozatai (a fenti korlát most is működik) a következő tulajdonsággal. Egy ⟨\overline{u}, \overline{z}⟩ (ℓ + s) méretű sorozathoz tartozó (s+1)-es utolsó eleme a Θ(\overline{u}, \overline{z}) értéke (ez Δ_{0}^{∗}, lásd fentebb). Minden 0 < j ≤ s-re az s + 1-es j-edik elemét úgy kapjuk meg, hogy megvizsgáljuk mindazokat az ⟨\overline{u}, \overline{z}′⟩-hoz tartozó s + 1-esek j + 1-edik elemét, ahol \overline{z} és \overline{z}′ csak a j-edik helyen tér el. Ha most j páratlan, és a megvizsgált elemek között volt igaz, akkor ez az érték is legyen igaz; ha j páros, akkor ez az érték pontosan akkor igaz, ha minden megvizsgált elem igaz. Végül egy s+1-es első (nulladik) eleme (ez felel meg a (∀\overline{u} < r) résznek) akkor igaz, ha a sorozat összes j = 1-es indexű eleme igaz volt. A fenti formula igaz, ha az s + 1-esek közül bármelyikben (vagy ami ugyanaz, az összesben) a nulladik elem igaz.

A fenti csekély módosításával kapjuk, hogy ⟨ℓ, s, ⌜Θ⌝⟩, a, \overline{x} és \overline{y}-ból egy Δ_{0}^{∗} formulával kaphatjuk meg F_{Θ}(a, \overline{x}, \overline{y}) értékét. Ehhez megjegyezzük, hogy r < a és azt hogy r tényleg a maximális olyan, amire s·(2^{r^{ℓ}} + 1) ≤ a, szintén könnyen felírható.

Végül a keresett állítás: z egy ∗-homogén kódja, ha minden z-beli elemekből álló (2s+1)-es sorozatra F_{Θ}(a, \overline{x}, \overline{y}) = 1. A z sorozat elemei kisebbek z-nél, az összes lehetséges (2s + 1)-es száma legfeljebb z^{2s+1} < z^{2k} és mindegyik Gödel-száma kisebb mint z^{(2s+1)^{3}}. Következésképp az ezeket tartalmazó sorozat Gödel-száma legfeljebb (z^{(2s+1)^{3}})^{z^{6k}}. (Az, hogy az összes (2s+1)-es megtalálható-e a sorozatban, könnyen felírható: akárhogy veszünk ki egy (2s + 1)-est és cseréljük ki bármelyik elemét egy másikra, az is benne kell legyen a sorozatban.) Ezen (2s + 1)-esek mindegyikére F értéke 1 kell hogy legyen, ezt pedig épp az előbb írtuk fel.

Definíció Legyenek ℓ és s pozitív természetes számok, és definiáljuk pároknak egy szinezését a következőképpen:

G_{ℓ,s}(a, b) = { 0  ha b < 2a 1  ha 2a ≤ b ≤ 2^{a} 2  ha 2^{a} < b ≤ 2^{2^{a}} 3  ha a < log log b ≤ 2a 4  ha 2a < log log b ≤ 3a ⋮ ℓ + s + 2 ha (ℓ + s)a < log log b ≤ (ℓ + s + 1)a ℓ + s + 3 egyébként.

7. Lemma Legyen H ⊂ [3, ω) ∗-homogén G_{ℓ,s}-re. Ekkor H bármely két szomszédos z_{k} és z_{k+1} elemére

(i) 2^{z_{k}} < z_{k+1};

(ii) 2^{2^{z_{k}}} < z_{k+1};

(iii) s·(2^{z_{k}^{ℓ}} + 1) < z_{k+1}.

Bizonyítás. Legyen z_{1} < z_{2} < z_{3} < … H összes eleme nagyság szerinti felsorolásban. Mivel H-nak n = z_{1}-nél több eleme van, azért H-ban van n + 1 indexű elem is, és ennek értéke legalább z_{1} + n = 2z_{1}. A (z_{1}, z_{n+1}) pár G szerinti színe a fenti definíció alapján nem 0, s mivel H homogén, azért tetszőleges két elemének színe sem lehet 0. Ez azt jelenti, hogy például (z_{1}, z_{2}) színe sem 0, azaz 2z_{1} ≤ z_{2}, továbbá ugyanezért 2z_{2} ≤ z_{3}, stb. Ebből z_{n+1} ≥ 2^{n}z_{1} > 2^{z_{1}} (z_{1} ≥ 3 alapján), vagyis (z_{1}, z_{n+1}) színe 1 sem lehet. Ezért bármely két szomszédos elem színe is legalább 2, vagyis 2^{z_{k}} < z_{k+1}, amivel igazoltuk (i)-t.

Most z_{1} ≥ 3 miatt H-ban van legalább négy elem, és z_{3} > 2^{z_{2}} > 2^{2^{z_{1}}} . Ezért (z_{1}, z_{3}) színe, és így egyetlen pár színe sem lehet 2 sem, ami (ii)-t adja. Ezt másképp felírva log log z_{3} > z_{2} és log log z_{2} > z_{1}. Most ezekből

log log z_{3} > z_{2} > 2 log log z_{2} > log log z_{2} + z_{1}

(hiszen z_{2} ≥ 4 miatt még z_{2} ≥ 2 log z_{2} is fennáll). Következésképp log log z_{3} és log log z_{2} nem eshet ugyanabba a z_{1} hosszú intervallumba. Ez pedig azt jelenti, hogy (z_{1}, z_{2}) és (z_{1}, z_{3}) nem lehet mindkettő ugyanolyan 3, 4, …, ℓ + s + 2 színű, tehát a homogén színe csak ℓ + s + 3 lehet. Ekkor viszont

log log z_{k+1} > (ℓ + s + 1)z_{k} > 1 + s + ℓ log z_{k} > log(1 + s + z_{k}^{ℓ}) > log(1 + log s + z_{k}^{ℓ}) > log log(s·(2^{z_{k}^{ℓ}} + 1)),

amiből z_{k+1} > s·(2^{z_{k}^{ℓ}} + 1), ahogyan kívántuk.

8. Lemma Az alábbi állítás felírható Δ_{0}^{∗} formulaként: “ha k éppen az ⟨ℓ, s⟩ sorozat Gödel-száma, akkor z egy G_{ℓ,s} szinezésre ∗-homogén sorozat kódja, aminek minimális eleme legalább 3.”

Bizonyítás. Az előzőekhez hasonlóan csak azt kell megfogalmaznunk egy Δ_{0}^{∗} formulával, hogy G(a, b) = ℓ + s + 3, vagyis hogy log log b > (ℓ + s + 1)a. Ez pedig a korábbiak után már egyszerű.

Definíció Legyen α(k, z) a következő Δ_{0}^{∗} formula: “minden olyan ⟨ℓ, s⌜Θ⌝⟩ hármasra, melynek Gödelszáma kisebb mint k, z egy, az F_{Θ} szinezésre és a G_{ℓ,s} szinezésre is ∗-homogén is sorozat kódja; továbbá z minimális eleme legalább k + 1.”

Az 6. és 8. lemmák alapján ez tényleg felírható Δ_{0}^{∗} formulaként.

3. Tétel Az ∀k ∃z α(k, z) formula Peano-beli következménye a Paris-Harrington féle ∀e ∀r ∃M M → (∗)_{r}^{e} partíció relációnak.

Bizonyítás. Minden szóbajövő F_{Θ} és G_{ℓ,s} szinezés legfeljebb (2k +1)-esekhez rendel szineket, továbbá legfeljebb 2k különböző színezés jön szóba. A 3. lemma pedig éppen azt mondja ki, hogy a közös ∗- homogén halmaz létezése következik a fenti partíció relációból. (Az ottani bizonyítás a fentiek mintájára különösebb nehézségek nélkül formalizálható.)

Minden k ∈ ω-ra nézzük mindazokat a z-ket, melyekre 𝔑 ⊧ α(k, z), és legyen z^{(k)} ezek közül a minimális. A z^{(k)} egy növő sorozat kódja, melynek minimális eleme nagyobb mint k, következésképp n_{k} elemszáma k-nál több.

Definíció Minden j ∈ ω-ra definiáljuk a h_{j} : ω → ω függvényeket a következőképpen:

h_{j}(k) = \{ \begin{matrix}z_{j}^{(k)} : a z^{(k)} sorozat j-edik tagja ha j < n_{k}; \\ a z^{(k)} sorozat utolsó tagja, ha j ≥ n_{k}. \end{matrix}

9. Lemma k < h_{0}(k), 2^{k} < h_{1}(k) ha k > 2, továbbá minden j ∈ ω-ra véges sok k kivételével 2^{2^{h_{j} (k)}} < h_{j+1}(k).

Bizonyítás. A lemma első állítása abból következik, hogy z_{k} minimális eleme legalább k+1. A második a 7. lemma (i) állítása, a harmadik pedig a 7. lemma (ii) részéből következik k > j esetén, ekkor ugyanis a z^{(k)} sorozatnak biztosan van j + 1-edik tagja is.

Definíció Legyen

F = {g ∈ ^{ω}ω : ∃j ∈ ω ∀i ∈ ω g(i) < h_{j}(i)}

és legyen D egy nem triviális ultraszűrő ω-n. Az F/D faktorstruktúra definíciója a szokásos. Egy f ∈ F-re f^{∗} jelöli f ekvivalencia osztályát.

Megjegyezzük, hogy F/D-ben az összeg, szorzat és a 2^{x} függvény is definiálva van, mivel véges sok argument kivételével h_{j} · h_{j} < h_{j+1} valamint 2^{h_{j}} < h_{j+1}.

10. Lemma Legyen Ψ(x_{1},…, x_{n}) egy Δ_{0}^{∗} formula. Ekkor F/D ⊧ Ψ(f_{1}^{∗},…, f_{n}^{∗}) akkor és csak akkor, ha

{i ∈ ω : 𝔑 ⊧ Ψ(f_{1}(i),…, f_{n}(i))} ∈ D.

Bizonyítás. Kvantormentes formulákra ez a definíció, egyébként mert F zárt a ≤-re.

11. Lemma Legyen \overline{g} ∈ F, \overline{g} ≤ h_{a_{0}} és Θ(\overline{y}, \overline{z}) egy kvantormentes Peano formula, melyben nem szerepel a hatványozás. Ekkor a következők ekvivalensek:

(i) F/D ⊧ ∃z_{1}∀z_{2} … Θ(\overline{g}^{∗}, \overline{z});

(ii) F/D ⊧ (∃z_{1} < h_{a_{1}}^{∗}) (∀z_{2} < h_{a_{2}}^{∗}) … Θ(\overline{g}^{∗}, \overline{z}) valamely a_{0} + 1 < a_{1} < … < a_{s}-re;

(iii) F/D ⊧ (∃z_{1} < h_{a_{1}}^{∗}) (∀z_{2} < h_{a_{2}}^{∗}) … Θ(\overline{g}^{∗}, \overline{z}) minden a_{0} + 1 < a_{1} < … < a_{s}-re.

Bizonyítás. A kvantorok számára vonatkozó indukcióval. Ha nincs kvantor, akkor az állítás semmitmondó, tehát igaz. (i)⇒(ii): Legyen f ∈ F olyan, ami mutatja, hogy a megfelelő z_{1} létezik, azaz F/D ⊧ ∀z_{2} … Θ(\overline{g}^{∗}, f^{∗}, \overline{z}); tegyük fel, hogy f < h_{b_{1}}, ahol b_{1} > a_{0} + 1. Ekkor az indukciós feltevés szerint ( f-et a \overline{g} paraméterek közé soroljuk) van b_{1} + 1 < b_{2} < … < b_{s}, hogy F/D ⊧ (∀z_{2} < h_{b_{2}}^{∗}) … Θ(\overline{g}^{∗}, f^{∗}, \overline{z}), és ekkor tényleg F/D ⊧ (∃z_{1} < h_{b_{1}}) (∀z_{2} < h_{b_{2}}^{∗}) … Θ(\overline{g}^{∗}, z_{1}, \overline{z}) valamely a_{0} + 1 < b_{1} < … < b_{s}-re. (ii)⇒(iii): A 10. lemma miatt (ii) akkor és csak akkor, ha

\{k ∈ ω : 𝔑 ⊧ (∃z_{1} < h_{a_{1}}(k)) (∀z_{2} < h_{a_{2}}(k)) … Θ(\overline{g}(k), \overline{z})\} ∈ D.

Legyen k elég nagy; ekkor {h_{j}(k) : j ∈ ω} ∗-homogén az F_{Θ} szinezésre, vagyis ha a_{1} < … < a_{s} és b_{1} < … < b_{s}, akkor h\overline{a}(k) ≡_{r} h\overline{b}(k) (mod Θ), vagyis minden \overline{u} < r esetén

(∃z_{1} < h_{a_{1}}(k)) (∀z_{2} < h_{a_{2}}(k)) … Θ(\overline{u}, \overline{z}) ⇔ (∃z_{1} < h_{b_{1}}(k)) (∀z_{2} < h_{b_{2}}(k)) … Θ(\overline{u}, \overline{z}).

Még csak azt kell észrevennünk, hogy a = h_{a_{0}+1} < h_{a_{1}} választással h_{a_{0}} ≤ r (ez a 7. lemma (iii) állítása), tehát \overline{g}(k) ≤ h_{a_{0}} ≤ r, s az állítás következik. (iii)⇒(i): azt mutatjuk meg, hogy ¬(i)⇒¬(iii). Ha F/D |̸= ∃z_{1}∀z_{2} … Θ(\overline{g}^{∗}, \overline{z}), akkor F/D ⊧ ∀z_{1}∃z_{2} … ¬Θ(\overline{g}^{∗}, \overline{z}). Legyen most b_{1} > a_{0} + 1 tetszőleges, és f ∈ F, f < h_{b_{1}}, ekkor F/D ⊧ ∃z_{2} … ¬Θ(\overline{g}^{∗}, f^{∗}, \overline{z}). Az indukciós feltevés szerint (eggyel kevesebb kvantor szerepel) ekkor tetszőleges b_{1} + 1 < b_{2} < … < b_{s} értékre F/D ⊧ (∃z_{2} < h_{b_{2}}) … ¬Θ(\overline{g}^{∗}, f^{∗}, \overline{z}). Rögzítsük most a b_{1} + 1 < b_{2} < … < b_{s} értékeket tetszőlegesen, ezek minden f < h_{b_{1}}-re jók, tehát

F/D ⊧ (∀z_{1} < h_{b_{1}}) (∃z_{2} < h_{b_{2}}) … ¬Θ(\overline{g}^{∗}, \overline{z}).

Ez mutatja, hogy (iii) nem teljesül.

4. Tétel F/D Peano-modell.

Bizonyítás. F/D-ben a teljes indukció kivételével minden Peano axióma igazsága közvetlenül adódik a struktúra definíciójából továbbá abból, hogy ez egy jó definíció. Tehát csak az indukció kell. Legyen ehhez Φ(u, \overline{p}) olyan Peano formula melyben nem szerepel a hatványozás (ez elég), \overline{p} ∈ F, és tegyük fel, hogy

F/D ⊧ Φ(0^{∗}, \overline{p}^{∗}) ∧ ∀x (Φ(x, \overline{p}^{∗}) → Φ(x + 1, \overline{p}^{∗}).

Tegyük fel mindjárt, hogy Φ prenex alakú, azaz ∃z_{1} ∀z_{2} … Θ(x, \overline{p}, \overline{z}). Legyen még g ∈ F tetszőleges, és a_{0} akkora, hogy g, \overline{p} < h_{a_{0}}. Azt akarjuk megmutatni, hogy F/D ⊧ Φ(g^{∗}, \overline{p}^{∗}). A 11. lemma szerint tetszőlegesen rögzítve az a_{0} + 1 < a_{1} < … < a_{s} számokat

F/D ⊧ Φ(0, \overline{p}^{∗}) ⇔ F/D ⊧ (∃z_{1} < h_{a_{1}}^{∗}) (∀z_{2} < h_{a_{2}}^{∗}) … Θ(0^{∗}, \overline{p}^{∗}, \overline{z}^{∗}).

Jelölje ez utóbbi Δ_{0}^{∗} (valójában Δ_{0}) formulát Ψ(0^{∗}, \overline{p}^{∗}, \overline{z}^{∗}). Tudjuk ugyancsak a 11. lemma alapján, hogy tetszőleges f ≤ g-re

F/D ⊧ Φ(f^{∗}, \overline{p}^{∗}) ⇔ F/D ⊧ Ψ(f^{∗}, \overline{p}^{∗}, h∗ ; \overline{a}).

Következésképp

F/D ⊧ Φ(0^{∗}, \overline{p}^{∗}, h∗ ; \overline{a}) ∧ (∀x < g^{∗}) (Ψ(x, \overline{p}^{∗}, h∗ ; \overline{a}) → Ψ(x + 1, \overline{p}^{∗}, h∗ ; \overline{a})).

Ez egy Δ_{0}^{∗} formula, tehát a 10. lemma alapján ez ultraszűrő sok helyen igaz, viszont azokon a helyeken a Ψ formula a g(j) helyen is igaz, tehát megint csak a 10. lemma szerint

F/D ⊧ Ψ(g^{∗}, \overline{p}^{∗}, h∗ ; \overline{a}).

Újfent alkalmazva a 11. lemmát kapjuk, hogy F/D ⊧ Φ(g^{∗}, \overline{p}^{∗}), ahogyan kívántuk.

A következő állítás adja a Paris-Harrington tétel utolsó még hiányzó láncszemét:

5. Tétel F/D |̸= ∀k ∃z α(k, z).

Az a bizonyos k, amire nem fogunk megfelelő z sorozatot találni, éppen az identitásfüggvény ekvivalencia osztálya lesz:

F/D |̸= ∃z α(Id^{∗}, z).

Először is, Id ∈ F, mivel j < h_{0}(j). Ha most g ∈ F ekvivalencia osztálya mégis ilyen volna, akkor lévén α egy Δ_{0}^{∗} formula, a 10. lemma szerint ultraszűrő sok k ∈ ω értékre

𝔑 ⊧ α(k, g(k)).

Tudjuk azt is, hogy g < h_{j} valamilyen j-re. Választva egy j-nél nagyobb k-t, g(k) < h_{j}(k) = z_{j}^{(k)} < z^{(k)}, viszont z^{(k)} definíciója szerint ő a legkisebb, amivel 𝔑 ⊧ α(k, z) teljesül. Az ellentmondás bizonyítja az állításunkat.