1
$\begingroup$

$V=L$ is a statement in set theory asserting that every set is constructible. It implies the axiom of choice.

I find this kind of confusing, since the axiom of choice is non-constructive. Can you, for example, find/construct a specific basis of any vector space in $ZFC + V=L$, or within $L$ itself?

$\endgroup$
6
$\begingroup$

Of course we can. Every proof using choice can now use the canonical global choice function given by the well ordering of $L$.

But since our usual framework is $\sf ZFC$ and not necessarily $V=L$, we can't appeal to $L$ in general.

For example, if we assume a measurable cardinal exists, then the reals of $L$ are in fact countable, how would that help us find a canonical Vitali set?

$\endgroup$
3
$\begingroup$

Intuitively speaking, the Axiom of Choice is "non-constructive" only when you apply it to objects which are themselves non-constructive. It says that ANY family (which is a set) of non-empty sets has a choice function, but if a specific family which is given to you constructively (still intuitively speaking), then the construction will allow you to also construct a choice function, so you don't need to appeal to the Axiom of Choice. Only when you want a choice function for some arbitrary family, you need the non-constructiveness of the axiom, which gives you a choice function "out of nowhere".

In particular, if you have $V=L$, then you don't need to appeal to the non-constructive axiom to get your choice funcions - you can simply construct them, using the constructible well-order of $L$. And even more particular, if you have some vector space in $L$ you can definitly define inductively a basis, again using the well-order of the elements, which is itself constructed inductively.

For a different example - in certain versions of type theory (of which I am no expert), which are intended to be highly constructive, you also get that the axiom of choice is valid, since in order to show that the collection you are talking about is indeed a collection of non-empty sets, you are actually required to provide a choice function, so the axiom of choice is actually somewhat trivial (see here).

$\endgroup$
  • 2
    $\begingroup$ The final paragraph is exactly right - for example, in Martin-Löf type theory, or in Bishop's version of constructivism, the axiom of choice comes along "for free" because the existence of a choice function follows directly from the definition of a "family of non-empty sets". $\endgroup$ – Carl Mummert Mar 1 '18 at 14:25
  • $\begingroup$ Well said. The student has become the teaching assistant. :P $\endgroup$ – Asaf Karagila Mar 1 '18 at 17:58
0
$\begingroup$

The ZF axioms allow many things that no person or computer can do. For example, the axiom of replacement allows you to apply an operation to all elements of a set, even if that set is infinite!

By applying operations to all members of infinite sets, you can define sets in ZF that encode solutions to problems that no computer or human can solve.

As an example, in ZF you can define the set that encodes the solution of the halting problem S := {n in N | algorithm #n halts}. But the halting problem is not solvable (there are algorithms that do not terminate but for which there is no proof that they do not terminate).

Now V is the universe of all sets, and L is the universe of all "constructible" sets. But the phrase "constructible" doesn't mean "something that anyone can actually construct". Instead, it means: sets that must exist if you accept the ZF axioms and the class of ordinals. That includes the set S which is ZF-definable but is definitely not constructible by any finite means.

If you accept ZF and the axiom V=L then you get a well-ordering for any set (and hence AC follows) but to work with this well-ordering you'd need to be able to do what ZF allows (you need a hypothetical machine that can apply operations to all members of infinite sets). Such a machine does not exist, so in practice the well-ordering that exists under ZF + V=L is not something that finite humans and computers can actually work with.

In short: Under ZF + V=L there does exist a well-ordering of the reals, but it is impossible for finite beings to give an explicit description of that well-ordering (it would require infinite memory + CPU time). So a well-ordering of the reals is "constructible" in ZF + V=L but not constructible by finite means.

Likewise, under ZF + V=L, any vector space immediately has a basis, but again, that basis is "constructible" and need not be "something that anyone can actually construct". For example, under ZF + V=L, the $\mathbb{Q}$-vector space $\mathbb{R}$ has a basis, but that basis is not constructible by finite means.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.