NetNews Usenet Archive 1992 #31/NN_1992_31.iso/spool/sci/math/17397

Text File | 1992-12-24 | 13.9 KB | 268 lines

Xref: sparky sci.math:17397 sci.logic:2477
Path: sparky!uunet!elroy.jpl.nasa.gov!ames!olivea!news.bbn.com!hsdndev!husc-news.harvard.edu!husc10.harvard.edu!zeleny
From: [e-mail] (Michael Zeleny)
Newsgroups: sci.math,sci.logic
Subject: Re: The Continuum Hypothesis:  Must it be {True or False}
Summary: yes
Message-ID: <[e-mail]>
Date: 24 Dec 92 21:17:44 GMT
References: <[e-mail]> <[e-mail]> <[e-mail]>
Organization: The Phallogocentric Cabal
Lines: 254
Nntp-Posting-Host: husc10.harvard.edu

In article <[e-mail]>
[e-mail] (Mark Corscadden) writes:

>In article <[e-mail]>
>[e-mail] (Daniel A. Asimov) writes:

DAA:
>>Do people buy this, that FLT must be {true or false}, regardless of
>>whether it is provably true or false (i.e., decidable)?
>>Dan Asimov

MC:
>In email, Dan suggested using the phrase "having determinate truth-value"
>to say that a proposition must be {true or false}, regardless of whether
>it is provably true or false.
>
>I'll shorten this, simply saying that such a proposition is "determinate".
>
>To answer Dan's question, I buy - beyond any doubt - that FLT is
>determinate.  On the other hand I can't convince myself that CH (the
>Continuum Hypothesis) is determinate, but at the same time I can't
>find any necessary reason to believe that CH is indeterminate either.
>
>Thinking about the difference between FLT and CH, I came up with a
>sufficient (to me) condition that a statement be determinate, though
>I have no reason to think that this condition is necessary.  This
>condition is described below along with the rationale behind it.  Does
>anyone recognize the condition below as matching something they've seen
>elsewhere, perhaps in a different context?  Any feelings about whether
>you agree with me that this really is a sufficient condition for a
>statement to be determinate?
>
>Roughly put, the condition says, "If you are talking about objects which
>can be completely identified by asking finite questions concerning them,
>and if you are using only properties defined in terms of such questions
>and the usual quantifiers, then any statement you make is determinate."
>A more precise formulation is given below.
>
>Most important of all, can anyone present an example of a proposition
>which does *not* satisfy the condition below, along with an argument
>that their proposition is nevertheless determinate?  How about a
>proposition that does satisfy the condition, along with an argument
>that said proposition is indeterminate?
>
>To talk about this you need to use some framework, so I'll use ZFC set
>theory which is a pretty well-known framework.  The discussion doesn't
>seem to require anything more than naive set theory, but it should always
>be possible to explicitly ground this stuff in ZFC if the extra precision
>is necessary for some reason.
>
>My condition says in part that your mathematical object must be completely
>identified by some class of finite questions having finite answers; call
>these specific questions the *basis* questions.  By Godel-numbering the
>basis questions and by expanding the set of questions in a mechanical way,
>you can transform the questions into non-negative integers and the answers
>can be limited to {yes , no} without loosing any generality.  Let X be the
>set of objects concerning which you wish to make determinate statements,
>and let F(x) give, for each object x, the answer to any *basis* question
>which can be asked concerning x.  Then my condition begins with these two
>requirements:
>
>(1) "F(x) provides the answers to all basis questions about x."
>    There is a set X and a function F that assigns to each x in X
>    a map F(x): N -> {yes,no}, where N is the set of non-negative
>    integers.
>
>(2) "The basis questions completely describe any given object."
>    The identity of x (an element of X) is completely determined
>    by the map F.  That is, the function F is injective (1-to-1).
>
>Now create a universe of discourse U by adjoining to X a copy of the natural
>numbers N.  Use the two atomic predicates A(n,m,p) (meaning n+m=p) and
>M(n,m,p) (meaning n*m=p) to allow you to talk about basic properties of
>the natural numbers.  Then add one additional atomic predicate P(n,x) for
>use in talking about the original objects from the set X.  The meaning of
>P(n,x) is:
>
>        n is a natural number
>        x is an object from the original set X
>        F(x) maps n to "yes".
>
>Then my sufficient (and possibly necessary???) condition that a statement
>be determinate ends with this third and final requirement:
>
>(3) The statement can be expressed using the atomic predicates above, along
>    with the usual quantifiers and logical connectives.
>
>
>I can't prove that this is a sufficient condition for a statement to be
>determinate, but then again I can't imagine a counterexample that meets
>the conditions above and yet can be argued to be indeterminate.  I would
>love to be floored by someone with a nice counterexample.
>
>Also I can't think of any examples that don't meet the conditions above
>and yet seem to me to be determinate of necessity, but again I'd love to
>be floored by a nice example.  Actually in this case, what is really needed
>is a broad class of statements all of which are determinate even though
>the conditions (1) - (3) are not in effect.  (Isolated statements which
>are determinate can always be manufactured by "ignoring" interesting
>properties and saying something trivial.)
>
>Note that my conditions (1) - (3) immediately force me to believe that
>all statements which can be made about natural numbers using the usual
>language of elementary number theory are determinate, which trivially
>includes FLT.  For those who took the time to follow all this so far
>but find it a bit abstract, here is an important example where the
>universe of discourse has cardinality greater than that of N, the set
>of natural numbers.
>
>Let the (primary) universe of discourse, X, be the set of all *subsets*
>of N.  Actually this example is the one that guided me when I invented
>the conditions (1) - (3).  When I visualize a generic subset of natural
>numbers I can picture it as a series, for example
>
>        { 3, 4, 7, 12, 13, 17, 24, 27, 28, ... }.
>
>This mental image of a generic subset of natural numbers is "complete"
>to me - in the sense that *any* specific issue that is relevant to the
>identity of such a subset must be settled by the contents of the mental
>image at *some* point, if the image is extended far enough; and there is
>nothing that prevents me from imagining that the image can be extended
>(in principle) to any degree that is necessary.
>
>After thinking about this, I decided that you could capture the essence
>of what is going on above by saying that you have a certain type of question
>which you can ask about a given subset of N, namely this type of question:
>
>        is 0 in the subset?
>        is 1 in the subset?
>        is 2 in the subset?
>        is 3 in the subset?
>
>and *anything* that is relevant to the identity of such a subset must
>be addressed by one or more questions of this type.  Another important part
>of the intuition I was trying to capture was that any element of a mental
>image I might have that is truly clear should be something that I can
>express to another person - which requires the ability to provide a
>finite description of some kind.
>
>Getting back to the example, the universe of discourse U consists of all
>*subsets* of N, with the *elements* of N thrown in for good measure.  The
>meaning of the atomic predicate P(n,x) is, "the number n is a member of
>the subset x".  Then you immediately have the following kinds of statements
>which are all determinate:
>
>        for all x, 0 is a member of x                           (false)
>        for all x, if 0 is in x then 1 is in x                  (false)
>        there is an x such that 0 is in x                       (true)
>
>In addition, you can define "x is a subset of y" using the open sentence:
>
>        for all n, if n is a member of x, then n is a member of y
>
>so any statements which are built up out of quantifiers and the relation
>"subset of" will also all be determinate.  I wonder whether the predicate
>"n is an element of x" is really sufficient to allow you to say a broad
>class of interesting things about this universe of discourse, though.
>If not, then all propositions may turn out to be determinate simply because
>you can't state any of the interesting propositions under these restrictions.
>I know too little about this particular universe of discourse to venture
>an opinion - as far as I know it is not studied for its own sake by
>anyone.  Contrast the universe of discourse consisting of N itself, which
>has been heavily studied for its own sake.  I believe that having just the
>two atomic predicates A(n,m,p) and M(n,m,p) is sufficient to allow you to
>form the interesting propositions concerning N, but I really don't know
>much about this particular kind of foundation issue.
>
>Anyway, there are consequences of using my conditions (1) - (3) that seem
>very arbitrary and bizarre to me, namely the limit on the cardinality of
>the set X (the primary universe of discourse).  The condition (2) that F
>be injective implies that the cardinality cannot exceed the cardinality
>of the continuum.  The example where X = "the set of all subsets of N" has
>an F which is also surjective (onto) so it represents a universe of maximal
>cardinality.  It seems odd to me that having *all* (quantified) statements
>be determinate would require this peculiar restriction on the cardinality
>of the universe of discourse, but I don't have any good example in hand of
>a larger universe where indeterminate statements cannot be formed
>regardless of how quantifiers and some interesting set of atomic predicates
>are used.
>
>Oh well, this question of the "determinateness" of mathematical statements
>seems very, very, important to me.  Which types of statements are
>determinate?  Why?  And yet I know that a lot of people with extreme
>beliefs in one direction or the other will see most of my discussion
>as meaningless.
>
>Are there people out there who share my feelings about how important
>the question of determinateness is, and understand what is troubling me
>well enough to provide insight?  Even if they think that my concerns are
>ultimately misguided?  And does anyone recognize my conditions (1) - (3)
>as being equivalent to something else that they are already familiar with
>which comes up naturally in conjunction with logic or determinateness?

