Demonstrate that A is a countable set.

Question

Question: Let $A = \{x \in \Bbb N \mid \exists y(x = 2y \lor x = y^2)\}$. Construct a surjective mapping $ f: \mathbb{N} \rightarrow A $. By doing this, you demonstrate that A is a countable set.

Approach: To construct a surjective mapping $ f: \mathbb{N} \rightarrow A $, we need to ensure that every element in set $ A $ is mapped to from some element in the set of natural numbers $ \mathbb{N} $.

Given the definition of set $ A = \{x \in \mathbb{N} \mid \exists y(x = 2y \lor x = y^2)\} $, we can see that any natural number can be represented either as twice another natural number or as the square of a natural number.

One way to construct a surjective mapping is as follows:

For even numbers $ x $, let $ f(x) = x/2 $.

For odd numbers $ x $, let $ f(x) = \sqrt{x} $.

This mapping ensures that every element in $ A $ is covered.

This demonstrates that $ A $ is a countable set because we can create a one-to-one correspondence between $ A $ and the set of natural numbers $ \mathbb{N} $.

Would this be enough to prove that A is a countable set?

Answer 1

Since you don’t need $f$ to be bijective, you have a lot of “wiggle room” to work with.

If $n$ is even, define $f(n)=n$. If $n$ is an odd square, define $f(n)=n$. If $n$ is odd but not a square, define $f(n)=n+1$.

Do you see why (a) $f$ maps $\Bbb N$ to $A$ and (b) why it does so surjectively?