Can I Prove Schröder-Bernstein With Just Definition of Bijection?

Question

If I have two injective functions $f : A \to B$ and $g : B \to A$, as Schröder-Bernstein (SB) says, then there is a function $h : A \to B$ which is bijective.

As for a proof, my reasoning goes something like this:

The injectivity of $f \implies |A| \leq |B|$. Similarly, the injectivity of $g \implies |B| \leq |A|$. At this point I would say that it is perhaps obvious that $|B| = |A|$ in order for the prior statements to remain true.

With that being said, the final question is whether or not $|A| = |B| \implies $ that there exists a function $h : A \to B$ which is bijective? I am reading (perhaps somewhat naively) on wikipedia that if X and Y are finite sets then a bijection exists $ \leftrightarrow$ $|A| = |B|$.

Taking the if and only if symbol as a statement of equivalence means that, at least in the finite case, considering the cardinalities of $A$ and $B$ proves the existence of $h$?

Answer 1

The conceptual order here must be a little different than you present it. If $A$ and $B$ are finite sets, then we can conclude from $|A|\leq|B|$ and $|B|\leq|A|$ that $|A|=|B|$ (as you write, it is "perhaps obvious"). But if $A$ and $B$ are infinite sets, it is far from obvious that we can make this jump. In fact, in the case of infinite sets, what $|A|\leq|B|$ means is that there is an injection from $A$ to $B$, and what $|A|=|B|$ means is that there is a bijection. So in order to make the jump from $|A|\leq|B|$ and $|B|\leq|A|$ to $|A|=|B|$, we first need the Schroder-Bernstein Theorem.

Answer 2

This is not obvious at all that $|A|\leq|B|$ and $|B|\leq|A|$ imply that $|A|=|B|$.

Consider a different notion of equivalence defined, say, on linearly ordered sets, with $|A|\leq|B|$ meaning now that there is an order embedding of $A$ into $B$, and $|A|=|B|$ means that there is an order isomorphism. (Of course, there is an implicit order, $<_A$ and $<_B$ given on these sets.)

Now consider $A=[0,1]$ and $B=(0,1)$ as ordered by the standard ordering of the real numbers. Then $A$ injects into $B$ by $f(x)=\frac14+\frac x2=\frac{2+x}4$, and $B$ injects into $A$ by the identity function. But $A$ and $B$ are not isomorphic.

Well, you might argue, they are kinda almost isomorphic. Then we can instead take $A=[0,1]$ and $B=[0,1]\cup[2,3]$ and now $A$ maps into $B$ using the identity function, and $B$ maps into $A$ by $x\mapsto\frac x3$. Again, these two are not isomorphic.

---

The reason you say that this is trivial, perhaps, is that you're thinking about the finite cardinals as a model of how sets should behave. There, if there are two injections then the equality is indeed an easy consequence of the pigeonhole principle.

This might have been Cantor's intuition, who also considered this somewhat trivial, by using an implicit assumption: $A$ and $B$ can be well-ordered, and then we can take the shortest order type of each and prove that they must be order isomorphic, similar to the pigeonhole principle argument.

But this appeals to the well-ordering principle, which many people have claimed to be "counter-intuitive",¹ and at the very least is not trivially obvious. And without the axiom of choice the Cantor–Bernstein theorem is still provable, so this cannot be the reason de jure for its proof to work. And infinite sets, in general, are very much not like finite sets.

Just to satisfy some of your curiosity, we can replace injections by surjections, and ask what happens if there are surjections from $A$ onto $B$ and from $B$ onto $A$. Does that entail the existence of a bijection? For finite sets, obviously yes, for the same reasons. But in general, without assuming the axiom of choice, we cannot prove this. We know that it is consistent that the axiom of choice fails, and there are two sets which surject onto one another, but there is no bijection between them.

Lest you worry too much, these are the kind of mistakes that many a great mathematician once made. You're in good company.

At the end of the day, the claim that $|A|\leq|B|$ and $|B|\leq|A|$ implies $|A|=|B|$ is restating the Cantor–Bernstein theorem.

---

Footnotes:

1. I disagree with that claim of course, and attribute it to historically bad teaching around this subject that treats this as somehow witchcraft is involved in producing this well-ordering. While it's true that it is not an explicit proof, having a well-ordering of the real numbers is no more counter-intuitive than proving that the rational numbers can be enumerated.

Answer 3

So, your argument is that when you surround $A$ and $B$ with vertical lines, and then put a horizontal line with two diagonal lines that meet on the right above it between them, this results in a "true" statement, and thus it follows that $A=B$? All you have shown is that a particular set of symbols apply. To make a mathematical proof, you need to refer to the concepts that those symbols represent.

When talking about "normal" numbers, the symbol $\leq$ has a reasonably intuitive meaning. But when mathematicians use the symbol in the context of transfinite numbers, they are not asserting that it means exactly the same thing as with finite numbers, any more than because absolute value bars mean "distance from zero on the number line" for real numbers, that's what it means for sets. The real numbers do have the property that if $a\leq b$ and $b \leq a$, then $a=b$, but that is a property of the real numbers and what we are referring to when we use the symbol $\leq$ within the context of real numbers. It doesn't follow that simply using the symbol $\leq$ to refer to a relation ensures that the relation will have this property. To claim that it has the property, you must actually prove that it has the property, not merely note that a symbol is being used to refer to the relation that, in other contexts, refers to a relation that has the property.