The axiom of choice is an axiom of set theory, and it is used when implicitly assuming that the universe consists of sets, and sets alone. That is - everything is a set.
For example, $0=\emptyset$ and $1=\{\emptyset\}$. Since everything is a set, consider a set $X$ and all its elements are non-empty sets themselves. Formally $\forall y(y\in X\rightarrow \exists z(z\in y))$.
The axiom of choice asserts the existence of a function whose domain is $X$ and its range is $\{z\mid\exists y(y\in X\land z\in y)\}$ (often denoted $\bigcup X$). The function has a very special property, namely $f(y)\in y$. It chooses someone from every element of $X$.
Some examples (which do not require the axiom of choice) are, $X=\mathcal P(\mathbb N)\setminus\{\emptyset\}$ that is all the non-empty subsets of natural numbers.
We can have $f(A)=\min A$, that is the least element of $A$ is returned. We can require something slightly more peculiar $f(A) = \min\{a\in A\mid a\text{ is even}\}$ if such $a$ exists, or $\min A$ otherwise.
These are two examples which do not require the axiom of choice since we are able to specify in a uniform formula who do we want to pick from every $A$.
A useful equivalence of the axiom of choice is Zorn's lemma. This lemma is somewhat complicated, but it asserts that if $(A,<)$ is a partially ordered set, and every linearly ordered subset of $A$ has an upper bound, then there exists a maximal element.
To elaborate on that, if $A$ is a non-empty set, and $<$ defines a partial order on $A$, if every $C\subseteq A$ which has the property $\forall a\forall b(a<b\lor b<a\lor a=b)$ has some $x\in A$ such that $\forall a(a\in C\rightarrow a<x)$ then there exists a maximal element - some $x\in A$ for which the property $\forall a(a\neq x\rightarrow a<x)$ is true.
Zorn's lemma is very useful in algebra, and used in the proof that every field has an algebraic closure; every vector space has a basis; and every ideal can be extended to a maximal ideal (and many many many other uses).
The proof uses heavily the axiom of choice (not surprisingly, since the two are equivalent) and in a nutshell we take one element, then $\{a_0\}$ is linearly ordered, therefore if $a_0$ is not maximal in $A$ we can extend it. That is the set $\{b\in A\mid a<b\land a\neq b\}$ is non-empty, and we can choose from it. We choose from non-empty subsets of $A$ until we either "find" a maximal element, or derive contradiction to one property or another.
I use "find" because many times the maximal element is one we cannot describe nicely by a sentence (and in fact without the axiom of choice there are vector spaces without basis, fields without algebraic closures and so on).
To understand the axiom of determinacy first we need to understand what there is to be determined.
Take $A\subseteq\mathbb N^\mathbb N$, that is a set of infinite sequences of natural numbers.
Now we play a game, I will be Player I (P-I) and you will be Player I (P-II). I will choose some $n\in\mathbb N$, and then you will choose another. The game is infinitely long and will have another round for every finite number of rounds.
Note that in the $n$-th round we have $x_n$ and $y_n$ (I chose $x$'s and you choose $y$'s). This defines a sequence:
$$a_n =\begin{cases}x_k & n=2k\\ y_k & n=2k+1\end{cases}$$
We say that I win the game if $\langle a_0,a_1\ldots\rangle\in A$, otherwise you win the game. If there is a strategy assuring victory for either one of us then we say that the game is determined. This is to say there is a function from $\mathbb N$ to $\mathbb N$ that given the current state of the game will give me a possible tail segment which assures one of the player's victory. (Note that there are usually a lot of possible strategies).
For example $A$ will be all the sequences which are constants $a_n=k$ for some $k$. Clearly you have a winning strategy. Whatever I chose at first, choose something else and I have no chance of winning.
Another example is $A$ will be the set of sequences that $a_n$ is even whenever $n$ is even ($a_n=n$, for example). All I have to do is choose even numbers in my turn, and I cannot lose.
The Axiom of determinacy asserts: Every game is determined. That is, if we play this sort of game then regardless to which set of sequences we have chosen, one of us can win.
The conflict with the axiom of choice is a bit technical for this post (and the part about determinacy could surely be phrased better by someone else), the idea is as such. If we assume the axiom of determinacy, then every game is determined. We will define $A$ by a transfinite induction. Since at each step during the game the collection of winning strategies is non-empty. We simply choose such winning strategy and ensure that it will not work by adding a sequence to $A$, repeating the process "enough" times we ensured that no strategy exists to determine the winner after any finite number of turns. This contradicts the assumption that every game is determined.
Determinacy is somewhat of a technical axiom, and while it was very natural to postulate this axiom in some parts of set theory (namely descriptive set theory), the mainstream mathematics has been made very comfortable with the axiom of choice, and as Theo points out in the comments some pathologies which we are used to are gone when assuming the axiom of determinacy.
This makes the axiom of choice more common in modern mathematics than determinacy. Things can change, though... things can change.
Added:
To understand the need for the axiom of choice, we return to Bertrand Russell's wonderful analogy. Given infinitely many pairs of shoes, you can always choose one from each pair, but to choose a sock from infinitely many pairs of socks you need the axiom of choice.
What does that mean? Well, given shoes you can easily say "Pick all the left shoes", and regardless of how many pairs are given in each pair there is exactly one left shoe. This defines a function which chooses an element of each pair. On the other hand socks are indistinguishable and you cannot say which one is the left and which one is the right.
What does that mean indistinguishable? Well, given one pair of socks $\{a,b\}$ we can always say "Oh, this is $a$ and this is $b$", even if our assignment of $a$ was arbitrary. Every time we are given three pairs of socks we can ad-hoc assign each pair as $a_i, b_i$ and pick the ones we assigned as $a_i$. However if there are infinitely many pairs of socks, can we always make such assignment? Well, only if we assume the axiom of choice holds.
The point is that a pair of socks has two elements in it. These are always distinct and we can always examine the pair by itself and distinguish between the two socks. We can always distinguish between three, four and five socks at once; as well ten or fifteen pairs of socks. We simply assign each collection of socks with different names to be able and temporarily tell which sock is which, then we can choose the names we would like.
Mathematically speaking if we are given a finite collection of non-empty sets, if we do not actually care about the choice of elements, as long as we choose exactly one from each set, it is always doable. First we need to understand that "not caring" means that we only require $f(A)\in A$ which is of course doable since $A$ is non-empty. However, in mathematics it is not enough to claim things, one has to prove them as well. In this case, we can simply write the following statment (assuming $A_1,\ldots, A_n$ are our non-empty sets):
$$\exists x_1\ldots\exists x_n(x_1\in A_1\land x_2\in A_2\land\ldots\land x_n\in A_n\bigwedge f(A_1)=x_1\land f(A_2)=x_2\land\ldots\land f(A_n)=x_n)$$
That is to describe exactly (I am somewhat cheating here, I did not describe it exactly, but I gave a close enough approximation) how $f$ looks like, it is the function (however a function may be defined set theoretically) that after fixing $x_i\in A_i$ simply returns $x_i$ as the choice from $A_i$. Since this is a finite collection of pairs we can describe this sort of choice.
If we have one pair then this sentence is very short, as we keep on adding pairs we will write longer and longer sentences. If we finally have infinitely many pairs then we cannot write this sort of sentence. We need to find a different formulation. This is where the ability to uniformly distinguish some unique element in each $A_i$ comes to help. Suppose $\varphi(x)$ is the property of being a left shoe. Let $B=\{B_n\mid n\in\mathbb N\}$ be a collection of infinitely many pairs of shoes. If we want to choose from each pair, we can simply do it as such:
$$\forall X(X\in B\rightarrow \varphi(f(X)))$$
Since there exists exactly one element, $a$ in every $X$ for which $\varphi(a)$ is true (i.e. there is exactly one left shoe in each pair of shoes) this implies the function $f$ is nicely defined, in a finite (and even short) sentence.
Now we return to the socks. There is no property $\varphi(x)$ such that in every pair of socks there is exactly one sock for which $\varphi$ is true. This means that we cannot write a very nice sentence as above, to choose one sock from each pair!
This is the (with a capital "the") key of the issue here. In a finite collection you can always distinguish every element from every other element. When looking at an infinite collection you may not be able to have this luxury.
What does that mean mathematically? It means that you may not be able to write a finite sentence to help you choose from infinitely many pairs without the axiom of choice - which asserts this sort of choice exists (it may not be computable or even definable except for knowing it exists somewhere in your universe, and therefore you can take an arbitrary one and use it for a while).
The answer is, you cannot.
It is consistent with ZF that the real numbers are a countable union of countable sets, this implies that every set of reals is Borel and therefore measurable. Of course, in such model it is nearly impossible to develop the analysis we know.
However it is consistent relative to an inaccessible cardinal that there is a model of ZF+DC where all the sets of real numbers are Lebesgue measurable, and DC allows us to do most of classical analysis too.
Non-measurable sets can be generated by free ultrafilters over $\mathbb N$ too, which as remarked is a strictly weaker assumption that the axiom of choice. If there are $\aleph_1$ many real numbers and DC holds then there is an non-measurable set as well, which implies that ZF+DC($\aleph_1$) also implies the existence of non-measurable sets of real numbers - however this is not enough to imply the existence of free ultrafilters over the natural numbers!
Several other ways to generate non-measurable sets of real numbers:
- The axiom of choice for families of pairs;
- Hahn-Banach theorem;
- The existence of a Hamel basis for $\mathbb R$ over $\mathbb Q$.
There are several other ways as well, but none are quite close to the full power of the axiom of choice.
One important remark is that we can ensure that the axiom of choice holds for the real numbers as usual, but breaks in many many severe ways much much further in the universe (that is counterexamples will be sets generated much later than the real numbers in the von Neumann hierarchy). This means that the axiom of choice is severely negated - but the real numbers still behave as we know them.
The above constructions and to further read about ways to construct non-measurable sets cf. Horst Herrlich, Axiom of Choice, Lecture Notes in Mathematics v. 1876, Springer-Verlag (2006).
Best Answer
First let me point out that you are mixing "constructive" and "constructible". There are plenty of non-constructive sets which are constructible. In particular because constructive usually refers to something more akin to the "definable from the usual structure of mathematical objects" and not "there is a set theoretic formula which defines it out of the blue".
The negation of the axiom of choice is as non-constructive as the axiom of choice. Just like the axiom of choice doesn't tell us what the choice function might be, the negation of the axiom of choice doesn't tell us what is the family of sets which does not have a choice function. It could be that the axiom of choice fails, for the first time, in some arbitrarily high von Neumann rank; or it could be that it only fails for very very very large families of sets; or it could be that it fails for particular type of families of sets, while it holds for other.
We can't say. In order to draw practical conclusions from the failure of the axiom of choice we usually have to assume more. For example "there is an infinite Dedekind-finite set of real numbers" is a failure of the axiom of choice which is more specific than just "the axiom of choice fails".
To solve this problem of non-constructivity you don't need to negate the axiom of choice, you need to change the system from a deeper place. Probably the law of excluded middle, which is responsible for us being able to assure that the non-constructive objects exist. This is why most constructive systems reject this law; and there is a theorem that the axiom of choice implies the law of excluded middle.
Within the confines of classical logic, and staying with $\sf ZF$:
You might want to ensure that there are sets which cannot be injected into an ordinal; but you can also require that there are sets which cannot be injected into a power set of an ordinal; and you can continue in this fashion.
So one option is to say the following: For each ordinal $\alpha$, there is a set which cannot be injected into $\mathcal P^\alpha(\eta)$ for any ordinal $\eta$. (Where $\mathcal P^\alpha$ is defined by iterating power sets, and taking union at limits.)
You might want to say, the axiom of choice implies the existence of all sort of crazy sets of real numbers. I'll choose "Every set is Lebesgue measurable", or "Every set has Baire property" or "Every game is determined". These axioms usually bring "order" to the world of non-constructive sets of reals. These are all consistent with $\sf DC$, which means that you can even develop reasonable analysis in those models.
And if the axiom of choice is mainly used for "There are some messed up sets of real numbers", things like the axioms above would essentially say "Every set of reals is well-behaved".
You might want to keep your focus on the real numbers, and say "Screw everything, I'm going nuclear" and require that the real numbers are a countable union of countable sets. This has the benefit of destroying completely the usual ways we define measure and category for sets of reals.
You can even go further than that, and require that for every ordinal $\kappa$, $\mathcal P(\kappa)$ is the countable union of sets of size $\kappa$. This is known as axiom $\sf (K)$, but we don't quite know if it's consistent (relative to very large cardinals, which are necessary to say the least). So you can instead take solace in choose "Every limit ordinal has cofinality $\omega$ which has some messed up consequences as well.
You can decide that you want amorphous sets, since those are "the ultimate counterexample". These are infinite sets that cannot be partitioned into two infinite sets. Strongly amorphous sets have the additional property that any partition is all singletons (except finitely many parts). These sets cannot be linearly ordered, they cannot be mapped onto $\omega$, and their cofinite sets make a complete ultrafilter.
Strongly amorphous sets cannot be endowed with any reasonable structure; but in general it is possible to have amorphous sets which are vector spaces over finite fields. Those spaces have the strange property that every proper subspace is finite.
And there are many other ways to say "I see the axiom of choice as responsible for ...", then the opposite would be "... fails in the most horrible way imaginable!".