10
$\begingroup$

How does one proove that the Countable axiom of choice is not provable in ZF?Is there any brief proof?Does the Independence of the countable axiom of choice implies the independence of the axiom of choice?

$\endgroup$
3
  • 7
    $\begingroup$ To forestall closure votes: even though this is a well-known result, the proof is difficult to follow if one is not a logician, and this is a result that lots of mathematicians could reasonably be interested in. I think this question is appropriate for MO. $\endgroup$ Mar 14, 2015 at 20:04
  • 3
    $\begingroup$ @NoahS: Conversely, a lot of questions arise here from other branches of mathematics that may well be textbook ones there but which logicians and computer scientists (for example) would like to see explained. That surely is the point of an interdisciplinary website. $\endgroup$ Mar 14, 2015 at 20:08
  • 1
    $\begingroup$ @PaulTaylor, I agree, although exactly where to draw the line is complicated. $\endgroup$ Mar 14, 2015 at 20:12

2 Answers 2

14
$\begingroup$

I'm going to play fast and loose with details here, but the outline is correct. To answer your new questions: no, there is no short proof. And this only shows one direction of the indpenedence of AC, that ZF doesn't prove AC; in the other direction, we need to show that ZF doesn't disprove AC. This is proved by showing that any model of ZF contains a really nice "inner model," called "$L$," in which ZFC (and much more) is true.


OK, so the details of the proof are quite complicated, but let me give an outline:

  • First, let's make it clear what we're going to prove. You've got your ZF axioms over here, and you want to show that they don't prove Countable Choice (CC) - assuming, of course, that ZF is consistent (otherwise it proves everything, including CC). To do this, we're going to show that if ZF is consistent, then ZF+$\neg$CC is consistent. Even thought this is a question about proofs, though, we're going to argue semantically: we'll show how, if you give me a model of ZF, I can give you a model of ZF+$\neg$CC. By Completeness + Soundness, this means that if ZF is consistent then ZF+$\neg$CC is consistent.

  • So this is going to be a relative construction: we'll start with some $V$ in which the ZF axioms (in fact, the ZFC axioms) are true, and we'll build a $W$ in which the ZF axioms are still true, and CC is false. In order to do this, though, we need some method to build models of ZF which gives us some measure of control over their properties. And this is really hard, since it's not even clear how to build models of ZF at all!

  • The trick is forcing. Given a partial order $\mathbb{P}$, we can think of the elements of $\mathbb{P}$ - conditions - as approximations to some bigger object. For example, if $\mathbb{P}$ is the set of finite binary strings, then an element of $\mathbb{P}$ is an approximation of a real number - an infinite binary string. Think of a condition as providing incomplete information about something we're trying to build; specifically, the thing the condition is approximating is a maximal filter through $\mathbb{P}$. This isn't by itself a new idea - this is how the Baire category theorem goes, and Cantor's diagonal proof.

  • OK, so what do posets have to do with models of ZF? To answer that question, let's talk about something completely different - the idea of an conditional name for a set. Remember that a model of ZF is built in layers - we start with $\emptyset$ as our 0th layer, and take powersets and limits to get successive layers, continuing all the way up the ordinals. (This can actually be formalized and proved as a theorem of ZF - the crucial axiom is Foundation.) This means we can think of a set as a well-founded tree, or as an instruction for how to build a set which is appropriately non-circular, e.g. the instructions

    • "This set has $\omega$-many elements;"
    • "The first element has one element;"
    • "That element has no elements;"
    • "The second element has one element;"
    • "That element has one element;"
    • "That element has no elements;"
    • . . .

