[FOM] dichotomies/constructivity
Harvey Friedman
friedman at math.ohio-state.edu
Mon Sep 9 14:40:53 EDT 2002
Epstein writes:
>
>Consider the following assertion:
>
>* There exists a non-Borel subset of the real line which can be expressed
> as the union of some linearly ordered (with respect to set inclusion)
> family of countable sets.
>
>Assertion * is in fact true, with a very quick proof in ZFC (I haven't
>checked whether Choice is truly necessary, but never mind that).
>
>The odd thing is that the proof takes the following form:
>
> "If the Continuum Hypothesis holds then ... whence *. On the other hand,
> if the Continuum Hypothesis does not hold, then ...' whence *."
But there is a quick proof without this dichotomy. Let A be a set of
real numbers such that the elements of A code well orderings of every
countable well ordered type, exactly one for each countable well
ordered type. Then by classical descriptive set theory, A is not
Borel. However, for each countable ordinal alpha, let S[alpha] be the
set of elements of A which code a well ordering of type < alpha.
These are countable and linearly (or even well) ordered by set
inclusion, and their union is A.
To code a well ordering means to directly code a set of natural
numbers that codes a well ordering of pairs of natural numbers, using
any fixed one-one function from pairs of natural numbers into natural
numbers. To directly code a set of natural numbers means that the set
of positions in the base 2 expansion to the right of the decimal
point that are 1 is exactly that set of natural numbers.
>The same person also told me that there is a theorem in number
>theory whose proof goes as follows:
>
>"If the Riemann Hypothesis then ... while if the Riemann Hypothesis fails
>then ...' "
>
>Can anyone supply details about this one?
>
My impression is that there are a number of examples of such, with
genuine dichotomies. I think that any analytic number theorist could
give you some good examples. E.g., Iwaniec at Rutgers, a particularly
famous analytic number theorist.
Of course, there is the foundational issue of just what we mean by a
proof by dichotomy. It is tempting to simply require that the proof
be constructive. Then proofs by dichotomy would be invalid. However,
that does not appear to be a reasonable requirement in set theoretic
contexts, since normally set theory is highly nonconstructive from
the outset.
In the case of number theory, this may well make good sense. Number
theory is generally constructive, but with some famous exceptions
that are not known to be nonconstructive. E.g., Falting's proof of
Mordell's conjecture and Roth's theorem on rational approximations.
So one can reasonably ask that a number theory theorem be proved
constructively, in which case using the RM in a dichotomy would be
rejected.
Unfortunately we don't have the tools to show existing theorems in
number theory are inherently nonconstructive. But here is a trivial
theorem that we know has no constructive proof:
Every polynomial with integer coefficients attains a value of least
magnitude over the integers.
More information about the FOM
mailing list