3
$\begingroup$

I'm thinking about the proof of the following theorem:

If $\mathcal A$ is a denumerable family of denumerable sets then $\bigcup \mathcal A$ is denumerable. (denumerable means that there is a bijection to $\mathbb N$)

The proof shows $|\mathbb N| \leq |\bigcup \mathcal A|$ and $|\mathbb N| \geq |\bigcup \mathcal A|$ rather than giving an explicit bijection $f: \mathbb N \to \bigcup \mathcal A$.

Question 1: In this case, is it possible to give an explicit bijection?

Question 2: In general, is it possible to find a bijection between set $A$ and $B$ if we know that $|A| = |B|$?

  • 0
    Of course you have to CHOOSE a bijection to $\mathbb N$ for each of your sets, requiring the Axiom of Choice. In that sense, your original question 1 has answer NO.2012-10-31
  • 0
    Dear @GEdgar, I think a bijection between $\mathcal A = \{A_i\}_{i \in I}$ and $F = \{f_i : A_i \to \mathbb N \}$ would be $g(A_i) = f_i$. Since I have a bijection $f: \mathbb N \to \mathcal A$, I get a bijection $g \circ f : \mathbb N \to F$. A bijection from $F$ to $\mathbb N$ then gives me a choice function on $P(F) \setminus \{ \varnothing \}$, since sets in bijection with $\mathbb N$ are well-ordered. Where does my reasoning go wrong?2012-10-31
  • 0
    @Matt: If $A$ is denumerable then there are $2^{\aleph_0}$ bijections between $A$ and $\mathbb N$. There is a huge difference between a countable union of *enumerated* sets (i.e. pairs of sets and bijections) and just any countable union of countable sets.2012-10-31
  • 0
    @AsafKaragila Why are there $2^{\aleph_0}$ bijections $A \to \mathbb N$ if $A$ is in bijection with $\mathbb N$?2012-10-31
  • 0
    @Matt: There are $2^{\aleph_0}$ permutations of $\mathbb N$ with itself. Compose each with a fixed bijection from $A$ to $\mathbb N$ to get another more!2012-10-31
  • 0
    @AsafKaragila Sorry, how did you compute $\aleph_0 ! = 2^{\aleph_0}$?2012-11-01
  • 0
    There are $2^{\aleph_0}$ partitions of $\mathbb N$ into exactly two disjoint infinite sets. For each such pair take the function which replaces these sets (in their order, first with first, second with second, etc.); this gives you at least that many permutations, and it is easy to compute there cannot be more.2012-11-01
  • 0
    @AsafKaragila I'm sorry, but how do I see that there are $2^{\aleph_0}$ partitions of $\mathbb N$ into two disjoint infinite sets?2012-11-01
  • 0
    @Matt: There are only countably many finite sets, and therefore only finitely many co-finite sets. Therefore you have $2^{\aleph_0}$ infinite co-infinite sets. Take the equivalence relation of being "equal or complement" and you have exactly two elements in every equivalence class; and therefore you have $2^{\aleph_0}$ pairs of partitions into two infinite co-infinite parts.2012-11-01
  • 0
    @AsafKaragila I'm sorry, I don't understand how the number of possible bijections between a set $A$ and $\mathbb N$ is relevant to whether I need AC or not.2012-11-01
  • 0
    @Matt: If you have so many bijections, and you need to *choose* one for each set, how will you do that without AC?2012-11-01
  • 0
    @AsafKaragila I have countably many sets. So I do it using countable choice. But even so: the number of possible bijections to choose from is irrelevant. Even if there was only one per set, we'd still need countable choice. So I still have no idea why you mention it.2012-11-01
  • 1
    @Matt: First, of course you use countable choice. In fact you use *less*. You can limit yourself to "countable choice from families of sets of size continuum" or even just "countable unions of countable sets are countable". If you have a single bijection of $A_i$ with $\mathbb N$ (e.g. if the sets are given as sequences) then there is absolutely no use of choice to show that the union is countable. And the only reason I bring this up is that your original comment to GEdgar indicated that you missed the point there. I don't care if you use choice, I'm not offended in any way...2012-11-01

5 Answers 5