Show that the union of countable sets is countable

[╔(σ_σ)╝]

Homework Statement

Show that if [tex]A_{1}[/tex], [tex]A_{2}[/tex],... are countable sets, so is [tex]A_{1}[/tex][tex]\cup[/tex] [tex]A_{2}[/tex][tex]\cup[/tex]...

Homework Equations

The Attempt at a Solution

Part one of the question is okay, I would like to believe I can handle that but, part B, I am not so sure.

My solution is as follows ( using the matrix in the attached picture)Line up [tex]A_{1}[/tex], [tex]A_{2}[/tex],[tex]A_{3}[/tex] ... in the "X-axis" ( it's more of an axis of positive integers) and then the line up the elements of of set along the vertical columns associated with each set. Then use the function is part A of the picture to define a bijection.
[tex]\varphi[/tex] : N XN [tex]\rightarrow[/tex] N by [tex]\varphi[/tex](i,j) = j + [tex]\frac{k(k+1)}{2}[/tex] where k= i+j.

Of course, I use the fact that the set of positive integers and natural numbers are of the same cardinality.


What do you guys think ? Is this okay ? Would this suffice?

I'm looking for another way of showing this same result, but one that is less "forced". Forced ,in the sense that, I was basicallly given the answer in part A of the question in the attached picture.

 

[vela]

What definition of countable are you using? Does it include finite sets or does it mean countably infinite?

I think your basic approach is correct if the sets are infinite. I'll leave it to the math experts here to guide you on the details.

 

[╔(σ_σ)╝]

My definition of countable includes both finite and denumerable sets ( sets that have the same cardinality with N). I am using the " elementary classical analysis" txt.

Using my approach, dealing with finite sets is not a problem; since all elements will fit into the matrix with a finite size.

Do you have a different approach ? If so, I would eb interested in it.

 

[vela]

My point about finite sets is that it introduces some details you have to worry about. For example, if all of your sets had n elements, then the bijection is from {1,...,n}xN to N, not NxN to N. Also, if you need a bijection in your definition, rather than an injection, then a finite set isn't countable.

 

[╔(σ_σ)╝]

Okay I see your point about the finite sets. If the set had finite elements then would need a different map.However, I am not what you mean by "if you need a bijection in your definition, rather than an injection, then a finite set isn't countable. " From what I understand if the elements in the set are finite but the number of sets is not then a map from {1,...,n}xN to N is definately not a bijection since it fails to be onto. Is this your point ? However, I assume the question was defined in such a way that it makes sense since it say we should prove it is countable.

 

[vela]

I just meant if your definition of countable means there's a bijection from a set to N, then a finite set can't be countable because there's no function that maps it onto N.

The only reason I brought this up is because you talked about a bijection between the union of the sets and N. Some definitions of countable require a bijection to N; others only say there has to be an injection to N.

 

[╔(σ_σ)╝]

I just meant if your definition of countable means there's a bijection from a set to N, then a finite set can't be countable because there's no function that maps it onto N.

The only reason I brought this up is because you talked about a bijection between the union of the sets and N. Some definitions of countable require a bijection to N; others only say there has to be an injection to N.

You have a point and i just took a look at my textbook. It says a set that is either finite or denumerable is said to be countable. An infinite set is denumerable it has the same number of elements is the set of integers {1,2,...}.

With this definition I guess there is room for injections( when the set is finite) and bijections, for infinite sets.