# countable union of sets

• Sep 27th 2008, 11:04 AM
frankdent1
countable union of sets
We're given n surjections fn= : {1,2,...,N} -> En. for all n in the Natural Numbers.
We have to prove that E= the union of all En is countable by defining a surjection from the natural numbers to the union of sets.

Since all the En have at most N elements, could I just define my surjection from {1,2,...,nN} and my function would be
F(i)={i for i in E
{s0 for i not in E
where so is a fixed element in E

E here could cover all of the Natural Numbers.
• Sep 27th 2008, 01:19 PM
Opalg
Quote:

Originally Posted by frankdent1
We're given n surjections fn= : {1,2,...,N} -> En. for all n in the Natural Numbers.
We have to prove that E= the union of all En is countable by defining a surjection from the natural numbers to the union of sets.

Since all the En have at most N elements, could I just define my surjection from {1,2,...,nN} and my function would be
F(i)={i for i in E
{s0 for i not in E
where so is a fixed element in E

E here could cover all of the Natural Numbers.

Given a natural number k, let n be the quotient and r the remainder when k is divided by N. So k=nN+r, with 0≤r<N. Define F by $F(k) = f_n(r+1)$. Then as k goes from nN to nN+(N-1), F(k) will go through all the values of f_n. Therefore the range of F (as k goes through all the natural numbers) will be the union of the sets E_n.
• Sep 27th 2008, 03:56 PM
frankdent1
Quote:

Originally Posted by Opalg
Given a natural number k, let n be the quotient and r the remainder when k is divided by N. So k=nN+r, with 0≤r<N. Define F by $F(k) = f_n(r+1)$. Then as k goes from nN to nN+(N-1), F(k) will go through all the values of f_n. Therefore the range of F (as k goes through all the natural numbers) will be the union of the sets E_n.

So what happends when k goes from 1 to N-1. for k=1, n=0 and r=1 meaning f_k = f_0 (2). Shouldn't we be starting from f_1 (1) since i'm using the functions f_n ={ i for i in E_n
{s0 fixed for i not in E_n
• Sep 27th 2008, 10:58 PM
Opalg
Quote:

Originally Posted by frankdent1
So what happens when k goes from 1 to N-1. for k=1, n=0 and r=1 meaning f_k = f_0 (2). Shouldn't we be starting from f_1 (1) since i'm using the functions f_n ={ i for i in E_n
{s0 fixed for i not in E_n

You're right, the numbers don't quite match up at the start of the sequence. Try this modification: Given a natural number k, let n be the quotient and r the remainder when k-1 is divided by N. So k=nN+(r+1), with 0≤r<N. Now define F as before by $F(k) = f_n(r+1)$.
• Sep 28th 2008, 09:33 AM
frankdent1
Quote:

Originally Posted by Opalg
You're right, the numbers don't quite match up at the start of the sequence. Try this modification: Given a natural number k, let n be the quotient and r the remainder when k-1 is divided by N. So k=nN+(r+1), with 0≤r<N. Now define F as before by $F(k) = f_n(r+1)$.

This makes sense only if we use F(k) = f_n+1 (r+1)
Because when k=1, r=0 and n=0 so we would use F(1) = f_0 (1). but f_0 is not defined, it should be f_1

Am I right?
• Sep 28th 2008, 10:17 AM
Opalg
Quote:

Originally Posted by frankdent1
This makes sense only if we use F(k) = f_n+1 (r+1)
Because when k=1, r=0 and n=0 so we would use F(1) = f_0 (1). but f_0 is not defined, it should be f_1

Am I right?

Yes, I think that finally nails it.