logika napredno (objasnjenje gradiva)

[anatomik]

u skripti koju koristim, pojavljuje mi se termin nestandarnog elementa. dakle, govori se o nestandardnom modelu PA, te se, u jednom dokazu, posebno napominje da je c nestandardni element nestandardnog modela. što tada znači nestandardni element? (termin nije definiran i prvi put se pojavljuje tek u tom dokazu).

zatim, u istom dokazu, za nestandardni element, koristi se konačan Ramseyev teorem. koliko znam, element nestandardnog modela PA ne mora biti konačan, kako onda mogu upotrijebiti konačnog Ramsey-a? Ok, u konačnom Ramseye-u ulazni podatak može biti bilo koji element modela, ali ako je tako, kako to da se proširena vezija Ramsey-a ne može dokazati u PA kao jednostavna posljedica toga da za svaki element modela bio on konačan ili beskonačan vrijedi konačni Ramsey?

imam još nejasnoća, ali evo, za početak.

[luka_m]

To znači da c nije prirodan broj (standardni model su prirodni brojevi s uobičajenim operacijama).
Kako točno izgleda teorem i dokaz?

[anatomik]

kaže u dokazu nestandarni element nestandardnog modela. znam što je nestandardan model, ali što je nestandardni element unutar nestandardnog modela?


Theorem 5.4.9 The combinatorial principle (∗) and the Paris–Harrington
Principle are not provable in Peano arithmetic.
Proof By the remarks after Lemma 5.4.4, it suffices to show that (∗) is
unprovable. Suppose that M is a nonstandard model of Peano arithmetic
and c is a nonstandard element of M. Suppose that M |= (∗). We will use
Lemma 5.4.8 to construct an initial segment of M where (∗) fails.
Because the Finite Ramsey Theorem is provable in Peano arithmetic,
there is a least w ∈ M such that M |= w → (3c + 1)2c+1
c . Let d ∈ M
be least such that if f1, . . . , fc : [d]2c+1 → d are regressive, then there is
Y ⊆ (c, d) with |Y | ≥ w and Y min-homogeneous for each fi.
Using the truth predicate for Δ0-sets, we can follow the proof of Lemma
5.4.5 inside M and obtain I ⊂ (c, d) with |I| ≥ c such that M believes I
is a set of diagonal indiscernibles for all Δ0-formulas from M with G¨odel
code at most c, free variables from v1, . . . , vc, and parameter variables from
w1, . . . , wc. In particular, I is a set of diagonal indiscernibles for all standard
Δ0-formulas.
Let x0 < x1 < . . . be an initial segment of I, and let N be the initial
segment of M with universe N = {y ∈ M : y < xi for some i = 1, 2, . . .}.
By Lemma 5.4.8, N is a model of Peano arithmetic. Clearly, c ∈ N and
d ∈ N. We claim that w ∈ N. Because the finite version of Ramsey’s
Theorem is provable in Peano arithmetic, there is w ∈ N such that N |=
w → (3c+1)2c+1
c . Because all functions from [w]2c+1 → c and all subsets
of w that are coded inMare coded in N,M |= w → (3c+1)2c+1
c . Because
w was minimal, w ≤ w and w ∈ N. By a similar argument, if d ∈ N and
N |= ∀f1, . . . , fc : [d]2c+1 → d is regressive, there is Y ⊆ (c, d) minhomogeneous
for each fi with |Y | ≥ w. Then, this is also true in M; thus,
by choice of d, d ≤ d. Because d ∈ N, this is a contradiction. Thus, (∗)
fails in N and (∗) is not provable from Peano arithmetic.

[luka_m]

Za nestandardne elemente, s wiki:
"The elements of any model of Peano arithmetic are linearly ordered and possess an initial segment isomorphic to the standard natural numbers. A non-standard model is one that has additional elements outside this initial segment". Dakle, nestandardni elementi su svi oni nakon običnih prirodnih brojeva.

Ako je Ramseyev teorem dokaziv u PA, to znači da je formula kojom se on izražava (za svaki x...) dokaziva u PA. Samim time je i istinita u svakom modelu PA. To ne znači da u svakom modelu ima isto značenje, npr. kvantifikacija u nestandardnim modelima uključuje neke nove objekte koji nisu prirodni brojevi.

"... kako onda mogu upotrijebiti konačnog Ramseya?", opet, zato što je formula kojom se izražava taj teorem dokaziva u PA. Nije bitno što model misli da ta formula izražava (priča li o prirodnim ili "beskonačnim" brojevima), zbog teorema adekvatnosti svaka dokaziva formula je istinita u svim modelima, pa tako i nestandardnima.

"kako to da se proširena vezija Ramsey-a ne može dokazati u PA kao jednostavna posljedica toga da za svaki element modela bio on konačan ili beskonačan vrijedi konačni Ramsey", ne ulazeći u to koliko ta ideja dokaza funkcionira, takav tip zaključivanja je zaključivanje "izvana". PA je formalni sustav koji (donekle, i sigurno ne potpuno) ocrtava prirodne brojeve. Kako je to formalni sustav, njegovi teoremi su samo one formule koje se mogu dokazati.

[anatomik]

razumijem. hvala puno. nešto moram proučit pa se možda javim s još kojim pitanjem.