# Show that there exists a bijection

#### mathmari

##### Well-known member
MHB Site Helper
Hey!!

Let $X$ be an infinite set and let $x\in X$. Show that there exists a bijection $f:X\to X\setminus \{x\}$. Use, if needed, the axiom of choice.

To show that $f$ is bijective we have to show that it is surjective and injective.

The axiom of choice is equivalent to saying that, the function $f:X\to X\setminus \{x\}$ is surjective if and only if it has a right inverse. So we have to show that the function $f$ has a right inverse, correct?

Next we have to show that the function is injective.

Is that the way we have to proceed for the proof? Or should we do something else?

#### Evgeny.Makarov

##### Well-known member
MHB Math Scholar
I don't know much about the axiom of choice, but the goal is not to use it, but to prove the original claim. If in the construction one needs this axiom, hopefully we will see it.

How would you prove that there is a bijection between $[0,1]$ and $[0,1)$?

#### mathmari

##### Well-known member
MHB Site Helper
How would you prove that there is a bijection between $[0,1]$ and $[0,1)$?
For that we use the function $f(x)=1-\frac{1}{2^x}$, or not?

#### Evgeny.Makarov

##### Well-known member
MHB Math Scholar
I don't see how it helps. In fact, I don't think a bijection can be continuous here.

#### Opalg

##### MHB Oldtimer
Staff member
Hey!!

Let $X$ be an infinite set and let $x\in X$. Show that there exists a bijection $f:X\to X\setminus \{x\}$. Use, if needed, the axiom of choice.
Suppose to start with that $X$ is a countable set. Then its elements can be listed as $X = \{x_n:n\in\Bbb{N}\}$, with $x_1=x$. The map given by $f(x_n) = x_{n+1}$ is then a bijection from $X$ to $X\setminus \{x\}$.

Now suppose that $X$ is uncountable. Let $S$ be a countable subset of $X$, with $x\in S$. As before, we can enumerate the elements of $S$ as $S = \{x_n:n\in\Bbb{N}\}$, with $x_1=x$. The map given by $$f(t) = \begin{cases}x_{n+1}&\text{ if }t = x_n\in S,\\t&\text{ if }t \notin S,\end{cases}$$ is again a bijection from $X$ to $X\setminus \{x\}$.

You now have to decide whether the Axiom of Choice has crept into the proof. The danger point is the instruction "Let $S$ be a countable subset of $X$." Is it possible to "choose" a countable subset of $X$ without using the Axiom of Choice?

#### mathmari

##### Well-known member
MHB Site Helper
You now have to decide whether the Axiom of Choice has crept into the proof. The danger point is the instruction "Let $S$ be a countable subset of $X$." Is it possible to "choose" a countable subset of $X$ without using the Axiom of Choice?
I think that the axiom of choice is necessary here to "choose" a countable subset of $X$. Is that correct?

#### Opalg

##### MHB Oldtimer
Staff member
I think that the axiom of choice is necessary here to "choose" a countable subset of $X$. Is that correct?
I'm not 100% sure about this, but I think that the Axiom of Choice is not needed here. The sequence $x_1,\;x_2,\;x_3,\ldots$ forming the set $S$ can be chosen one element at a time, using induction (which can be done within the basic Zermelo–Fraenkel set theory). The Axiom of Choice is only needed when an infinite number of choices have to be made simultaneously.

#### mathmari

##### Well-known member
MHB Site Helper
I'm not 100% sure about this, but I think that the Axiom of Choice is not needed here. The sequence $x_1,\;x_2,\;x_3,\ldots$ forming the set $S$ can be chosen one element at a time, using induction (which can be done within the basic Zermelo–Fraenkel set theory). The Axiom of Choice is only needed when an infinite number of choices have to be made simultaneously.
Can we do that in that way because the subset is countable?

#### Evgeny.Makarov

##### Well-known member
MHB Math Scholar
The book "Basic Set Theory" by A. Shen and N. K. Vereshchagin and this question from StackExchange say that the axiom of choice is needed to select a countable subset of an infinite set.