11
$\begingroup$

Let $S$ be an infinite set and $n$ be a natural number. Does there exist partition of $S$ in which each subset has size $n$?

  1. This is pretty easy to do for countable sets. Is it true for uncountable sets?

  2. If (1) is true, can it be proved without choice?

$\endgroup$
3
  • 1
    $\begingroup$ If you can write $S$ as a union of $n$ disjoint subsets, say $S_1 \cup \dots \cup S_n$ where the $S_i$'s all have the same cardinality, then take a bijection $\pi_i : S_1 \to S_i$ and consider the sets $\{ \{ \pi_i(s) \, | \, 1 \le i \le n \} \, | \, s \in S_1 \}$ which form a partition of $S$ with $n$ elements for each element of your partition. So we've reduced the problem to finding a partition of $S$ in $n$ subsets of the same cardinality... I'm stuck there. $\endgroup$ May 6, 2013 at 6:16
  • $\begingroup$ I don't understand why you accepted an answer to (1) only, in the presence of an other answer that addresses both (1) and (2). $\endgroup$ May 6, 2013 at 7:46
  • $\begingroup$ @MarcvanLeeuwen The other answer came after I'd accepted Hagen's already. You are right, though, I've moved the accept. $\endgroup$
    – Alexander Gruber
    May 6, 2013 at 7:49

6 Answers 6

10
$\begingroup$

The answer is yes, under the axiom of choice, such a partition is possible. There are several ways of seeing this. For example, choice gives us that any set is in bijection with an infinite ordinal. But, for any infinite ordinal $\alpha$, there is a bijection between $\alpha$ and $\alpha\times \{1,\dots,n\}$. The bijection is in fact canonical, in the sense that there is a "uniform" procedure that applied to any infinite ordinal $\alpha$ produces such a bijection. If you are somewhat familiar with ordinal numbers, a proof can be found in this blog post of mine.

Of course, if $\alpha$ is in bijection with $X$, then $\alpha\times \{1,\dots,n\}$ is in bijection with $X\times \{1,\dots,n\}$, so the latter is in bijection with $X$. The required partition is then the image under the bijection of the sets $A_a=\{(a,i)\mid 1\le i\le n\}$, for $a\in X$.

(To mention but one other standard argument, using choice, we have that $X$ and $X\times X$ are in bijection so, invoking the Bernstein-Schroeder theorem, we conclude that $X$ and $X\times\{1,\dots,n\}$ are in bijection as well.)

On the other hand, the answer is no, without the axiom of choice it is in general not possible to produce such a partition. This is addressed at length in this MO answer, with details in the references linked there.

$\endgroup$
5
$\begingroup$

For infinite sets $S$ and finite sets $A$, we have $|S\times A|=|S|$. If we let $A=\{1,\ldots,n\}$, then the images of sets $\{s\}\times A$, $s\in S$, under a corresponding bijection make a partition as desired.

$\endgroup$
2
  • $\begingroup$ Your solution is cleaner than mine, but I believe we share the same ideas. The preimage of your set $S \times \{i\}$ under the bijection given by $|S \times A| = |S|$ would be my set $S_i$. $\endgroup$ May 6, 2013 at 6:23
  • 3
    $\begingroup$ this solution uses some choice. The case where $S$ is countable does not require choice, but the claimed cardinal equality required for general cardinalities does require choice. $\endgroup$ May 6, 2013 at 6:46
4
$\begingroup$

There is a concept called amorphous sets, which becomes interesting when the axiom of choice fails. These sets are such that you cannot partition them into two distinct infinite sets.

One property of amorphous sets is that if we take an infinite partition of an amorphous set, then all but finitely many parts have the same size (and all these sizes are finite, of course). There are unbounded amorphous sets, which can be partitioned into arbitrarily large size, but there are also bounded amorphous sets.

So bounded amorphous sets form a counterexample to (1), they cannot be partitioned into sets of size $n$ for large enough $n$.

But this property of "non-divisibility" can be found in other sets, which are not amorphous. Although it is often harder to prove this property holds. For example in Cohen's first model there exists an infinite set of real numbers which does not have a countably infinite subset. This set is not amorphous because amorphous sets cannot be linearly ordered. And yet, it follows from the construction of the model that every partition of that set into finite parts is almost entirely singletons.

$\endgroup$
2
$\begingroup$

For 1. Take any bijection $f$ between your set and $(0,1)$. Divide $(0,1)$ into $n$ intervals. The sets parametrized by $x$ in $\left(0,\frac{1}{n}\right)$ are $f^{-1}\left(\left\{x,x+\frac{1}{n},x+\frac{2}{n},x+\frac{3}{n},...,x+\frac{n-1}{n}\right\}\right)$.

$\endgroup$
1
$\begingroup$

A geometric answer, for cardinality $c$. For $x, y \in S^1$ (the unit circle), let $x \sim y$ iff $x$ and $y$ are vertices of the same regular $n$-gon centered at the origin. Now the title of this question speaks of infinite sets generally, which is a different question. The approach by Hagen von Eitzen is probably about the best you'll find in the general case.

$\endgroup$
0
$\begingroup$

If you can write $S$ as a union of $n$ disjoint subsets, say $S_1 \cup \dots \cup S_n$ where the $S_i$'s all have the same cardinality, then take a bijection $\pi_i : S_1 \to S_i$ and consider the sets $\{ \{ \pi_i(s) \, | \, 1 \le i \le n \} \, | \, s \in S_1 \}$ which form a partition of $S$ with $n$ elements for each element of your partition. So we've reduced the problem to finding a partition of $S$ in $n$ subsets of the same cardinality...

If $S$ has the cardinality of $\mathbb R$ (not a set theorist here... $c$ stands for $|\mathbb R|$?), we might as well just solve the problem for $\mathbb R$ using the bijection given from the bijection from Cantor-Bernstein-Schroeder's theorem (which doesn't rely on choice, apparently!). Take $$ S_1 = ]-\infty, 1], \quad \dots \quad S_i = \, ]i-1,i], \quad \dots \quad S_n = \, ]n-1,\infty[ $$ and in this case since you don't need choice to compute a bijection between those intervals, you're good to go.

Hope that helps,

$\endgroup$
2
  • 1
    $\begingroup$ you don't need choice to get a bijection from $S$ to $\mathbb R$ since you assumed $S$ has the same cardinality as $\mathbb R$. $\endgroup$ May 6, 2013 at 6:23
  • 1
    $\begingroup$ @Ittay : Hm, I always thought that the Cantor-Bernstein-Schroeder theorem relied on choice! I just learned that it didn't. Thanks for pointing that out! $\endgroup$ May 6, 2013 at 6:26

You must log in to answer this question.

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