# Countability of any set with cardinality larger than that of $\mathbb N$

I should preface my question by saying that I am only a college freshman finishing multivariable calculus, so please keep that in mind when answering. I would consider myself more-or-less mathematically mature, though, so don't hesitate to give me technical answers.

After reading some random things online about the countability of $\mathbb Q$, $\mathbb R$, etc., I came up with a question: how can a set that's theoretically larger than $\mathbb N$ ever be considered countable? Take $\mathbb Q$, for example. Is there anything wrong with the following "proof" that $\mathbb Q$ is not countable:

1. For every natural number $n$, we can find one unique rational number $\frac{1}{n}$. There are therefore at least $\aleph_0$ rational numbers (where $\aleph_0$ is the cardinality of $\mathbb N$).
2. Let $n = 3$. We know that there is at least one other rational number that has 3 in the denominator: 2. We thus know that there is (at least) one additional rational number $\frac{2}{3}$ besides the $\aleph_0$ we already know about. We can thus say that the cardinality of $\mathbb Q$ is at least $\aleph_0 + 1$.
3. A function is bijective iff it is both injective and surjective. A function $f : A \rightarrow B$ is injective iff every element of $A$ maps to exactly one element of $B$. A corollary of this is that for $f$ to be injective, and thus bijective, $|A|$ must not be less than $|B|$.
4. A set is countable iff there exists a bijection between the natural numbers $\mathbb N$ and the set. The cardinality of $\mathbb N$ is $\aleph_0$ and the cardinality of $\mathbb Q$ is at least $\aleph_0 + 1$. Therefore, $|\mathbb N| < |\mathbb Q|$. Because of this, there cannot be a bijection between $\mathbb N$ and $\mathbb Q$, and thus $\mathbb Q$ is not countable. QED

However, Wikipedia says that $\mathbb Q$ is countable and that its cardinality is $\aleph_0$! One possible issue may be that I butcher the concept of aleph numbers, but even if I do, doesn't the general concept still hold? How can it be that a set if countable if it is larger than $\mathbb N$?

It would be great if you can clarify any concepts I'm obviously not understanding. Thanks!

• Infinite cardinal numbers have the singular property that $a<b$ implies $a+b=b$. THese are not usual numbers! Nov 25, 2015 at 8:40

A set $X$ is countable if there is an surjectve map from $\mathbb{N}$ to $X$.

What you've done is shown that there is a map from $\mathbb{N}$ to $\mathbb{Q}$ which is not surjective - but this doesn't contradict the existence of some other map, from $\mathbb{N}$ to $\mathbb{Q}$, which is surjective!

Think of it this way: consider the map $f(x)=x+1$. This is a map from $\mathbb{N}$ to $\mathbb{N}$ which is not surjective; does this mean that $\mathbb{N}$ is larger than itself?

My answer to the related question Are there fewer positive integers than all integers? might be useful to you.

• Your linked answer was a big help, but I'm just not understanding why it works that way. What is the inherent difference between the cardinalities of $\mathbb N$, $\mathbb Q$, and $\mathbb R$ that allows us to say that there is a bijection between $\mathbb N$ and $\mathbb Q$ but not $\mathbb N$ and $\mathbb R$? Nov 25, 2015 at 8:36
• @AaronHall Well, there's two parts to this. First, we have to show that there is a bijection between $\mathbb{N}$ and $\mathbb{Q}$. This is tricky, but not too hard - if you want to solve it on your own, first try to show that there is a bijection between $\mathbb{N}$ and $\mathbb{N}^2$ (the set of ordered pairs of natural numbers). (cont'd) Nov 25, 2015 at 8:38
• Second, we have to show that there is no bijection between $\mathbb{N}$ and $\mathbb{R}$. This is the really interesting part! It was proved by Cantor, and - though the proof isn't very long - can be quite difficult at first. Google "Cantor's diagonal argument." Nov 25, 2015 at 8:40
• I think I get it now. We can say that every integer or rational number is the result of some "finite modification" (for lack of a better term) of one or more natural numbers. For integers, it's negation, and for rationals, it's division. However, there are real (specifically irrational) numbers that cannot be the result of such a finite modification (often the best we can do is an infinite Taylor series, such as for $\pi$). Is this right? Nov 25, 2015 at 8:48
• It's basically right, yes (it's informal, but so is intuition in general). Nov 25, 2015 at 8:52