Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Recall that Cohen's second model adds sets of generic reals such that there is a countable family of pairs with no choice function, i.e. a surjective function $f: A \to \omega$ such that each fibre of of $f$ is a 2-element set and $f$ has no section.

Clearly in the category of sets arising from such a model, given a map $g:B \to \omega$ with a section $s:\omega \to B$ (for example, an isomorphism), a surjective map $p:E \to B$ and a map $h:E \to A$ such that $f\circ h = g\circ p$, then we know that $p$ has no section. Thus there are plenty of examples of violations of AC, although the existence of $s$ is clearly problematic.

But do any weaker choice principles hold in this model?

share|improve this question
    
The question itself is great, however as I try to indicate in my answer there are many different answers. I suspect there are a few more "metrics" which are far less common to measure this sort of distance. I might be able to tell you more in a few years when I've had the time to toy with them properly... :-) –  Asaf Karagila Dec 18 '11 at 7:27

1 Answer 1

up vote 10 down vote accepted

The axiom of choice breaks pretty bad in this model, some stray observations:

  1. The axiom of choice for countable families of finite sets. This implies breaking almost any feasible form of "choice function for X families" sort of principle, in turn all the Dependent Choice principles.

  2. There exists an infinite Dedekind finite set, therefore not every infinite set has a countable subset.

  3. The ordering principle fails, not every set can be linearly ordered. In extension of that the Boolean Prime Ideal Theorem breaks down

I'm not sure about other choice principles that you have in mind, and since there are so many of them it would be a better idea if you point out what sort of choice principles you are looking for.

I have several educated guesses, which I have not yet been able to confirm and thus I will update this during the day (or week) as I have progress in locating references:

  1. If you consider KWP principles, where KWP($k$) says that for every there is some ordinal $\alpha$ such that $|x|\le\mathcal P^k(\alpha)$ ($k$-th iteration of the power set operation); I suspect that KWP(3) should hold in this model.

    It is worth noting that KWP(2) already fails in this model as it implies the ordering principle which, as the above remarks explain, fails.

  2. Every infinite set can be mapped surjectively onto $\omega$.

Since both principles are not trivially concluded in this model it would probably require some meddling with the definitions of the forcing and the permutations thereof.


Update I:

We use the following claim to partially prove my first guess:

  • Suppose $A,B$ are sets then $|\mathcal P(A)\times\mathcal P(B)|\le\mathcal P(A\times B)$, the proof is by the injection $\langle X,Y\rangle\mapsto X\times Y$.

In Consequences of the Axiom of Choice it says that SVC holds in this model, it also follows from several different arguments in Blass' original paper [1]. I could not find a direct reference to what is the set which proves SVC in this model, as Blass writes that one needs to consider a different generic set.

However under the (reasonable?) assumption that this set is the set of socks (denoted by $S$), which is the set which can be partitioned into countably many pairs without a choice function. Every sock is a set of reals so the collection of all socks is a set of sets of real numbers, that is $S\subseteq\mathcal P^2(\omega)$

Now the SVC($S$) axiom says that for every $x$ there is an ordinal $\alpha$ such that $|x|\le^* |S\times\alpha|$. This means that $|x|\le2^{|S\times\alpha|}$ (consider $f$ to be the surjection guaranteed, consider the map sending $a\in x$ to its fiber in $f$).

Now we have by the claims above and the fact that $x\le y\rightarrow 2^x\le2^y$:

$$\mathcal P(S\times\alpha)\le \mathcal P^2(\mathcal P(\omega)\times\alpha))\le \mathcal P^2(\mathcal P(\omega)\times\mathcal P(\alpha))\le \mathcal P^3(\omega\times\alpha)$$

We can also assume without loss of generality that $\omega\times\alpha$ is equipotent with $\alpha$. This implies that KWP(3) holds in this model if indeed my guess was correct and $S$ was taken as above.

This also shows that in the KWP($k$) "metric" the second model of Cohen is not very far from ZFC, although this is indeed a very different metric than usually.


Bibliography:

  1. Andreas Blass, Injectivity, Projectivity, and the Axiom of Choice. Transactions of the American Mathematical Society, Vol. 255, (Nov., 1979), pp. 31-59
share|improve this answer
    
Cool! I wasn't sure what sort of principles to ask for, but the axiom of multiple choice (in the sense that one can choose a non-empty subset of each fibre of a surjective map) might be handy to know about. Incidentally, what does KWP stand for? –  David Roberts Dec 18 '11 at 21:07
    
@David: KWP stands for Kinna-Wagner Principle(s). The original formulation was to choose a proper non-empty subset for every set, much like MC. This turned out to be equivalent to being injective into a power set of an ordinal. This was then generalized by Monro, Jech calls that $K(n)$ but $KWP(n)$ is a suited name, I believe since this is how it is presented in Felgner's book and Monro's papers. The fact that the ordering principle does not hold, however, means that you cannot necessarily choose a subset of each fiber. –  Asaf Karagila Dec 18 '11 at 21:13
    
Can I ask a basic question: what does $\le^\ast$ mean? It's hard to search for latex notation on the web ;) Or is it explained by your 'this means that...'? (or does 'this means that...' mean that it is a consequence of the first thing?) –  David Roberts Dec 18 '11 at 23:20
    
Actually, going back a step, since we are talking in the absence of AC, what is your definition of $\le$? –  David Roberts Dec 18 '11 at 23:24
    
@David: $x\le y$ if there is an injection from $x$ into $y$; and $x\le^* y$ if there is a surjection from $y$ onto $x$. It is a common notation in choiceless contexts. Since I've seen you asking more than a few questions about AC I assumed that you are already familiar with the notation. Either way, now you are :-) –  Asaf Karagila Dec 18 '11 at 23:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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