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.
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.
|