8

Let AC denote the Axiom of Choice. Let PP denote the so-called "Partition Principle" which states that "If S is a non-empty set and T is a non-empty set of pairwise disjoint subsets of S, then S can be mapped onto T". It is well known that "AC implies PP" is provable in ZF, but the question of whether "PP implies AC" is provable in ZF has long been an open problem. What is the present status of this problem? Has any progress been made on it? Or-on the other hand-have any models of ZF been constructed in which pp is true and some consequence of AC -such as the existence of non-measurable sets of real numbers-is false? If "pp implies AC" could be proved in ZF, this would seem to provide a powerful philosophical argument for accepting AC. In my opinion, any set theory in which pp can be disproved yields a really counter-intuitive picture of the "Set-theoretical Universe".

François G. Dorais
  • 43,723
Garabed Gulbenkian
  • 6,115
  • PP+DC implies the existence of a nonmeasurable set - http://mathoverflow.net/questions/22927/why-worry-about-the-axiom-of-choice/22935#22935 – François G. Dorais Jul 06 '13 at 18:47
  • 3
    I think I'm missing something. Fix some $t\in T$; why isn't the following map a surjection? $f: x\mapsto s\in T$ if $x\in s$, $x\mapsto t$ if $\forall s\in T(x\not\in s)$. Since the sets in $T$ are pairwise disjoint, and $T$ is nonempty, this is well defined, and can be proved to exist by ZF, and since each element of $T$ is a subset of $S$ this map is clearly onto. (Unless $T$ happens to contain $\emptyset$, but then just take $t=\emptyset$.) What am I missing? – Noah Schweber Jul 06 '13 at 18:51
  • 2
    Garabed, PP states that if $A\leq^\ast B$ then $A\leq B$, where $\leq$ means there is an injection and $\leq^\ast$ means there is a surjection. – Asaf Karagila Jul 06 '13 at 18:54
  • 4
    Noah is right. The conclusion of PP should not be that S can be mapped onto T (which is trivial) but that T can be mapped one-to-one into S. – Andreas Blass Jul 06 '13 at 19:03
  • 1
    Related. – Andrés E. Caicedo Jul 06 '13 at 20:17
  • @Andres: And in that spirit, Second and third edits of this question are also related to this thread (and to yours). – Asaf Karagila Jul 06 '13 at 20:29
  • This reminds me the question whether PP for reals implies the existence of a well ordering of reals. We may prove that there is a $ZF$-universe in which there is a transversal for any countable Borel equivalence relation but no well ordering of reals. We are not sure whether over $ZF+DC$, the full PP for reals implies the existence. – 喻 良 Jul 07 '13 at 08:01
  • @Liang: Is this problem still open? (I'm asking because I've toyed with it before.) – Asaf Karagila Jul 07 '13 at 08:32
  • I stated a version of PP which simply stipulates that the – Garabed Gulbenkian Jul 07 '13 at 18:03
  • I don't seem able to enter any comments. I need help! – Garabed Gulbenkian Jul 07 '13 at 18:07
  • Don't press "enter" until you're done writing your comment. – Asaf Karagila Jul 07 '13 at 18:09
  • Maybe I am missing something in my statement of pp but I cannot quite see what. My statement simply insures that the – Garabed Gulbenkian Jul 07 '13 at 18:40
  • Maybe I am missing something in my statement of PP but I cannot quite see what. My statement simply insures that the cardinal number of T (however cardinal numbers are defined) is never greater than the cardinal number of S. I thought that this is what PP states. – Garabed Gulbenkian Jul 07 '13 at 18:51
  • Garabed, no that is $\sf WPP$ (the Weak Partition Principle). The Partition Principle itself states that if $S$ can be mapped onto $T$ then the cardinal of $T$ is less or equal than the cardinal of $S$. – Asaf Karagila Jul 07 '13 at 19:14
  • @Asaf, it is still open. – 喻 良 Jul 08 '13 at 04:30
  • I see what is wrong with my statement of PP. In the absence of AC, even though S can be mapped on to T, this does not imply (in ZF) that T can necessarily be mapped injectively into S (which is what is meant by saying that the cardinal number of T is less than or equal to the cardinal number of S). Thanks for pointing out my mistake. – Garabed Gulbenkian Jul 08 '13 at 17:29

1 Answers1

12

To my best knowledge, the Banaschewski-Moore paper from some twenty years ago is pretty much the last recorded progress on the topic.

The two main papers on the subject are the Banaschewski-Moore paper and a paper by Higasikawa, both are from more or less twenty years ago.

  1. Bernhard Banaschewski, Gregory H. Moore, The dual Cantor-Bernstein theorem and the partition principle, Notre Dame J. Formal Logic 31 (3), (1990), 375–381.

  2. Masasi Higasikawa, Partition principles and infinite sums of cardinal numbers. Notre Dame J. Formal Logic 36 (1995), no. 3, 425–434.

You can find a nice diagram of implications in Gregory Moore's book "Zermelo's Axiom of Choice" (which, oddly enough, is the second time I refer to on this site today).

I have some master plan on how to prove its independence from the axiom of choice, but it's a wild and vague dream at the moment which doesn't worth much mentioning except for the fact that I believe, at the moment, that PP does not imply the axiom of choice. For whatever that is worth.

One interesting fact on $\sf PP$ is that it implies the existence of non-measurable sets of real numbers all by itself. $\sf PP$ implies $\sf DC$, as well $\aleph_1\leq2^{\aleph_0}$ and therefore implies the existence of a non-measurable set. But in fact even much weaker versions of $\sf PP$ imply the existence of non-measurable, for example $\sf WPP$ which asserts $A\leq^\ast B\rightarrow B\nless A$, or in other words: if $B$ can be mapped onto $A$ then it cannot have a strictly smaller cardinality.

The reason that $\sf WPP$ implies the existence of a non-measurable set is that $\Bbb R$ can always be mapped onto $[\Bbb R]^\omega$, the set of countably infinite sets of real numbers, and of course can be mapped into that set injectively.

Since in $\sf ZF$ we have $\Bbb R\leq[\Bbb R]^\omega\leq^\ast\Bbb R$, in $\sf ZF+WPP$ we have that $\Bbb R$ is equipotent with $[\Bbb R]^\omega$. Sierpinski proved from this assumption that there exists a non-measurable set.

Sierpinski, W. "L’axiome de M. Zermelo et son rôle dans la théorie des ensembles et l’analyse." Bulletin de l’Académie des Sciences de Cracovie, Classe des Sciences Math., Sér. A (1918), 97-152.

Community
  • 1
Asaf Karagila
  • 38,140