From: markc@smsc.sony.com (Mark Corscadden)
Subject: Re: The Continuum Hypothesis:  Must it be {True or False}, or Not?
Organization: Sony Microsystems Corp, San Jose, CA
Date: Thu, 24 Dec 92 03:49:38 GMT

In article <1992Dec14.200024.6435@nas.nasa.gov> asimov@wk223.nas.nasa.gov (Daniel A. Asimov) writes:
>       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

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?

Mark Corscadden
markc@smsc.sony.com
work: (408)944-4086