The first thing you need to ask yourself, about finite sets, is this: When do two sets have the same cardinality?
The way mathematics works is to take a property that we know very well, and do our best to extract its abstract properties to describe some sort of general construct which applies in as many cases as possible.
So how do we compare the sizes of two finite sets? If we can write a table, in one column the set $A$ and in the other the set $B$, and each element from $A$ appears in a unique cell; and each element of $B$ appears in a unique cell. If this table have no rows in which there is only one element, then the sets $A$ and $B$ are equal. For example:
$$\begin{array}{lc}
\text{Two equal sets:} &
\begin{array}{c|c|c}A & a_1& a_2\\\hline B & b_1& b_2\end{array} \\
\text{Non-equal sets:} &
\begin{array}{c|c|c|c}A & a_1 & a_2 & a_3\\\hline
B & b_1 & b_2\end{array} &
\end{array}$$
It is clear that this methods captures exactly when two sets have the same size. We don't require one set to be the subset of another; nor we require that they share the same elements. We only require that such table can be constructed.
Well, the generalization is simply to say that there exists a function from $A$ to $B$ which is injective and surjective, namely every element of $A$ has a unique element of $B$ attached to it; and every element of $B$ has a unique element of $A$ attached to it.
It turns out, however, that this notion has a quirky little thing about infinite sets: infinite sets can have proper subsets with the same cardinalities.
Why is this happening? Well, infinity is quite the strange beast. It goes on without an end, and it allows us to "move around" and shift things in a very nice way. For example consider the following table:
$$\begin{array}{c|c|c|c|c|c}
\mathbb N&0&1&\cdots&n&\cdots\\\hline
\mathbb N\setminus\{0\}& 1&2&\cdots & n+1&\cdots
\end{array}$$
It is not hard to see that this table has no incomplete rows and that every element of the left set ($\mathbb N$) appears exactly once, and every element of the right set ($\mathbb N\setminus\{0\}$) appears exactly once!
This can get infinitely more complicated, and so on and so on.
One can ask, maybe we are thinking about it the wrong way? Well, the answer is that it is possible. We can define "size" in other ways. Cardinality is just one way. The problem is that there are certain properties we want the notion of "size" to have. We want this notion to be anti-symmetric and transitive, for example.
Namely, if $A$ is smaller or equal than $B$ and $B$ is smaller or equal in size than $A$, then $A$ and $B$ have the same size; if $B$ also has the same size as $C$ as well, then $A$ and $C$ are of the same size too. It turns out that the notion described by functions has these properties. Other notions may lack one or both. Some notions of "size" lack anti-symmetry, others may lack transitivity.
So it turns out that cardinality is quite useful and it works pretty fine. However it has a peculiarity... well, who hasn't got one these days?
To overcome this, we need to change the way we think a bit: proper subset need not have a strictly smaller cardinality. It just should have not a larger cardinality. This is the right generalization from the finite case, rather than the naive "strict subset implies strictly smaller".
To read more:
- Is there a way to define the "size" of an infinite set that takes into account "intuitive" differences between sets?
Suppose $A$ is bijective to $[n] := \{1, 2, \ldots, n\}$ for some $n$. Then any proper subset $\tilde{A}$ of $A$ will have cardinality $|\tilde{A}|= m$ for some $m<n$ (in other words, $\tilde{A}$ is bijective to $[m]$ with $m<n$). By the hint given at the end of the problem, no map from $[n]$ to $[m]$ is injective, so $[n]$ is not bijective to $[m]$. Hence, $A$ is not bijective with $\tilde{A}$, for any proper subset $\tilde{A}$. By definition, $A$ is finite.
I'll leave it to you to prove the other direction.
Best Answer
First of all, I suggest you find a good article/book on Cantor's work on multiple infinities. Reading that will enlighten you and answer probably most of the questions you have concerning this subject. Try these lecture notes.
But to give a brief answer to your current questions:
Per definition, two sets have the same cardinality if there exists a bijection between them. This definition was introduced by Cantor because for infinite sets, you could not just count the elements. Not all infinite sets have the same cardinality. For example, the natural numbers $\mathbb{N}$ and the real numbers $\mathbb{R}$ do not have the same cardinality. This was proven with the diagonal argument.
$\mathbb{N}$ and $\mathbb{Z}$ are both infinite sets. I suggest you check out their definitions on wikipedia (the natural numbers, the integers). They also, like Ali said in his post, have the same cardinality. The bijection that was given by him is probably the easiest one to grasp.
As for $\mathbb{Q}$, the rational numbers, this is also an infinite set that has the same cardinality as $\mathbb{N}$ (and thus also $\mathbb{Z}$). I suggest you check out the bijection that is given in the lectures notes that I linked above, that one is probably the clearest one.