gasarch@brillig.umd.edu (William Ian Gasarch) (06/04/90)
A while back I posted an annoucement of a new result (reposted below),
and offered people to ask me to email the paper to them (about 50 did so).
That offer is still open, but this posting is for people who have been
unable to receive it.
IF you want the paper and have either been unable to contact me or
to receive it, then either email me your address (if you are able to send but
receive) and I will snail mail it, or mail me (William Gasarch, Dept. of C.S.,
University of Maryland at College Park, College Park, MD., 20742)
your address.
___________________________________________________
ANNOUCEMENT OF A NEW RESULT:
The following have been known for a while:
1) First order Presburger arithmetic (can use + and <) is decidable.
2) The following problem is undecidable: Given a formula $\phi(X)$
that uses the langauge $+,<$ and one free set variable $X$, all
the rest of the variables are bound number variables,
determine if there are an uncountable number of sets $A$ such that $\phi(A)$
is true.
Therefore the following result, due to Solovay (and posted here with his
permission) is SURPRISING
3) There is a recursive function $f$ that behaves as follows:
The domain of $f$ is the set of formulas $phi(X)$ mentioned in $2)$ above
On input $\phi(X)$, $f$ returns one of $\{ \phi(X), NOT(\phi(X)) \}$.
If the returned formula is $\phi(X)$ then there are an uncountable number
of sets $A$ for which $\phi(A)$ is true.
If the returned formula is $NOT(\phi(X))$ then there are an uncountable number
of sets $A$ for which $NOT(\phi(A))$ is true.
VERY SKETCHY PROOF:
Given a formula $\phi(X)$, a sort-of quantifier elimination
is performed where you end up with a quantifier free formula $\psi(X)$
such that $\phi(X)$ and $\psi(X)$ are equivalent for sets of a certain
type, (``$k$-good sets'' where $k$ is determined during the quandifier
elimination). There are an uncountable number of $k$-good sets
(actually a continumm number), and it is relativiely easy to determine
if a quantifier free formula $\psi(X)$ is true for an uncountable number
of sets.
FOR A MORE DETAILED PROOF:
The paper IS available. It is ``Learning via Queries to ${+,<]$''
(by Gasarch, Pleszkoch, and Solovay)
and you can request it from me. I can email TeX code for it.
___________________________________________
Historical Note:
The problem came up while working on inductive inference- recursion
theoretic learnign theory. The decidability result turned out to be JUST
what we needed. It is probably more interesting in its own right then the
original problem. The paper above has both.
bill gasarch
gasarch@cs.umd.edu