MHB Show that there exists a bijection

  • Thread starter Thread starter mathmari
  • Start date Start date
  • Tags Tags
    Bijection
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

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)
 
Physics news on Phys.org
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)$?
 
Evgeny.Makarov said:
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? (Wondering)
 
I don't see how it helps. In fact, I don't think a bijection can be continuous here.
 
mathmari said:
Hey! :o

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?
 
Opalg said:
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)
 
mathmari said:
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.
 
Opalg said:
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)
 
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.
 
Back
Top