Union of Countable Infinite Sets: Impossibility or Reality?

[ehrenfest]

Homework Statement

Why is the union of two countably infinite sets countably infinite?

Homework Equations

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.

 

[bomba923]

Hint: Consider all possible intersections

 

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

 

[bomba923]

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

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

 

[ehrenfest]

Now, if only there were two proper subsets of N that were disjoint and each in bijection with N

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

 

[CompuChip]

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

 

[ehrenfest]

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

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?

 

[JonF]

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

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

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

 

[genneth]

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?

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.

 

[ehrenfest]

Interesting.

 

[Dick]

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?

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

 

[matt grime]

That was not stated in the original post

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.

 

[bomba923]

It doesn't bloody well need to be (it is the 'worst case scenario')

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 \

 

[ehrenfest]

What does OP stand for?

 

[genneth]

What does OP stand for?

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.

 

[learningphysics]

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.

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.

 

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

 

[bomba923]

Post #2

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.

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.

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}$$
Your bijection could be
$$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}$$
Your bijection could be
$$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:

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

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

 

[genneth]

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

 

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

 

[learningphysics]

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.

This question seemed more about the subtleties to me... with this construction:

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

(B - A intersection B) may be finite... so the bijection to Z doesn't work in this case... it's still a straightforward problem... just pointing out that there's another situation here to be dealt with here...

Also another thing... the use of the theorem, "an infinite subset of a countably infinite set is countably infinite"... we don't know whether the OP can use that or not...

 

[JonF]

This question seemed more about the subtleties to me... with this construction:



(B - A intersection B) may be finite... so the bijection to Z doesn't work in this case... it's still a straightforward problem... just pointing out that there's another situation here to be dealt with here...

Also another thing... the use of the theorem, "an infinite subset of a countably infinite set is countably infinite"... we don't know whether the OP can use that or not...

You’re right I didn’t consider the finite case but it’s so trivial it’s hardly worth mentioning.

The theorem you mentioned I didn’t ask him to use, but told him it might be a good idea to try and prove it to see if he really understands what’s going on.

 

[learningphysics]

You’re right I didn’t consider the finite case but it’s so trivial it’s hardly worth mentioning.

The theorem you mentioned I didn’t ask him to use, but told him it might be a good idea to try and prove it to see if he really understands what’s going on.

But I thought that theorem was used here:

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

to show that if (B - A intersection B) is infinite, then it is countably infinite...

 

[JonF]

If you want to show that if A and B are countable, then A u B is countable you can just show that:

A u (B – A n B) is countable. Clearly (B – A n B) is countable since it’s subset of B. Also these two sets are disjoint. We can also assume that (B – A n B) is infinite, because if it is finite this proof is trivial (the OP should have proved a countable set unioned with a finite set is countable already).

Then you can just use the bijection I hinted at earlier.

 

[HallsofIvy]

Let x₁, x₂, ... be members of the first set. We can do that because it is countable.
Let y₁, x₂, ... be members of the second set. We can do that because it is countable.

Now consider the sequence x₁, y₁, x₂, y₂, ... . Does that give you an idea for a bijection with the positive integers?

 

[CompuChip]

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?

Perhaps it's time for some examples. In all examples, I assume the sets under consideration are disjoint. If they are not, you need to do a little more work (as shown in the posts) but it doesn't affect the idea.

• Suppose I have two finite sets, $\{x_1, \cdots, x_n\}$ and $\{y_1, \cdots, y_m\}$. The first one has cardinality n, the second cardinality m. The union is $\{x_1, \cdots, x_n, y_1, \cdots, y_m\}$ and has cardinality n+m; that is: there is a bijection between this set and the numbers 1, 2, ..., n+m. Symbolically, $n \oplus m = (n + m)$.
• Suppose one of the sets is countably infinite, say $y_1, y_2, y_3, \cdots$. Then the cardinality of the first is n (a number) and the second we call $\omega$. Countably infinite means by definition that there is a bijection to the integers (which is why I could label them by 1, 2, 3, etc. in the first place ). The union is again countable infinite. For it is $\{ x_1, x_2, \cdots, x_{n-1}, x_n, y_1, y_2, ...$. Again there is a bijection with the natural numbers, because I can just map 1 through n to the x's and for m>n, assign m to $y_{n - m}$. Symbolically, $\omega \oplus m = \omega$.
• Suppose both are countably infinite. Then both sets have a bijection to the natural numbers so we can call the elements $x_1, x_2, x_3, \cdots \text{ and } y_1, y_2, \cdots$. Then clearly there is also a bijection to the integers, sending i to $x_i$ if i is positive, and to $y_{-i+1}$ otherwise (check!) Now all you need to do is find a bijection from Z to N (try it yourself, hint: 0, 1, -1, 2, -2, 3, -3, ...). This proves that the union of two countably infinite sets is countably infinite. (Question for you: why is this a proof for the union of any two disjoint countably infinite sets? Hint: compose bijections) Symbolically, $\omega \oplus \omega = \omega$.
• In the same symbolic notation, $2^\omega \oplus \omega = \omega$, where $2^\omega$ is the cardinality of the real numbers. Try proving it. (Hint: ever heard of Hilbert's hotel? You want a bijection from $\mathbb{R} \cup \mathbb{N} \to \mathbb{R}$ (disjoint union implied) so you only have to make space for the naturals. Suppose you map each non-integer to itself, and map each integer to twice itself, can you figure out how to fit in the extra countably infinite set of naturals?)

I hope the first three examples provide some insight and explanation (and a useful exercise) and the last one is a nice challenge for you to check if you got the trick.

 

[matt grime]

Dear god, the amount of pissing around here making this way too complicated is frankly amazing. I hope the OP isn't learning from this thread since it is an appalling attempt at explaining it.

 

[iopmar06]

Would the following argument be sufficient?

If two sets A and B are countable then there are bijections
$$f: A \rightarrow N$$ and $$g: B \rightarrow N$$.

Define a map p: (A U B) -> N by

p(n) = f(n) if n is in A
p(n) = g(n) if n is in B\A

If you show that p is a bijection then (A U B) is equivalent to N so (A U B) is countable.

 

[CompuChip]

The statement "n is in A" doesn't make sense, unless A is a subset of N. It is easier to assume B disjoint from A (otherwise take B' = B \ A) and perform a construction like: match A to even numbers and B to odd numbers.

 

[HallsofIvy]

Since A is countable, it can be ordered as {a₁, a₂, a₃, ...}. Since B is countable, it can be ordered as {b₁, b₂, b₃, ...}.

Consider {a₁, b₁, a₂, b₂, a₃, b₃, ...}

If A and B are disjoint, that is an ordering of AUB. If they are not disjoint, a subset of that is an ordering of AUB.