How to tell which set is larger.

Question

If I am given two infinite sets A and B which do not have a bijection between them I know that one set would be larger than the other . But, how could I tell which set is larger? What additional properties would I need to know about the sets to tell which is larger and which is smaller?

Answer 1

Without an injection you need cardinality inequalities.

• If there's an injection $f:A \to B$ then $|A| \le |B|$

• If there's a surjection $f:A \to B$ then $|B| \le |A|$.

When you know there isn't a bijection then you can say it's a strict inequality. As mentioned in Arthur's solution, establishing a strict inequality is not always decidable in ZFC.

Examples

$f:\mathbb{Q} \to \mathbb{R}$ defined by $f(q)=q$ is injective therefore $|\mathbb{Q}| \le |\mathbb{R}|$.

$f:\mathbb{R}^n \to \mathbb{Z}$ defined by $f(\vec{x})= \textbf{floor}(x_1)$ is onto so $|\mathbb{R}^n| \ge |\mathbb{Z}|$

It's actually even more handy when you have the theorem $|A|=|B|$ iff $|A|\le |B|$ and $|A| \ge |B|$.

Answer 2

You can't know that one is larger than the other. The standard example is any of the uncountably infinite ordinal numbers (as long as they're not too large) versus the real numbers. Cantor drove himself mad trying to figure this out, and we know now that in standard (ZF) set theory, they are incomparable.

Even with the axiom of choice, which implies that there is some ordinal number with a bijection to $\Bbb R$, exactly which one is still impossible to assert.

Answer 3

"which do not have a bijection between them I know that one set would be larger than the other"

You actually don't know that unless you know a bijection is impossible. It's not enough just to not have one; you have to know one is impossible.

The options are:

You know a bijection $f: A\to B$ exists. $|A| = |B|$.

You are told that a bijection $f: A\to B$ is impossible but you know nothing else then $|A| \ne |B|$ but ... we know nothing more.

You don't know if an bijection does or does not exist and you don't know anything about other functions then ... you don't know a thing.

Basically:

If you have an injection $g:A\to B$ then $|B| \ge |A|$.

If you have a surjection $h:A\to B$ then $|A| \ge |B|$.

If you know an injection $g:A\to B$ is impossible then you know $|A| > |B|$.

If you know a surjection $h:A \to B$ is impossible then you know $|B| > |A|$.

If you have any of knowledge combination of knowledge and ignorance you may or may not know more details.

But to prove things are not the same size you must prove certain mappings are impossible.