Which of the following sets are countable (NBHM 2016)

Which of the following sets are countable (NBHM 2016)
  1. The set of all algebraic numbers
  2. the set of all strictly increasing infinite sequences of positive integers
  3. the set of all infinite sequences of integers that are in arithmetic progression.

Solution:

1. (Countable) Proof of the set of algebraic numbers is countable is standard. For example, a nice proof can be seen in the principles of mathematical analysis by Walter Rudin.

2. (Uncountable

Fact 1: The set of all subsets of $\mathbb{N}$ is uncountable.

Fact 2: The set of all finite subsets of $\mathbb{N}$ is countable. Therefore

Fact 3: The set of all infinite subsets of $\mathbb{N}$ is uncountable.

Now, the bijection between the set of all strictly increasing infinite sequences of positive integers and the set of all infinite subsets of $\mathbb{N}$ is immediate. For example, map the sequence$x_1,x_2,\dots$ to the infinite set $\{x_1,x_2,\dots\}$ This function is well defined because the sequences are strictly increasing and the bijection can be verified directly.

3. (Countable) Let $\{x_n\}$ be an infinite arithmetic progression of integers, then it can be uniquely represented as a pair $(x_0, d) \in \Bbb{Z} \times \Bbb{Z}$ where $x_0$ is the first term and $d$ is the common difference of the progression. Now mapping $\{x_n\}$ to the pair $(x_0, d) \in \Bbb{Z} \times \Bbb{Z}$ defines a well-defined map between the set of all infinite sequences of integers that are in arithmetic progression and $\Bbb{Z} \times \Bbb{Z}$. This map is injective because if we change the profession either its first term changes or its common difference changes.  Therefore the set of all infinite sequences of integers that are in the arithmetic progression is in bijection with a subset of $\Bbb{Z} \times \Bbb{Z}$ and hence countable.

Share to your groups:

SHARE YOUR DOUBTS AND COMMENTS BELOW IN THE COMMENTS SECTION. ALSO SUBSCRIBE TO MY BLOG

No comments:

Post a Comment

Featured Post

NBHM 2020 PART A Question 4 Solution $$\int_{-\infty}^{\infty}(1+2x^4)e^{-x^2} dx$$

Evaluate : $$\int_{-\infty}^{\infty}(1+2x^4)e^{-x^2} dx$$ Solution : $$\int_{-\infty}^{\infty}(1+2x^4)e^{-x^2} dx = \int_{-\infty}^{\inft...

Popular Posts