If the set of odd numbers is a subset of $\mathbb N$ then surely it is smaller than $\mathbb N$ I have been studying Cantor's theorem, and I follow entirely that the set of natural numbers $\mathbb{N}$ is countable, as is the set of odd numbers (let's call it $\mathbb{O}$).
I understand his proof that there is a correspondence between the two sets and feel like I could accept that they therefore have the same cardinality based on that ... but ... hold on ...
We know that $\mathbb{O}$ is a subset of $\mathbb{N}$ right? $\mathbb{N}$ certainly contains all of the odd numbers. 
We also know that $\mathbb{N}$ contains numbers that are not odd. 
So if $\mathbb{N}$ contains all of $\mathbb{O}$ and some other stuff as well then surely it would be totally justified to argue that $\mathbb{N}$ is larger than $\mathbb{O}$?
 A: "Larger" means different things depending on the circumstance.
One common notion of larger and smaller comes from partially ordered sets.  A partially ordered set is a set $X$, together with a special relation on $X$, commonly denoted by the symbol '$<$'.  If $x, y \in X$, the symbol $x < y$ is read as "$x$ is less than $y$," or "$y$ is bigger than $x$."  The relation is required to satisfy the following conditions:

1 . If $x, y, z$ are in $X$, with $x < y$ and $y < z$, then $x < z$.
2 .  Let "$x \leq y$" mean that $x < y$ or $x = y$.  Then if $x \leq y$ and $y \leq x$, then $x = y$.

Note that we are NOT saying that any two elements of $X$ can necessarily be compared.  A partially ordered set with this property is called totally ordered.
Thus a partially ordered set gives a notion of elements being bigger or smaller than others.  Here are some examples:

1 .  Let $X$ be the set of all subsets of some given set $S$.  For $A, B \in X$, set $A \leq B$ if and only if $A \subseteq B$.

It is in this sense that the set of odd numbers is smaller than the set of natural numbers.

2 .  Let $X$ be the same set as in (1), but this time, set $A \leq B$ if and only if $A \supseteq B$.

So here, the notion of bigger doesn't conform to the usual notion.

3 .  Let $X = \mathbb{R}$, and for $x, y \in X$, set $x < y$ to be the usual thing.

This is a total ordering.

4 .  Let $X = \mathbb{R}$, but this time set $x < y$ if and only if $|x| < |y|$.

This is actually not a partially ordered set, since $-5$ and $5$ are "less than or equal to each other," yet they are not equal.  It does arguably give a good notion of size though: we think of $-10$ as being bigger than $5$ in this sense.
Another common notion of size in mathematics, specifically the size of sets, is cardinality.  This is the thing you first mentioned: one say that the cardinality of a set $X$ is less than or equal to that of a set $Y$ if there exists an injective map of $X$ into $Y$.
If the cardinality of $X$ is less than or equal to that of $Y$, and vice versa, then one can show (under some reasonable assumptions) that there exists a bijective map $X \rightarrow Y$.  One says in this case that $X$ and $Y$ have the same cardinality.  It is in this sense that the set of natural numbers and the set of odd numbers have the same size.
Moreover, one can show that for any sets $X$ and $Y$, one of their cardinalities is less than or equal to that of the other.  So we can sort of say that cardinality is a total ordering, but we don't say this to avoid logical inconsistencies.  A partial ordering is defined on the elements of a given set, and we don't consider all sets to be members of a given set.
A: Ponder this.  If you have an infinite set, does adding or subtracting a single element make it larger or smaller?
How can it.  The set still remains infinite.  Measuring the size of the set can no longer be done by counting. Neither set has fewer elements than the other.  So we can't say one is smaller than the other.
All right.  Now suppose you are talking and say "$A\subset B $ so $A $ is smaller than $B $ ...." and some snot - nosed 5 year old says "Why?" and you say "well, it's smaller because it has fewer elements"
And the brat says "Why?" and you say "Every element in A is in B but there are elements in B that aren't in A so B has more elements than A".
And the kid says "Why?" and you say "If $B $ has $b $ elements and $x $ are the elements in $B $ that aren't in $A $ then $A $ has $b-x $ and $b-x<b $".
And the kid says "Why?" and you say "listen, punk, you start off with $b$ and every time you remove one you make it smaller so you get a smaller set, then a smaller, then a smaller".
And the kid opens his mouth and you expect another "Why?" but instead the pest says "What if the set is infinite?".
And you say "Well, when you remove elements from an infinite set then you get.... oh."
So.  No, Being a proper subset and the other set having elements you don't have does NOT mean the subset is smaller or has fewer elelements.
.... but there is a chapter 2 coming...
A: Consider the correspondence
$n \to 4n-1$
I.e.,
$1\to 3$
$2\to 7$
Etc.
Now it looks like there only enough natural numbers to cover a proper subset of the odds.  So does that mean there are more odd natural numbers than natural numbers?
A: It depends on your definition of "larger". Once you make that precise, you'll answer your own question.
A: This all depends on how you define 'smaller', and how you want to use it. Yes, if $A$ is a strict subset of $B$, then we can reasonably call $A$ 'smaller' than $B$, even if we deal with infinite sets. However, one big drawback of using the strict subset relation to define 'smaller' is that you wouldn't be able to compare the sizes of sets of different elements. For example, $A = \{ a \}$ is now no longer smaller than $B = \{ b,c \}$ .... which is clearly an undesired result.
So, instead of using the subset relation, most of the time mathematicians use Cantor's notion of cardinality to do set-size comparisons. And yes, while this has some unintuitive results (such as there being 'just as  many' odd numbers as natural numbers), this notion does allow us to compare 'sizes' of sets with different elements, and it does obey the following properties that one would like such a set-size comparison notion to have, for example:


