Countable infinite sets

  • Thread starter ehrenfest
  • Start date
  • #26
CompuChip
Science Advisor
Homework Helper
4,306
48
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, [itex]\{x_1, \cdots, x_n\}[/itex] and [itex]\{y_1, \cdots, y_m\}[/itex]. The first one has cardinality n, the second cardinality m. The union is [itex]\{x_1, \cdots, x_n, y_1, \cdots, y_m\}[/itex] and has cardinality n+m; that is: there is a bijection between this set and the numbers 1, 2, ..., n+m. Symbolically, [itex]n \oplus m = (n + m)[/itex].
  • Suppose one of the sets is countably infinite, say [itex]y_1, y_2, y_3, \cdots[/itex]. Then the cardinality of the first is n (a number) and the second we call [itex]\omega[/itex]. 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 :smile:). The union is again countable infinite. For it is [itex]\{ x_1, x_2, \cdots, x_{n-1}, x_n, y_1, y_2, ...[/itex]. 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 [itex]y_{n - m}[/itex]. Symbolically, [itex]\omega \oplus m = \omega[/itex].
  • Suppose both are countably infinite. Then both sets have a bijection to the natural numbers so we can call the elements [itex]x_1, x_2, x_3, \cdots \text{ and } y_1, y_2, \cdots[/itex]. Then clearly there is also a bijection to the integers, sending i to [itex]x_i[/itex] if i is positive, and to [itex]y_{-i+1}[/itex] 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, [itex]\omega \oplus \omega = \omega[/itex].
  • In the same symbolic notation, [itex]2^\omega \oplus \omega = \omega[/itex], where [itex]2^\omega[/itex] is the cardinality of the real numbers. Try proving it. (Hint: ever heard of Hilbert's hotel? You want a bijection from [itex]\mathbb{R} \cup \mathbb{N} \to \mathbb{R}[/itex] (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.
 
Last edited:
  • #27
matt grime
Science Advisor
Homework Helper
9,420
4
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.
 
  • #28
14
0
Would the following argument be sufficient?

If two sets A and B are countable then there are bijections
[tex]f: A \rightarrow N [/tex] and [tex]g: B \rightarrow N[/tex].

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.
 
Last edited:
  • #29
CompuChip
Science Advisor
Homework Helper
4,306
48
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.
 
  • #30
HallsofIvy
Science Advisor
Homework Helper
41,847
966
Since A is countable, it can be ordered as {a1, a2, a3, ...}. Since B is countable, it can be ordered as {b1, b2, b3, ...}.

Consider {a1, b1, a2, b2, a3, b3, ...}

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.
 

Related Threads on Countable infinite sets

  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
3
Views
1K
Replies
11
Views
3K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
1
Views
2K
Replies
3
Views
10K
Replies
1
Views
3K
  • Last Post
Replies
4
Views
3K
Replies
3
Views
2K
Top