Two sets are said to be equivalent if they consist of the same elements. This can be usually proved by exhibiting an injective function from each set into the other, i.e. by proving that each set is a subset of the other (Cantor-Berstein-Schroder Theorem). Note that the equivalence is independent of the cardinality of these sets.

N = the set of natural numbers.
Nn = The set of first n natural numbers

A set is said to be finite if there exists a one-one onto relation between it, and Nn.
A set is said to be denumerable if there exists a one-one onto relation between it and N.
A set is said to be countable (or countably finite) if it is finite or denumerable.
A set which is not countable is said to be uncountable.

Now, that we are thorough with there basic definitions, realize that the set of all integers is countable ( map 1 -> 0; 2n -> n and 2n-1 -> -n). Also amazing would be to realize that the set of rational numbers is countable (proof follows)

In fact, there exists a bijection from N onto NxN, NxNxN and so on (do not confuse it with N^2, N^3 or so; there is nothing like it; coz you may be tempted to believe a bijection from N to N^N)
Now, rational numbers are of the form p/q where p, q are integers and q != 0. Hence, N -> Q is equivalent to N -> NxN…etc

Of course, there is! If I am able to prove that each subset is

Advertisements