Intereting Posts

Normal derivative of a $H^1$- Sobolev function
primes represented integrally by a homogeneous cubic form
Lyapunov Stability of Non-autonomous Nonlinear Dynamical Systems
Increasing functions are Baire one
$FTC$ problem $\frac d{dx}\int_1^\sqrt xt^tdt$
Are these two spaces homotopy equivalent?
Finding an equation for a circle given its center and a point through which it passes
How do I find the cumulative distribution function of a binomial random variable?
Show that $\lim\limits_{n \to \infty} \sup\limits_{k \geq n} \left(\frac{1+a_{k+1}}{a_k}\right)^k \ge e$ for any positive sequence $\{a_n\}$
Classification Theorem for Non-Compact 2-Manifolds? 2-Manifolds With Boundary?
Finding the first digit of $2015^{2015}$
Separability of Banach Spaces
Proof that a certain entire function is a polynomial
Expected value problem, 10 floors and 12 people get on an elevator
Proof of the extreme value theorem without using subsequences

I’ve been trying to find this proof:

If there exists $f \colon A\to B$ injective and $g \colon A \to B$ surjective, prove there exists $h \colon A \to B$ bijective.

I thought of using cardinality, but I think it’s possible to prove that without using it. Anyone knows how to?

- Do there exist bijections between the following sets?
- Arithmetics of cardinalities: if $|A|=|C|$ and $|B|=|D|$ then $|A\times B|=|D\times C|$
- Medial Limit of Mokobodzki (case of Banach Limit)
- Show A is countable infinity
- Can an infinite cardinal number be a sum of two smaller cardinal number?
- Raising a partial function to the power of an ordinal

- Intuitive explanation for how could there be “more” irrational numbers than rational?
- Book on the Rigorous Foundations of Mathematics- Logic and Set Theory
- Given an infinite poset of a certain cardinality, does it contains always a chain or antichain of the same cardinality?
- exercise VII.G5 in kunen
- The set that only contains itself
- Is it possible to formalize all mathematics in terms of ordinals only?
- Can we conclude $\prod_{\kappa \in Crd, \kappa=1}^{\kappa<\aleph_\alpha}\kappa=2^{\aleph_\alpha}$ in ZFC?
- Is there a difference between allowing only countable unions/intersections, and allowing arbitrary (possibly uncountable) unions/intersections?
- Ordered tuples of proper classes
- $\{S\} \not\in S$ in ZFC?

This is generally not true in $ZF$ (cf. this MathOverflow question).

Assuming the axiom of choice, this becomes relatively simple.

Since $g$ is surjective, for every $b\in B$ the set $g^{-1}(b)$ is nonempty. If so we can choose $a_b$ to be such that $g(a_b) = b$ for every $b\in B$ (this can be a proper subset of $A$). The function $b\mapsto a_b$ is an injective function from $B$ into $A$.

By the Cantor-Bernstein theorem (which does not require the axiom of choice) we have that there exists a bijection $h$ as needed.

**Addendum:** Proof of the Cantor-Bernstein theorem using the axiom of choice

Suppose $A$ and $B$ are sets and there exists $f\colon A\to B$ injective, and $g\colon B\to A$ injective. Then there exists $h\colon A\to B$ bijective.

*Proof:* By the axiom of choice we can well order $A$ and $B$ as the least order type possible. So without the loss of generality we may assume $A=\alpha$ and $B=\beta$ for two ordinals.

Since two well orders are comparable in the embedding relation (i.e. $\alpha$ can be embedded into an initial segment of $\beta$, or vice versa) and in particular $\alpha\subseteq\beta$ or $\beta\subseteq\alpha$, we have if so that $f\colon\alpha\to\beta$ and $g\colon\beta\to\alpha$ are two injective functions.

Recall that $\beta$ was the least ordinal bijectible with $B$, so if $\alpha<\beta$ there is no injection from $\beta$ into $\alpha$. Therefore $g$ witnesses $\beta\le\alpha$.

