GO Classes DPP | TOC|COUNTABILITY

Answer 1

I. THE SET OF ALL POLYNOMIALS WITH RATIONAL COEFFICIENTS.

• COUNTABLE. A polynomial is defined by a finite sequence of coefficients (e.g., $a_n x^n+ \left.\cdots+a_1 x+a_0\right)$. Each coefficient is a rational number.
   
• The set of rational numbers $\mathbb{Q}$ is countable.
   
• The set of all finite-length tuples of rational numbers $\left(\mathbb{Q}^k\right.$ for any finite $\left.k\right)$ is countable.
   
• The set of all polynomials is a countable union of these countable sets (one set for each degree $k$ ). A countable union of countable sets is countable.

II. THE SET OF ALL SUBSETS OF THE NATURAL NUMBERS $\mathbb{N}$.
 

• UNCOUNTABLE. This is the definition of the power set of $\mathbb{N}$, denoted $P(\mathbb{N})$.
   
• The set $\mathbb{N}$ is countably infinite (its cardinality is $\aleph_0$ ).
   
• Cantor's Theorem states that the power set of any set $A$ has a strictly greater cardinality than $A$.
   
• Therefore, the cardinality of $P(\mathbb{N})$ is $2^{K_0}$, which is uncountable.

III. THE SET OF ALL FUNCTIONS FROM $\{0,1\}$ TO $\mathbb{N}$.
 

• COUNTABLE. A function $f:\{0,1\} \rightarrow \mathbb{N}$ is just a mapping of two values: $f(0)$ and $f(1)$.
   
• $f(0)$ must be an element of $\mathbb{N}$.
   
• $f(1)$ must be an element of $\mathbb{N}$.
   
• The set of all such functions is therefore in a one-to-one correspondence with the set of all ordered pairs $\left(n_1, n_2\right)$ where $n_1, n_2 \in \mathbb{N}$. This is the set $\mathbb{N} \times \mathbb{N}$.
   
• The Cartesian product of two countable sets is countable.
   

IV. THE SET OF ALL INFINITE-LENGTH BINARY STRINGS.
 

• UNCOUNTABLE. This set is famously proven to be uncountable using Cantor's diagonalization argument.
   
• This set can also be shown to have the same cardinality as the set of real numbers between 0 and 1 (by treating each string as a binary expansion).