Halving an Infinite Set

In this post, we consider the following:

Conjecture. Let $S$ be an infinite set. Then, there exists a partition of $S$ into two subsets that are in bijection with each other.

Remark. If $S$ is finite, then this is true iff $|S|\mod 2 = 0$ . We don’t need the Axiom of Choice (AC) for that; however, for $S$ an arbitrary infinite set, I suspect we’d need AC.

Proof. Consider $A = \left\{ (s,0):s \in S \right\},B = \left\{ (s,1):s \in S \right\},S^{'} = A \cup B$ . We have $|A| = |B| = |S|$ by construction, so we have that $\left| S^{'} \right| = |S|$ as well. Thus, there exists a bijection $f:S \rightarrow S^{'}$ . This bijection is exactly the key to defining the desired partition: define $A^{'} = f^{- 1}(A),B^{'} = f^{- 1}(B)$ . Since $A,B$ are disjoint by construction, by properties of bijections we have that $A^{'},B^{'}$ are disjoint as well, and also by properties of bijections (see “Topology as an Algebraic Structure”) we have $A^{'} \cup B^{'} = f^{- 1}(A) \cup f^{- 1}(B) = f^{- 1}(A \cup B) = S$ . Thus, $\left( A^{'},B^{'} \right)$ is the desired partition. $\blacksquare$

I suspect that AC comes in with the construction of $f$ , which I suspect in general requires a choice function. (More generally, if $A,B$ are in bijection and possibly infinite, then I suspect in general a bijection $f:A \rightarrow B$ can only be defined via a choice function.) Thus, I suspect that this result is equivalent to the Axiom of Choice for general infinite sets $S$ . (Note that the result is immediate without AC if $S$ is a countable set — just pick out the even-indexed and odd-indexed elements.) Also, by induction we have that if $n \in \mathbb{Z}_{+}$ , then for any infinite set $S$ we can find a partition $\left( S_{i} \right)_{i = 1}^{n}$ of it such that the $S_{i}$ are all in bijection with each other. If the “halving infinite set” is equivalent to AC, then this would also be equivalent to AC. However, this general statement would be true if $S$ was a countable set regardless of AC.

Let’s try to show that the halve infinite set result implies AC. Say we have an indexed family of nonempty sets $S = \left\{ S_{i} \right\}_{i \in I}$ . We want to assume the result and construct a choice function $f:I \rightarrow \cup S$ .

Let $i \in I$ . If $S_{i}$ is a finite set, then $S_{i}$ is in bijection with $S_{n}$ for some $n \in \mathbb{Z}_{+}$ . Let $f(i)$ be the image of 1 under this bijection (the first element in the finite set ordering.) (I don’t think constructing this bijection for finite sets requires the Axiom of Choice.)

Otherwise, $S_{i}$ is an infinite set. Then, there exists a partition $(A,B)$ of $S_{i}$ such that we can find a bijection $g:A \rightarrow B$ . We want to use $g$ to somehow “pick” an element of $S_{i}$ that we then select as the image of our choice function $f$ .

It remains to continue this.

Started June 9, 2022; revisited January 2023.

Share and like (need WordPress account to like):

Leave a comment Cancel reply