-1

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?

Andrés E. Caicedo
  • 79,201
Ryan Cole
  • 815
  • 1
    take a look here for a possible approach different to construct a direct bijection between the sets – Masacroso May 28 '18 at 02:14
  • Do you know a bijection is impossible? Or do you just not know what one is? If you can get an injection from A to B then $|A| \le |B|$. And if we can get a surjection from B to A then $|A| \le |B|$. But we can't know that $|A| < |B|$ unless we can prove an injection for $B$ to $A$ or a surjection from $A$ to $B$ can not exist. Likewise if we don't have any map.... we can't know anything. – fleablood May 28 '18 at 02:28

3 Answers3

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.

Arthur
  • 199,419
  • I believe this may be true for ordinals but his question was about sets and cardinality not ordinals. – N8tron May 28 '18 at 02:19
  • Note: any collection containing the ordinals must be a proper class not a set :) – N8tron May 28 '18 at 02:20
  • @N8tron I'm not talking about the class of ordinals at all. Any ordinal is a set, and has a well-defined cardinality. This cardinality, of uncountable, but still small enough, is incomparable in size to $\Bbb R$. That's what I'm using here. – Arthur May 28 '18 at 02:26
  • Ahh so you're just giving one example where it's undecidable. I can live with that since you can still establish inequalities just proving the strict inequalities is undecidable for some sets. I think some of what you're referencing here is the continuum hypothesis being independent right? – N8tron May 28 '18 at 02:32
  • @N8tron Independence of CH from ZFC is exactly what I'm getting at here. Note that you often can't get any inequalities. For instance, CH is the statement $|\Bbb R|=\aleph_1$ (the smallest uncountable cardinal). Without CH (which isn't the same as assuming "not CH") we cant really tell at all whether $|\Bbb R|$ is larger than, smaller than or equal to $\aleph_2$ (the second smallest uncountable cardinal) at all. – Arthur May 28 '18 at 02:37
  • Sure you must be careful about referencing the successor of ordinals, but given two sets you can sometimes determine inequalities by injections and surjections, as long as you're at least including Axiom of choice and using the von Neumann cardinal assignment. In particular it's not too difficult to see the inequality between a set and it's powerset $|A| \le |2^A|$. I just feel you need to allow a little room here for when inequalities can actually be established. – N8tron May 28 '18 at 02:56
2

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|$.

N8tron
  • 2,507
2

"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.

fleablood
  • 124,253