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

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.

  • 1
    Are we talking about [Cantor-Schroeder-Bernstein](http://en.wikipedia.org/wiki/Cantor%E2%80%93Bernstein%E2%80%93Schroeder_theorem)? 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.2012-11-01
  • 0
    @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.2012-11-01
  • 0
    I'm sorry: then why does it say "However, its various proofs are non-constructive"? Is the Wikipedia article wrong?2012-11-01
  • 1
    @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?2012-11-01
  • 0
    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.2012-11-01
  • 1
    @Matt: There are people who reject the law of excluded middle. For them the proof of this theorem is *not* valid. Many of these people are doing what it is known as "constructive mathematics" in one way or another. This is a strong assertion than the common "define an object", in that aspect the proof *is* constructive because it tells you exactly how to define the bijection. However the proof relies on the fact that something is either true or false, which is rejected by some people.2012-11-01
  • 0
    Ok. Could you re-write your last 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
    Regarding Q2: But how can I write down the bijection $f:A \to B$ if I know that it exists?2012-11-02
  • 1
    @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.2012-11-02
  • 0
    @AsafKaragila That's what I thought. So this answer is actually incorrect?2012-11-02
0

Let $(A_i)_{i \ge 0}$ be a countable family of sets and $A = \cup A_i$.

For each $i \ge 0$ let there be given $([a_i]_k)_{\,k \ge 1}$, a bijective enumeration of the set $A_i$.

We will be using the following result (see it also used over here).

Proposition 1: A set $A$ is countably infinite if there exist a family of subsets of $A$,
$(A_n)_{\, n \ge 0}$ satisfying

$\quad |A_n| = n$
$\quad A_k \subset A_{k+1} \; \text{ for } k \ge 0$
$\quad A = \bigcup_k A_k$

Moreover, the chain $A_0 \subset A_1 \subset A_2 \dots$ defines an explicit bijective enumeration of the set $A$.

Proof
Given such a chain of finite subsets, for every $k \ge 1$ there exist one and only one element $a_k \in A_k$ such that $a_k \notin A_{k-1}$. One can also easily show that $(a_k)_{\,k \ge 1}$ is a bijective enumeration of $A$. $\quad \blacksquare$

For each $i \ge 0$ and $m \ge 1$ we define

$\quad A_{(i,m)} = \{ x \in A_i \,| \, x \in \{([a_i]_1,([a_i]_2,\dots,([a_i]_m\}\}$

We define

$$\quad R_m = \bigcup_{i=1}^m A_{(i,m)}$$

If $B$ is any subset of $A$ and if $R_m$ is not included in $B$ we can apply an operator $\mathcal R_m$ to $B$ as follows:

$\quad B \mapsto B \cup \{\hat r\}$

where $\hat r$ is 'cranked-out' as follows:

$\text{1. }$ Find the smallest integer $k$ with $1 \le k \le m$ such that $A_{(k,m)}$ is not contained in $B$.

$\text{2. }$ Find the smallest integer $j$ with $1 \le m \le m$ such that $[a_k]_j \notin R_m$; set $\hat r = [a_k]_j$.

If $C$ is any proper subset of $A$ we define $\mathcal M$ on $C$ as follows:

$\quad C \mapsto m \; \text{ where } m \text{ is the smallest positive integer such that } R_m \text{ is not included in } C$

All the constructions are now available to define the recursion. With $D_0 = \emptyset$ and given $D_k \subsetneq A$ with $k \ge 0$, define

$$ D_{k+1} = \mathcal R_{\mathcal M (D_k)}(D_k)$$

It is easy to see that this chain satisfies the conditions stated in proposition 1.

-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.

  • 0
    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.2012-11-02
  • 0
    @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.2012-11-02
  • 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