This is a simple doubt of mine about the basics of measure theory, which should be easy for the logicians to answer. The example I know of non Borel sets would be a Hamel basis, which needs axiom of choice, and examples of non Lebesgue measurable set would be [Vitali sets](http://en.wikipedia.org/wiki/Vitali_set), which seems to be unprovable without axiom of choice. Then I saw [the answer of François G. Dorais](https://mathoverflow.net/questions/23202/explicit-big-linearly-independent-sets/23206#23206). His construction of an uncountable $\mathbb{Q}$-independent set in $\mathbb R$ does not require axiom of choice. Which leaves a faint hope for the following:



> 
> Is it possible to construct without using the axiom of choice examples of non Borel sets?
> 
> 
> 


There is a classic example of an analytic but non-Borel set due to Lusin, described by Gerald Edgar [here](https://groups.google.com/forum/#!search/not-Borel$20continued-fraction/sci.math/OZE06oaV5RQ/HqTYd6cGFSgJ), but it is not clear to me whether it needs axiom of choice since it seems to be putting restrictions on higher and higher terms in the continued fraction expansion. Since I do not know logic and set theory, I hoped of asking the experts.



Non-Borel sets without axiom of choice
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).


