Can you verify this proof of the Schroeder-Bernstein theorem?

Question

I'm a freshman in college and my professor challenged us to find a proof of this theorem. Please don't give me the answer but please verify if this proof works or, if not, if it is the start of a proof that needs to be filled in, or if you think I should abandon this line of thought. If it doesn't work, please explain why. This is kind of a sketch of a proof, really, and (I think) it uses the axiom of choice which I don't like, but it's a start. (I'm not sure if it actually uses the AoC. Does it?)

Theorem: Let $A$ and $B$ be sets. Let $f:A\to B$ and $g:B\to A$ be injections. Then there is a bijection from $A$ onto $B$.

Lemma: Let A and B be sets such that there is no bijection from A onto B. Let $f:A\to B$ and $g:B\to A$ be injections. Then there is at least one element $x\in A$ such that $f(x)\not= g^{-1}(x)$.

Proof: By contradiction. Assume that $f(a)=g^{-1}(a)$ for every $a\in A$ where $g^{-1}(a)$ is defined. Either $A=g[B]$ or $g[B]\subset A$ (strictly contained). If $g[B] = A$, then $f=g^{-1}$ and $f$ is a bijection, which is a contradiction. So $g[B]\subset A$. But since $g^{-1}$ is a surjection, every element of $B$ is mapped to an element of $A$, so for any $x\in A-g[B]$, $f(x)=f(y)$ for some $y\in g[B]$ and $f$ is not injective, which is a contradiction.

proof of theorem: By contradiction. Assume there is no bijection from $A$ onto $B$.

By the lemma, since f and g are injections, there must be a $a\in A$ such that $f(a)\not=g^{-1}(a)$. Similarly, there must be a $b\in B$ such that $g(b)\not=f^{-1}(b)$. Let $A'$ and $B'$ be the subsets of A and B where $a\in A',b\in B'$ iff $f(a)\not=g^{-1}(a), g(b)\not= f^{-1}(b)$

Define $h:A\to B$ where $$h(x)=f(x)$$ whenever $f(x)=g^{-1}(x)$ and $$h(a)=b $$where $a$ is some element of $ A'$ and $b$ is some element of $ B'$.

Clearly, $h:A-A'\to B-B'$ is a bijection, since $f=g^{-1}$ is a bijection.

Also, $h:A'\to B'$ is a bijection because

And then something about how there is always a $d\in B'$ for any $c\in A'$, meaning they come in pairs, but then we can define $h(c)=d$ and get our bijection again.

So $h:A\to B$ is a bijection, which is a contradiction.

Answer 1

If you are okay with using AC, then there is the argument which boils down to "$|A|\le|B|$ and $|B|\le|A|$ so $|A|=|B|$". Unpacking all the notation and hidden lemmas leads to the following:

An ordinal is a transitive set well-ordered by the $\in$ relation, and it is not difficult to prove that there are a proper class of ordinals, and the class of ordinals is itself well-ordered by $\in$. Assuming the well-ordering theorem, which is an AC equivalent, given any set $A$ we can find a well-ordering $R$ of $A$, and the order type of $R$ is an ordinal $\alpha$, which is then in bijection with $A$. Thus the class of all ordinals in bijection with $A$ is nonempty, so there is a unique least such ordinal, and we define this to be $|A|$, the cardinal of $A$. (Note that AC is not needed to define cardinals, but only to show that every set is associated with a cardinal.)

Since ordinals are totally ordered, we have a much simpler theory of set sizes in this context. First let's show:

Lemma: If $A\subseteq \alpha$ is a set of ordinals contained in an ordinal $\alpha$, then $|A|\le\alpha$.

Proof: Since $A$ is well-ordered by $\epsilon$ (as a set of ordinals), we can define a bijection $f$ by letting the $\beta$ be mapped to the $\beta$-smallest element of $A$ (more precisely: define $f$ by transfinite recursion so that $f(\beta)=\min(A\setminus f[\beta])$, which is to say, set $f(\beta)$ to be the smallest element of $A$ which is not $f(\gamma)$ for any $\gamma<\beta$). This process terminates eventually, because $A$ is a set, and the result is a bijection from some ordinal $\kappa$ to $A$.

Since $f$ is a strictly increasing ordinal function, we in fact have $f(\beta)\ge\beta$ (which can be proven by transfinite induction), so $\alpha\ge\sup_{\beta<\kappa}f(\beta)\ge\sup_{\beta<\kappa}\beta=\kappa$, and since $\kappa$ is in bijection with $A$, $|A|\le\kappa\le\alpha$ as desired.

And now we are nearly done. If $f:A\to B$ is an injection, then letting $i:B\to|B|$ be a bijection, $i\circ f:A\to|B|$ is an injection and $i\circ f[A]$ is a set of ordinals contained in $|B|$, so by the lemma, $|i\circ f[A]|\le|B|$, and since $i\circ f$ is also a bijection between $A$ and $i\circ f[A]$, $|A|=|i\circ f[A]|\le|B|$.

And now we can proceed along the lines mentioned at the beginning. If $f:A\to B$ and $g:B\to A$ are bijections, then $|A|\le|B|$ and $|B|\le|A|$, so since ordinals are totally ordered, $|A|=|B|$, and so there is a bijection from $|A|=|B|$ to $A$ and to $B$, which we can compose to get a bijection from $A$ to $B$. (Reminder: this proof requires AC, but only in order to ensure that $|A|$ and $|B|$ are defined. It still works without AC if you assume that $A$ and $B$ are well-orderable.)