Before we start, just note that whenever I mention , or the naturals, I am referring to: 0,1,2,3,... (also known as the set of positive integers, or ).

(a): We know that if exists a surjection , then we deduce something about the cardinality of the two sets, specifically that . Since is countable, and the size of set can be no bigger than that, must be countably infinite (that is, there is also a bijection between and ) or finite.

You can try to list the elements of like . If they correspond bijectively to the naturals, they are countable by definition of having the same cardinality.

Conversely, there exists an element in the naturals, say , that is not hit by an element in , then is finite with a cardinality of . For example, say that , meaning there is no 100th element in set , so that means that must have 99 elements or have a cardinality of 99.

(b): Simply use the fact that a finite Cartesian product of countable sets is countable. So in this case, you have a Cartesian product of the naturals with the naturals (both of which are countable and it is a finite product because you are multiplying only two terms together). So it is countable.

If that is not sufficiently convincing, recall that the Cartesian of two sets represents the set of all pairs with elements from the two sets: where . Thus, we can enumerate the elements of the Cartesian product of the positive integers as such:

Then count them by going diagonally and eliminating redundant elements. So we enumerate by: and then removing redundant elements, we get something like . Obviously if we can do this type of counting, the set is countable, lol

(c) To show that the positive rationals are countable, it suffices to construct an injective function . Let us define as:

where

This function is injective, as whenever it must be the case that . So by virtue of an injective function, we argue that . But it is clear that the naturals are a subset of the positive rationals, so . Then from these two facts, we have , so the positive rationals must be countable.

(d) Google for "Cantor's Diagonalization Argument" or "Power set of the naturals" and you will find your answer. This is one of the most fundamental facts in set theory on countability and uncountability, so there will be a lot of available material on this =)