*

*Every set is the same size as itself

*If $A$ is smaller or equal in size than $B$, and $B$ is smaller or equal than $A$, then $A$ and $B$ are the same size

*If $A$ is smaller or equal than $B$, and $B$ is smaller or equal than $C$, then $A$ is smaller or equal than $C$

*For any two sets, $A$ is smaller or equal than $B$, or $B$ is smaller or equal than $A$


Notice that the subset relation has the first three properties as well, but it doesn't have the last property, and so using the notion of cardinality can give us important results that we cannot get using the subset relation.
Of course, this does not mean that you can't use the subset relation, or that using the subset relation can't give you useful results, or that it would be wrong to think of 'smaller than'  in terms of the subset relation. For example, given that the set of odd numbers is a strict subset of all natural numbers tells you that here are natural numbers that are not odd, and that is a useful result. 
As another example: There are only countably many Turing-machines, but uncountably many functions from natural numbers to natural numbers. So in that case, we use their difference in cardinality to conclude that there are functions from natural numbers to natural numbers that are not Turing-computable.  However, suppose that there were only countably many of such functions. Then cardinality would not have helped us prove this result.  But if we could have proven that the set of all Turing-computable functions is a strict subset of all such functions, then we would have gotten our result after all.
This example of uncomputable functions shows another important point, and that is that these different notions of 'smaller than' and 'just as many' are often 'vehicles', or a means to an end. And, as such, while we can quibble over whether there really are more natural numbers than odd numbers, for our eventual results this may not matter at all.
Indeed, nothing forces you to use the notion of cardinality when doing set-size comparisons, and indeed we are not forced to say that there are just as many odd numbers as natural numbers. But what you do need to do is to spell out exactly wat you mean when you make claims involving 'smaller' or 'just as many', especially when it comes to infinite sets.
A: 
So if $\mathbb{N}$ contains all of $\mathbb{O}$ and some other stuff as well then surely
  it would be totally justified to argue that $\mathbb{N}$  is larger than $\mathbb{O}$ ?

It surely is! As you point out yourself, we have $\mathbb{O}\subsetneq\mathbb{N}$ and that is exactly in which sense $\mathbb{O}$ is smaller than $\mathbb{N}$. On the other hand, you also correctly noted that there is a bijective mapping between $\mathbb{N}$ and $\mathbb{O}$ so in that sense, it is not the case that $\mathbb{N}$ is "larger" than $\mathbb{O}$. However, this is no contradiction as we apply two different notions of one set being "larger" than another set. What is probably irritating you is the fact that in the finite case these two notions are kind of "consistent" in the sense that:
if $A\subsetneq B$ then $|A|<|B|$
which does not hold in the general case. 
A: Imagine that you didn't know that $\mathbb O$ is a subset of $\mathbb N$, or that they have any elements in common. Imagine that you couldn't even inspect the properties of the elements of $\mathbb O$ and $\mathbb N$. Imagine that you didn't even recognize those elements as numbers. To paint a picture, imagine that someone takes a copy of $\mathbb O$ and a copy of $\mathbb N$ and encloses all of their elements in whimsically colored hardwood boxes.
Now, all you know is that $\mathbb N=\{a,b,c,d,\ldots\}$ and $\mathbb O=\{A,B,C,D,\ldots\}$, where $a$ denotes the teal-striped rosewood box, etc. Maybe $a$ contains the number $0$. Maybe $B$ contains the number $3$. But you have no way of knowing that.
Under these restrictions, how will you compare the sizes of $\mathbb O$ and $\mathbb N$? Can you come up with any justification that one is larger than the other?
A: For the following lists,
$$1,2,3,...$$
$$1,3,5,...$$
erase the labels, and replace them by dots:
$$\small{\bullet,\;\bullet,\;\bullet,\;...}$$
$$\small{\bullet,\;\bullet,\;\bullet,\;...}$$
Now which list has more elements?

The key idea is that for comparing the "sizes" of two sets, labels shouldn't matter. What matters for determining equal size is one-to-one correspondence.
A: A set is called "Dedekind infinite" if and only if it can be put into one-to-one correspondence with a proper subset of itself.
Example: N = {1, 2, 3, ...} = set of natural numbers is in 1-1 correspondence with O = {odds}, using f(n) = 2n-1, as already noted.
One can prove that a set is Dedekind infinite if and only if it is infinite (in usual sense). It is for infinite sets that we have the seeming paradox noted so far about subsets.
The answer is that we don't use terms like "larger" based on the idea of the subset relation. It is simply not done because it is not useful and it is even confusing insofar as it overlooks this seeming paradox.
N and O have the same cardinality, owing to the bijection f(n) = 2n-1. The fact that O is a proper subset of N is initially confusing, but we never speak of N being "larger than" O.
BONUS: This reminds me of a puzzle. You have infinitely many rooms numbered 1, 2, 3, ... ad infinitum, each filled with a rock. Each room has exactly one rock, and there are no other rooms. I come to you and bring one more rock. How can I arrange to have each and every rock (mine plus originals) in a room, but with no two rocks in one room?
VARIATION: Same as before, but I bring my own infinity of rocks, numbered 1, 2, 3, ... and want to combine with existing infinity so as to have each rock in a room, with no two rocks sharing a room. How?
Have fun!
(Dr. Michael W. Ecker is a retired Penn State U. associate professor of mathematics. He also was editor-publisher of Recreational & Educational Computing in addition to holding other positions.)
A: What I find curious...
If you say O and N are the same size, how comes that would you remove all numbers found in O from N, there would be an infinite amount of numbers left in N. For me that would be an indicator that the size of N is in fact larger.
Kinda like that, you would always find a correlation for O in N but this is not true for N in O -> qed. N is larger? :-)
