Countable infinite sets

1. Sep 12, 2007

ehrenfest

1. The problem statement, all variables and given/known data
Why is the union of two countably infinite sets countably infinite?

2. Relevant equations

3. The attempt at a solution

So, you have bijections with the naturals for each of the two sets and you need to find a new bijection from the naturals to their union. It seems impossible to me.

2. Sep 12, 2007

bomba923

Hint: Consider all possible intersections

Last edited: Sep 12, 2007
3. Sep 12, 2007

matt grime

Uh, why? You're supposed to assume that the two sets are disjoint.

It might help to think the other way round: there are bijections from X to N and Y to N. Now, if only there were two proper subsets of N that were disjoint and each in bijection with N (this is clearly an equivalent problem - whenever you have a question about countable sets, you can replace all of them with a (different) copy of N by definition)....

4. Sep 12, 2007

bomba923

That was not stated in the original post, but it does make the proof shorter and simpler.

5. Sep 12, 2007

ehrenfest

But there aren't!! That sentence just seems manifestly contradictory to me.

6. Sep 12, 2007

CompuChip

Hint (I hope): $$\{ 0, 2, 4, 6, 8, \cdots \} \cup \{ 1, 3, 5, 7, 9, \cdots \} = \mathbb{N}$$.

7. Sep 12, 2007

ehrenfest

I am still not convinced. If you have two sets with the same number of elements as each other and as the set of natural numbers (they are countably infinite). How can you add those elements together without the cardinality of the set increasing?

8. Sep 12, 2007

JonF

you can easily construct disjoint sets if you can't assume they are:

A u B = A u (B - A intersection B)

9. Sep 12, 2007

genneth

If you think that, your idea of cardinality is wrong. Two sets have the same cardinality iff there exists a bijection between them. No other definition is acceptable. Thus, the even and odd numbers have the same cardinality, because you can use (+1) as a bijective mapping to go from the evens to the odds. At the same time, they are both bijective to the natural numbers, in a fairly obvious manner. Thus, the three sets have the same cardinality.

10. Sep 12, 2007

ehrenfest

Interesting.

11. Sep 12, 2007

Dick

A set having a proper subset of the same cardinality as itself is the basic definition of 'infinite'.

12. Sep 12, 2007

matt grime

It doesn't bloody well need to be (it is the 'worst case scenario'), and doesn't alter the fact that your suggestion wasn't at all helpful.

13. Sep 13, 2007

bomba923

Not for us, but for one (the OP) who is just learning (for what may be the first time, presumably from the posts) about sets and cardinality, such a statement may warrant a proof \

Last edited: Sep 13, 2007
14. Sep 13, 2007

ehrenfest

What does OP stand for?

15. Sep 13, 2007

genneth

Original poster or original post. It's usually good for focusing the discussion on the actual topic of the thread. Which ironically, we've now failed to do.

16. Sep 13, 2007

learningphysics

The case where the two sets are disjoint seems like the most straightforward one to me... construct a bijection from the first set to the odds... second to the evens... thereby constructing a bijection of the union to the naturals...

But in the case of the two sets intersecting constructing such a bijection seems less straightforward to me. particulary the case of an infinite intersection.

17. Sep 13, 2007

matt grime

Sigh. If you read the other posts here someone pointed out what to do if you really want to consider the idea of intersecting sets: replace XuY with Xu(Ynx^c).

18. Sep 13, 2007

bomba923

Post #2

Clearly the intersection of countable sets A,B is itself countable, since $$\left| {A \cap B} \right| \leqslant \left| A \right|$$.
Hence the intersection is either finite or countably infinite.

Finite case: Let
$$\begin{gathered} C = A \cap B,\;\left| {A \cap B} \right| = N \in \mathbb{N} \hfill \\ D = A - C \hfill \\ E = B - C \hfill \\ \end{gathered}$$
$$b\left( n \right) = \left\{ \begin{gathered} c_n ,\;n \leqslant N \hfill \\ d_n ,\;n > N \wedge n\;{\text{is odd}} \hfill \\ e_n ,\;n > N \wedge n\;{\text{is even}} \hfill \\ \end{gathered} \right.$$

Countably infinite case: Let
$$\begin{gathered} C = A \cap B,\;\left| {A \cap B} \right| = \left| \mathbb{N} \right| \hfill \\ D = A - C \hfill \\ E = B - C \hfill \\ \end{gathered}$$
$$b\left( n \right) = \left\{ \begin{gathered} c_n ,\;n\bmod 3 = 0 \hfill \\ d_n ,\;n\bmod 3 = 1 \hfill \\ e_n ,\;n\bmod 3 = 2 \hfill \\ \end{gathered} \right.$$

**Edit:
That essentially is the idea, hinted in previous posts but not quite so quickly received

Last edited: Sep 13, 2007
19. Sep 13, 2007

genneth

Guys... we're drifting a bit from the original problem.

20. Sep 13, 2007

JonF

The question was pretty much answered a few posts ago. Consider two disjoint sets (this can be done by making the replacements either me or Matt stated). Then use the fact that N is bijective with Z and it follows pretty immediately (map one set to positives and the other to negatives and chuck out 0).

It might be a good exercise for the OP to see if as a corollary he can prove that a countable union of countable sets is countable.

Last edited: Sep 13, 2007