Is there a way to define the "size" of an infinite set that takes into account "intuitive" differences between sets?

The usual way to define the "size" of an infinite set is through cardinality, so that e.g. the sets $\{1, 2, 3, 4, \ldots\}$ and $\{0, 1, 2, 3, 4, \ldots\}$ have the same cardinality. However, is this the only way to define a useful "size" of an infinite set? Could one conceivably define a "size" where the two example sets have different sizes?

The question is what do you want to capture in the notion of cardinality, and what is your settings.

For example, if you only care about subsets of the natural numbers you can say that $A$ has cardinality larger than $B$ if either $A$ is strictly larger than $B$ or the complement of $A$ is strictly smaller.

In this sense, $|\{0,1,2,\ldots\}|$ is larger than $|\{1,2,3,4\ldots\}|$, as the former is everything is the latter has a non-empty complement (namely, $\{0\}$). This notion is not a linear order, which may seem a bit bad but then again - without the axiom of choice cardinalities are not linearly ordered anyway.

Another example is if you fix for every set $A$ a linear ordering $\leq_A$. Now we say that $|A|\leq|B|$ if and only if $(A,\leq_A)$ is embedded into $(B,\leq_B)$. This notion of size is also nice and has the benefit of $\mathbb N$ being strictly smaller than $\mathbb Z$ and both smaller than $\mathbb Q$ (as order types, of course).

On the other hand, this notion of cardinality lacks the Cantor-Bernstein property, namely anti-symmetry: the order type of $\mathbb Q\cap[0,1]$ and that of $\mathbb Q\cap(0,1)$ are not equal, but either one embeds into the other.

This is also a bit bad, but there is a natural ordering on cardinals which also lacks this property without the axiom of choice: $|A|\leq^\ast|B|$ if and only if $A=\varnothing$ or there exists a surjection $f\colon B\to A$. Without the axiom of choice it is consistent that there are two sets which can be mapped onto one another, but not bijectively.

The above can be generalized to any form of structure. Simply fix for every set in the universe some sort of structure and consider the embedding as a natural order. However in many cases you do lose something in the sense that this is no longer acting as we would expect from cardinality. Or perhaps we are expecting the wrong things...

Further reading: