6
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ 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. $\endgroup$
    – Goldstern
    Commented Nov 25, 2012 at 21:57
  • $\begingroup$ I assume that by $< $ you mean there is an injection one way, but not the other way. $\endgroup$
    – Goldstern
    Commented Nov 25, 2012 at 21:58
  • $\begingroup$ @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. $\endgroup$
    – András Salamon
    Commented Nov 26, 2012 at 0:48
  • $\begingroup$ I see; this is equivalent to what I said. $\endgroup$
    – Goldstern
    Commented Nov 26, 2012 at 0:53

1 Answer 1

Reset to default
8
$\begingroup$

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$.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Joel David Hamkins
    Commented Nov 26, 2012 at 0:33
  • $\begingroup$ 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. $\endgroup$
    – András Salamon
    Commented Nov 26, 2012 at 0:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .