I have two questions to answer about the properties of sets:

1) Prove that the union of a finite set and a countable set is countable. I am thinking that a finite set by definition has the cardinality of {1,2,...,n} and a countable set has the cardinality of natural numbers, so both have the cardinality of natural numbers? I don't see how to prove this rigorously, as it seems to be very basic intuition?

2) Prove that the union of two countable sets is countable. Again, can (or why not) this be proven by the same logic as 1) ?

  • $\begingroup$ HINT: Any subset of a countable set is also countable. Not all countable sets are finite. $\endgroup$ – CAGT Jan 20 '14 at 21:37
  • $\begingroup$ Have you put any effort into searching for the question on the site before posting it? $\endgroup$ – Asaf Karagila Jan 20 '14 at 21:37

One must be careful with intuition about infinite sets, because there are times that it fails spectacularly. To show that two sets have the same cardinality, it is best to simply write down a bijection between the two (or use a more powerful tool such as the Schroeder-Bernstein theorem).

To demonstrate the first, think about listing the $n$ things in your finite set, and then listing the countably many things in your infinite set: If you can write your infinite set as $A = \{a_1, a_2, a_3, ...\}$ and your finite set $B = \{b_1, ..., b_n\}$, can you write down a bijection between

$$\{b_1, b_2, ..., b_n, a_1, a_2, a_3, ...\}$$ and the set $\mathbb{N}$?

Likewise, given two countable sets, try interlacing elements, e.g. $\{a_1, b_1, a_2, b_2, ...\}$ and see if you can biject it with $\mathbb{N}$.

  • $\begingroup$ Do I understand correctly that it's necessary to combine the two sets and formally state that there is a bijection between the combination and N, as both sets have the cardinality of natural numbers? How would this help us avoid the potential infinite sets problem that you mentioned? $\endgroup$ – user120494 Jan 20 '14 at 21:44
  • 1
    $\begingroup$ @burgundy7 Yes, it's sufficient to prove that there exists a bijection: This is exactly the definition of a countable set, usually. As far as intuition, just be careful that there are many non-intuitive results, and to avoid errors it's necessary to make precise what you're saying. $\endgroup$ – user61527 Jan 20 '14 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy