Main Page | Report this Page
 
Science Forum Index  »  Logic Forum  »  Scott on CH in 2nd order set theory
Page 1 of 1    

Scott on CH in 2nd order set theory

Author Message
Frederick Williams
Posted: Fri Jun 30, 2006 8:45 am
Guest
In the foreword to J L Bell's Boolean-valued Models and Independence
Proofs in Set Theory (first edition), D S Scott writes

"... in second-order formulations of set theory it [that's CH]
would be decided: only we cannot know which way."

What does that mean? To start with, what is second order set theory?
My guess is that it's one in which axiom schemata are replaced with
single axioms with a "for all formulae phi" quantifier. But what would
be a second order formulation of a classes-and-sets theory? One with
quantifiers binding classes? Is the set theory in the appendix of
Kelley's topology text one of those?

--
Remove "antispam" and ".invalid" for e-mail address.
 
Aatu Koskensilta
Posted: Fri Jun 30, 2006 9:12 am
Guest
Frederick Williams wrote:
Quote:
In the foreword to J L Bell's Boolean-valued Models and Independence
Proofs in Set Theory (first edition), D S Scott writes

"... in second-order formulations of set theory it [that's CH]
would be decided: only we cannot know which way."

What does that mean?

It means that either CH or its negation is a logical consequence of the
axioms of second order set theory. CH is actually equivalent to its
being a logical consequence of these axioms, but since second order
logic is not complete the only way to know whether this is the case is
to either prove or disprove CH.

Quote:
To start with, what is second order set theory?
My guess is that it's one in which axiom schemata are replaced with
single axioms with a "for all formulae phi" quantifier.

No. The schemata are replaced by single sentences formulated using
ordinary second order quantifiers, so that the axiom schema of
separation, for example, becomes a single axiom

AxAPEyAz(z \in y iff z \in x and P(z))

where P ranges over all subcollections of the universe of model.

Quote:
But what would
be a second order formulation of a classes-and-sets theory?

Every axiom schema would be replaced with a single universal second
order axiom.

--
Aatu Koskensilta (aatu.koskensilta@xortec.fi)

"Wovon man nicht sprechen kann, daruber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
 
Aatu Koskensilta
Posted: Fri Jun 30, 2006 9:55 am
Guest
Aatu Koskensilta wrote:
Quote:
CH is actually equivalent to its being a logical consequence of these axioms,
but since second order logic is not complete the only way to know whether this
is the case is to either prove or disprove CH.

That sentence didn't come out quite as I intended. Here's an improved
version that avoids the possible ambiguity:

CH is equivalent to its being a logical consequence of these axioms,
but since second order logic is not complete the only way to know
whether that is the case is to either prove or disprove CH.

--
Aatu Koskensilta (aatu.koskensilta@xortec.fi)

"Wovon man nicht sprechen kann, daruber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
 
george
Posted: Fri Jun 30, 2006 6:42 pm
Guest
Quote:
Frederick Williams wrote:
In the foreword to J L Bell's Boolean-valued Models and Independence
Proofs in Set Theory (first edition), D S Scott writes

"... in second-order formulations of set theory it [that's CH]
would be decided: only we cannot know which way."

What does that mean?

Exactly what it says.
There are some things you do not know.

Aatu Koskensilta wrote:
Quote:
It means that either CH or its negation
is a logical consequence of the
axioms of second order set theory.

You are skipping some steps.
Logical consequence is supposed to involve equivalence
across all models. That is NOT the issue here. What IS
going on here is that the standard semantics of second-
order logic winds up privileging a single model. This sort of
moots "logical consequence".

Quote:
To start with, what is second order set theory?
My guess is that it's one in which axiom schemata are replaced with
single axioms with a "for all formulae phi" quantifier.

The schemata for the first-order versions of the axioms
ALREADY HAVE a "for all formulae phi" quantifier, or
at least "for all formulae phi with the right number of unbound
variables" quantifier. You would have to replace that with
something else.


Quote:
No.
The schemata are replaced by single sentences formulated using
ordinary second order quantifiers, so that the axiom schema of
separation, for example, becomes a single axiom

AxAPEyAz(z \in y iff z \in x and P(z))

where P ranges over all subcollections of the universe of model.

But what would
be a second order formulation of a classes-and-sets theory?

