[FOM] Re: FOM Digest, Vol 16, Issue 1

[Ali Enayat]

This is a response to the query of G. Kapoulas:

"I was told that the definition of an ultrafilter requires the use of
$L_{{\omega_1} \omega}$  language. Does anyone know a reference  for this
or what is the logical complexity  for the definition  of an ultrafilter,
or a quick description of the definition".

The easy answer is "at least as definable as a well-ordering of the
continuum" (based on the classical proof of the existence of nonprincipal
ultrafilters from the existence of a well-ordering of the continuum of Ulam
[1926]).

Sierpinski [1938], on the other hand, proved that a nonprincipal
ultrafilter U on N, when viewed as a subset of the Cantor set 2^N, is
neither L-measurable (L = Lebesgue), nor has the Baire property; in
particular U cannot be analytic (continuous image of Borel), or
co-anayltic, so that's the first *undefinability* result concerning
ultrafilters, in light of the natural correspondence between Borel sets and
infinitary formulae.

The quickest way to see that a nonprincipal ultrafilters U on N is not
measurable is to note that

(1) if U is L-measuarble, then U must have measure 1/2 (based on symmetry
considerations);

(2) nonprincpal ultrafilters are "tail sets" (membership in U is invariant
under finite changes); and

(3) Kolmogorov's zero-one law states that every measurable tail set has
either measure 0 or measure 1.

Later [1940] Godel's work on the constructible universe showed that it is
consistent with ZFC for there to exist a *projective* i.e., obatainable
from a Borel set by finitely many applications of projections and
complementation) nonprincipal ultrafilter, since in Godel's constructible
universe, there is a projective well-ordering of the continuum.

With the advent of the method of forcing [in the early 1960's] a large
number of results about definability of ultrafilters appeared that
culminated in the following fundamental paper of Solovay and Pincus (one of
whose results was independently obtained by H. Friedman, using a different
method, see below).

Pincus, David; Solovay, Robert M.
Definability of measures and ultrafilters.
J. Symbolic Logic 42 (1977), no. 2, 179--190


Friedman, Harvey
On definability of nonmeasurable sets.
Canad. J. Math. 32 (1980), no. 3, 653--656.

***********************************************************************


Ali Enayat
Department of Mathematics and Statistics
American University
4400 Massachusetts Ave, NW
 Washington, DC 20016-8050
(202) 885-3168