# Name for this generalized pigeonhole principle?

For a set $X$, let $|X|$ denote its cardinality. A block of a partition is a non-empty element of the partition.

Let $P$ and $Q$ be two partitions of a set $X$. If $|P| < |Q|$ then $P$ contains a block $B$ which intersects two distinct blocks of $Q$.

What is this principle called?

The proof is immediate for finite $X$, and is an easy consequence of the Axiom of Choice for infinite $X$. I am interested in using this result, and would like to refer to its proper name and to cite it correctly. Jech's Set Theory and several online sources don't seem to mention this result. In particular the Consequences of the Axiom of Choice project doesn't seem to list it (at least not in this specific form).

I would also be interested to know whether this principle is equivalent to some known consequence of the Axiom of Choice.

-
It certainly follows from "If $A$ maps onto $B$, then $B$ maps 1-1 into $A$.'' As I recall, it is not known whether the latter is equivalent to AC. – Goldstern Nov 25 '12 at 21:57
I assume that by $<$ you mean there is an injection one way, but not the other way. – Goldstern Nov 25 '12 at 21:58
@Goldstern: I was using the notation from Jech, where this means $|X| \le |Y|$ and $|X| \ne|Y|$: there exists an injection but no bijection. – András Salamon Nov 26 '12 at 0:48
I see; this is equivalent to what I said. – Goldstern Nov 26 '12 at 0:53

## 1 Answer

This is equivalent to the Weak Partition Principle (a close relative of the Partition Principle mentioned by Goldstern). The Weak Partition Principle is form 100 in Consequences of the Axiom of Choice by Howard and Rubin (the Partition Principle is form 101).

The Weak Partition Principle asserts that if there is a surjection from $X$ onto $Y$ then it is not the case that $X$ has strictly smaller cardinality than $Y$ (i.e. $X \prec Y$). In contrapositive form, if $X \prec Y$ then there is no surjection from $X$ onto $Y$.

To see that the Weak Partition Principle implies your statement, note that if $P$ contains no block which intersects two distinct blocks of $Q$ then each block of $P$ is contained in a unique block of $Q$ and the map $P \to Q$ thus defined is necessarily a surjection. By the Weak Partition Principle, this cannot hold at the same time as the hypothesis $P \prec Q$.

For the converse, suppose that the Weak Partition Principle fails as witnessed by sets $X \prec Y$ and a surjection $p:X \to Y$. Let $Q = \lbrace p^{-1}(y) : y \in Y \rbrace$ and $P = \lbrace \lbrace x \rbrace : x \in X\rbrace$. These are two partitions of $X$ with $P \prec Q$ and every block of $P$ is clearly contained in a unique block of $Q$.

-
This argument also shows that the principle is equivalent to the special case where $P$ is the partition into singletons. This special case can alternatively be described as the assertion that no set is strictly smaller than a partition of it. See how it is put by Dr. Strangechoice mathoverflow.net/questions/22927/…, whom I believe you know very well. In particular, the principle implies that $\kappa^+\leq 2^\kappa$ for every infinite cardinal $\kappa$. – Joel David Hamkins Nov 26 '12 at 0:33
Thank you. The citation seems to be to * A. Lindenbaum and A. Tarski, "Communication sur les recherches de la théorie des ensembles", Comptes rendus des séances de la Société des Sciences et des Lettres de Varsovie, Classe III, 19, 299–330, 1926. – András Salamon Nov 26 '12 at 0:40