Sunday 19 August 2018

elementary set theory - Let $X$ and $Y$ be countable sets. Then $Xcup Y$ is countable




Since $X$ and $Y$ are countable, we have two bijections:



(1) $f: \mathbb{N} \rightarrow X$ ;



(2) $g: \mathbb{N} \rightarrow Y$.



So to prove that $X\cup Y$ is countable, I figure I need to define some function,



h: $\mathbb{N} \rightarrow X\cup Y$




Thus, I was wondering if I could claim something similar to the following:



since we have (1) & (2) it follows that we also have the bijections



$\alpha : \{n\in \mathbb{N} : n = 2k + 1, k\in \mathbb{N}\} \rightarrow X$;



$\beta : \{n\in \mathbb{N} : n = 2k, k\in \mathbb{N}\} \rightarrow Y$;



because we have bijections from $\mathbb{N}$ to the evens and odds respectively.




Then define $h := \alpha$ for odd $n$, $h := \beta$ for even $n$.



Thus, since $\forall n\in \mathbb{N}$(either $n$ is even or $n$ is odd but not both) $h$ is a bijection from $\mathbb{N}$ to $X\cup Y$.



Thanks for reading, and for answering if you answer. I'm just really unsure if my logic holds here, or if I'm even approaching this right because I've been stuck on this problem for a little while today.



p.s sorry for asking so many questions recently, I'm trying to study on my own and apparently I get confused and stuck more easily than I thought I would without a teacher.



EDIT: (1) fixed the even and odd.

(2) I do mean countably infinite. My bad, going through some notes I found online they were using the notation of "countable" for what you call "countably infinite", and "at most countable" for what you called "countable"
(3) Thanks for the good answers, I do see now that this makes breaks down when they are not disjoint, but at least I'm not too far off.


Answer



By countable you seem to mean countably infinite. That may not be the formal definition in your book. The formal definition of countable that I am more accustomed to is that a set $S$ is countable if there is a bijection between $S$ and a subset of $\mathbb{N}$.



If the more general definition is the formal definition of countable used in your book, you will need to either break up the proof into a number of cases, or write an argument that simultaneously covers all cases. That can be done, but there will be greater clarity if you take the number of cases approach.



For countably infinite sets $X$ and $Y$, the proof technique that you used is very good if $X$ and $Y$ are disjoint. The notation that you used is not familiar to me. It is clear what you intend the functions $\alpha$ and $\beta$ to do. It would have been relatively easy to be totally explicit, as follows.



If $n$ is odd, then $h(n)=f((n+1)/2)$; if $n$ is even then $h(n)=g(n/2)$.




You will need to modify your method to take care of the cases where $X$ and $Y$ are not disjoint. The intuition is clear, and even, informally, a procedure for finding a bijection. But it is a very good idea to write out all of the details.



I hope this gives a good way to begin. I can append more details if you like.


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...