1
$\begingroup$

Given $A$ an uncountable set, is it true that $A \times \mathbb N$ is in bijection with $A$ itself?

I think this should be true, but how to construct a bijection?

$\endgroup$
  • $\begingroup$ It's true. I assume the axiom of choice is available; you will need it. By the way, you could replace "uncountable" with "infinite", but the case where $A$ is countably infinite is trivial. $\endgroup$ – bof Oct 8 '17 at 2:46
  • 2
    $\begingroup$ Hint: it will be enough (and may be easier) to prove that $A$ is in bijection with $B\times\mathbb N$ for some set $B.$ Once you have that, then $A\times\mathbb N$ is in bijection with $(B\times\mathbb N)\times\mathbb N,$ which is in bijection with $B\times(\mathbb N\times\mathbb N),$ which is in bijection with $B\times\mathbb N,$ which is in bijection with $A.$ $\endgroup$ – bof Oct 8 '17 at 2:47
  • $\begingroup$ Hint: you might start by using the axiom of choice to prove that there is a partition $B$ of $A$ into countably infinite sets, and then make further use of the axiom of choice to get a bijection between $A$ and $B\times\mathbb N.$ $\endgroup$ – bof Oct 8 '17 at 2:51
  • $\begingroup$ @bof strange, but user488869's sole contribution to this site was his answer to this one question, and then they unregister. Also, is their answer correct? (see my comment to this 'disappearing' user). $\endgroup$ – CopyPasteIt Oct 8 '17 at 15:00
  • $\begingroup$ @MikeMathMan Yes, their answer is correct for the reason bof points out. $\endgroup$ – Noah Schweber Oct 21 '17 at 2:42
1
$\begingroup$

Consider the collection of all $(B,\phi)$ where $B \subseteq A$ is a subset and $\phi : B \rightarrow B \times \mathbb{N}$ is a bijection. It is nonempty (it contains any countable set), partially ordered by $(B,\phi) < (C,\psi)$ if $B \subseteq C$ and $\psi|_B = \phi$, and every chain has an upper bound. By Zorn's lemma there is a maximal element $(B,\phi)$.

$B$ must be in bijection to $A$: if not, then $A \backslash B$ is infinite and you can choose an infinite, countable subset $U \subseteq A$ disjoint from $B$ and use any bijection $U \times \mathbb{N} \rightarrow U$ to extend $\phi$ to a bijection $$(B \cup U) \times \mathbb{N} \longrightarrow B \cup U,$$ contradicting maximality of $(B,\phi)$.

$\endgroup$
  • $\begingroup$ @bof That's a good point. I think this can be fixed. $\endgroup$ – user488869 Oct 8 '17 at 3:05
  • $\begingroup$ Not able to conclude as you do that "if not, then $A \backslash B$ is infinite". Appears to me that nothing prevents $B$ from being all of $A$ except for one missing element $\hat a \in A$. $\endgroup$ – CopyPasteIt Oct 8 '17 at 14:29
  • 2
    $\begingroup$ @MikeMathMan If $|B|=|A|$ and $|B\times\mathbb N|=|B|,$ then $|A\times\mathbb N|=|A|$ and everything is fine. So what we're using here is the fact that, if $A$ is infinite and $F$ finite, then $|A\setminus F|=|A|,$ a simpler consequence of the axiom of choice than the OP's question. $\endgroup$ – bof Oct 8 '17 at 21:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.