MHB How can we show that the inverse is bijective?

[evinda]

Hello! (Happy)

In my lecture notes, there is this remark:

A set $X$ is countable iff there is a $f:X \overset{\text{bijective}}{\longrightarrow} \omega$ iff $X$ is the range of a bijective sequence of lengh $\omega$.

$$f^{-1}: \omega \overset{\text{bijective}}{\longrightarrow} X$$

then $X=rng(f^{-1})=\{ f^{-1}(n): n \in \omega\}$.I was wondering how we can show that if $f$ is bijective that then $f^{-1}$ is also bijective.
We know that $f$ is injective.
So we have that for $x_1, x_2 \in X$ with $f(x_1)=f(x_2) \Rightarrow x_1=x_2$

We also know that $f$ is surjective, so we can deduce that $\forall y \in \omega$ there is a $x \in X$ such that $f(x)=y$.We want to show that if $y_1, y_2 \in \omega$ with $f^{-1}(y_1) \neq f^{-1}(y_2)$ we have that $y_1 \neq y_2$.

How could we do this? Could you give me a hint? (Thinking)

 

[Evgeny.Makarov]

This question is not about countable sets.

We want to show that if $y_1, y_2 \in \omega$ with $f^{-1}(y_1) \neq f^{-1}(y_2)$ we have that $y_1 \neq y_2$.

I don't think $f^{-1}(y_1) \neq f^{-1}(y_2)\implies y_1 \neq y_2$ expresses the fact that $f^{-1}$ is injective.

In dealing with injectivity of some function $g$, I recommend the positive version: $g(x_1)=g(x_2)\implies x_1=x_2$ instead of its contrapositive: $x_1\ne x_2\implies g(x_1)\ne g(x_2)$.

 

[Nono713]

How about showing that bijectivity between two sets is an equivalence relation on sets? You are only interested in the symmetry property, but perhaps proving the reflexivity and transitivity properties would give you some ideas on how to go about the problem.​

 

[evinda]

In dealing with injectivity of some function $g$, I recommend the positive version: $g(x_1)=g(x_2)\implies x_1=x_2$ instead of its contrapositive: $x_1\ne x_2\implies g(x_1)\ne g(x_2)$.

We want to show that $f^{-1}: \omega \to X$ is injective.

So in this case the positive version is this: $f^{-1}(y_1)=f^{-1}(y_2) \Rightarrow y_1=y_2$ where $y_1, y_2 \in \omega$, right?But how could we show this? (Thinking)

 

[Evgeny.Makarov]

So in this case the positive version is this: $f^{-1}(y_1)=f^{-1}(y_2) \Rightarrow y_1=y_2$ where $y_1, y_2 \in \omega$, right?But how could we show this?

Apply $f$ to both sides of $f^{-1}(y_1)=f^{-1}(y_2)$.

 

[Nono713]

I think I see the problem here. You haven't actually defined $f^{-1}$ mathematically, so you can't really prove anything. The simplest definition of $f^{-1}$ is the (unique) function satisfying $f(f^{-1}(x)) = f^{-1}(f(x)) = x$ for all $x \in X$, which combined with Evgeny's hint immediately leads to the injectivity of $f^{-1}$. Another possible definition is given by $f^{-1}(y) = x$ if and only if $f(x) = y$. Both definitions are equivalent, the first one being more function-centric and the second one more akin to relations, and of course both depend on $f$ being injective (if $f$ is not injective we get a contradiction). Note you have to stick with one definition unless you are prepared to prove that the two are equivalent.

It might seem like "cheating" to define $f^{-1}$ like that, but it really isn't. If you think about it, we are just describing the properties we would like $f^{-1}$ to have: an inverse function ought to satisfy $f(f^{-1}(x)) = x$ for all $x$. So we state that a function that has this property is called an ("the", after we prove it is actually unique) inverse function of $f$, we call it $f^{-1}$, and only then can we begin working with $f^{-1}$ as a mathematical object.​

 

[evinda]

So can we prove as follows that $f^{-1}: \omega \to X$ is bijective?

In order to prove that $f^{-1}$ is injetive, we want to show that for $y_1, y_2 \in \omega$ with $f^{-1}(y_1)=f^{-1}(y_2) \Rightarrow y_1=y_2 $,