describe the set $\{\{\}, \{\{\}\}, \{\{\{\}\}\}, . . .\}.$

  • Now, we could imagine a similar set of instructions which were conditional - e.g., "This set is the emptyset if my name is Steve, and otherwise is the set containing the emptyset." These things feel like sets in a lot of ways, but they aren't quite - in the same way that a formula isn't a sentence without evaluating the free variables, or a polynomial isn't a set of points without describing the field its over, these names aren't really referring to individual sets. Still, they're not far off: we can evaluate names, once we supply sufficient information - for example, once I tell you my name isn't Steve you know the name above refers to the set $\{\{\}\}$.

  • So here's an idea for how to, given a model $V$ of ZF, build a new "thing" $W$: take all the names in $V$ which refer to only a certain kind of information - say, "names of people" - provide some "complete information" - say, everyone's name - and then evaluate all those names to produce actual sets; and say $W$ is the collection of all the sets produced in that way.

  • Oh hey, I used the word "complete" - that sounds like what I said about posets! In fact, for our purposes, a "name" will be "an ambiguous description of a set, which depends on questions of the form "Is $x$ in $G$?" where $G$ is only known to be a maximal filter of some fixed poset $\mathbb{P}$." Formally, the class of $\mathbb{P}$-names is defined inductively, as: $$\mbox{A $\mathbb{P}$-name is a set of ordered pairs $(p, \nu)$, where $p\in\mathbb{P}$ and $\nu$ is a $\mathbb{P}$-name;}$$ $$\mbox{the *evaluation* $\mu[G]$ of a name $\mu$ on a max. filter $G\subseteq\mathbb{P}$ is $\mu[G]=\{\nu[G]: \exists p\in G((p, \nu)\in \mu)\}$.}$$ That is, thinking of $\mu$ as a set of instructions for how to build a set, we're looking at instructions of the form "If $p\in G$, then put (the thing defined by the following sub-instructions) into our set; otherwise, ignore (the following sub-instructions)."

  • Now here's the neat bit: it turns out that if $V$ is a countable (not a problem, use Lowenheim-Skolem) model of ZFC, $\mathbb{P}\in V$ is a poset, and $G$ is a maximal filter through $\mathbb{P}$ which meets every dense subset of $\mathbb{P}$ living in $V$ - called a generic filter; note that this means $G\not\in V$, probably - then $V[G]$, the set of all $\mathbb{P}$-names in $V$ evaluated at $G$, is a model of ZFC! (We call such a $V[G]$ a generic extension of $V$.) So this is great . . .

  • . . . except we don't want choice to hold. And this is a problem - if we assume merely "ZF is consistent," the only model we can easily describe is $L$, which satisfies ZFC. So we need some way to start with a model of ZFC, and turn it into a model where choice fails.

  • To do this, we go back to the description of $V[G]$, and make it smaller - rather than throw in all the names, well restrict attention to good names for some value of "good." It turns out that the right notion of "good" here has to do with families of groups of automorphisms of $\mathbb{P}$ - roughly, a name is good if it is fixed by one of the groups of automorphisms. Different families of automorphisms give rise to different notions of good - and in particular, if our family includes the trivial group, then every name is good. It turns out that we preserve the axioms of ZF by doing this, so this is a viable construction to try.


OKAY, THAT WAS LONG. So let me very briefly describe how the actual construction goes:

  • Start with $V\models ZFC$ countable.

  • Let $\mathbb{P}$ be the poset $((2^{<\omega})^\omega)^\omega$ - basically, an element of $\mathbb{P}$ is an approximation to a countable family of countable families of reals - or, we're building countably many "blocks" of countably many rows, and each row represents a real.

  • For $F$ a finite set of rows, let $S_F$ be the set of automorphisms of $\mathbb{P}$ which only act by swapping rows, don't swap rows between blocks, and don't move the rows in $F$.

  • Then the resulting "good names" give the model we're looking for - our generic filter $G$ is (basically) a countable collection of sets of reals, but no choice function has a good name.

