سوال ۹۸ کنکور ارشد علوم کامپیوتر ۱۳۹۹

We must find the set that is countably infinite: in bijection with $\mathbb{N}$ (infinite, but not bigger than $\mathbb{N}$). Three of the options are uncountable; only one is countably infinite.

Option 1 — finite sequences of rationals (countably infinite). Fix a length $n$. A sequence of $n$ rationals is an element of $\mathbb{Q}^{n}$. Since $\mathbb{Q}$ is countable and a finite Cartesian product of countable sets is countable, each $\mathbb{Q}^{n}$ is countable. The set of all finite sequences is $\bigcup_{n=0}^{\infty} \mathbb{Q}^{n},$ a countable union of countable sets, hence countable. It is clearly infinite (e.g. the one-term sequences $(q)$ for $q\in\mathbb{Q}$). So it is countably infinite. ✓

Option 2 — all (infinite) sequences of naturals (uncountable). This is $\mathbb{N}^{\mathbb{N}}$, the set of all functions $\mathbb{N}\to\mathbb{N}$. It contains $\{0,1\}^{\mathbb{N}}$, which already has cardinality $2^{\aleph_0}=\mathfrak{c}$. Uncountable. ✗

Option 3 — constant sequences of reals (uncountable). A constant sequence $(r,r,r,\dots)$ is determined by the single real $r$, so this set is in bijection with $\mathbb{R}$. Its cardinality is $\mathfrak{c}$. Uncountable. ✗

Option 4 — binary sequences (uncountable). This is $\{0,1\}^{\mathbb{N}}$, of cardinality $2^{\aleph_0}=\mathfrak{c}$ by Cantor's diagonal argument. Uncountable. ✗

Only option 1 is countably infinite.

Pitfall: Finite sequences over a countable alphabet form a countable set, but allowing infinite-length sequences (an actual function on all of $\mathbb{N}$) jumps to the uncountable $\mathfrak{c}$ — even over the two-letter alphabet $\{0,1\}$. The single word "finite" in option 1 is the whole point.