Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How do you prove that any collection of sets {$X_n : n \in \mathbb{N}$} such that for every $n \in \mathbb{N}$ the set $X_n$ is equinumerous to the set of natural numbers, then the union of all these sets, $\bigcup_{i\in \mathbb{N}}$ $X_i$ is also equinumerous to the set of natural numbers. Also by equinumerous I mean there exists a one-to-one and onto function $f:X_n \to \mathbb{N}$.

Is this statement still false as it stands?

share|improve this question
1  
By "equivalent"... what exactly do you mean? –  Arturo Magidin Aug 2 '11 at 19:37
    
@Arturo: There exist a one-to-one and onto function $f$ $:$ $A$ $\to$ $N$ –  Mark Aug 2 '11 at 19:39
1  
i.e., you want show that "the union of denumerable sets is denumerable". The statement, as given, is false, then; if you take "enough" sets that are bijectable with $\mathbb{N}$, the union may fail to be bijectable to $\mathbb{N}$; for example, $\mathbb{N}\times\mathbb{R}$ is bijectable with $\mathbb{R}$, and $\mathbb{N}\times\mathbb{R}$ is the union $\cup (\mathbb{N}\times\{r\})$ over all $r\in\mathbb{R}$. Each $\mathbb{N}\times\{r\}$ is bijectable with $\mathbb{N}$, but the union is not. –  Arturo Magidin Aug 2 '11 at 19:41
    
This question is not well defined. How big is the collection of the sets? Each of the sets? Do you work in ZFC, or some other theory? –  Asaf Karagila Aug 2 '11 at 19:42
    
I'm assuming $N$ is $\mathbb{N}$ (you can type it with \mathbb{N}); what is $Z_n$, though? –  Arturo Magidin Aug 2 '11 at 19:43

2 Answers 2

up vote 12 down vote accepted

The answer depends on your set theory.

If your set theory includes the Axiom of (Countable) Choice, then you can proceed as follows:

  1. For each $n\in\mathbb{N}$, select a bijection $f_n\colon X_n\to\mathbb{N}$. (This step requires the Axiom of Countable Choice);
  2. Select a bijection $g\colon\mathbb{N}\times\mathbb{N}\to\mathbb{N}$; there are several explicit examples of this. For example, the Cantor pairing function $g(a,b) = \frac{(a+b)(a+b+1)}{2}$.
  3. Define $f\colon \bigcup\limits_{n\in\mathbb{N}}(X_n\times\{n\})\to \mathbb{N}$ by mapping $(x,n)$ to $g(f_n(x),n)$.

This defines a bijection between the disjoint union of the $X_n$ onto $\mathbb{N}$. To get a bijection in the case where the $X_n$ are not disjoint, note that $\bigcup\limits_{n\in\mathbb{N}} X_n$ embeds into the disjoint union (map $x$ in the union to $(x,m)$ where $m$ is the smallest $n\in\mathbb{N}$ such that $x\in X_n$), which is bijectable to $\mathbb{N}$; then use the Cantor-Bernstein Theorem applied to this embedding and to embedding that maps $\mathbb{N}$ to $X_1$ into the union to get a bijection.

However, if your set theory does not include the Axiom of Choice, then the answer may be that the union need not be bijectable with $\mathbb{N}$. In particular, it is consistent with ZF that the real numbers are a countable union of countable sets, and of course the real numbers are not bijectable with $\mathbb{N}$.

share|improve this answer

If you want to show that the countable union of countable subsets is countable, you can use Cantor-Schroeder-Bernstein (I don't think it uses AC --even in summer :) ), and set up injections between $\mathbb N$ and $\mathbb N \times \mathbb N $, and the other-way-around , by generalizing this:

take any two primes , say 2,3, and map : $(a,b)\rightarrow 2^a3^b$ ( you can see that, to generalize to a product of k-copies of $\mathbb N$, just take k different primes; if you want an actually countably-infinite product, this is maybe more delicate), and an injection in the opposite direction is given by , e.g., n->(n,0,0,...).

And, BTW, any choice of injections in CSBernstein allows to construct an actual bijection.

EDIT: I think it is not too hard to show the map (a,b)->$2^a3^b$ is an injection; if we had $2^a3^b=2^{a'}3^{b'}$, it would follow that $2^{a-a'}3^{b-b'}=1$; by simple divisibility arguments, each of the factors on the left-hand side would have to divide 1; it then follows that a-a'=0 and b-b'=0, i.e., a=a', b=b'.

EDIT#2 : Please see some of the caveats in the comments section about concluding that the union of countables is countable.

share|improve this answer
    
It is consistent without choice that $\aleph_1$ is a countable union of countable sets. You have to have choice for that, even if Cantor-Bernstein doesn't require it. –  Asaf Karagila Aug 2 '11 at 22:44
    
Sorry, but isn't the countable union of countable counatble, i.e., $\aleph_0$? –  gary Aug 2 '11 at 23:15
    
@gary: As Asaf says, in the absence of the axiom of choice, it is possible for a countable union of countable sets to be uncountable. For example, there is a model of ZF where $\mathbb{R}$ is a countable union of countable sets. –  Zhen Lin Aug 3 '11 at 0:42
    
Yes, my bad, I keep assuming ZFC automatically; I keep imposing my assumptions on questions; I am becoming senile way too early. –  gary Aug 3 '11 at 1:18
1  
@gary: Basically, the problem is that one needs to choose countably many embeddings/bijections into $\mathbb{N}$ simultaneously. On the other hand, the union of countably many sets that come equipped with embeddings into $\mathbb{N}$ can be shown to be countable in ZF, without having to invoke choice; that is, if you have a family $(X_n,f_n)$, $n\in\mathbb{N}$, with $f_n\colon X_n\to \mathbb{N}$ one-to-one for each $n$, then it is easy to prove that $\cup X_n$ is countable; but without having the $f_n$ given, that's when you need AC (at least countably). –  Arturo Magidin Aug 3 '11 at 11:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.