Well, I do not see this discussion as terribly meaningful, because it
opens more questions than in purports to settle.  But instead of
criticizing the above points, I sdhall lay down some observations.

FLT is a \Pi^0_1 sentence.  In any first-order, or otherwise complete
theory, undecidability of a \Pi^0_1 sentence requires that it be false
in some models of the theory, but true in others; for otherwise by
semantic completeness it would have been provable or refutable,
according as it were valid or contradictory.  The question of truth
reduces to whether the sentence can be false in a standard model, --
iff not, it is by definition true.  Now, by Tarski's definition of
satisfaction, falsehood in the models of the theory depends on the
existence therein of a witness set for the \Sigma^0_1 negation of the
original sentence; but in case of an arithmetical sentence, these
witnesses must be the integers.  If they are standard integers, then
they have names in the language of the theory, and therefore the
original sentence receives an explicit refutation in the latter, in
contradiction to the hypothesis of undecidability.  On the other hand,
if all the witnesses in all the relevant models are *non-standard*
integers, then _a fortiori_ the proposition in question is true in all
standard models, and so true _simpliciter_, albeit not valid. Hence,
if a \Pi^0_1 sentence is undecidable in a semantically complete theory
of Peano Arithmetic, wherein provability is coincident with validity,
then it is _ipso facto_ true.

