[FOM] dichotomies/constructivity

[Harvey Friedman]

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.