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|$?

  • 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

4

First note that the Cantor-Bernstein is constructive and does give us a bijection.

Secondly, if we require the sets in $\cal A$ are pairwise disjoint then we can explicitly define a map by sending $A_i$ to $\{i\}\times\Bbb N$ and composing the whole thing with the Cantor pairing function. However if we don't have this assumption then we cannot do it that way because the function from the union is not well-defined anymore. We could require that an element is mapped to $\langle i,k\rangle$ where $i$ is the least index such that $a\in A_i$, but then the function is not a bijection anymore.

For this reason it is often simpler just to show mutual bijections (or in the $\mathbb N$ case, a surjection from $\mathbb N$ onto the union is also enough).

As for your second question, the answer is no. By the assumption that $|A|=|B|$ we can prove that there exists a bijection between $A$ and $B$, but it is not necessary that we can define it. This of course, depends on the meaning of "define", but if we take it to mean write an explicit formula that the collection of sets satisfying it is a bijection between $A$ and $B$, then the answer is no.

For example, if we can write down a definitive bijection between $\mathbb R$ and some ordinal then we invariably solve the continuum hypothesis. We could of course parameterize, but that would depend on parameters which are not definable themselves. In fact, if your underlying theory is merely ZF then such bijection would also prove that $\mathbb R$ can be well-ordered, which cannot be done without choice.

  • 0
    Ok. Could you re-write your l$a$st paragraph to make it clearer? I don't understand it. Thanks.2012-11-02
3

Let $U=\bigcup\limits_{A\in\mathcal A}A$. If one knows a bijection $A:\mathbb N\to\mathcal A$, hence $\mathcal A=\{A(n)\mid n\in\mathbb N\}$, and if, for every $A(n)$ in $\mathcal A$, one knows a bijection $B_n:\mathbb N\to A(n)$, then the function $C:\mathbb N\times\mathbb N\to U$, $(n,k)\mapsto B_n(k)$, is a surjection. If $\mathcal A$ is made of disjoint sets, $C$ is a bijection.

In the general case, $|U|\leqslant|\mathbb N\times\mathbb N|=|\mathbb N|$. Since $A(0)\subseteq U$ and $|A(0)|=|\mathbb N|$, this is enough to deduce that $|U|=|\mathbb N|$.

When $\mathcal A$ is not made of disjoint sets, one could get an explicit bijection between $\mathbb N\times\mathbb N$ and $U$ based on the bijections $B_n$, using $B_n$ only on the elements of $A(n)$ not already in $\bigcup\limits_{k\lt n}A(k)$, and concatenating recursively the result, but to write down completely this construction would be somewhat messy.

1

Q1. Yes, see Cantor-Bernstein's theorem.

Q2. Yes, this is the definition of $|A|=|B|$. And, $|A|\le |B|$ is defined as there is an injection $A\to B$, and the Cantor Bernstein theorem states that $|A|\le |B|\le |A| \implies |A|=|B|$ (using the axiom of choice).

Anyway, in your case the same method works as for the denumerablility of $\Bbb Q$, or $\Bbb N\times\Bbb N$, and no need for the general Cantor-Bernstien.

  • 0
    @AsafKaragila That's what I thought. So this answer is actually incorrect?2012-11-02
-1

The answer to question one is given in did's answer and is yes, in this case we can write down a bijection explicitly, even if we don't assume $A$ and $B$ to be disjoint.

The answer to question two is given in Asaf's answer and is no, in general we cannot expect to write down the bijection even if we know that it exists. For example, let's assume we know that there is a bijection $f: \mathbb R \to \omega_2$. Since $\omega_2$ is an ordinal it is well-ordered so that $\mathbb R$ would automatically also be well-ordered, without the need for AC. But we know that $\mathbb R$ is not well-ordered unless we assume AC.

  • 1
    You got the gist of what I was saying, but you translated it wrong. At least that last part. Your last sentence reads "The real numbers cannot be well-ordered if and only if the axiom of choice fails", which is false. It is consistent that $\mathbb R$ can be well-ordered and the axiom of choice fails, but it is not provable without *some* choice that the real numbers can be well-ordered.2012-11-02