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

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

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

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 .

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 .

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?

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.