If a function A $\to$ B is bijective then if A is infinite, so it is B (Proof with Dedekind’s definition of infinite sets).

elementary-set-theory

Theorem: Be A, B sets that can be be mapped bijectively. If A is infinite, so it is B. Note that we only use Dedekind's definition of infinite sets here: If N $ \subset$ M and f: M $\to$ N bijective then M is infinite.

There is a proof in my textbook I do not understand. The proof looks like this:

Let A' $ \subset$ A and $f$: A $\to$ A' bijective. Further we assume $h$: A $\to$ B bijective.
We assume $g: h \circ f \circ h^{-1}$: B $\to$ B.
Then $g$ is injective. There's some x $\in$ A – A', so $h(x) \notin rng(g)$. More precisely it holds: rng($g$) = $h''A' \subset h''A = B$.
Therefore $g: B \to rng(g) \subset B$ is a witness for the infinity of B.

I am too new to set theory to understand this proof. Following you see my so-far attempt to make some sense of the upper proof:

  1. Let A' $ \subset$ A and $f$: A $\to$ A' bijective. Further we assume $h$: A $\to$ B bijective. (Just the premises of the theorem.)

  2. Further we assume a function $g: h \circ f \circ h^{-1}$, so the mapping goes: B $\to$ A $\to$ A' $\to$ A $\to$ B. Because of A' $ \subset$ A we know that some x $\in$ A – A'. In the case of $h$: A $\to$ B alone, which is bijective, it means that x has an image $h(x)$ which is in rng($h$) = B, so $h(x)$ $\in$ B. But in case of $g$ the element $h(x)$ $\notin$ rng($g$) because x cannot map from A' going forward, so it cannot be in rng($g$) as $h(x)$. Therefore rng($g$) $\subset$ B.

  3. But then why $g: B \to rng(g)$ is bijective?

So basically I need someone to lead me thru the upper proof of my textbook by explaining more what's going on than the short proof tells. I just added my thoughts, so that you can see my thinking/mistakes and also see that I tried.

Best Answer

The function $g$, as constructed, is just the identity function. That is, for every $b\in B$, you have $g(b)=b$. Therefore, the conclusion that $\mathrm{rng}(g)\subset B$ is wrong.

More precisely, your problem arrives when you say this:

Because of A' ⊂ A there is some x ∈ A - A' which is not mapped thru f^-1 (i.e. from A' → A), so that f^-1(x) ∉ rng(f^-1)

The thing is that sure, there exists some $x$ such that $x\in A\setminus A'$. However, that x is not in the domain of $f^{-1}$, so it makes no sense to speak of the element $f^{-1}(x)$.

What I instead advise you do is to define the set $B'=h(A')$ and try

  1. Prove that $B'\neq B$ (i.e., prove that $B'\subset B$)
  2. Find a bijection between $B'$ and $B$ (do this using the known bijection $f$ between $A'$ and $A$).

After the edit:

As far as I see, your only problem is with proving that $g:B\to\mathrm{rng}(g)$ is a bijective function. But this is a fairly simple thing to prove. In fact, the function is surjective practically by definition (i.e., every element in its codomain must, by definition, be in the range), and it is injective because it is a composite of injective functions, and those are always injective.

If you want, a direct proof that $g$ is injective would be this. If $g(x_1)=g(x_2)$, then $$g(x_1)=h(f(h^{-1}(x_1)))=h(f(h^{-1}(x_2)))=g(x_2).$$

Now, everything falls out because of injectivity:

  1. Because $h$ is injective, we know that $h(a)=h(b)\implies a=b$, so we have (substitute $a=f(h^{-1}(x_1))$, $b=f(h^{-1}(x_2))$) that $f(h^{-1}(x_1))=f(h^{-1}(x_2))$.
  2. Now, because $f$ is injective, we know that $f(a)=f(b)\implies a=b$, so we have (substitute $a=h^{-1}(x_1), b=h^{-1}(x_2)$) that $h^{-1}(x_1)=h^{-1}(x_2)$.
  3. Because $h^{-1}$ is injective, we know that $h^{-1}(a)=h^{-1}(b)\implies a=b$, so we have (substitute $a=x_1, b=x_2$) that $x_1=x_2$.

Therefore, we proved that $g(x_1)=g(x_2)\implies x_1=x_2$, so we proved that $g$ is injective.

minor point:

Let me just take a minute to also comment on your proof. It is a little confusingly written, and it makes things look more complicated than they really are. Especially here:

But in case of $g$ the element $h(x)$ $\notin$ rng($g$) because x cannot map from A' going forward, so it cannot be in rng($g$) as $h(x)$. Therefore $\mathrm{rng}(g) \subset B$.

This looks really strange, and I think can be written much more clearly. In particular, you want to prove that $\mathrm{rng}(g)\neq B$, You can prove that by finding a $y$ that is in $B$, but not in $\mathrm{rng}(g)$.

proof: So, we take $x\in A\setminus A'$ (we know such a value exists) and define $y=h(x)$.. I claim that $y\in B$ and $y\notin \mathrm{rng}(g)$.The first part is obvious, so let me just prove the second. The proof will be by contradiction. Assume $y\in \mathrm{rng}(g)$. This means (by the definition of $\mathrm{rng}$ that there exists some $x'\in B$ such that $$g(x')=y.$$

Further, we know $y=h(x)$ and we know that $g=h\circ f\circ h^{-1}$. So we can write out the above equation as

$$h(f(h^{-1}(x'))) = h(x)$$

from the injectivity of $h$, we can now conclude that $x=f(h^{-1}(x'))$. This means, by definition, that $x\in\mathrm{rng}(f)$. But we know that $\mathrm{rng}(f)=A'$, so we conclude that $x\in A'$.

But we started out the proof by taking $x\in A\setminus A'$, which is in contradiction with the conclusion. So the premise of our proof by contradiction, which was "$y\in \mathrm{rng}(g)$", must be wrong. So $g\notin\mathrm{rng}(g)$, which is what we wanted to show. End of proof.

Related Question