1
$\begingroup$

I have not studied the axiom of choice, I know how to prove that the union of two countable sets is countable and I want to use that a proceed by induction, but I'm not sure if my argument is okay. Let A and B be countable sets then since we know $A \cup B$ is countable the base case holds true. Then let us suppose it true for $\bigcup_{i=1}^{n-1}A_{i}$ and prove it for $\bigcup_{i=1}^n A_i$

Way 1: By induction hypothesis $\bigcup_{i=1}^{n-1} A_i$ is countable so lets denote it by $A$, then $A \cup A_n$ is just the union of two sets which is again true by the base case. Pretty sure this is wrong.

Way 2: By induction hypothesis $A = \bigcup_{i=1}^{n-1} A_i$ is countable and there exist bijection $f: \Bbb{N} \rightarrow A$, there also exists a bijection $g: \Bbb{N} \rightarrow A_n$ Then define

$$ h(n) = \begin{cases} f(k), & \text{if } n = 2k \\[2ex] g(k), & \text{if } n = 2k -1 \end{cases} $$ We have a bijection .

$\endgroup$
  • $\begingroup$ Way 1 works fine. $\endgroup$ – Justin Benfield Jun 12 '16 at 0:11
  • $\begingroup$ You may be interested to know that even a countable union of countable sets is countable. $\endgroup$ – Justin Benfield Jun 12 '16 at 0:12
  • $\begingroup$ How do you know that union of two countable sets is countable? Have you proven that? If not, you need to. $\endgroup$ – Justin Benfield Jun 12 '16 at 0:13
  • $\begingroup$ @JustinBenfield You my be interested to know that in the general case some form of the axiom of choice is required to prove that a countable union of countable sets is countable. It's not needed for the case of finite unions. $\endgroup$ – BrianO Jun 12 '16 at 0:14
  • $\begingroup$ @BrianO: Are you sure? Wouldn't you be able to exploit the fact that $\mathbb{N}$ is well ordered by $\leq$ along with induction to prove that countable union is countable without axiom of choice? $\endgroup$ – Justin Benfield Jun 12 '16 at 0:16

Your Answer

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

Browse other questions tagged or ask your own question.