1
$\begingroup$

I have come across a rather unsatisfying proof to this, which, in fact, I cannot even understand fully. Here it goes.

We can say that $A=\cup_{i \in I} A_i$ where $I \sim \mathbb{N}$. Without loss of generality we can say that $I$ is $\mathbb{N}$, so: $A=\cup_{n \in \mathbb{N}} A_n$.

I will not state what I was thinking about. We have some set $A_1$ then some set $A_2$ etc... we know that they are individually countable, i.e. there is bijection for each of the set to the natural numbers, we need to show that there is such a bijection for the union of these sets. In my view it is not possible to construct some function $f$ for the union that by definition would map everything from set $A_1$ then proceed to map everything from set $A_2$ etc., this is due to $2$ reasons, first: there are countably infinite number of elements in each of the sets, so we will "run out of indices" and second there is a countably infinite number of sets themselves. For that reason, one should define the bijection $f$ for the union in such a manner that you take "first" element from set $A_1$ then take first element from set $A_2$ etc. But even this has a problem, because there is a countably infinite number of sets, so "we will run out of indices" by even taking the first elements of each set. It would be quite easy to show this result for say 10 sets or whatever the natural fixed number, but there is a problem when we are asked to show it for the countable number of such sets. I am also thinking about these countable sets in a very general perspective, I do not think of them as containing numbers (maybe you want to count the number of "wiggles" in the fractal shape, for example, and those are the objects of your sets; not sure, whethr that would be a countable set or just uncountable infinite).

The solution that I see is the following, which assumes that the elements of the sets are numbers. They define $n_a = min\{n \in \mathbb{N}, a \in A_n\}$. Then they say that for any $n \in \mathbb{N}$ (which I think they mean to say $a \in A_n$) $\exists \ f_n: A_n \rightarrow \mathbb{N}$. Then define $f:A\rightarrow \mathbb{N}$ by $f(a)=f_{n_a}(a)$. I do not follow this. What if set $A_1$ has all elements greater than $1$ then the minimum is always $n$ i.e. $1$ so for each element in that set you would be calling the function $f_1$, which makes sense. Now imagine that set $A_2$ has all elements greater than $2$, so minimum is $2$ and you would be calling $f_2$, but what if this function $f_2$ is now mapping to the same natural numbers all over again as the $f_1$?

EDIT: also what if $a \in A_n$ is some irrational number. How will you call $f_{\text{irrational number}}$..

Problem 1.23

$\endgroup$
2
  • 1
    $\begingroup$ If you assume that all your sets are countably infinite and disjoint, then the proof is the same as showing that $\mathbb{N} \times \mathbb{N}$ is countable: biject each set with $\mathbb{N}$, then each set forms a "row" of an infinite 2D array. Then traverse this array in the familiar diagonal manner. You then have some technicalities to sort out if the sets are sometimes finite and/or sometimes non-disjoint (but intuitively this can only make the cardinality smaller). $\endgroup$ – Ian Feb 23 '17 at 20:11
  • 1
    $\begingroup$ See this: math.stackexchange.com/questions/603456/… $\endgroup$ – Sungjin Kim Feb 23 '17 at 20:19
3
$\begingroup$

Think of $\mathbb{N} \times \mathbb{N}$ as a double-entry array and put the elements of $A_{i}$ into column $\#i$. You then just need a bijection between $\mathbb{N}$ and $\mathbb{N} \times \mathbb{N}$, which is quite easy to do (for instance $(i,j) \mapsto 2^{i}(2j+1)-1$).

$\endgroup$
1
  • $\begingroup$ this is so neat and brilliant! Thanks $\endgroup$ – Naz Feb 23 '17 at 20:31

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.