Every axiom schema would be replaced with a single universal second
order axiom.

That's not the point.
The point is that the second-order quantifiers are
intended to range over "all possible" subcollections of the
first-order domain. The fact that it is THAT "full"
collection - of - collections that is the intended domain of the
second-
order model
is what enables/requires the 2nd-order model to decide things that
are not decidable at first-order. Or so Dana Scott thinks.
What it really means for the standard semantics to have "full"
powersets is not actually as simple as people think it is.
 
Frederick Williams
Posted: Fri Jun 30, 2006 8:38 pm
Guest
Aatu Koskensilta wrote:
Quote:

Frederick Williams wrote:

But what would
be a second order formulation of a classes-and-sets theory?

Every axiom schema would be replaced with a single universal second
order axiom.

Von Neumann, Bernays, G\"odel doesn't have schema, it's finitely
axiomatizable. (Hence my question.)

--
Remove "antispam" and ".invalid" for e-mail address.
 
Aatu Koskensilta
Posted: Sat Jul 01, 2006 2:28 am
Guest
Frederick Williams wrote:
Quote:
Aatu Koskensilta wrote:
Frederick Williams wrote:

But what would
be a second order formulation of a classes-and-sets theory?
Every axiom schema would be replaced with a single universal second
order axiom.

Von Neumann, Bernays, Gödel doesn't have schema, it's finitely
axiomatizable. (Hence my question.)

That's true. "Second order NBG" doesn't mean anything determinate - in
general a first order theory does not uniquely (or even non-uniquely)
determine any second order theory in a non-trivial sense. It could be
taken to refer to a theory with second order separation for sets, i.e.
the axiom I gave in the earlier post, together with the predicative
class construction axioms. But such a theory is rather pointless.
Morse-Kelley set theory, on the other hand, can be seen as a first order
version of second order set theory, where the class variables are seen
as non-logical and certain second order logical principles such as class
comprehension are taken as non-logical first order axioms.

--
Aatu Koskensilta (aatu.koskensilta@xortec.fi)

"Wovon man nicht sprechen kann, daruber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
 
Frederick Williams
Posted: Sat Jul 01, 2006 8:08 am
Guest
george wrote:
Quote:

Frederick Williams wrote:

To start with, what is second order set theory?
My guess is that it's one in which axiom schemata are replaced with
single axioms with a "for all formulae phi" quantifier.

The schemata for the first-order versions of the axioms
ALREADY HAVE a "for all formulae phi" quantifier, or
at least "for all formulae phi with the right number of unbound
variables" quantifier.

I was distinguishing a "for all formulae phi" quantifier in the language
from a "for all formulae phi" in the metalanguage.

--
Remove "antispam" and ".invalid" for e-mail address.
 
george
Posted: Sun Jul 02, 2006 11:32 am
Guest
Quote:
Frederick Williams wrote:
But what would
be a second order formulation of a classes-and-sets theory?
.....
Von Neumann, Bernays, Gödel doesn't have schema, it's finitely
axiomatizable. (Hence my question.)

Aatu Koskensilta wrote:
Quote:
That's true. "Second order NBG" doesn't mean anything determinate

In that case, 1st-order ZFC doesn't either.
It's hard to see how ANY 1st-order set theory can be meaningfully
lifted to 2nd-order. The problem is, once you have predicates as
members of your universe of discourse, THEY ARE all sets.
They are ESPECIALLY all OF THE sets, if you are using the standard
semantics of SECOND order logic, which requires that predicate
variables be able to range over "all conceivably/metahphysically
possible"
classes (i.e. subcollections of the universe) of 0th-order objects.
To any set you could conceive of, under THIS semantics, there ALREADY
corresponds A PREDICATE. Therefore, it is simply never relevant to
allege xey. The OBVIOUSLY proper way of phrasing xey, in the context
of a 2nd-order language, is y(x) . You simply cannot draw any
meaningful
distinction between a set y and the corresponding unary predicate ?ey.
If the axioms are not present for the purpose providing a definition of
e, since e is not needed at all, since it is just predication between a
1st-
and 0th- order object of the existing universe of discourse, then how
can
you have a set theory at all?
 
