0
$\begingroup$

So i have a little bit problems proofing this.

 |A| ≤ |B| iff |B| ≥ |A| 

i know, that if |A| ≤ |B| => f: A => B, must be injective

and likewise, that if |B| ≥ |A| => g: B => A, A = ø or it must be surjective.

Good, but how do i exactly do this proof? I am a little bit lost on how to write it down in a mathematical accurate way. Would anyone be able to help me out?

Thanks in advance

$\endgroup$
1
  • 2
    $\begingroup$ The notation is terrible. $\geq$ and $\leq$ are usually understood to be the same relation written backwards. $\endgroup$
    – Asaf Karagila
    Jan 13, 2021 at 14:57

1 Answer 1

2
$\begingroup$

I will prove the first implication and leave the other to you.
Assume $\vert A\vert\leq \vert B\vert$.
If $A=\emptyset$, there is nothing to prove, so we can assume $A\ne\emptyset$. Since $\vert A\vert\leq \vert B\vert$ there is an injective map $f:A\to B$. We prove that this has a left-inverse, i.e. there is a $g:B\to A$ such that $g\circ f=\operatorname{id}_A$. Pick $a_0\in A$ arbitrary (possible since $A\ne\emptyset$). Then we define $g:B\to A$ as follows: \begin{align*} g(b)=\begin{cases} a ~~~\text{if }a\in A,f(a)=b\\a_0~~~\text{otherwise, i.e. if }b\notin f(A)\end{cases} \end{align*} Note that this is well-defined since $f$ is injective, i.e. if there is som $a\in A$ with $f(a)=b$ then this $a$ is uniquely determined. Similarly we can check that $g\circ f = \operatorname{id}_A$. Now we claim that this $g$ has to be surjective. Let $a\in A$. Then $g(f(a))=\operatorname{id}_A(a)=a$ hence $f(a)$ is a preimage of $a$ for $g$, so $g$ is surjective. So we proved that there is a surjective map $B\to A$, hence $\vert B\vert\geq\vert A\vert$.
Now do something similar for the other direction, i.e. $\vert B\vert\geq\vert A\vert\implies \vert A\vert\leq\vert B\vert$.

(Here I assumed that the definition of $\vert B\vert\geq\vert A\vert$ is that there is a surjective map $B\to A$ and for $\vert A\vert\leq\vert B\vert$ that there is an injective map $A\to B$)

$\endgroup$
1
  • $\begingroup$ Thanks, i'll study your answer. $\endgroup$
    – Prometheus
    Jan 13, 2021 at 12:53

Not the answer you're looking for? Browse other questions tagged .