 |
|
| Science Forum Index » Logic Forum » O-PA, CON(ZF) and non-standard moels of ZF.... |
|
Page 1 of 2 Goto page 1, 2 Next |
|
| Author |
Message |
| Marina Gotovchits... |
 Posted: Wed Oct 28, 2009 1:09 am |
|
|
|
Guest
|
Let O-PA be Peano Arithmetic extended with the omega.rule. As is well
known, O-PA is complete, and for any aithmetically true sentence A, O-
PA "proves" A. (Or so we think, unless we suffer from certain highly
finitist, or ultra-predicativist, qualms, e.g. à la Leonard Nelson.)
Suppose ZF is consistent. It then seems that an arithmetical sentence
to the effect CON(ZF) is true. So CON(ZF) should hold in O-PA.
Now, does this not mean that if ZF is consistent then there is a non-
standard model of ZF in O-PA?
If right, how is the situation with regard to the 1-consistency of
certain extensions of ZF. Let e.g. G be the theory ZFC + LCA, where
LCA is some large cardinal axiom. If G is 1-consistent, it again seems
that this can be expressed in an arithmetical sentence 1-CON(G), and
since true, 1-CON(G) will hold in O-PA. Does this mean that there is a
non-standard 1-consistent model of G in O-PA? |
|
|
| Back to top |
|
|
|
| Marina Gotovchits... |
| Posted: Wed Oct 28, 2009 1:19 am |
|
|
|
Guest
|
On 28 Okt, 12:09, Marina Gotovchits <renessa... at (no spam) gmail.com> wrote:
[quote]Let O-PA be Peano Arithmetic extended with the omega.rule. As is well
known, O-PA is complete, and for any aithmetically true sentence A, O-
PA "proves" A. (Or so we think, unless we suffer from certain highly
finitist, or ultra-predicativist, qualms, e.g. à la Leonard Nelson.)
[/quote]
Sorry, I meant Edward Nelson, of course. |
|
|
| Back to top |
|
|
|
| Marina Gotovchits... |
| Posted: Wed Oct 28, 2009 3:34 am |
|
|
|
Guest
|
On 28 Okt, 12:19, Marina Gotovchits <renessa... at (no spam) gmail.com> wrote:
[quote]On 28 Okt, 12:09, Marina Gotovchits <renessa... at (no spam) gmail.com> wrote:
Let O-PA be Peano Arithmetic extended with the omega.rule. As is well
known, O-PA is complete, and for any aithmetically true sentence A, O-
PA "proves" A. (Or so we think, unless we suffer from certain highly
finitist, or ultra-predicativist, qualms, e.g. à la Leonard Nelson.)
Sorry, I meant Edward Nelson, of course.[/quote] |
|
|
| Back to top |
|
|
|
| Rupert... |
| Posted: Wed Oct 28, 2009 6:34 pm |
|
|
|
Guest
|
On Oct 28, 10:09 pm, Marina Gotovchits <renessa... at (no spam) gmail.com> wrote:
[quote]Let O-PA be Peano Arithmetic extended with the omega.rule. As is well
known, O-PA is complete, and for any aithmetically true sentence A, O-
PA "proves" A. (Or so we think, unless we suffer from certain highly
finitist, or ultra-predicativist, qualms, e.g. à la Leonard Nelson.)
Suppose ZF is consistent. It then seems that an arithmetical sentence
to the effect CON(ZF) is true. So CON(ZF) should hold in O-PA.
Now, does this not mean that if ZF is consistent then there is a non-
standard model of ZF in O-PA?
[/quote]
I don't understand this. How can you do model theory in the first-
order language of arithmetic?
[quote]If right, how is the situation with regard to the 1-consistency of
certain extensions of ZF. Let e.g. G be the theory ZFC + LCA, where
LCA is some large cardinal axiom. If G is 1-consistent, it again seems
that this can be expressed in an arithmetical sentence 1-CON(G), and
since true, 1-CON(G) will hold in O-PA. Does this mean that there is a
non-standard 1-consistent model of G in O-PA?[/quote] |
|
|
| Back to top |
|
|
|
| Marina Gotovchits... |
| Posted: Wed Oct 28, 2009 10:19 pm |
|
|
|
Guest
|
On 29 Okt, 05:34, Rupert <rupertmccal... at (no spam) yahoo.com> wrote:
[quote]On Oct 28, 10:09 pm, Marina Gotovchits <renessa... at (no spam) gmail.com> wrote:
Let O-PA be Peano Arithmetic extended with the omega.rule. As is well
known, O-PA is complete, and for any aithmetically true sentence A, O-
PA "proves" A. (Or so we think, unless we suffer from certain highly
finitist, or ultra-predicativist, qualms, e.g. à la Leonard Nelson.)
Suppose ZF is consistent. It then seems that an arithmetical sentence
to the effect CON(ZF) is true. So CON(ZF) should hold in O-PA.
Now, does this not mean that if ZF is consistent then there is a non-
standard model of ZF in O-PA?
I don't understand this. How can you do model theory in the first-
order language of arithmetic?
[/quote]
Is your problem that the theory is first-order? I should think not. By
the Skolem-Löwenhem Theorem, if ZF has a model, it has a countable
model. Now CON(ZF) should be ezpressible in arithmetic. Hence the
question.
[quote]
If right, how is the situation with regard to the 1-consistency of
certain extensions of ZF. Let e.g. G be the theory ZFC + LCA, where
LCA is some large cardinal axiom. If G is 1-consistent, it again seems
that this can be expressed in an arithmetical sentence 1-CON(G), and
since true, 1-CON(G) will hold in O-PA. Does this mean that there is a
non-standard 1-consistent model of G in O-PA?[/quote] |
|
|
| Back to top |
|
|
|
| Rupert... |
| Posted: Thu Oct 29, 2009 10:40 am |
|
|
|
Guest
|
On Oct 29, 7:19 pm, Marina Gotovchits <renessa... at (no spam) gmail.com> wrote:
[quote]On 29 Okt, 05:34, Rupert <rupertmccal... at (no spam) yahoo.com> wrote:
On Oct 28, 10:09 pm, Marina Gotovchits <renessa... at (no spam) gmail.com> wrote:
Let O-PA be Peano Arithmetic extended with the omega.rule. As is well
known, O-PA is complete, and for any aithmetically true sentence A, O-
PA "proves" A. (Or so we think, unless we suffer from certain highly
finitist, or ultra-predicativist, qualms, e.g. à la Leonard Nelson.)
Suppose ZF is consistent. It then seems that an arithmetical sentence
to the effect CON(ZF) is true. So CON(ZF) should hold in O-PA.
Now, does this not mean that if ZF is consistent then there is a non-
standard model of ZF in O-PA?
I don't understand this. How can you do model theory in the first-
order language of arithmetic?
Is your problem that the theory is first-order? I should think not. By
the Skolem-Löwenhem Theorem, if ZF has a model, it has a countable
model. Now CON(ZF) should be ezpressible in arithmetic. Hence the
question.
If right, how is the situation with regard to the 1-consistency of
certain extensions of ZF. Let e.g. G be the theory ZFC + LCA, where
LCA is some large cardinal axiom. If G is 1-consistent, it again seems
that this can be expressed in an arithmetical sentence 1-CON(G), and
since true, 1-CON(G) will hold in O-PA. Does this mean that there is a
non-standard 1-consistent model of G in O-PA?- Hide quoted text -
- Show quoted text -
[/quote]
Con(ZF) is an arithmetical sentence, yes. What you are calling O-PA is
basically true arithmetic, the set of arithmetical sentences which are
true in the standard model. And this will include Con(ZF) on the
assumption that ZF is consistent.
But I don't understand what it means to say "there is a nonstandard
model of ZF in O-PA". That seems to mean something like "O-PA proves
that there is a nonstandard model of ZF", but the problem is that I
cannot talk about arbitrary countable models of ZF in the first-order
language of arithmetic. I can do so in the second-order language of
arithmetic. |
|
|
| Back to top |
|
|
|
| Marina Gotovchits... |
| Posted: Thu Oct 29, 2009 1:09 pm |
|
|
|
Guest
|
On 29 Okt, 21:40, Rupert <rupertmccal... at (no spam) yahoo.com> wrote:
[quote]On Oct 29, 7:19 pm, Marina Gotovchits <renessa... at (no spam) gmail.com> wrote:
On 29 Okt, 05:34, Rupert <rupertmccal... at (no spam) yahoo.com> wrote:
On Oct 28, 10:09 pm, Marina Gotovchits <renessa... at (no spam) gmail.com> wrote:
Let O-PA be Peano Arithmetic extended with the omega.rule. As is well
known, O-PA is complete, and for any aithmetically true sentence A, O-
PA "proves" A. (Or so we think, unless we suffer from certain highly
finitist, or ultra-predicativist, qualms, e.g. à la Leonard Nelson.)
Suppose ZF is consistent. It then seems that an arithmetical sentence
to the effect CON(ZF) is true. So CON(ZF) should hold in O-PA.
Now, does this not mean that if ZF is consistent then there is a non-
standard model of ZF in O-PA?
I don't understand this. How can you do model theory in the first-
order language of arithmetic?
Is your problem that the theory is first-order? I should think not. By
the Skolem-Löwenhem Theorem, if ZF has a model, it has a countable
model. Now CON(ZF) should be ezpressible in arithmetic. Hence the
question.
If right, how is the situation with regard to the 1-consistency of
certain extensions of ZF. Let e.g. G be the theory ZFC + LCA, where
LCA is some large cardinal axiom. If G is 1-consistent, it again seems
that this can be expressed in an arithmetical sentence 1-CON(G), and
since true, 1-CON(G) will hold in O-PA. Does this mean that there is a
non-standard 1-consistent model of G in O-PA?- Hide quoted text -
- Show quoted text -
Con(ZF) is an arithmetical sentence, yes. What you are calling O-PA is
basically true arithmetic, the set of arithmetical sentences which are
true in the standard model. And this will include Con(ZF) on the
assumption that ZF is consistent.
But I don't understand what it means to say "there is a nonstandard
model of ZF in O-PA". That seems to mean something like "O-PA proves
that there is a nonstandard model of ZF", but the problem is that I
cannot talk about arbitrary countable models of ZF in the first-order
language of arithmetic. I can do so in the second-order language of
arithmetic.
[/quote]
Thanks Rupert,
I have, after having posed the question, come to see that it was ill
posed. These matters of couse all depend upon what we mean by a
"model". But it seems, and I believe uncontroverially, that this
should mean something like "there is a pair <V,e> so that V contain
the "sets" in the theory and e is a sub"set" of V2 so that ......
blah, blah". So I agree that we need to move somewhat upwards in the
hierarcy of subsystems of second-order arithmetic to have such a
countable model for ZF. My question should have been posed as
folllows, perhaps: If we have the omega-rula along the climb up the
hierarchy of subsystems os SOA, how far do we need to go in order to
have a model of ZF if ZF is consistent? Perhaps only ACA(0)? ATR(0)?
PI-1-1? Higher?
I don't see any need for talking about "arbitrary" countable models of
ZF here. |
|
|
| Back to top |
|
|
|
| Aatu Koskensilta... |
| Posted: Thu Oct 29, 2009 5:28 pm |
|
|
|
Guest
|
Marina Gotovchits <renessanse at (no spam) gmail.com> writes:
[quote]My question should have been posed as folllows, perhaps: If we have
the omega-rula along the climb up the hierarchy of subsystems os SOA,
how far do we need to go in order to have a model of ZF if ZF is
consistent?
[/quote]
WKL-0 proves the completeness theorem, and thus in particular that if ZF
is consistent it has a model.
--
Aatu Koskensilta (aatu.koskensilta at (no spam) uta.fi)
"Wovon mann nicht sprechen kann, darüber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus |
|
|
| Back to top |
|
|
|
| Marina Gotovchits... |
| Posted: Fri Oct 30, 2009 12:41 am |
|
|
|
Guest
|
On 30 Okt, 00:28, Aatu Koskensilta <aatu.koskensi... at (no spam) uta.fi> wrote:
[quote]Marina Gotovchits <renessa... at (no spam) gmail.com> writes:
My question should have been posed as folllows, perhaps: If we have
the omega-rula along the climb up the hierarchy of subsystems os SOA,
how far do we need to go in order to have a model of ZF if ZF is
consistent?
WKL-0 proves the completeness theorem, and thus in particular that if ZF
is consistent it has a model.
[/quote]
Aha! Thank you very much Aatu!! I recall Simpson's Theorem I.10.3.8
(page 36 of his Book), which states that WKL(0) is equivalent, over RCA
(0), to "Gödel's completeness theorem: every (consistent) finite, or
countable, set of sentences in the predicate calculus has a countable
model.
Does this mean that if ZF is consistent, then a countable model "lives
in" WKL(0)+the omega rule. Or do we need to go slightly higher for the
model to be representable by a "set" in a subsystem of SOA. I ask this
because Gödel's completeness theorem here may be interpreted
existentially relative to WKL(0). I.e.. GCT and WKL(0) are equivalent,
over RCA(0), so maybe WKL(0)+ the omega rule only asserts that there
IS a countable model of ZF (if ZF is consistent), without itself
exhibiting such a model. If so, when does the model itself become a
"set"? |
|
|
| Back to top |
|
|
|
| Rupert... |
| Posted: Fri Oct 30, 2009 6:56 am |
|
|
|
Guest
|
On Oct 30, 9:41 pm, Marina Gotovchits <renessa... at (no spam) gmail.com> wrote:
[quote]On 30 Okt, 00:28, Aatu Koskensilta <aatu.koskensi... at (no spam) uta.fi> wrote:
Marina Gotovchits <renessa... at (no spam) gmail.com> writes:
My question should have been posed as folllows, perhaps: If we have
the omega-rula along the climb up the hierarchy of subsystems os SOA,
how far do we need to go in order to have a model of ZF if ZF is
consistent?
WKL-0 proves the completeness theorem, and thus in particular that if ZF
is consistent it has a model.
Aha! Thank you very much Aatu!! I recall Simpson's Theorem I.10.3.8
(page 36 of his Book), which states that WKL(0) is equivalent, over RCA
(0), to "Gödel's completeness theorem: every (consistent) finite, or
countable, set of sentences in the predicate calculus has a countable
model.
Does this mean that if ZF is consistent, then a countable model "lives
in" WKL(0)+the omega rule. Or do we need to go slightly higher for the
model to be representable by a "set" in a subsystem of SOA. I ask this
because Gödel's completeness theorem here may be interpreted
existentially relative to WKL(0). I.e.. GCT and WKL(0) are equivalent,
over RCA(0), so maybe WKL(0)+ the omega rule only asserts that there
IS a countable model of ZF (if ZF is consistent), without itself
exhibiting such a model. If so, when does the model itself become a
"set"?
[/quote]
Assuming that ZF is consistent, in WKL_0+the omega rule we can prove
that there exists a model of ZF. We probably can't prove that the
natural numbers are standard in this model. Was that your question? |
|
|
| Back to top |
|
|
|
| Marina Gotovchits... |
| Posted: Fri Oct 30, 2009 7:24 am |
|
|
|
Guest
|
On 30 Okt, 17:56, Rupert <rupertmccal... at (no spam) yahoo.com> wrote:
[quote]On Oct 30, 9:41 pm, Marina Gotovchits <renessa... at (no spam) gmail.com> wrote:
On 30 Okt, 00:28, Aatu Koskensilta <aatu.koskensi... at (no spam) uta.fi> wrote:
Marina Gotovchits <renessa... at (no spam) gmail.com> writes:
My question should have been posed as folllows, perhaps: If we have
the omega-rula along the climb up the hierarchy of subsystems os SOA,
how far do we need to go in order to have a model of ZF if ZF is
consistent?
WKL-0 proves the completeness theorem, and thus in particular that if ZF
is consistent it has a model.
Aha! Thank you very much Aatu!! I recall Simpson's Theorem I.10.3.8
(page 36 of his Book), which states that WKL(0) is equivalent, over RCA
(0), to "Gödel's completeness theorem: every (consistent) finite, or
countable, set of sentences in the predicate calculus has a countable
model.
Does this mean that if ZF is consistent, then a countable model "lives
in" WKL(0)+the omega rule. Or do we need to go slightly higher for the
model to be representable by a "set" in a subsystem of SOA. I ask this
because Gödel's completeness theorem here may be interpreted
existentially relative to WKL(0). I.e.. GCT and WKL(0) are equivalent,
over RCA(0), so maybe WKL(0)+ the omega rule only asserts that there
IS a countable model of ZF (if ZF is consistent), without itself
exhibiting such a model. If so, when does the model itself become a
"set"?
Assuming that ZF is consistent, in WKL_0+the omega rule we can prove
that there exists a model of ZF. We probably can't prove that the
natural numbers are standard in this model. Was that your question?
[/quote]
No.I thought the omega rule would guarantee that the natural numbers
are standard. Am I wrong?
Let WO be the system WKL(0) + the omega-rule. From what's on the
table, as I understand it, WO prowes that (EX)(X is a model of ZF).
Here the quantifier is over sets, and not numbers, of course. The
question is wheter there, in case ZF is consistent, is a closed set-
term A such that WO proves that A is a model of ZF. |
|
|
| Back to top |
|
|
|
| Marina Gotovchits... |
| Posted: Fri Oct 30, 2009 8:50 am |
|
|
|
Guest
|
[quote]Let WO be the system WKL(0) + the omega-rule. From what's on the
table, as I understand it, WO prowes that (EX)(X is a model of ZF).
Here the quantifier is over sets, and not numbers, of course. The
question is wheter there, in case ZF is consistent, is a closed set-
term A such that WO proves that A is a model of ZF.
[/quote]
I now realize that SOA of course does not have the kind of closed set
terms I was here asking for, so that (EX)(X is a model of ZF) is as
much as we can get in SOA. (My questions are motivated from another
context.) Anyway, intuitively this says that a model of ZF exists.
Is the model transitive? |
|
|
| Back to top |
|
|
|
| Rupert... |
| Posted: Fri Oct 30, 2009 11:13 am |
|
|
|
Guest
|
On Oct 31, 5:50 am, Marina Gotovchits <renessa... at (no spam) gmail.com> wrote:
[quote]Let WO be the system WKL(0) + the omega-rule. From what's on the
table, as I understand it, WO prowes that (EX)(X is a model of ZF).
Here the quantifier is over sets, and not numbers, of course. The
question is wheter there, in case ZF is consistent, is a closed set-
term A such that WO proves that A is a model of ZF.
I now realize that SOA of course does not have the kind of closed set
terms I was here asking for, so that (EX)(X is a model of ZF) is as
much as we can get in SOA. (My questions are motivated from another
context.) Anyway, intuitively this says that a model of ZF exists.
Is the model transitive?
[/quote]
We can prove that a model exists, but we cannot prove that a well-
founded model exists, for the reasons Aatu has discussed. |
|
|
| Back to top |
|
|
|
| Marina Gotovchits... |
| Posted: Fri Oct 30, 2009 11:55 am |
|
|
|
Guest
|
On 30 Okt, 21:59, Aatu Koskensilta <aatu.koskensi... at (no spam) uta.fi> wrote:
[quote]Rupert <rupertmccal... at (no spam) yahoo.com> writes:
Assuming that ZF is consistent, in WKL_0+the omega rule we can prove
that there exists a model of ZF. We probably can't prove that the
natural numbers are standard in this model.
We can't prove in WKL_0 + all arithmetical truths that WKL_0 + all
arithmetical truths is consistent, and hence certainly not that ZFC +
all arithmetical truths is consistent (which is just another way of
saying: ZFC has an omega-model).
[/quote]
I am a bit bewildered at this point. We agreed that if ZF is
consistent, then an arithmetical sentence CON(ZF) will hold true, and
so is provable in WKL(0)+the omega-rule(=WO in the following). An
appeal to the fact that WKL(0) is equivalent, under RCA(0), to Gödel's
completeness theorem, then licenses the inference that WO proves that
there is a model of ZF.
OF course, WO cannot prove its own consistency. But is CON(WO) at all
a well-formed sentence? For a recursively axiomatizable theory like ZF
we indeed have an arithmetical provability predicate and so can define
CON(ZF). But it seems to me that we do not have an arithmetical
provability predicate for WO. So it is not clear to my mind what the
statement "WO is consistent" should mean in arithmetical terms, and
how it relates to my starting point with CON(ZF).
In my original query I also related a similar query to the 1-
consistency of certain strong theories. Let us strengthen this to
their omega consistency. We may as well concentrate on ZF. Is not OCON
(ZF) (a statement to the effect that ZF is omega consistent) also
representable as an arithmetical sentence? If so, will it not produce
an omega consistent model e.g. in WO? (If it is not so representable,
there is something crucial in one at points heated discussion between
Harvey Friedman and Solomon Feferman which I miss out on. Is it that 1-
consistency is so representable while omega-consistency is not,
perhaps?) |
|
|
| Back to top |
|
|
|
| Marina Gotovchits... |
| Posted: Fri Oct 30, 2009 12:13 pm |
|
|
|
Guest
|
On 30 Okt, 22:13, Rupert <rupertmccal... at (no spam) yahoo.com> wrote:
[quote]On Oct 31, 5:50 am, Marina Gotovchits <renessa... at (no spam) gmail.com> wrote:
Let WO be the system WKL(0) + the omega-rule. From what's on the
table, as I understand it, WO prowes that (EX)(X is a model of ZF).
Here the quantifier is over sets, and not numbers, of course. The
question is wheter there, in case ZF is consistent, is a closed set-
term A such that WO proves that A is a model of ZF.
I now realize that SOA of course does not have the kind of closed set
terms I was here asking for, so that (EX)(X is a model of ZF) is as
much as we can get in SOA. (My questions are motivated from another
context.) Anyway, intuitively this says that a model of ZF exists.
Is the model transitive?
We can prove that a model exists, but we cannot prove that a well-
founded model exists, for the reasons Aatu has discussed.
[/quote]
I think I see that, (even though the regularity axiom will hold true
in the model...).
If an omega model is not secured, it raises the question whether
minimal models can be obtained using stronger principles like Bar
Induction and Iterated Inductive Definitions beyond ACA. |
|
|
| Back to top |
|
|
|
|
|
All times are GMT - 5 Hours
The time now is Sat Dec 12, 2009 3:37 am
|
|