# Developing intuition for a world without AC

So after 25 years without doing any serious math, I've gotten the bug again. In my spare time (I have a full-time job as a lawyer), I've been starting to work my way through Set Theory: An Introduction to Independence Proofs by Kunen and I've started to participate here.

Both sources have convinced me that I need to develop some intuition for what the world looks like without AC. I screwed up an attempted answer on this site (which really embarrasses me) and, despite some fairly detailed discussion found via Google searches, I am having significant trouble with Kunen's exercise on Hartog's $$\aleph$$-function.

I'm not yet ready to ask for help with the Kunen exercise. But if there's a site on line where I can start to develop some intuition for what the world looks like without AC, I'd very much appreciate that. Thanks for any help you can provide.

• There are a fair number of questions and good answers (many by Asaf Karagila) on this site concerning the Axiom of Choice. Always remember to check existing questions before asking a new question on the topic. Feb 5, 2019 at 19:30
• Thanks. I was hoping for something that was somewhat more cohesive, or at least more compact. Ideal from my perspective would be discussion of a specific and relatively intuitive model for ZF + $\lnot$AC. Feb 5, 2019 at 21:47
• Not to sound smug, but read plenty of answers on this site. Feb 5, 2019 at 21:59
• Just to introduce one kind of ZF set which cannot exist in ZFC, which I learned about first from Asaf, read about Amorphous Sets (en.wikipedia.org/wiki/Amorphous_set) and on this site. Feb 5, 2019 at 22:07
• Here is a talk I came across on here or overflow a while back math.yorku.ca/~moliver/how.pdf Feb 6, 2019 at 2:04

There is no "easy" way to get intuition. If you want to get better you need to solve exercises. Many of them.

Two wonderful sources for exercises are:

1. Jech, "The Axiom of Choice".
2. Herrlich, "The Axiom of Choice",

In addition you can also use the many answers on this site which contain somewhat deep explanations, and try to extract some semblance of intuition from them.

But the real truth is that choice is finicky. Choice is hard. Choice is confusing. Infinite sets are weeeeeeeeirrrrrdddddd.Even I don't have a very amazing intuition without choice, because there's always stuff you've never thought about, stuff that's confusing you, stuff that's surprising you. It never ends. And that's part of the fun!

• I'd suggest spending some time meditating on what Jech calls the basic Fraenkel model. And then the second Fraenkel model. Admittedly, there's a lot of weeeeirrrrrdddness that doesn't show up in these two models, but enough does show up to give a good start on developing intuition. Feb 5, 2019 at 23:16
• The Jech book is cheap enough that I've now already bought it. It'll probably take me quite some time to make progress (that pesky full-time job gets in the way), but it looks like exactly the sort of thing I was hoping for, and your pointer to specific models within the book is also quite helpful. Feb 6, 2019 at 2:12
• @Robert: Let me add that while these specific models are important, and the construction can help you develop intuition, I don't think that you should put too much stress on that. If anything, the exercises at the end of Ch. 4 are much more helpful for intuition, especially the ones involving model theoretic notions (see also my paper about Preserving Dependent Choice for modern style arguments in the same vein). The models will give you some idea as to why things break, but not really intuition as to how far they break. Doing the exercises is more important in my opinion [...] Feb 6, 2019 at 11:52
• [...] but of course you can only do the problems once you've understood the constructions as they appear in the chapter. So it's not something to skim through. Feb 6, 2019 at 11:52

Asaf's answer is the "right answer", but I'll give a quick (well, as quick as I can) high-level overview of the basic Fraenkel model, which is not a model of ZF where choice fails, but rather a model of ZFA (ZF with atoms/urelements) where choice fails.

The key intuition is that the axiom of choice 'breaks symmetry' when it makes arbitrary choices amongst some symmetric options, whereas all the other axioms preserve symmetry. The reason atoms are useful is that, due to foundation, there are no nontrivial automorphisms of a transitive model of ZF. However, when we have atoms, we can permute the atoms and these permutations induce automorphisms.

We can envision a set as a graph with edges given by the membership relation $$\in.$$ Then we can unpack the elements of the set as well, and their elements, and so on. This gives a picture of the transitive closure of the set. Well-foundedness implies that the graph has finite depth (although it may be incomprehensibly wide), and each terminal node is an empty set. Atoms are objects that have no elements, but are not the empty set. When we add atoms to the mix, the terminal nodes may be either the empty set or an atom. Formally, we have a picture like the cumulative hierarchy, only instead of starting with $$V_0=\emptyset,$$ we start with the set of atoms $$A,$$ and work our way up through higher ranks in a similar fashion.

If we take any permutation $$\pi:A\to A$$ of the set of atoms, we can extend that to an automorphism of the model by letting $$\pi \emptyset = \emptyset,$$ $$\pi a = \pi(a)$$ for any atom, and, recursively, $$\pi x = \{\pi y: y\in x\}.$$ (In other words, just permute those terminal nodes. Notice particularly that any "pure" set, i.e. one whose transitive closure contains no atoms, is fixed by $$\pi$$.) Thus we have a group action on our universe that it makes sense to talk about things being symmetrical with respect to.

Consider a universe with a countably infinite set $$A$$ of atoms, and the group $$G$$ of permutations of $$A.$$ For any set $$x$$, we can define the subgroup we define the subgroup fixing $$x$$ as $$S(x) = \{\pi \in G: \pi x = x\}.$$ We will say $$x$$ is symmetric if $$S(x)$$ is "large", in a sense we will define precisely. We say a set is hereditarily symmetric if it is symmetric, all of its elements are symmetric, all of its elements' elements are symmetric, and so on. It turns out that the sub-universe consisting of all the hereditarily symmetric sets is a model of ZFA in which choice fails badly.

