Welcome to our community

Be a part of something great, join today!

Show that there exists a bijection

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,118
Hey!! :eek:

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? (Wondering)
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,502
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
Apr 14, 2013
4,118

Evgeny.Makarov

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

Opalg

MHB Oldtimer
Staff member
Feb 7, 2012
2,725
Hey!! :eek:

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
Apr 14, 2013
4,118
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? (Wondering)
 

Opalg

MHB Oldtimer
Staff member
Feb 7, 2012
2,725
I think that the axiom of choice is necessary here to "choose" a countable subset of $X$. Is that correct? (Wondering)
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
Apr 14, 2013
4,118
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? (Wondering)
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,502
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.