$f^{-1}(y_1)=f^{-1}(y_2) \Rightarrow f(f^{-1}(y_1))=f(f^{-1}(y_2)) \Rightarrow y_1=y_2$.

Therefore $f^{-1}: \omega \to X$ is 1-1.

Now we want to show that $f^{-1}$ is surjective, i.e. that $\forall x \in X$ there is a $b \in \omega$ such that $f^{-1}(b)=x$

$f^{-1}(b)=x \Rightarrow f(f^{-1})(b)=f(x) \Rightarrow b=f(x)$
We cannot conclude from the surjectivity of $f$ that it holds:
$f: X \to \omega$ is surjective. That means that $\forall y \in \omega$ there is a $x \in X$ such that $f(x)=y$.How else could we deduce that $f^{-1}$ is surjective? (Thinking)

 

[Evgeny.Makarov]

In order to prove that $f^{-1}$ is injetive, we want to show that for $y_1, y_2 \in \omega$ with $f^{-1}(y_1)=f^{-1}(y_2) \Rightarrow y_1=y_2 $,

$f^{-1}(y_1)=f^{-1}(y_2) \Rightarrow f(f^{-1}(y_1))=f(f^{-1}(y_2)) \Rightarrow y_1=y_2$.

Therefore $f^{-1}: \omega \to X$ is 1-1.

Yes.

Now we want to show that $f^{-1}$ is surjective, i.e. that $\forall x \in X$ there is a $b \in \omega$ such that $f^{-1}(b)=x$

$f^{-1}(b)=x \Rightarrow f(f^{-1})(b)=f(x) \Rightarrow b=f(x)$

The arrows must be reversed. You need to exhibit a $b$ and prove $f^{-1}(b)=x$, not use it as an assumption.

We cannot conclude from the surjectivity of $f$ that it holds:
$f: X \to \omega$ is surjective.

And I cannot conclude from your post that you wrote a post. (Smile)

 

[evinda]

The arrows must be reversed. You need to exhibit a $b$ and prove $f^{-1}(b)=x$, not use it as an assumption.

So do you mean that we have to use the surjectivity of $f: X \to \omega$?
If so, it is as follows:

$f$ is surjective. That means that $\forall y \in \omega, \exists x \in X$ such that $f(x)=y$.

$f(x)=y \Rightarrow f^{-1}(f(x))=f^{-1}(y) \Rightarrow f^{-1}(y)=x$But in order to show that $f^{-1}: \omega \to X$ is surjective we want to show that $\forall y \in $ X, $\exists x \in$ ω such that $f^{-1}(x)=y$.
Or am I wrong? (Thinking)

And I cannot conclude from your post that you wrote a post. (Smile)

(Bigsmile)

I meant that we cannot conclude from the surjectivity of $f$ that it holds that $f^{-1}: X \to \omega$ is surjective. (Giggle) (Wasntme)

 

[Evgeny.Makarov]

So do you mean that we have to use the surjectivity of $f: X \to \omega$?

I did not say to use the surjectivity of $f$. I just said that the arrows in that quote should be reversed.

 

[evinda]

I did not say to use the surjectivity of $f$. I just said that the arrows in that quote should be reversed.

So do we suppose a $b$ such that $f(x)=b$ ? (Thinking)

 

[Evgeny.Makarov]

So do we suppose a $b$ such that $f(x)=b$ ?

One can suppose a proposition, but not an object such as a number.

Given an $x$, you need to find a $b$ such that $f^{-1}(b)=x$. Take $b=f(x)$; then $f^{-1}(b)=f^{-1}(f(x))=x$, as required.

 

[evinda]

One can suppose a proposition, but not an object such as a number.

Given an $x$, you need to find a $b$ such that $f^{-1}(b)=x$. Take $b=f(x)$; then $f^{-1}(b)=f^{-1}(f(x))=x$, as required.

I see.. (Nod) But we have to take a $b \in f(X)$, right? (Thinking)

EDIT: But it is $f(X)=\omega$ since $f$ is surjective, right?

 

[Evgeny.Makarov]

I wrote a complete proof that $f^{-1}$ is surjective. Nothing else is necessary.

 

[evinda]

I wrote a complete proof that $f^{-1}$ is surjective. Nothing else is necessary.

Nice! Thanks a lot! (Happy)