We define a subgroup $$H$$ of $$G$$ to be large if there is a finite subset $$E\subseteq A$$ such that if $$\pi(a) = a$$ for all $$a\in E,$$ then $$\pi\in H.$$ This $$E$$ is called a "support" for $$H.$$ In other words, this subgroup contains all the great many permutations that fix some "small" (i.e. finite) set of atoms. Recall $$x$$ is symmetric if $$S(x)$$ is large, so if $$x$$ is symmetric, we can guarantee $$\pi x=x$$ by having $$\pi$$ fix some finite set of atoms.

We will sketch the main results

Theorem. The class of hereditarily symmetric sets is a model of ZFA.

Proof. We will just do pairing. Let $$x$$ and $$y$$ be hereditarily symmetric, with supports $$E_1$$ and $$E_2.$$ Let $$\pi$$ fix $$E_1\cup E_2,$$ which is a finite set. Let $$z=\{x,y\}.$$ Then $$\pi z = \{\pi x,\pi y\} = \{x,y\},$$ since $$\pi$$ fixes the support of both $$x$$ and $$y$$. Thus $$z$$ is symmetric, and both its elements are hereditarily symmetric, so $$z$$ is hereditarily symmetric. Thus the class of hereditarily symmetric sets is closed under pairing.

All the other closure properties can be proven similarly. The hardest are the ones where there is an arbitrary formula (replacement and separation), but it will be helpful to first prove the fact that $$\phi(x,y,\ldots)\leftrightarrow \phi(\pi x, \pi y, \ldots)$$

So, the intuition is that doing the usual set theoretical combinatorics with symmetric building blocks only yields symmetric results. (In fact, Jech uses the Godel operation approach, which makes being a model of ZF or ZFA largely a question of closure under set theoretical operations, avoiding pesky formulas.)

Finally, we have

Theorem. The axiom of choice fails over the hereditarily symmetric sets. In particular, the set $$A$$ of atoms is an infinite set which is Dedekind-finite.

Proof. First, it's not hard to see that $$A$$ is hereditarily symmetric. Since $$A$$ is infinite, for any $$n,$$ there is an injection $$f:n\to A.$$ We can see this $$f$$ is hereditarily symmetric as well: $$f= \{(0,a_0), (1,a_1),\ldots, (n-1,a_{n-1})\}$$ so $$\pi f =\{(\pi 0, \pi a_0),\ldots\} = \{(0,(\pi (a_0)), \ldots, (n-1,\pi(a_{n-1}))\},$$ where we recall pure sets, such as the natural numbers, are fixed by any $$\pi.$$ If we choose $$E=ran(f),$$ we see that any $$\pi$$ fixing $$E$$ fixes $$f.$$ Thus $$f$$ is hereditarily symmetric. So for any $$n$$, there is a hereditarily symmetric injection $$f:n\to A,$$ thus $$A$$ is infinite in the class of hereditarily symmetric sets.

On the other hand let $$f$$ be an injection $$f:\omega \to A.$$ We can see that $$f$$ is not symmetric, since for any finite set $$E$$ of atoms, we can always find a permutation that fixes $$E,$$ but moves some atom in the range of $$f.$$ Thus, in the class of hereditarily symmetric sets, there is no injection $$\omega\to A,$$ i.e. $$A$$ is Dedekind finite. This implies that $$A$$ cannot be well-ordered, since otherwise the initial segment length $$\omega$$ of the well-ordering would be an injection $$\omega\to A.$$

There is a lot more to study about this model. And this whole process can be generalized by picking different groups of permutations and different "notions of largeness" in order to create other models where choice fails in different ways. (The "notions of largeness" are called normal filters. They are often generated by collections of "small" sets of atoms, generalizing the collection of finite sets used here. These collections of small sets are called normal ideals.)

As I mentioned before, this uses the atoms in an essential way (alternatively you can work in models where foundation fails and use Quine atoms instead of atoms). In ZF, the models you construct are similar, but the big difficulty is where to find the symmetry transformations given that there are no automorphisms of models. The answer involves forcing, so is more technically complicated (thus >30 years between Fraenkel and Cohen), but you can read about it in Jech's book. In fact, the similarity can be made precise in the form of embedding theorems, also covered in the book.

• To be sure I understand the basics here, an atom is not itself a set (because it has the same elements as $\emptyset$ but is not itself $\emptyset$) but can be an element of a set. Feb 6, 2019 at 4:27
• Yes, that's right. For ZFA we weaken the axiom of extensionality to say any two sets with the same elements are equal, and a bunch of other minor modifications of the axioms and basic definitions need to be made. Feb 6, 2019 at 4:32
• Seems like a straightforward way to handle that is to define a unary "set" relation and then tweak the other axioms as needed. Does that work? Is it conservative? Feb 6, 2019 at 4:37
• Sure. It can be done a bunch of different ways. I think making a constant symbol $A$ for the set of atoms and then letting the set predicate be $x\notin A$ is the most straightforward. Feb 6, 2019 at 5:03
• Here are some links: math.stackexchange.com/a/58384/622 and math.stackexchange.com/a/29469/622 and later on, when you learn forcing-style arguments math.stackexchange.com/a/343985/622 is also relevant. There might be more, but three is enough for now... :) Feb 6, 2019 at 11:48