george
Posted: Sun Jul 02, 2006 12:02 pm
Guest
Quote:
In the foreword to J L Bell's Boolean-valued Models and Independence
Proofs in Set Theory (first edition), D S Scott writes
"... in second-order formulations of set theory it [that's CH]
would be decided: only we cannot know which way."

Frederick Williams wrote:
Quote:
What does that mean?
To start with, what is second order set theory?
My guess is

Please don't guess. There is a standard answer.
Google it if you know how.

I'm afraid, however, that it is far from clear to me that
the standard answer can actually make any sense.

Here is an interesting treatment:
web.mit.edu/dmytro/www/NewSetTheory.htm

It alleges, in relevant part, the following:

* Higher Order Set Theory
* * Unsuccessful Attempts
....
* * * Simple attempts at higher order set theory appear trivial or
meaningless.

Continuing in that vein,

* Second order logic about sets does not increase
* expressive power either (unless one works in a
* system where the power set axiom is false),
* as second order statements about S are first order
* statements about the power set of S.
* Second order logic about V appears meaningless
* because (in the required sense) there are no proper classes.

I don't concur with this last part.
In the first place, he has not clarified what HE thinks the
"required" sense of proper classes is. In real life, there are
3 different ways for a class to be proper. It can fail to be
a member of any other class, it can be equipollent with the
class of all sets, or it can be equipollent with the domain
of discourse. In NBG these are all equivalent but under other
treatments they may not be. If the required sense is that a
set has to be a member of another class, then yes, there
are no proper classes in the required sense, at 2nd order.
But the other criteria are more complicated.

As I said in a parallel reply, the single biggest reason why
2nd-order set theory is meaningless is that set-membership too-
easily EQUATES to predication; In 2nd-order logic, if y is any set,
then there must exist a corresponding isomorphic predicate y(.)
satisfying xey <-> y(x). What happens to this when you get deeper
nested chains of membership is unfortunately unclear to me, though.
 
Barb Knox
Posted: Sun Jul 02, 2006 8:58 pm
Guest
In article <1151861555.396384.225670@75g2000cwc.googlegroups.com>,
"george" <greeneg@cs.unc.edu> wrote:

Quote:
Frederick Williams wrote:
But what would
be a second order formulation of a classes-and-sets theory?
....
Von Neumann, Bernays, Gödel doesn't have schema, it's finitely
axiomatizable. (Hence my question.)

Aatu Koskensilta wrote:
That's true. "Second order NBG" doesn't mean anything determinate

In that case, 1st-order ZFC doesn't either.
It's hard to see how ANY 1st-order set theory can be meaningfully
lifted to 2nd-order. The problem is, once you have predicates as
members of your universe of discourse, THEY ARE all sets.
They are ESPECIALLY all OF THE sets, if you are using the standard
semantics of SECOND order logic, which requires that predicate
variables be able to range over "all conceivably/metahphysically
possible"
classes (i.e. subcollections of the universe) of 0th-order objects.
To any set you could conceive of, under THIS semantics, there ALREADY
corresponds A PREDICATE. Therefore, it is simply never relevant to
allege xey. The OBVIOUSLY proper way of phrasing xey, in the context
of a 2nd-order language, is y(x) . You simply cannot draw any
meaningful
distinction between a set y and the corresponding unary predicate ?ey.
If the axioms are not present for the purpose providing a definition of
e, since e is not needed at all, since it is just predication between a
1st-
and 0th- order object of the existing universe of discourse, then how
can
you have a set theory at all?

ISTM that with the full 2nd-order semantics, predicates correspond to
CLASSES, only some of which can be sets. If every predicate P had a
corresponding set p (a 0-order object) then you would in effect have
full naive set comprehension, which is bad. So, some predicates (e.g.
for the Russell class) can not correspond to sets.
 
Frederick Williams
Posted: Mon Jul 03, 2006 8:55 am
Guest
george wrote:

Quote:
Please don't guess. There is a standard answer.
Google it if you know how.

There is more than one way to get info. from the Internet; Google is
one, sci.logic is another.

Quote:
Here is an interesting treatment:
web.mit.edu/dmytro/www/NewSetTheory.htm

Thanks for the reference.

--
Remove "antispam" and ".invalid" for e-mail address.
 
 
Page 1 of 1    
All times are GMT - 5 Hours
The time now is Sat Jul 04, 2009 6:36 pm