On the other hand, in second-order PA, all models are standard by
categoricity; in other words, the adoption of a full strength
induction axiom allows us to characterize the integers up to
isomorphism.  But then the completeness argument, as distinct from
soundness alone, is likewise inapplicable for standard second-order
semantics.  (All we can get is that undecidability in second-order PA
entails falsehood in a faithful (satisfying AC and every instance of
comprehension) Henkin model.  Henkin semantics is non-categorical, and
generally is equivalent to the case of many-sorted first-order logic,
so I think that the first-order situation is recapitulated in this
case.)  But the moral of this story is that there is a critical
difference between undecidability in a first-order theory, which by
L\"owenheim-Skolem theorems cannot characterize infinite structures up
to isomorphism, and a higher-order theory, which can do so.

Thus the Continuum Hypothesis is independent of first-order ZFC;
however ZF^2, which assumes a second-order version of Replacement, is
known to settle all set-theoretic question for sets up to the rank
\kappa, the first inaccessible cardinal, -- alas, it is not known
which way they are settled.  But one thing I would emphasize, is that
to strive for certainty by rejecting all higher-order arguments, is
tantamount to losing conceptual certainty in the very same matters
which allow one to define first-order semantics.  For instance, the
concept of finitude is not fixed in any first-order language, because
of the above considerations.

>Mark Corscadden
>[e-mail]
>work: [phone]

Some discussion of the concepts used in my argument will be found in
Stewart Shapiro's _Foundations without Foundationalism_, Oxford, 1991.

cordially,
mikhail [e-mail]
"Nothing can be said truly of what does not exist."