[FOM] Question about hard-core independence
Haim Gaifman
hg17 at columbia.edu
Mon Feb 17 18:26:44 EST 2003
Some comments on one of the emerging points:
>> I do not know what you mean by "all statements given so far".
>> We have statements constructed along the lines suggested by
>> Torkel Franzen and Harvey Friedman for which we have no grounds to
>> assume that they are decidable in ZFC, or ZFC and any large cardinal
>> axioms. For instance, Harvey's example is of the type:
>> A = R(ZFL) ==> B
>> where R(ZFL) is the Rosser sentence of ZFL (ZF + V=L), and
>> B is any $\Pi_1$ arithmetical sentence. Choose any open hard
>> $\Pi_1$ problem as A (e.g., that all perfect numbers are even)
>> and you get an example whose independence is known on
>> the basis of reasons that would be hardly disputable (the consistency
>> of ZF), but for which we do not have any clue to its truth.
>> Since we believe in R(ZFL), deciding A amounts to the same
>> as deciding B.
> Presumably, weak large cardinal axioms will decide B, and therefore
> decide A. We just don't know yet which way they decide B.
Note: There was a typo in my last message; I wrote 'choose any open
hard $\Pi_1$ problem as A', it should have been: 'choose any open hard
$\Pi_1$ problem as B'. I hope that this was obvious.
You imply that well-known unsolved problems in number theory, such as
the Goldbach conjecture, the statement that all perfect numbers are
even, the Riemann hypothesis, the existence of infinitely many twin
primes (this one is actually a $\Pi_2$ statement) and scores of
others, are in fact decidable in ZFC+some weak large cardinal
assumptions. We know of course that some ``natural'' combinatorial
arithmetical statements are derivable from the consistency of certain
weak large cardinal assumptions, but not from weaker theories.
But I do not see how such assumptions are going to play a role in
say, a proof of Goldbach's conjecture. If this will turn out to be
the case, that is: if any of the classical problems will be first
settled by appeal to large cardinals, it will be sensational!
(It will be so even if the appeal to large cardinals can be later eliminated).
There is also a serious possibility that some of these
conjectures are undecidable, or cannot be decided by a proof of
"feasible length''. I therefore propose to treat them as "simple
hard problems'' whose decidability status is unknown.
The idea of a hard-core independence result is to have a
hard problem, whose independence is known (on good reasons),
of the kind established in set theory. This need not cast a doubt on
the intended interpretation of the theory in question. But the absence
of hard-core independence for arithmetic or for ZFL may be related to
the fact that their intended interpretation appears less ambiguous
than that of ZF. I think that my suggested ''second try'' may capture
that notion. At least, I have not seen counterexamples so far and the
set theoretic independence results seem to pass the required
criterion.
I shall comment on some other points in your last message in a
separate reply.
Haim Gaifman
John Steel wrote:
> On Mon, 10 Feb 2003, Haim Gaifman wrote:
>
> > Dear John Steel
> > I am sorry for the very late reply. Late as it is, some points would still
> > benefit from clarification:
> >
> > >All of the statements given so far are decided by very weak
> > >large cardinal axioms, presumably, though we don't know which
> > > way they go yet.
> >
> > I do not know what you mean by "all statements given so far".
> > We have statements constructed along the lines suggested by
> > Torkel Franzen and Harvey Friedman for which we have no grounds to
> > assume that they are decidable in ZFC, or ZFC and any large cardinal
> > axioms. For instance, Harvey's example is of the type:
> > A = R(ZFL) ==> B
> > where R(ZFL) is the Rosser sentence of ZFL (ZF + V=L), and
> > B is any $\Pi_1$ arithmetical sentence. Choose any open hard
> > $\Pi_1$ problem as A (e.g., that all perfect numbers are even)
> > and you get an example whose independence is known on
> > the basis of reasons that would be hardly disputable (the consistency
> > of ZF), but for which we do not have any clue to its truth.
> > Since we believe in R(ZFL), deciding A amounts to the same
> > as deciding B.
>
> Presumably, weak large cardinal axioms will decide B, and therefore
> decide A. We just don't know yet which way they decide B.
>
> >
> > >Turning "the sum of what we have good reason to believe" into the basis
> > >for a precisely defined concept of hard-core independence seems hopeless.
> >
> > It goes without saying that 'hard-core independence' is not proposed
> > as a precise concept; just as 'what we have good reasons to believe'
> > is not a precise concept. But there is real gain if we succeed to
> > define (or at least clarify) the first on the basis of the second.
> > You may be right that we cannot do it, but I am not so sure as you
> > about its "hopelessness". If your "hopeless" refers to making
> > the two concepts precise then I agree, of course.
> >
> > I think that we shall agree that if one accepts a theory T then one
> > should accept also various natural strengthenings of it (like
> > adding the scheme Provable_T (A)---> A). Large cardinal axioms are
> > a different matter. The "larger" the cardinal the more you will have
> > divergent opinions. So "good reasons" is an imprecise graded concept.
> > But this is not a reason to avoid taking a serious systematic look at it.
> >
> I agree. Philosophers have been studying what constitutes
> "good reasons" for thousands of years, so if we hope for progress,
> we have to stick close to the subject at hand, and we have to make use
> of the relatively recent advances of math. logic and set theory.
>
> > You are right in interpreting my question as one about the possible
> > ambiguity of the concept of "set". This is a very good way of putting
> > it. And I agree that adding V=L is likely to remove the ambiguity;
> > or, in other words, that there is no ambiguity about the concept of
> > "constructible set".
> >
> >
> > > I think adding V=L may very well remove all ambiguity,
> > > but at the cost of speaking a less expressive language.
> >
> > "Less expressive language" needs clarification. There is the familiar
> > intuition that most sets are not constructible. But one should give
> > a better criterion than an appeal to that kind of intuition.
> > One gets a nicer theory of sets of reals by assuming axioms
> > that contradict V=L, but this is another, different kind
> > of reason.
> >
>
> I sais pretty much all I have to say on this subject in
> "Mathematics needs new axioms" (BSL, Dec. 2000), my part in a panel
> discussion with Feferman, Maddy, and Friedman, so I hope it's ok if I just
> give you that reference.
>
> > >I do think there could be a way to show that
> > >the full language of set theory is ambiguous without getting into abstract
> > >theories of meaning. We do that all the time, by exhibiting the distinct
> > >possible meanings. (Einstein didn't need a theory of meaning to show that
> > >"A is simultaneous with B" is ambiguous.)
> >
> > What you mean by "abstract theories of meaning"?
>
> Meaning=use is one, meaning=method of verification is another.
> There's a large literature in Philosophy.
>
> I
> > certainly do *not* suppose that we have to lay down some general "theory
> > of meaning" in order to approach these problems.
>
> Then we agree.
>
> On the contrary,
> > the theory of meaning, whatever it is, will emerge from this kind of
> > of investigation.
>
> I'm not so sure of that.
>
> We do not have to be told that we are speaking
> > prose in order to speak it.
> >
> > Haim Gaifman
> >
> > John Steel wrote:
> >
> > > All of the statements given so far are decided by very weak
> > > large cardinal axioms, presumably, though we don't know which
> > > way they go yet. I think that is why they are unsatisfying as
> > > examples of "hard-core independence". They are probably not
> > > independent of the sum of what we have good reason to believe.
> > > (Of course, it could turn out that your S is some arithmetic sentence
> > > which is provably independent of all the large cardinal axioms we know of,
> > > but if you find such an S, then ...Wow!)
> > >
> > > I personally don't think V=L is independent of the sum of what we have
> > > good reason to believe, since it is decided by large cardinal axioms.
> > >
> > > Turning "the sum of what we have good reason to believe" into the basis
> > > for a precisely defined concept of hard-core independence seems hopeless.
> > >
> > > I took the original question as a way of asking whether taking "set" to
> > > mean constructible set removes all ambiguity from the language of set
> > > theory. (That may not have been how Prof. Gaifman was thinking of it.
> > > It does seem implicit in the latest formulation involving
> > > independence methods which "manipulate directly the semantics".) I think
> > > adding V=L may very well remove all ambiguity, but at the cost of speaking
> > > a less expressive language. I do think there could be a way to show that
> > > the full language of set theory is ambiguous without getting into abstract
> > > theories of meaning. We do that all the time, by exhibiting the distinct
> > > possible meanings. (Einstein didn't need a theory of meaning to show that
> > > "A is simultaneous with B" is ambiguous.)
> > >
> > > Whether there is actually any such ambiguity seems like an open
> > > question, to me. The proving conditional generic absoluteness theorems at
> > > the $\Sigma^2_n$ level for incompatible theories which are provably (from
> > > large cardinal assumptions) true in (necessarily different) set-generic
> > > extensions is one approach to exhibiting an ambiguity.
> > >
> > > John Steel
> > >
> > > On Mon, 13 Jan 2003, Haim Gaifman wrote:
> > >
> > > > Obviously, I was trying to find a definition
> > > > that would rule out uninteresting arithmetical
> > > > examples obtained by Goedelian techniques, and
> > > > I did not succeed.
> > > >
> > > > Actually, your construction leaves something open.
> > > > Your assumption:
> > > >
> > > > > (1) We know T+Con(T) to be consistent,
> > > >
> > > > should be interpreted as having a proof of this in some
> > > > theory. The theory T to which I applied
> > > > the notion of hard-core independence is ZFL.
> > > > Your construction yields a statement whose
> > > > independence is derived not from con(ZFL)---as I
> > > > specified---but from con(ZFL+con(ZFL)).
> > > > But this is bad enough.
> > > >
> > > > Furthermore, Harvey Friedman provided an arithmetical example
> > > > (using Goedelian results) in which the relative
> > > > independence is derivable in PA from Con(ZFL):
> > > > Let S be any extension
> > > > of ZFL obtained by adding a statement for which we
> > > > have no reason to believe either that it is provable or
> > > > disprovable in ZFL. Then the sentence:
> > > > R(ZFL) ==> Con(S) has the desired properties, where
> > > > R(ZFL) is the Rosser sentence for ZFL.
> > > >
> > > > This creates the following situation:
> > > > Take any set theory T you are prepared
> > > > to adopt for the purposes of doing math.
> > > > Then there exists an arithmetical statement of
> > > > the form: D&~D', where D and D' are diophantine
> > > > sentences (that is, claiming the existence
> > > > of solutions to certain diophantine equations), such that
> > > > we have no idea about its truth and such that,
> > > > if T is consistent, then T does not decide it.
> > > > This however does not add doubts about
> > > > the reality, or uniqueness, of the standard model of natural
> > > > numbers. If I have doubts, they do not stem from
> > > > such examples, especially after I have seen
> > > > the proof of such independence results.
> > > >
> > > > On the other hand the set-theoretic independence
> > > > results do raise doubts about the reality of
> > > > "Cantor's Universe", or about its uniqueness.
> > > > The doubts depend on the methods these
> > > > claims are proved, rather than on the claims
> > > > themselves. The methods manipulate
> > > > directly the semantics rather than the syntax.
> > > > Can we have a more precise
> > > > characterization of such "hard-core independence"?
> > > > One can of course rule out, by definition,
> > > > examples that can be reduced to
> > > > arithmetical statements.. But I do not find this a
> > > > satisfactory solution.
> > > >
> > > > My first question still remains: is there
> > > > a "hard-core" independence result
> > > > for ZFL? But now the notion is not
> > > > precisely defined. It indicates the
> > > > kind of non-arithmetical result
> > > > obtained for ZFC.
> > > >
> > > > Haim Gaifman
> > > >
> > > > _______________________________________________
> > > > FOM mailing list
> > > > FOM at cs.nyu.edu
> > > > http://www.cs.nyu.edu/mailman/listinfo/fom
> > > > _______________________________________________
> > > > FOM mailing list
> > > > FOM at cs.nyu.edu
> > > > http://www.cs.nyu.edu/mailman/listinfo/fom
> > > >
> >
> > _______________________________________________
> > FOM mailing list
> > FOM at cs.nyu.edu
> > http://www.cs.nyu.edu/mailman/listinfo/fom
> >
-------------- next part --------------
An HTML attachment was scrubbed...
URL: /pipermail/fom/attachments/20030217/8c40ff91/attachment.html
More information about the FOM
mailing list