$\endgroup$
9
  • 1
    $\begingroup$ You may also be interested in the following: another question mathoverflow.net/questions/104450/road-to-solovays-land; Timothy Chow's article arxiv.org/abs/0712.1320; Cohen's account projecteuclid.org/download/pdf_1/euclid.rmjm/1181070010; and many others. $\endgroup$ Mar 14, 2015 at 20:49
  • 1
    $\begingroup$ OK!That helped a lot thank you!I am new in set theory studies and i am more intersted on weaker forms of the axiom of choice,equivalent forms and the consistency of the AC.Plus i recently found a proof for the sentence "every finite set has a choice fuction"(in ZF).So the question occurs about the Countable axiom of choice(CAC) is there any proof that CAC is not provable in ZF(okay independence needs to verify that ZF doesn't disprove AC).You seem well informed on the matter and i whould like a bit more help.How does the CAC implies that every infinite set has a countable subset? $\endgroup$ Mar 14, 2015 at 23:26
  • $\begingroup$ I have a hint but probably i am missing something obvious..Let's assume that A is infinite set then we construct the set of all one-to-one sequences in A of length n.We do so for every n and we name the previous set as A_{n} for each n.Then the family of all A_{n} is a set,let's call it S.Using a choice fuction on S we obtain a countable subset of A.The exact statment of CAC i am using is "Every countable family of nonemplty sets has a choise fuction".And F is a choice fuction for the family of non empty sets S iff F(X) is in X (for all X in S). $\endgroup$ Mar 14, 2015 at 23:34
  • $\begingroup$ Yes, that hint is basically the whole problem - given an infinite set $A$, for each $n$ the set $A_n=\{X: X$ is an injection from $n$ into $A\}$ is nonempty, so - by countable choice - the family $\{A_n: n\in\omega\}$ has a choice function. What is this choice function? Well, it's essentially a sequence of sequences of distinct elements of $A$, of increasing length. Concatenating these sequences gives an infinite sequence of elements of $A$ - a single element might occur multiple times in this sequence, but infinitely many elements will occur. Delete repetition, and we're done. $\endgroup$ Mar 14, 2015 at 23:38
  • 1
    $\begingroup$ For the exercise :We need to work with sequences cause we know that the union of these sequence is also a sequence therefore the union is countable.Am i right? $\endgroup$ Mar 15, 2015 at 0:33
4
$\begingroup$

First of all, the easy answer.

We can prove that the axiom of choice implies the axiom of countable choice, quite easily. So by showing that the axiom of choice is consistent with the axioms of $\sf ZF$, and the negation of the axiom of countable choice is consistent as well with the rest of the axioms, we essentially prove the independence of both at once.

Of course, the axiom of choice is strictly stronger and we can use other weakened versions of the axiom of choice to prove the independence of the axiom of choice from the axiom of countable choice as well.

The harder answer is just going to be a broad strokes argument of the technical part.

  1. Godel proved that if the axioms of $\sf ZF$ are consistent, then you can define a subclass of the universe of $\sf ZF$ which satisfy $\sf ZFC$ and much much more. This class is called $L$ in modern times, and it has many many wonderful properties.

    This means that if there is a model of $\sf ZF$, then there is a model of $\sf ZFC$, which alternatively means that if $\sf ZF$ is consistent then $\sf ZFC$ is consistent.

  2. On the other hand, Fraenkel proved that if you allowed urelements, or atoms (which are non-sets objects) to exist, then the axiom of choice is not provable. His methods were later corrected by Mostowski and improved by Specker (which is why these models are often called FM(S) models).

    When Paul Cohen first described forcing, he showed how to transfer the core ideas from the existence of atoms to forcing extensions. He constructed two basic models which mimicked Fraenkel's original constructions. In both the axiom of countable choice fails pretty bad.

    The basic idea is that you add to the model, using forcing, a sequence of sets which are "generic" and from the original model's point of view, they are "almost" the same. Then using one of two clever (but often equivalent) constructions, you can keep those new sets, but forget the enumeration of the sequence, in a way that leaves them un-well orderable, and in fact without a countably infinite subset.

You can find the proofs for all those, and much much more in Jech "The Axiom of Choice", as well in most modern set theory 'big books' (Jech, Kunen, Halbeisen).

$\endgroup$
6
  • 1
    $\begingroup$ To elaborate on (2), the issue of how to transfer those core ideas from the context of urelements to genuine ZF results was seriously investigated by Jech and Sochor, and later by Pincus, who developed powerful machinery to say: "Oh hey, we can do this thing with urelements, so we must be able to do it without them." $\endgroup$ Mar 14, 2015 at 20:51
  • 1
    $\begingroup$ Noah, it is true, and it didn't end there. I prefer to look at the meta-meta-arguments, rather than embedding theorems. Meaning under what circumstances we can "essentially repeat" the same construction with forcing and obtain the same results in terms of truth values of the statements we wish to investigate; and thus discard all the use of atoms from the get go. $\endgroup$
    – Asaf Karagila
    Mar 14, 2015 at 20:53
  • 1
    $\begingroup$ That's a very good point - I like the embedding theorems partly because they lead to a nice combinatorial question, "What's the lowest rank where we can shove this construction in?" $\endgroup$ Mar 14, 2015 at 20:54
  • $\begingroup$ And I don't like them exactly because the approach is "Shove it all into one cardinal", rather than "reiterate the construction carefully, and you can't lose!" :-) $\endgroup$
    – Asaf Karagila
    Mar 14, 2015 at 20:54
  • 1
    $\begingroup$ In the present situation, you can get from an urelement proof (the basic Fraenkel model) to a pure-set proof more easily than by the Jech-Sochor construction. Adjoin to the basic Fraenkel model an $A$-indexed family of Cohen reals (force with Fin($A\times\omega$,2)), and then take the pure part of the resulting model. You get the basic Cohen model, which, of course, violates countable choice. $\endgroup$ Mar 15, 2015 at 4:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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