GATE CS 1994 Q3.9 — Sets, Relations and Functions

The statement is True (represented by 1).

Proof / Explanation:

By definition, a set $S$ is countable if there exists an injective function $f: S \to \mathbb{N}$ (where $\mathbb{N}$ is the set of natural numbers).

Let $A$ be any subset of $S$ (i.e., $A \subseteq S$).

1. Since $S$ is countable, there exists an injection $f: S \to \mathbb{N}$.
2. We can define a restriction function $g: A \to \mathbb{N}$ such that $g(x) = f(x)$ for all $x \in A$.
3. Since $f$ is injective, $g$ is also injective. That is, if $g(x) = g(y)$ for $x, y \in A$, then $f(x) = f(y)$, which implies $x = y$.
4. The existence of an injective function from $A$ to $\mathbb{N}$ proves that $A$ is countable.

Thus, every subset of a countable set is indeed countable.