How to show $|S| = |S \times A|$, where $S$ is infinite and $A$ is finite.

Question

Exactly what the title says. I have a proof where at one point, I use the fact that two copies of $S$ can be put in bijection with $S$, but I don't know how I'd prove that.

For countable sets, I can construct an explicit bijection, so I thought about partitioning $S$ into countable sets. But how can I be sure such a partition exists? I can't just say "take a countable subset, then take a countable subset of the remaining set, etc". I can surject it into a countable set, but I don't think that helps me much.

Is there a trick to doing this? (Also, I use the Axiom of Choice elsewhere in the proof, so that's allowable)

Answer 1

You have to use the axiom of choice to prove this result in it generality. You can use several of its equivalents, of course, and it depends which one you are the most comfotable with.

You mentioned that you don't know much about ordinals and well-orders. So let us take another approach.

First of all, note that it suffices to prove that for $A=\{0,1\}$. If $A$ has more elements then one can proceed by induction by breaking $A$ into smaller parts and using the induction hypothesis and the case above.

So now to prove that $S\times\{0,1\}$ and $S$ have the same cardinality. Let us use Zorn's lemma and prove the following thing:

There exists a partition of $S$ that each part has size $\aleph_0$.

Why would that be helpful? If we write $S=\bigcup S_i$, where $S_i$ is our partition into countably infinite parts, then $S\times\{0,1\}=\bigcup S_i\times\{0,1\}$. Using the axiom of choice the result is simple now, and I will leave it to you to finish the proof on your own.

So let us prove the main cake: the existence of this partition. Using Zorn's lemma we need to come up with a partial order that every chain has an upper bound, and then argue that the maximal element must have the wanted properties.

Let $P$ be the set of all partitions into $\aleph_0$-sized parts of a subset of $S$, and let us order them by $\subseteq$. Since $S$ is infinite, and the axiom of choice holds, it has a countably infinite subset which has an obvious partition. So now $P$ is non-empty, and let $C$ be a chain in $P$, it is easy to check that $T=\bigcup C$ is a partition of a subset of $S$, and each of its parts have size $\aleph_0$.

We can conclude, if so, that by Zorn's lemma there is a maximal element, $T$. By definition $T$ is a partition of a subset of $S$, let $S'=\bigcup T$, then $S\setminus S'$ cannot be infinite, or else we can add another infinite part to $T$ and contradict its maximality. Therefore it must be finite, if it is empty we are done, otherwise just pick one $S_i\in T$ and replace it by $S_i\cup(S\setminus S')$ which is a countably infinite set as wanted.

Answer 2

Enumerate $S = \{ s_{\alpha} : \alpha < \lambda \}$ and $A = \{ a_i : i < n \}$. Define a map $S \times A \to S$ by $$(s_{\alpha}, a_i) \mapsto s_{\alpha \cdot n + i}$$ Check that this is an injection, and deduce the result.