No, it is not possible. It is consistent with ZF without choice that
the reals are the countable union of countable sets. (*)
From this it follows that all sets of reals are Borel. Of course, the "axiom" (*) makes it impossible to do any analysis. As soon as one allows the bit of choice that it is typically used to set up classical analysis as one is used to (mostly countable choice, but DC seems needed for Radon-Nikodym), one can implement the arguments needed to show
(**) The usual hierarchy of Borel sets (obtained by first taking open sets, then complements, then countable unions of these, then complements, etc) does not terminate before stage $\omega_1$ (this is a kind of diagonal argument).
Logicians call the sets obtained this way $\Delta^1_1$. They are in general a subcollection of the Borel sets. To show that they are all the Borel sets requires a bit of choice (One needs that $\omega_1$ is regular).
There is actually a nice result of Suslin relevant here. He proved that the Borel sets are precisely the $\Delta^1_1$ sets: These are the sets that are simultaneously the continuous image of a Borel set ($\Sigma^1_1$ sets), and the complement of such a set ($\Pi^1_1$ sets).
That there are $\Pi^1_1$ sets that are not $\Delta^1_1$ (and therefore, via a bit of choice, not Borel) is again a result of Suslin. He also showed that any $\Sigma^1_1$ set is either countable, or contains a copy of Cantor's set and therefore has the same size as the reals. His example of a $\Sigma^1_1$ not $\Delta^1_1$ set uses logic (a bit of effective descriptive set theory), and nowadays is more common to use the example of the $\Pi^1_1$ set WO mentioned by Joel, which is not $\Delta^1_1$ by what logicians call a boundedness argument.
A nice reference for some of these issues is the book Mansfield-Weitkamp, Recursive Aspects of Descriptive Set Theory, Oxford University Press, Oxford (1985).
There is a canonical way of checking the literature for most questions of this kind. Since they come up with some frequency, I think having the reference here may be useful.
First, look at "Consequences of
the Axiom of Choice" by Paul Howard
and Jean E. Rubin, Mathematical
Surveys and Monographs, vol 59, AMS,
(1998).
If the question is not there, but has
been studied, there is a fair chance
that it is in the database of the book
that is maintained online,
http://consequences.emich.edu/conseq.htm
Typing "Ascola" on the last entry at the page just linked, tells me this is form 94 Q. Note the statement they provide is usually called the classical Ascoli theorem:
For any set $F$ of continuous functions
from ${\mathbb R}$ to ${\mathbb R}$, the following conditions
are equivalent:
1. Each sequence in $F$ has a subsequence that converges
continuously to some continuous
function (not necessarily in $F$ ).
2. (a) For each $x \in{\mathbb R}$ the set $F (x) =\{f (x) \mid f \in F \}$ is bounded, and
(b) $F$ is equicontinuous.
To see the other equivalent forms of entry 94, type "94" on the line immediately above.
From there we learn: Form 94 is "Every denumerable family of non-empty sets of reals has a choice function."
There are some other equivalent forms that may be of interest. For example:
- (94 E) Every second countable topological space is Lindelöf.
- (94 G) Every subset of ${\mathbb R}$ is separable.
- (94 R) Weak Determinacy. If $A$ is a subset of ${\mathbb N}^{\mathbb N}$ with the property that
$\forall a \in A\forall x \in{\mathbb N}^{\mathbb N}($ if $x(n) = a(n)$ for $n = 0$ and $n$ odd, then $x\in A)$, then in the game $G(A)$ one of the two players has a winning strategy.
- (94 X) Every countable family of dense subsets of ${\mathbb R}$ has a choice function.
Proofs and references are provided by the website and the book. A reference that comes up with some frequency in form 94 is Rhineghost, Y. T. "The naturals are Lindelöf iff Ascoli holds". Categorical perspectives (Kent, OH, 1998), 191–196, Trends Math., Birkhäuser Boston, Boston, MA (2001).
Best Answer
In the 1960's, Bob Solovay constructed a model of ZF + the axiom of dependent choice (DC) + "all sets of reals are Lebesgue measurable." DC is a weak form of choice, sufficient for developing the "non-pathological" parts of real analysis, for example the countable additivity of Lebesgue measure (which is not provable in ZF alone). Solovay's construction begins by assuming that there is a model of ZFC in which there is an inaccessible cardinal. Later, Saharon Shelah showed that the inaccessible cardinal is really needed for this result.