Show that there exists a bijection

  • MHB
  • Thread starter mathmari
  • Start date
  • Tags
    Bijection
In summary: So I'm not sure if it's possible to do it without the axiom of choice. In summary, the conversation discusses the existence of a bijection between an infinite set $X$ and the set $X\setminus \{x\}$, where $x$ is an element of $X$. The use of the Axiom of Choice is mentioned, and a possible proof is provided for both countable and uncountable sets. The question of whether the Axiom of Choice is necessary is also raised.
  • #1
mathmari
Gold Member
MHB
5,049
7
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)
 
Physics news on Phys.org
  • #2
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)$?
 
  • #3
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)
 
  • #4
I don't see how it helps. In fact, I don't think a bijection can be continuous here.
 
  • #5
mathmari said:
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?
 
  • #6
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)
 
  • #7
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.
 
  • #8
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)
 
  • #9
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.
 

Related to Show that there exists a bijection

1. How do you define a bijection?

A bijection is a function that maps each element from one set to a unique element in another set. This means that for every element in the first set, there is a corresponding element in the second set, and each element in the second set is only mapped to by one element in the first set.

2. What is the importance of proving the existence of a bijection?

Proving the existence of a bijection is important because it shows that two sets have the same cardinality, or number of elements. This means that the two sets are essentially the same size, and can be thought of as equal in terms of their elements.

3. How do you show that a bijection exists between two sets?

To show that a bijection exists between two sets, you must first define a function that maps elements from one set to the other. Then, you must prove that the function is both injective and surjective. This means that the function must be one-to-one, meaning each element in the first set is only mapped to by one element in the second set, and onto, meaning each element in the second set is mapped to by at least one element in the first set.

4. Can a bijection exist between two infinite sets?

Yes, a bijection can exist between two infinite sets. This is because the concept of cardinality still applies to infinite sets, and a bijection can show that two infinite sets have the same number of elements.

5. How is a bijection different from other types of functions?

A bijection is different from other types of functions because it is both injective and surjective. This means that it is a one-to-one correspondence between two sets, whereas other types of functions may not have this property. Additionally, a bijection must have a unique inverse function, meaning that it can be reversed to map elements from the second set back to the first set.

Similar threads

Replies
7
Views
2K
  • Precalculus Mathematics Homework Help
Replies
4
Views
2K
  • Topology and Analysis
Replies
3
Views
289
  • Differential Equations
Replies
1
Views
829
  • Topology and Analysis
Replies
8
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
595
  • Topology and Analysis
Replies
8
Views
179
Replies
1
Views
377
Replies
6
Views
2K
Replies
2
Views
2K
Back
Top