The same argument holds for $\alpha$ and $A$ so $f$ witnesses $\alpha\le\beta$. Since the ordinals are linearly ordered, anti-symmetry implies $\alpha=\beta$.

The function $h$ is the composition of the well ordering functions of $A$ and $B$, that is if $w_1\colon A\to\alpha$ is the bijection of $A$ with $\alpha$, and $w_2\colon B\to\beta$ the bijection we used to well order the set $B$, define $h=w_2^{-1}\circ w_1\colon A\to B$ which is a bijection.

I’m not sure that this is the original Cantor proof, but it works, and I don’t think that the proof Cantor used was too different, perhaps the use of ordinals was slightly different (back then they only used the fact that well orders are embeddable into each other nicely).

As soon as we know that existence of surjective map $A\to B$ ~~is equivalent~~ implies to existence of injective map $B\to A$, this is the Cantor-Bernstein theorem.

The above claim follows from the following equivalent form of Axiom of Choice:

(S) For every surjective map $g: A\to B$ there exists a map $h: B\to A$ such that $(\forall b\in B) h(g(b))=b$.

http://en.wikipedia.org/wiki/Axiom_of_Choice#Equivalents

The proof of AC $\Rightarrow$ (S) was given in Asaf’s post. A map $h$ fulfilling the above property is injective.

Some proofs of Cantor-Bernstein can be found here:

http://www.proofwiki.org/wiki/Cantor-Bernstein-Schroeder_Theorem

I do like the proof which uses Knaster-Tarski theorem. (In fact proof 3 from the above link is the same thing as showing Knaster-Tarski in this special case.)

Brown, Pearcy: An introduction to analysis, Theorem 4.1

**EDIT:** GEdgar pointed out an error in my original formulation. Let me address this shortly. (I hope I remember it correctly.) The following two claims work for any sets $A$, $B$:

- $g: A\to B$ is surjective $\Leftrightarrow$ there exists $h: B\to A$ such that $g\circ h=id_B$. (I.e., $g$ has right inverse.)
- We are given a map $h: B\to A$. If there exists $g: A\to B$ such that $h\circ g=id_A$, then $h$ is injective.

Under the assumption $B\ne\emptyset$ we get

- $h: B\to A$ is injective $\Rightarrow$ there exists $g: A\to B$ such that $h\circ g=id_A$. (I.e., $h$ has left inverse.)

The last claim is not true for $B=\emptyset$ and $A\ne\emptyset$, since empty function from $\emptyset$ fo $A$ is injective, but there is no function from a non-empty set to $\emptyset$.

- Help with a limit of an integral: $\lim_{h\to \infty}h\int_{0}^\infty{{ {e}^{-hx}f(x)} dx}=f(0)$
- What is the square of summation?
- Are finitely generated projective modules free over the total ring of fractions?
- Verification of convolution between gaussian and uniform distributions
- Evaluate Integral $\int_{c\ -\ j\infty}^{c\ +\ j\infty} \left({\sigma\,x^{-1}}\right)^s{\Gamma(\beta_1-1+s)\over \Gamma(\beta_1+\beta_2-1+s)}\,ds$
- What's the nth integral of $\frac1{x}$?
- Min-Max Principle $\lambda_n = \inf_{X \in \Phi_n(V)} \{ \sup_{u \in X} \rho(u) \}$ – Explanations
- Familiar spaces in which every one point set is $G_\delta$ but space is not first countable
- Is the $\sum\sin(n)/n$ convergent or divergent?
- For $n \in \mathbb{N}$, show that $4^n + 10 \times 9^{2n-2}$ is divisible by 7
- Show that the sequence $\sqrt{2},\sqrt{2\sqrt{2}},\sqrt{2\sqrt{2\sqrt{2}}},…$ converges and find its limit.
- Can differential forms be generalized to (separable) Banach spaces?
- Finding $d=\gcd(a,b)$; finding integers $m$ and $n$: $d=ma+nb$
- point deflecting off of a circle
- Proof for number of weak compositions