Can every infinite set be divided into pairwise disjoint subsets of size $n\in\mathbb{N}$?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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,

Answer 4

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

Answer 5

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.

Answer 6

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.