1
$\begingroup$

Theorem: Consider sets $A \ne \emptyset \ne B$ with $B \subseteq A.$ If there's an injective function $A \to B$, then there's a bijective function $A \to B$

Little note: Suppose $x \in A$. Then $f(x) \in B$. But $B \subseteq A$ and so $f(x) \in A$ meaning $f(f(x)) \in B$ which implies $f(f(x)) \in A$ and $f(f(f(x))) \in B \ldots.$ We let $f^1(x) = f(x)$ and in general, for any $k \ge 2$, $f^k(x) = f(f^{k-1}(x))$.

Proof:

Let $f: A \to B$ be injective and not surjective. Then $B - \text{range}(f) \ne \emptyset.$ Define $B' \subseteq B$ as $B' = \{f^n(x): x \in A - B, n \in \mathbb N\}$ meaning $B' \subseteq \text{range}(f).$ Let $C = (A - B) \cup B'$ and consider $f_1: C \to B'.$ Suppose $y \in B'.$ Then $y = f^n(x)$ for some $x \in A - B$ and some natural $n. \ \color{blue}{\text{This implies $y = f(x)$ for some $x \in A - B$ or $y = f(x)$ for some $x \in B'$}}$. Thus $f_1$ is surjective meaning it's also bijective. Let $D = B - B'.$ Since $B - \text{range}(f) \ne \emptyset$ and $B - \text{range}(f) \subseteq B - B'$ we have $D \ne \emptyset.$ Also note, $D \cap B' = \emptyset = D \cap C.$ Define $h: C \cup D \to B' \cup D$ as $h(x) = \cases{f_1(x) \text{ if } x \in C \\ I_D(x) \text{ if } x \in D}$. Then $h$ is bijective from $C \cup D = A$ to $B' \cup D = B \ \blacksquare$


I don't understand the conclusion in blue. We have $y = f^n(x)$ for some $n$. This $n$ is not necessarily $1$ to give us $y = f(x)$ for some $x \in A - B$. Also, how do we get $y = f(x)$ for some $x \in B'?$ Thanks.

$\endgroup$

2 Answers 2

1
$\begingroup$

Since $y \in B'$, then by definition $y = f^n(x)$ for some $x \in A-B$, as noted in the sentence before. We can now make a case distinction:

  • $n = 1$, then $y = f^1(x) = f(x)$ with $x \in A-B$,
  • $n > 1$, then $y = f^n(x) = f(f^{n-1}(x))$ and since $n-1 \geq 1$, we have $f^{n-1}(x) \in B'$.

One of those must happen.

Minor note on notation: in the second case we get "$y = f(x)$ for some $x \in B'$", but this "$x \in B'$" is a different $x$ than before.

$\endgroup$
0
$\begingroup$

For all n in N, f$^n$(x) in B'.
Thus y = f$^n$(x) = f(f$^{n-1}$(x)).

The point of this proof is to prove the proposition without AxC.
An AxC proof is much simpler.

Do note that there was no blue characters that showed up in your post.

$\endgroup$
2
  • $\begingroup$ The sentence that begins This implies does appear in blue; perhaps your browser isn’t rendering the MathJax correctly. $\endgroup$ Mar 31, 2020 at 22:37
  • $\begingroup$ @BrianM.Scott Mathjack is unduly complicated and not standardized for all platforms. For example, there are three versions of every post. The post, the mathjacked post and the mathjacked up version that appears on the website. $\endgroup$ Apr 1, 2020 at 2:56

You must log in to answer this question.

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