When is an infinite set larger than another infinite set?

Question

Somewhat of a basic question that I've been pondering about, suppose we have 2 finite sets $A,B$, arbitrary sets with arbitrary elements that we know nothing about, except that they are both finite.

We can intuitively say that $card(A) < card(B)$ if there is a function $f:A \to B$ that is injective but not surjective (or "on to"). a simple example would be $A=\{1\}$, $B=\{1,0,-1\}$, $f(x)=x$.

the case that $A$ is finite but $B$ is infinite is also an easy case, it is not hard to show using that above definition that $card(A) < card(B)$, a very intuitive result.

But if $A,B$ are both infinite sets, the above definition fails.

a simple example as to why this fails can be $A=\{2,4,6,...\}$ and $B=\{1,2,3,...\}$ and $f: A\to B$, $f(x)=x$.

$f$ in this case is injective, but not surjective, it is not a bijection. So does that mean $card(A) < card(B)$? it shouldn't, because $f(x)=0.5x$ is a bijection. they should be of same cardinality.

To sum up, is there a better criteria to determine which set is bigger, apart from "$B$ is bigger than $A$ if there is an injective function from $A$ to $B$ that is not surjective and also it is impossible to find a bijection between them" ? To prove that a bijection does not exist between $2$ sets is not always trivial. So what is the criteria that one set is strictly larger than another?

Answer 1

It means that there is an injection from $A$ into $B$, but there is no bijection between $A$ and $B$.

Assuming the axiom of choice, this is the same as saying that there is no surjection from $A$ onto $B$ (but without the axiom of choice, it is possible that $A$ maps injective (with one function) and surjectively (with another) onto $B$, but not bijectively (with any function)).

As often is the case with infinite sets, it might not be possible to actually prove that one cardinal is strictly larger than the other. For example, $2^{\aleph_0}$, the cardinality of $\Bbb R$, is not necessarily strictly larger than $\aleph_1$, the cardinality of $\omega_1$ the first uncountable ordinal, and it is consistent that the two cardinals are equal, and it is consistent that they are not equal (in which case $\aleph_1$ is strictly smaller).

Answer 2

I think given infinite sets $A,B$, an equivalent definition in terms of surjections and not bijections is:

The cardinality of $B$ is bigger than $A$ iff for all functions $g:A \to B, \space g$ is not a surjection. So just finding one example of a function that is not a surjection is not sufficient to show that the two sets do not have the same cardinality. In your example of $A = \{2,4,6, \dots \}, B= \{1,2,3 ,\dots\}$ it is true that you found a non-surjective function $f$. But since there is a surjection $h:A \to B$ where $h(x) = \frac{x}{2}$ we can not conclude that the cardinality of $A$ is less than $B$. It can be challenging to show that no surjection exists. Are you familiar with the Cantor-Schroeder-Bernstein Theorem? You may be able to prove two sets have the same cardinality without having to consider surjections. Otherwise, a proof by contradiction might work to show no surjective function exists.

https://en.wikipedia.org/wiki/Cantor%E2%80%93Bernstein%E2%80%93Schroeder_theorem