# Explicit bijection between equipotent sets?

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

-
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. – GEdgar Oct 31 '12 at 14:11
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? – Rudy the Reindeer Oct 31 '12 at 15:50
@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. – Asaf Karagila Oct 31 '12 at 20:00
@AsafKaragila Why are there $2^{\aleph_0}$ bijections $A \to \mathbb N$ if $A$ is in bijection with $\mathbb N$? – Rudy the Reindeer Oct 31 '12 at 21:31
@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... – Asaf Karagila Nov 1 '12 at 22:21

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.

-
Are we talking about Cantor-Schroeder-Bernstein? Because if we are: "... An important feature of this theorem is that it does not rely on the axiom of choice. However, its various proofs are non-constructive, as they depend on the law of excluded middle, ...". I thought non-constructive meant that it doesn't give you the actual thing you're after (bijection in this case). The proof argues with infinite sequences of elements. I don't see how it gives me the bijection. Perhaps you could elaborate? Cheers mate. – Rudy the Reindeer Nov 1 '12 at 9:20
@Matt: The proof goes like "Take $f$ and $g$ to be injective functions, now define the following sequence of sets, now define a bijection $h$." So it gives you a bijection, it gives you an explicit definition for the bijection, if we took an element such that ... then ...; otherwise .... Of course, we have to use $f$ and $g$ as parameters, but that much is fine. – Asaf Karagila Nov 1 '12 at 9:22
I'm sorry: then why does it say "However, its various proofs are non-constructive"? Is the Wikipedia article wrong? – Rudy the Reindeer Nov 1 '12 at 9:29
@Matt: There is an immense ambiguity as to what does "constructive proof" mean: Are you talking about defining an object; are you talking about using law of excluded-middle; are you talking about doing things within a particular constructive system? – Asaf Karagila Nov 1 '12 at 13:33
I am not sure what you mean. I think constructive proof means it constructs the thing you claim exists. In this case, the bijection between the 2 sets. – Rudy the Reindeer Nov 1 '12 at 13:35

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.

-

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.

-
Regarding Q2: But how can I write down the bijection $f:A \to B$ if I know that it exists? – Rudy the Reindeer Nov 2 '12 at 8:00
@Matt: You can't always write it. Unless you use "write" in a very broad sense. For example, assume CH we can show that there is a bijection between $\mathbb R$ and $\omega_1$. But in the common sense of the word, to write it down would be to prove it exists in ZF, or ZFC. We cannot do that because CH is not provable from ZFC, so it means that we cannot write down such function. – Asaf Karagila Nov 2 '12 at 8:05
@AsafKaragila That's what I thought. So this answer is actually incorrect? – Rudy the Reindeer Nov 2 '12 at 8:06

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.

-
No, $\mathbb R$ can be well-ordered even if we assume less than AC. For example, we can simply assume that $\mathbb R$ is well-ordered. Your last sentence implies that a well-ordering of $\mathbb R$ would imply the axiom of choice. – Asaf Karagila Nov 2 '12 at 9:45
@AsafKaragila This is how I understand your answer. I am trying to state your answer in my own words. Can you help me by explaining to me what you actually meant? Thanks. – Rudy the Reindeer Nov 2 '12 at 10:33
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. – Asaf Karagila Nov 2 '12 at 11:43