By Frege’s Theorem, I mean the result that second-logic plus Hume’s
Principle is sufficient to prove second-order arithmetic. Hume’s
Principle is the intuitively true statement that the number of a
predicate or concept F is equal to the number of the concept G iff
there is a 1-1 correspondence between F and G. It is a well known
result that impredicative second-order logic is needed for Frege’s
theorem. My question is, what semantics is required? Would Henkin
Semantics suffice? Or is the Standard Semantics needed?
Any help would be greatly appreciated.
Thank You in Advance.
lugit…@gmail.com wrote:
> By Frege’s Theorem, I mean the result that second-logic plus Hume’s
> Principle is sufficient to prove second-order arithmetic. …
> My question is, what semantics is required? Would Henkin
> Semantics suffice? Or is the Standard Semantics needed?
> Any help would be greatly appreciated.
> Thank You in Advance.
Frege’s Theorem is a claim about what can be deduced in a certain
*second-order deductive system*. It’s a claim about a syntactic proof
relation. So Frege’s Theorem doesn’t "require" a semantics.
True, it wouldn’t be so interesting if the proof-rules weren’t
) But they are.
inituitively sound
If I recall Henkin semantics restricted to faithful models is (more
than?) enough to warrant the relevant rules.
- Hide quoted text — Show quoted text -
Peter_Smith wrote:
> lugit…@gmail.com wrote:
> > By Frege’s Theorem, I mean the result that second-logic plus Hume’s
> > Principle is sufficient to prove second-order arithmetic. …
> > My question is, what semantics is required? Would Henkin
> > Semantics suffice? Or is the Standard Semantics needed?
> > Any help would be greatly appreciated.
> > Thank You in Advance.
> Frege’s Theorem is a claim about what can be deduced in a certain
> *second-order deductive system*. It’s a claim about a syntactic proof
> relation. So Frege’s Theorem doesn’t "require" a semantics.
> True, it wouldn’t be so interesting if the proof-rules weren’t
) But they are.
> inituitively sound
> If I recall Henkin semantics restricted to faithful models is (more
> than?) enough to warrant the relevant rules.
I’m not sure what a faithful model is. My question is, is there a
"second-order deductive system" sound with respect to Henkin Semantics
under which Hume’s Principle implies second-order arithmetic? If not,
is there a second-order deductive system sound (I know it can’t
additionally be complete) with respect to Standard Semantics under
which Hume’s Principle implies Second-Order Arithmetic?
Any further help would be greatly appreciated.
Thank You in Advance.
lugit…@gmail.com wrote:
> I’m not sure what a faithful model is. My question is, is there a
> "second-order deductive system" sound with respect to Henkin Semantics
> under which Hume’s Principle implies second-order arithmetic?
The short but not-quite-accurate answer is "yes".
The longer answer is that the second-order deductive system needed for
a proof of Frege’s Theorem to go through involves a strong
comprehension principle. The deductive system is, however, sound and
complete when we restrict ourselves to Henkin models tweaked to verify
comprehension (the "faithful" models). So the relevant semantics is a
bit more structured than unrestricted "pure" Henkin semantics (but
still Henkin-style, and not as restricted as "standard semantics").
At least, I hope that’s right
- Hide quoted text — Show quoted text -
Peter_Smith wrote:
> lugit…@gmail.com wrote:
> > I’m not sure what a faithful model is. My question is, is there a
> > "second-order deductive system" sound with respect to Henkin Semantics
> > under which Hume’s Principle implies second-order arithmetic?
> The short but not-quite-accurate answer is "yes".
> The longer answer is that the second-order deductive system needed for
> a proof of Frege’s Theorem to go through involves a strong
> comprehension principle. The deductive system is, however, sound and
> complete when we restrict ourselves to Henkin models tweaked to verify
> comprehension (the "faithful" models). So the relevant semantics is a
> bit more structured than unrestricted "pure" Henkin semantics (but
> still Henkin-style, and not as restricted as "standard semantics").
> At least, I hope that’s right
Could you give me a bit more detail? I am still not understanding what
restrictions we should place on Henkin Semantics. What do you mean by
"tweaked to verify comprehension?" Doesn’t second-order logic by
definition have comprehension? Isn’t Henkin Semantics by itself
compatible with the axiom that given any wff with a free variable x,
there exists a concept (or predicate) that is true of x iff the wff is
true of x? In Robbin’s "Mathematical Logic, A First Course" for
instance, Henkin Semantics is used for second-order logic, but the
exact comprehension scheme I just stated is used. When use say
"Frege’s Theorem involves a strong comprehension principle," do you
mean that it is stronger than the one I just named? If so, what is it?
lugit…@gmail.com wrote:
> Isn’t Henkin Semantics by itself
> compatible with the axiom that given any wff with a free variable x,
> there exists a concept (or predicate) that is true of x iff the wff is
> true of x?
No. Take the following instance of comprehension principle
EXAxAy(Xxy <–> x =/= x)
That asserts the existence of an empty relation that obtains between
nothing. But since pure Henkin semantics puts no constraints on which
subsets of the domain are in the scope of the second-order quantifiers,
some Henkin structures will have no empty relations and hence not
verify this instance of comprehension.
You might find Chapters 3 and 4 of Shapiro’s book on second-order logic
help a lot here.
Peter_Smith wrote:
>So the relevant semantics is a
> bit more structured than unrestricted "pure" Henkin semantics (but
> still Henkin-style, and not as restricted as "standard semantics").
How can anyone allege that the standard semantics is "restricted"?
The standard semantics by definition is supposed to include every-
subclass-that-is[platonistically]-conceivable. The only restriction is
one AGAINST ALLOWING ANY[other] restrictions.
- Hide quoted text — Show quoted text -
Peter_Smith wrote:
> lugit…@gmail.com wrote:
> > Isn’t Henkin Semantics by itself
> > compatible with the axiom that given any wff with a free variable x,
> > there exists a concept (or predicate) that is true of x iff the wff is
> > true of x?
> No. Take the following instance of comprehension principle
> EXAxAy(Xxy <–> x =/= x)
> That asserts the existence of an empty relation that obtains between
> nothing. But since pure Henkin semantics puts no constraints on which
> subsets of the domain are in the scope of the second-order quantifiers,
> some Henkin structures will have no empty relations and hence not
> verify this instance of comprehension.
> You might find Chapters 3 and 4 of Shapiro’s book on second-order logic
> help a lot here.
Although I can’t find a flaw in your reasoning, it seems to lead to
absurd conclusions. If your reasoning is correct, than Henkin
Semantics is utterly useless, even for second-order arithmetic. This
is because even second-order arithmetic has such a comprehension
scheme. So *is* Henkin Semantics useless?
george wrote:
> Peter_Smith wrote:
> >So the relevant semantics is a
> > bit more structured than unrestricted "pure" Henkin semantics (but
> > still Henkin-style, and not as restricted as "standard semantics").
> How can anyone allege that the standard semantics is "restricted"?
> The standard semantics by definition is supposed to include every-
> subclass-that-is[platonistically]-conceivable. The only restriction is
> one AGAINST ALLOWING ANY[other] restrictions.
Well, pure Henkin semantics allows the domain of the second-order
quantifiers to be ANY subset of the powerset of the domain of the
first-order quantifiers. Standard semantics insists that there is only
ONE option for the domain of the second-order quantifiers, the domain
has to be the full powerset of the domain of the first-order
quantifiers. So, Henkin semantics allows unrestriced choice of
second-order domain; faithful Henkin semantics puts on more
restrictions; standard semantics — looked at along that dimension of
variation — involves the most restricted choice, only one choice
allowed! Sorry if you didn’t like my way of putting it, though I’m
suspect you knew very well what I was saying.
lugit…@gmail.com wrote:
> So *is* Henkin Semantics useless?
No, but we need the restriction to faithful models. Check out Shapiro,
as his is the classic modern treatment of this stuff and very clear.
> lugit…@gmail.com wrote:
> > Isn’t Henkin Semantics by itself
> > compatible with the axiom that given any wff with a free variable x,
> > there exists a concept (or predicate) that is true of x iff the wff is
> > true of x?
Peter_Smith wrote:
> No. Take the following instance of comprehension principle
> EXAxAy(Xxy <–> x =/= x)
No.
That IS NOT an an instance of the comprehension schema
that lugit gave. For starters, lugit’s WAS UNARY.
If x is lugit’s ONE free variable, then the relevant wff here is
x=/=x,
and comprehension is supposed to gurantee the existence NOT
of a binary X, but of a UNARY predicate true of and only of those x
that make this true. Can Henkin semantics fail to include the empty
UNARY predicate??
If you consider Ay[Xxy<->x=/=x] as the wff, then both X and x are free
but the comprehension schema that lugit was talking about is worrying
about the freedom of x, NOT that of X, and his comprehension principle
WILL produce a *unary* predicate from this wff, depending on the prior
definition of X. If we call this predicate P (for "Produced" from/by
the
*correctly* intended comprehension schema), then it will satisfy
Ax[Px<=df=> Ay[~Xxy] ], and regardless of your semantics or your
definition of X, this P *must* exist.
lugit’s question was about which 1st-order predicates are required by
comprehension, BEFORE it was about which 2nd-order ones are required
by the semantics.
You suggested that lugit read Shapiro.
That is all well and good, but maybe you should read Robbin
for the particular comprehension axiom he was trying to talk about.
- Hide quoted text — Show quoted text -
Peter_Smith wrote:
> george wrote:
> > Peter_Smith wrote:
> > >So the relevant semantics is a
> > > bit more structured than unrestricted "pure" Henkin semantics (but
> > > still Henkin-style, and not as restricted as "standard semantics").
> > How can anyone allege that the standard semantics is "restricted"?
> > The standard semantics by definition is supposed to include every-
> > subclass-that-is[platonistically]-conceivable. The only restriction is
> > one AGAINST ALLOWING ANY[other] restrictions.
> Well, pure Henkin semantics allows the domain of the second-order
> quantifiers to be ANY subset of the powerset of the domain of the
> first-order quantifiers. Standard semantics insists that there is only
> ONE option for the domain of the second-order quantifiers, the domain
> has to be the full powerset of the domain of the first-order
> quantifiers. So, Henkin semantics allows unrestriced choice of
> second-order domain; faithful Henkin semantics puts on more
> restrictions; standard semantics — looked at along that dimension of
> variation — involves the most restricted choice, only one choice
> allowed! Sorry if you didn’t like my way of putting it, though I’m
> suspect you knew very well what I was saying.
I think George means that in Henkin Semantics, although the set of
models is not restricted, the set of validities is restricted. In the
standard semantics, the set of models is restricted, but the set of
validities is not restricted. And restrictions on the set of
validities seem to be more important than restriction on the set of
model.
george wrote:
> > lugit…@gmail.com wrote:
> > > Isn’t Henkin Semantics by itself
> > > compatible with the axiom that given any wff with a free variable x,
> > > there exists a concept (or predicate) that is true of x iff the wff is
> > > true of x?
lugit was concerned with a logic in which we can derive Frege’s
Theorem. As I recall, that requires comprehension for relations (or
functions).
To be sure — I was merely pointing out that there was a sensible
enough reading on which what I said was OK.
george wrote:
> Can Henkin semantics fail to include the empty UNARY predicate??
Why not? The unary quantifiers in a Henkin interpretation run over some
given subset of the powerset of the domain, and there is no stipulation
that that subset contain the empty set. So yes, a particular Henkin
interpretation can fail to include the empty property. So the instance
of the unary comprehension principle EXAx(Xx <–> x=/=x) will fail.
Won’t it?
On 24 Sep 2006 09:43:14 -0700, Peter_Smith <ps…@cam.ac.uk> said:
> lugit…@gmail.com wrote:
>> So *is* Henkin Semantics useless?
> No, but we need the restriction to faithful models. Check out Shapiro,
> as his is the classic modern treatment of this stuff and very clear.
Enderton’s classic text _A Mathematical Introduction to Logic_ also has
a nice overview of 2nd-order languages with both standard semantics and
general semantics.
Peter_Smith wrote:
> george wrote:
> > Can Henkin semantics fail to include the empty UNARY predicate??
> Why not? The unary quantifiers in a Henkin interpretation run over some
> given subset of the powerset of the domain, and there is no stipulation
> that that subset contain the empty set. So yes, a particular Henkin
> interpretation can fail to include the empty property. So the instance
> of the unary comprehension principle EXAx(Xx <–> x=/=x) will fail.
> Won’t it?
This seems ridiculous to me. Similar arguments could be made about ANY
predicate, since there will be a Henkin Model that does not include it.
Yet there are axiomatizations of second-order arithmetic that are
sound with respect to Henkin Semantics, and such axiomatizations
require some form of comprehension. So by your arguments, we would
have to conclude that some sentences that are sound with respect to
Henkin Semantics do not satisfy all Henkin Models.
lugit…@gmail.com wrote:
> This seems ridiculous to me. Similar arguments could be made about ANY
> predicate, since there will be a Henkin Model that does not include it.
> Yet there are axiomatizations of second-order arithmetic that are
> sound with respect to Henkin Semantics, and such axiomatizations
> require some form of comprehension. So by your arguments, we would
> have to conclude that some sentences that are sound with respect to
> Henkin Semantics do not satisfy all Henkin Models.
It’s just a matter of terminology. One might call a Henkin model any
structure <P,M, …> where P is a subset of the powerset of M, in which
case the deductive systems you mention are unsound. Or one might put
more requirements on the models and obtain what Peter calls a faithful
model; if you require that P contain all definable subsets (and
relations, if you’re considering those) of M then the deductive systems
are sound. Nothing profound here. As a sidenote, I, too, would require a
"Henkin model" to contain all the definable subsets – the unrestricted
concept seems somewhat uninteresting.
–
Aatu Koskensilta (aatu.koskensi…@xortec.fi)
"Wovon man nicht sprechen kann, daruber muss man schweigen"
– Ludwig Wittgenstein, Tractatus Logico-Philosophicus
On Mon, 25 Sep 2006 22:56:07 +0300, Aatu Koskensilta
<aatu.koskensi…@xortec.fi> said:
- Hide quoted text — Show quoted text -
> lugit…@gmail.com wrote:
>> This seems ridiculous to me. Similar arguments could be made about ANY
>> predicate, since there will be a Henkin Model that does not include it.
>> Yet there are axiomatizations of second-order arithmetic that are
>> sound with respect to Henkin Semantics, and such axiomatizations
>> require some form of comprehension. So by your arguments, we would
>> have to conclude that some sentences that are sound with respect to
>> Henkin Semantics do not satisfy all Henkin Models.
> It’s just a matter of terminology. One might call a Henkin model any
> structure <P,M, …> where P is a subset of the powerset of M, in which
> case the deductive systems you mention are unsound. Or one might put
> more requirements on the models and obtain what Peter calls a faithful
> model; if you require that P contain all definable subsets (and
> relations, if you’re considering those) of M then the deductive systems
> are sound. Nothing profound here. As a sidenote, I, too, would require a
> "Henkin model" to contain all the definable subsets – the unrestricted
> concept seems somewhat uninteresting.
That’s how Enderton defines the notion of a general (i.e., Henkin)
structure, just FYI.
Chris Menzel wrote:
> On Mon, 25 Sep 2006 22:56:07 +0300, Aatu Koskensilta
> <aatu.koskensi…@xortec.fi> said:
>> As a sidenote, I, too, would require a "Henkin model" to contain all
>> the definable subsets – the unrestricted concept seems somewhat uninteresting.
> That’s how Enderton defines the notion of a general (i.e., Henkin)
> structure, just FYI.
I’m not quite sure how to interpret that. Enderton defines a general
structure with or without the requirement that the definable subsets be
included?
–
Aatu Koskensilta (aatu.koskensi…@xortec.fi)
"Wovon man nicht sprechen kann, daruber muss man schweigen"
– Ludwig Wittgenstein, Tractatus Logico-Philosophicus
- Hide quoted text — Show quoted text -
Aatu Koskensilta wrote:
> Chris Menzel wrote:
> > On Mon, 25 Sep 2006 22:56:07 +0300, Aatu Koskensilta
> > <aatu.koskensi…@xortec.fi> said:
> >> As a sidenote, I, too, would require a "Henkin model" to contain all
> >> the definable subsets – the unrestricted concept seems somewhat uninteresting.
> > That’s how Enderton defines the notion of a general (i.e., Henkin)
> > structure, just FYI.
> I’m not quite sure how to interpret that. Enderton defines a general
> structure with or without the requirement that the definable subsets be
> included?
> —
> Aatu Koskensilta (aatu.koskensi…@xortec.fi)
> "Wovon man nicht sprechen kann, daruber muss man schweigen"
> – Ludwig Wittgenstein, Tractatus Logico-Philosophicus
Well, I looked it up in Manzano’s "Extensions of First-Order Logic" and
it says that "All models of generalized semantics must include the set
of (parametrically) definable relations and thus the existence of these
relations are automatic validities of a 2-sorted system that should be
called second-order logic" I believe generalized semantics is the same
as Henkin Semantics, but I’m not sure.
lugit…@gmail.com wrote:
> I believe generalized semantics is the same as Henkin Semantics, but I’m not sure.
They’re used pretty much interchangeably in the literature, yes.
–
Aatu Koskensilta (aatu.koskensi…@xortec.fi)
"Wovon man nicht sprechen kann, daruber muss man schweigen"
– Ludwig Wittgenstein, Tractatus Logico-Philosophicus
lugit…@gmail.com wrote:
> I believe generalized semantics is the same as Henkin Semantics,
> but I’m not sure.
The terms are used pretty much interchangeably in the literature, yes.
–
Aatu Koskensilta (aatu.koskensi…@xortec.fi)
"Wovon man nicht sprechen kann, daruber muss man schweigen"
– Ludwig Wittgenstein, Tractatus Logico-Philosophicus
Now that we have the whole Henkin Semantics/faithful model thing out of
the way, I have another question. If the set of models under
consideration in Henkin Semantics are restricted to the "faithful
models," or those which have all definable subsets of the domain as
predicates, does there exist a formal deductive system that is both
sound and complete with respect to this semantics. Or is the classic
result about a sound and complete system with respect to Henkin
Semantics only true when the set of predicates has no requirements?
lugit…@gmail.com wrote:
> Now that we have the whole Henkin Semantics/faithful model thing out of
> the way, I have another question. If the set of models under
> consideration in Henkin Semantics are restricted to the "faithful
> models," or those which have all definable subsets of the domain as
> predicates, does there exist a formal deductive system that is both
> sound and complete with respect to this semantics.
Yes. Pick any of the standard deductive systems for second order logic,
it will be both sound and complete w.r.t. the class of (faithful) Henkin
models. (If you include the axiom of choice as a logical principle you
have to take some care, and require faithful models to contain also
choice functions, but even then the completeness proof is pretty much a
straightforward adoption of the ordinary Henkin style completeness proof
for first order logic.)
–
Aatu Koskensilta (aatu.koskensi…@xortec.fi)
"Wovon man nicht sprechen kann, daruber muss man schweigen"
– Ludwig Wittgenstein, Tractatus Logico-Philosophicus